العثور على سلاسل فرعية عددية رياضيا، دون مقارنة السلسلة

Question

لقد كانت هذه مشكلة واجهتني في العمل في الأصل، ولكنها الآن شيء أحاول حله من أجل فضولي.

أريد معرفة ما إذا كان int 'a' يحتوي على int 'b' بأكثر الطرق فعالية.لقد كتبت بعض التعليمات البرمجية، ولكن يبدو أنه بغض النظر عما أكتبه، فإن تحليلها في سلسلة ثم استخدام IndexOf يكون أسرع بمرتين من القيام بذلك رياضيًا.

الذاكرة ليست مشكلة (في حدود المعقول)، فقط سرعة معالجة محضة.

هذا هو الكود الذي كتبته للقيام بذلك رياضياً:

private static int[] exponents = {10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000 };

private static boolean findMatch(int a, int b) {
    if (b > a) return false;

    if (a == b) return true;

    int needleLength = getLength(b);

    int exponent = exponents[needleLength];
    int subNum;
    while (a >= 1) {
        subNum = a % exponent;

        if (subNum == b)
            return true;

        a /= 10;
    }
    return false;
}

private static int getLength(int b) {

    int len = 0;

    while (b >= 1) {
        len++;
        b /= 10;
    }

    return len;
}

إليك طريقة السلسلة التي أستخدمها، والتي يبدو أنها تتفوق على الطريقة الرياضية أعلاه:

private static boolean findStringMatch(int a, int b) {      
    return String.valueOf(a).indexOf(String.valueOf(b)) != -1;      
}

وعلى الرغم من أن هذا ليس مطلوبًا حقًا بالنسبة لي لإكمال عملي، كنت أتساءل فقط عما إذا كان بإمكان أي شخص التفكير في أي طريقة لتحسين طريقتي في القيام بذلك رياضيًا، أو نهج جديد تمامًا تمامًا.مرة أخرى، الذاكرة ليست مشكلة، أنا فقط أصور من أجل السرعة المطلقة.

أنا مهتم حقًا برؤية أو سماع أي شيء يقدمه أي شخص في هذا الشأن.

يحرر: عندما أقول يحتوي أعني أنه يمكن أن يكون في أي مكان، لذلك على سبيل المثال، findMatch(1234, 23) == true

يحرر: لكل من يقول أن هذا الهراء غير قابل للقراءة وغير ضروري:كنت في عداد المفقودين هذه النقطة.كان الهدف هو التعرف على مشكلة مثيرة للاهتمام، وليس التوصل إلى إجابة لاستخدامها في كود الإنتاج.

Answer 1

وهذا هو طول خط Kibbee، ولكن حصلت قليلا مفتون هذا قبل أن تنشر وعمل ذلك:

long mask ( long n ) { 
    long m   = n % 10;
    long n_d = n;
    long div = 10;
    int  shl = 0;
    while ( n_d >= 10 ) { 
        n_d /= 10;
        long t = n_d % 10;
        m |= ( t << ( shl += 4 ));
    }
    return m;
}

boolean findMatch( int a, int b ) { 
    if ( b < a  ) return false;
    if ( a == b ) return true;

    long m_a = mask( a );    // set up mask O(n)
    long m_b = mask( b );    // set up mask O(m)

    while ( m_a < m_b ) {
        if (( m_a & m_b ) == m_a ) return true;
        m_a <<= 4;  // shift - fast!
        if ( m_a == m_b ) return true;
    }  // O(p)
    return false;
}       

void testContains( int a, int b ) { 
    print( "findMatch( " + a + ", " + b + " )=" + findMatch( a, b ));
}

testContains( 12, 120 );
testContains( 12, 125 );
testContains( 123, 551241238 );
testContains( 131, 1214124 );
testContains( 131, 1314124 );

---

ومنذ 300 حرف أبعد ما يكون قليلا جدا لجعل حجة في، أنا تحرير هذا المنصب الرئيسي للرد على Pyrolistical.

وعلى عكس OP، وأنا لم يكن ذلك فوجئت أن جمعت indexOf الأصلي كان أسرع من التعليمات البرمجية جافا مع الأوليات. لذلك كان هدفي ليس أن تجد شيئا أعتقد أنه كان أسرع من الأسلوب الأصلي دعا zillions من الأوقات في جميع أنحاء كود جافا.

ويتكون OP من الواضح أن هذا لم يكن مشكلة الإنتاج، وأكثر على غرار فضول الخمول، وبالتالي يحل جوابي أن الفضول. كان تخميني أن السرعة كانت قضية، عندما كان يحاول ايجاد حل لها في الإنتاج، ولكن كما مجرد فضول الخمول، "سيتم تسمى هذه الطريقة الملايين والملايين من المرات" لم يعد ينطبق. كما كان عليه أن يشرح للملصق واحد، انها لم تعد السعي إلى رمز الإنتاج، وبالتالي فإن تعقيد الأمور لم تعد.

وبالإضافة إلى أنه يوفر تنفيذ الوحيد على الصفحة التي تمكن من العثور على "123" في "551241238"، وذلك ما لم صحة مصدر قلق غريبة، لأنها توفر ذلك. أيضا مساحة حل "خوارزمية أن يحل المشكلة رياضيا باستخدام البدائيون جافا ولكن يدق الأمثل التعليمات البرمجية الأصلية" قد يكون <م> فارغ .

وبالاضافة الى ذلك، ليس من الواضح من تعليقك أم لا يمكنك مقارنة التفاح على التفاح. المواصفات وظيفية و (الباحث، الباحث) -> منطقية، وليس F (سلسلة، سلسلة) -> منطقية (والذي هو نوع من مجال indexOf). لذلك إلا إذا اختبرت شيئا من هذا القبيل (والتي يمكن أن تزال تغلب الألغام، وأنا لن يفاجأ بفظاعة.) أحمال إضافية <م> قد تلتهم بعض من تلك الزائدة 40٪.

boolean findMatch( int a, int b ) { 
    String s_a = "" + a;
    String s_b = "" + b;
    return s_a.indexOf( s_b ) > -1;
}

ويفعل نفس الخطوات الأساسية. تسجيل <الفرعية> 10 (أ) ترميز + تسجيل <الفرعية> 10 (ب) الترميز + العثور فعلا المباراة، وهو كذلك O (<م> ن ) حيث < م> ن هو أكبر اللوغاريتم.

Answer 2

وو<م> يجب تكون أسرع طريقة سلسلة، لأن المشكلة هي النصوص، وليس الرياضية. لاحظ أن لديك "يحتوي على" العلاقة تقول شيئا عن الأرقام، إلا أنها تقول شيئا عن من العشرية التمثيل.

لاحظ أيضا أن وظيفة كنت تريد أن تكتب سيكون غير قابل للقراءة - سوف مطور آخر يفهم أبدا ما تقومون به. (انظر ما مشكلة كان لديك مع ذلك هنا.) إصدار سلسلة، من ناحية أخرى، هو واضح تماما.

Answer 3

ووالتحسين الوحيد الذي أستطيع أن أفكر في أن أعمل تحويلها إلى سلسلة بنفسك ومقارنة أرقام (من اليمين إلى اليسار) كما تفعل التحويل. أولا تحويل جميع أرقام من ب، ثم تحويل من الحق على حتى تجد المباراة على الرقم الأول من ب (من اليمين). مقارنة حتى جميع المباريات ب أو كنت أصاب عدم تطابق. إذا كنت أصاب عدم التوافق، التراجع إلى النقطة التي تبدأ مطابقة الرقم الأول من ب، مقدما في والبدء من جديد.

سيكون

وIndexOf للقيام أساسا نفس خوارزمية تتبع الظهر، إلا من الناحية اليسرى. اعتمادا على الأرقام الفعلية وهذا قد يكون أسرع. أعتقد إذا كانت الأرقام العشوائية، ينبغي أن يكون منذ ينبغي أن يكون هناك العديد من الأوقات عندما لم يكن لديك لتحويل جميع لذلك.

Answer 4

ويبدو أن الدالة تقوم به في الواقع بشكل جيد جدا، ولكن تحسن طفيف:

private static boolean findMatch(int a, int b) {
        if (b > a) return false;

        if (a == b) return true;

        int needleLength = getLength(b);

        int exponent = exponents[needleLength];
        int subNum;
        while (a > b) {
                subNum = a % exponent;

                if (subNum == b)
                        return true;

                a /= 10;
        }
        return false;
}

وفقط لأنه بمجرد أن أصغر ب، ليست جديرة يحتفظ تبحث، أليس كذلك؟ حظا سعيدا وآخر إذا وجدت الحل!

Answer 5

هذا هو مشكلة مثيرة للاهتمام.العديد من وظائف String.class هي في الواقع وظائف أصلية مما يجعل التغلب على String اقتراحًا صعبًا.ولكن هنا بعض المساعدين:

نصيحة 1: عمليات الأعداد الصحيحة البسيطة المختلفة لها سرعات مختلفة.

من خلال الحسابات السريعة في نماذج البرامج أظهرت:

% ~ T
* ~ 4T
/ ~ 7T

لذا فأنت تريد استخدام أقل قدر ممكن من القسمة لصالح الضرب أو المعامل.لا تظهر عوامل الطرح والجمع والمقارنة لأنها تنفخ كل هذه العناصر خارج الماء.كما أن استخدام "النهائي" قدر الإمكان يسمح لـ JVM بإجراء تحسينات معينة.تسريع وظيفة "getLength":

private static int getLength(final int b) {        
   int len = 0;
   while (b > exponents[len]) {
       len++;
   }
   return len + 1
}

وهذا يعطي تحسينًا بمقدار 7 أضعاف في الوظيفة.يمكنك الحصول على استثناء IndexOutOfBounds إذا كان b > الحد الأقصى الخاص بك في الأسس.لحل ذلك، يمكنك الحصول على:

private static int getLength(final int b) {        
   int len = 0;
   final int maxLen = exponents.length;
   while (len < maxLen && b > exponents[len]) {
       len++;
   }
   return len + 1;
}

هذا أبطأ قليلًا ويمنحك طولًا غير صحيح إذا كان b كبيرًا جدًا، لكنه لا يسبب استثناءً.

نصيحة 2: يضيف الإنشاء غير الضروري للكائن/البدائي واستدعاءات الأسلوب إلى وقت التشغيل.

أعتقد أن "getLength" لا يتم استدعاؤه في أي مكان آخر، لذلك في حين أنه قد يكون من الجيد أن يكون لديك وظيفة منفصلة، ​​من وجهة نظر التحسين، فهي عبارة عن استدعاء أسلوب غير ضروري وإنشاء الكائن "len".يمكننا وضع هذا الرمز في المكان الذي نستخدمه فيه.

private static boolean findMatch(int a, final int b) {
        if (b > a) return false;
        if (a == b) return true;
        int needleLength = 0;
        while (b > exponents[len]) {
            needleLength ++;
        }
        needleLength++;

        final int exponent = exponents[needleLength];
        int subNum;
        while (a >= 1 && a <= b) {
                subNum = a % exponent;
                if (subNum == b)
                        return true;
                a /= 10;
        }
        return false;
}

لاحظ أيضًا أنني قمت بتغيير الحلقة السفلية لتشمل أيضًا "a <= b".لم أختبر ذلك ولست متأكدًا مما إذا كانت عقوبة التكرار تتفوق على حقيقة أنك لا تضيع أي تكرارات.أنا متأكد من أن هناك طريقة للتخلص من عملية القسمة باستخدام الرياضيات الذكية، لكن لا يمكنني التفكير فيها الآن.

Answer 6

وأم، أنا سوء الفهم المحتمل تماما هذا السؤال، ولكن .....

// Check if A is inside B lol
bool Contains (int a, int b)
{
    return (a <= b);
}

وإلا إذا كنت تريد أن تعرف ما إذا كان تسلسل معين من الأرقام ضمن سلسلة أخرى من الأرقام.

في هذه الحالة، وتحويلها إلى سلسلة سوف يكون أسرع من القيام الرياضيات لأنها من أصل الرقم.

Answer 7

وهذا بأي حال من الأحوال يجيب عن سؤالك، على الإطلاق، لكنه على أي حال المشورة: -)

ووfindMatch اسم الأسلوب ليس صفي للغاية. في هذه الحالة، كنت قد وContainerBuilder.number(int) أسلوب ثابت، الذي عاد ContainerBuilder، والتي لديها contains طريقة عليه. وبهذه الطريقة يصبح التعليمات البرمجية:

boolean b = number(12345).contains(234);

وناتئة بعض النصائح على المدى الطويل!

وأوه نعم، يعني أنا أقول أيضا، يجب عليك <م> تعريف ما تعنيه ب "يحتوي على"

Answer 8

هل هناك أي طريقة لحساب هذا في ثنائي؟ من الواضح أن قيمة ثنائية من عدد صحيح يحتوي على عدد صحيح ثنائي حرف آخر لا يعني أن decical يفعل نفس الشيء. ومع ذلك، هناك نوع من trickary الثنائية التي يمكن استخدامها؟ ربما تحويل numer مثل 12345-0001 0010 0011 0100 0101، ومن ثم القيام ببعض الشيء تحول لمعرفة إذا كان واردا 23 (0010 0011) في هناك. لأن مجموعة الطابع الخاص بك هو 10 أحرف فقط، يمكنك خفض الوقت اللازم للحساب عن طريق متجر 2 قيم الأحرف في بايت واحد.

وتحرير

والتوسع في هذه الفكرة قليلا. إذا كان لديك 2 الأعداد الصحيحة، A و B، وتريد أن تعرف إذا كانت A يحتوي B، عليك التحقق من 2 الأشياء الأولى. إذا (أ) هو أقل من B، A ثم لا يمكن أن تحتوي B. إذا A = B ثم A يحتوي B. عند هذه النقطة يمكن تحويلها إلى سلاسل *. إذا ويحتوي على نفس العدد من الأرقام طابع B، A ثم لا يحتوي B، إلا أنهم متساوون، ولكن لن نكون هنا إذا كانت تساوي، لذلك إذا كان كل من السلاسل هي نفس الطول، لا يحتوي على ب . عند هذه النقطة، فإن طول ويكون أطول من B. لذا، الآن يمكنك تحويل السلاسل إلى القيم الثنائية معبأة بهم كما أشرت في الجزء الأول من هذا المنصب. تخزين هذه القيم في مجموعة من أعداد صحيحة. الآن يمكنك القيام أحادي المعامل والقيم عدد صحيح في مجموعة الخاصة بك، وإذا كانت النتيجة هي A، ثم ويحتوي B. الآن يمكنك تحويل مجموعة من الأعداد الصحيحة لB، إلى اليسار 4 بت، والقيام conparison مرة أخرى. هل هذا حتى تبدأ ظهرت بت من يسار B.

* أن * في الفقرة السابقة يعني أنك قد تكون قادرة على تخطي هذه الخطوة. قد يكون هناك طريقة للقيام بذلك دون استخدام السلاسل على الإطلاق. قد يكون هناك بعض خدعة الثنائية يتوهم يمكنك القيام به للحصول على تمثيل ثنائي معبأة ناقشت في الفقرة الأولى. ينبغي أن يكون هناك بعض خدعة الثنائية يمكنك استخدامها، أو بعض الرياضيات سريعة والتي سيتم تحويل عدد صحيح إلى القيمة العشرية ناقشت من قبل.

Answer 9

هل لي أن أسأل حيث كنت تستخدم هذه الوظيفة في التعليمات البرمجية؟ ربما هناك طريقة أخرى للحل الذي سيكون أسرع بكثير المشكلة هو حل حاليا. هذا يمكن أن يكون مثل عندما سألني صديقي لإعادة ضبط غيتاره تماما، وأنا فعلت هذا قبل تحقيق يمكنني أن خفضت مجرد سلسلة السفلية من خطوة كاملة، وحصلت على نتيجة مماثلة.

Answer 10

ومعلوماتك

http://refactormycode.com/

ويمكن أن تعمل من أجلك.