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

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

Так что, хотя мне действительно не нужно выполнять мою работу, мне просто интересно, может ли кто-нибудь подумать о том, чтобы еще больше оптимизировать мой способ сделать это математически или совершенно новый подход. Снова память не проблема, я просто стреляю по чистой скорости.

Мне очень интересно видеть или слышать что-либо, что может предложить любой человек.

EDIT: Когда я говорю, я имею в виду содержит может быть где угодно, так, например, findMatch (1234, 23) == истинный

EDIT: Для всех говорят, что это дерьмо не читается и не нужно: вам не хватает смысла. Дело в том, чтобы разобраться в интересной проблеме, а не придумать ответ, который будет использоваться в производственном коде.

Answer 1

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

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

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

Плюс это обеспечивает единственную реализацию на странице, которой удается найти «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; 
} 

Он выполняет те же основные шаги. войти (а) кодирование + _{войти 10} (б) кодирование + на самом деле найти матч, который а также вывода (п), где п является самым крупным логарифм.

Answer 2

Гм, я, вероятно, совершенно неправильное понимание вопроса, но .....

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

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

В этом случае преобразование его в строку будет быстрее, чем вычисление математики.

Answer 3

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

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

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

Juts некоторый совет для долгосрочного использования!

Ах да, я хотел сказать, кроме того, вы должны определить, что вы подразумеваете под «содержит»

Answer 4

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

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

Answer 5

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

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

Answer 6

Есть ли способ вычислить это в двоичном формате? Очевидно, что двоичное значение целого числа, содержащего двоичное целое другого символа, не означает, что это делает то же самое. Однако существует ли какая-то двоичная хитрость, которая может быть использована? Может быть, конвертировать цифру как 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 7

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

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 8

FYI

http://refactormycode.com/

Может работать для вас.

Answer 9

Это интересная проблема. Многие из функций 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; 
} 

Это немного медленнее и дает вам неправильную длину, если б слишком большой, но это не исключение.

СОВЕТ 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; 
} 

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

Answer 10

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