Нахождение числовых подстрок математически, без сравнения строк

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

Это должно быть более быстрым строковым способом, потому что ваша проблема текстовая, а не математическая. Обратите внимание, что ваше отношение «содержит» ничего не говорит о числах, оно только говорит об их десятичных представлениях.

Обратите внимание, что функция, которую вы хотите написать, будет нечитаемой - другой разработчик никогда не поймет, что вы делаете. (Смотрите, какие у вас проблемы с этим здесь.) С другой стороны, строковая версия совершенно ясна.

Answer 2

Это по линии Кибби, но я был немного заинтригован этим, прежде чем он написал и решил:

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 символов - это слишком мало, чтобы приводить аргументы, я редактирую этот основной пост, чтобы ответить на "Пиролистику".

В отличие от OP, я не был удивлен, что нативный скомпилированный indexOf был быстрее, чем код Java с примитивами. Поэтому моя цель не состояла в том, чтобы найти что-то, что, как мне показалось, было быстрее, чем нативный метод, называемый миллионы раз по всему Java-коду.

ОП ясно дал понять, что это была не производственная проблема, а скорее по линии праздного любопытства, поэтому мой ответ разрешает это любопытство. Я предположил, что скорость была проблемой, когда он пытался решить ее в процессе производства, но из любопытства «этот метод будет вызываться миллионы и миллионы раз» больше не применяется. Как он должен был объяснить одному постеру, его больше не используют в качестве производственного кода, поэтому сложность больше не имеет значения.

Кроме того, он обеспечивает единственную реализацию на странице, которой удается найти «123» в «551241238», поэтому, если правильность не является посторонней проблемой, он обеспечивает это. Также пространство решения «алгоритма, который решает проблему математически с использованием примитивов Java, но опережает оптимизированный нативный код», может быть EMPTY .

Плюс, из вашего комментария не ясно, сравнивали ли вы яблоки с яблоками. Функциональной спецификацией является f (int, int) -> boolean, а не f (String, String) -> boolean (что является разновидностью домена indexOf). Так что, если вы не протестируете что-то подобное (что все еще может побить мою, и я не буду сильно удивлен), дополнительные накладные расходы могут съесть некоторые из этих 40%.

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

Выполняет те же основные шаги. log ₁₀ (a) кодировка + log ₁₀ (b) кодировка + фактическое нахождение соответствия, что также O ( n ) где n - самый большой логарифм.

Answer 3

Единственная оптимизация, о которой я могу подумать, - это выполнить преобразование в строку самостоятельно и сравнить цифры (справа налево) во время преобразования. Сначала преобразуйте все цифры b, а затем преобразуйте справа от a, пока не найдете совпадение по первой цифре b (справа). Сравнивайте, пока все b не совпадут или вы не попадете в несоответствие. Если вы столкнулись с несоответствием, вернитесь к точке, с которой начинаете сопоставлять первую цифру b, продвиньтесь в a и начните сначала.

IndexOf должен будет выполнять в основном тот же алгоритм обратного отслеживания, кроме слева. В зависимости от фактических чисел это может быть быстрее. Я думаю, что если числа случайные, так и должно быть, так как должно быть много раз, когда не нужно конвертировать все.

Answer 4

Это интересная проблема. Многие из функций String.class на самом деле являются нативными, что затрудняет избиение String. Но вот несколько помощников:

СОВЕТ 1: Различные простые целочисленные операции имеют разные скорости.

По быстрым расчетам в примерах программ показано:

% ~ T
* ~ 4T
/ ~ 7T

Таким образом, вы хотите использовать как можно меньшее деление в пользу умножения или по модулю. Не показаны операторы вычитания, сложения и сравнения, потому что они выдувают все это из воды. Кроме того, максимально возможное использование «final» позволяет 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;
}

Кроме того, обратите внимание, что я изменил нижний цикл while, чтобы также включить «a <= b». Я не проверял это и не уверен, что штраф за каждую итерацию превосходит тот факт, что вы не теряете ни одной итерации. Я уверен, что есть способ избавиться от деления, используя умную математику, но я не могу думать об этом прямо сейчас. </p>

Answer 5

Похоже, что ваша функция работает довольно хорошо, но небольшое улучшение:

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;
}

Просто потому, что если а меньше b, то он не достоин искать, не так ли? Удачи и напишите, если найдете решение!

Answer 6

Могу я спросить, где вы используете эту функцию в своем коде? Может быть, есть другой способ решить проблему, которую он сейчас решает, который был бы намного быстрее. Это может быть похоже на то, когда мой друг попросил меня полностью перенастроить его гитару, и я сделал это, прежде чем понял, что мог просто опустить нижнюю струну на целый шаг и получить эквивалентный результат.

Answer 7

FYI

http://refactormycode.com/

Может работать на вас.

Answer 8

Есть ли способ рассчитать это в двоичном виде? Очевидно, что двоичное значение целого числа, содержащее двоичное целое число другого символа, не означает, что десятичное число делает то же самое. Тем не менее, есть ли какой-то двоичный трюк, который можно использовать? Может быть, преобразовать числовое значение, например 12345, в 0001 0010 0011 0100 0101, а затем выполнить сдвиг битов, чтобы выяснить, содержится ли там 23 (0010 0011). Поскольку ваш набор символов составляет всего 10 символов, вы можете сократить время вычислений, сохранив 2-значные значения в одном байте.

EDIT

Расширяю эту идею немного. если у вас есть 2 целых числа, A и B, и вы хотите узнать, содержит ли A B, вы сначала проверяете 2 вещи. если A меньше B, то A не может содержать B. Если A = B, то A содержит B. В этот момент вы можете преобразовать их в строки *. Если A содержит такое же количество символов, что и B, то A не содержит B, если только они не равны, но мы не были бы здесь, если бы они были равны, поэтому, если обе строки имеют одинаковую длину, a не содержит b , На этом этапе длина A будет больше, чем B. Итак, теперь вы можете преобразовать строки в их упакованные двоичные значения, как я отмечал в первой части этого поста. Сохраните эти значения в массиве целых чисел. Теперь вы выполняете побитовое И целочисленных значений в вашем массиве, и если результат равен A, то A содержит B. Теперь вы смещаете массив целых чисел для B в 4 левых бита и снова выполняете сравнение. Делайте это, пока не начнете выталкивать биты слева от B.

* Это * в предыдущем абзаце означает, что вы можете пропустить этот шаг. Может быть способ сделать это без использования строк вообще. Там может быть какой-то причудливый двоичный трюк, который вы можете сделать, чтобы получить упакованное двоичное представление, которое я обсуждал в первом абзаце. Должен быть какой-то двоичный трюк, который вы можете использовать, или некоторая быстрая математика, которая преобразует целое число в десятичное значение, которое я обсуждал ранее.

Answer 9

Это никоим образом не отвечает на ваш вопрос, но в любом случае это совет: -)

Имя метода findMatch не очень наглядно. В этом случае у меня будет статический метод ContainerBuilder.number(int), который возвращает ContainerBuilder, в котором есть метод contains. Таким образом, ваш код становится:

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

Советы на долгую перспективу!

О, да, я хотел сказать также, вы должны определить, что вы подразумеваете под "содержит"

Answer 10

Хмм, я, наверное, совершенно не понимаю вопроса, но .....

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

Если вы не хотите знать, находится ли определенная последовательность чисел в другой последовательности чисел.

В этом случае преобразование его в строку БУДЕТ быстрее, чем математическое вычисление, чтобы выяснить это.