Математический поиск числовых подстрок без сравнения строк
https://stackoverflow.com/questions/231917
-
04-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Первоначально это была проблема, с которой я столкнулся на работе, но теперь я просто пытаюсь решить эту проблему из собственного любопытства.
Я хочу выяснить, содержит ли 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
РЕДАКТИРОВАТЬ: Для всех, кто говорит, что эта хрень нечитабельна и ненужна:вы упускаете суть.Цель заключалась в том, чтобы разобраться в интересной проблеме, а не найти ответ для использования в рабочем коде.
Решение
Это по линии Кибби, но я был немного заинтригован этим, прежде чем он написал и решил это:
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 с примитивами. Поэтому моя цель не состояла в том, чтобы найти что-то, что, как мне показалось, было быстрее, чем нативный метод, называемый миллионы раз во всем коде Java.
ОП дала понять, что это не производственная проблема, а скорее в духе праздного любопытства, поэтому мой ответ разрешает это любопытство. Я догадывался, что скорость была проблемой, когда он пытался решить ее в процессе производства, но в качестве праздного любопытства & Quot; этот метод будет вызываться миллионы и миллионы раз & Quot; больше не применяется. Как он должен был объяснить одному постеру, его больше не используют в качестве производственного кода, поэтому сложность больше не имеет значения.
Кроме того, он предоставляет единственную реализацию на странице, которой удается найти " 123 " в " 551241238 " ;, поэтому, если правильность не является посторонней задачей, она это обеспечивает. Также пространство решения & Quot; алгоритм, который решает проблему математически с использованием примитивов Java, но превосходит оптимизированный собственный код & Quot; может быть ПУСТО .
Кроме того, из вашего комментария не ясно, сравнивали ли вы яблоки с яблоками. Функциональная спецификация: f (int, int) - & Gt; логическое значение, а не f (String, String) - > логический (который является разновидностью домена indexOf). Поэтому, если вы не протестируете что-то подобное (что все еще может превзойти мое, и я не буду сильно удивлен), дополнительные накладные расходы могут съесть некоторые из этих 40%.
boolean findMatch( int a, int b ) {
String s_a = "" + a;
String s_b = "" + b;
return s_a.indexOf( s_b ) > -1;
}
Он выполняет те же основные шаги. log 10 (a) кодировка + log 10 (b) кодировка + фактическое нахождение соответствия, что также равно O ( n ) где < em> n - самый большой логарифм.
Другие советы
Это должно быть более быстрым строковым способом, потому что ваша проблема текстовая, а не математическая. Обратите внимание, что ваш & Quot; содержит & Quot; отношения ничего не говорят о числах, они только говорят что-то об их десятичном представлении.
Обратите внимание, что функция, которую вы хотите написать, будет нечитаемой - другой разработчик никогда не поймет, что вы делаете. (Посмотрите, какие у вас проблемы с этим здесь.) Строковая версия, с другой стороны, совершенно ясна.
Единственная оптимизация, о которой я могу подумать, - это выполнить преобразование в строку самостоятельно и сравнивать цифры (справа налево) во время преобразования. Сначала преобразуйте все цифры b, а затем преобразуйте справа от a, пока не найдете совпадение по первой цифре b (справа). Сравнивайте, пока все b не совпадут или вы не столкнетесь с ошибкой Если вы столкнулись с несоответствием, вернитесь к точке, с которой вы начинаете сопоставлять первую цифру b, продвиньтесь в a и начните сначала.
IndexOf должен будет делать в основном тот же алгоритм обратного отслеживания, кроме слева. В зависимости от фактических чисел это может быть быстрее. Я думаю, что если числа случайные, то так и должно быть, так как должно быть много раз, когда не нужно конвертировать все.
Похоже, ваша функция на самом деле работает довольно хорошо, но небольшое улучшение:
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;
}
Просто потому, что если a меньше b, он не достоин того, чтобы искать, не так ли? Удачи и напишите, если найдете решение!
Это интересная проблема. Многие из функций String.class на самом деле являются нативными, что затрудняет избиение String. Но вот несколько помощников:
СОВЕТ 1: Различные простые целочисленные операции имеют разные скорости.
По быстрым расчетам в примерах программ показано:
% ~ T
* ~ 4T
/ ~ 7T
Таким образом, вы хотите использовать как можно меньшее деление в пользу умножения или по модулю. Не показаны операторы вычитания, сложения и сравнения, потому что они выдувают все это из воды. Кроме того, используя & Quot; final & Quot; насколько это возможно, JVM позволяет выполнять определенные оптимизации. Ускорение & Quot; getLength & Quot; Функция:
private static int getLength(final int b) {
int len = 0;
while (b > exponents[len]) {
len++;
}
return len + 1
}
Это дает примерно 7-кратное улучшение функции. Вы получаете исключение indexOutOfBounds, если b & Gt; ваш максимум в показателях. Чтобы решить эту проблему, вы можете иметь:
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 " ;. Я не проверял это и не уверен, что штраф за каждую итерацию превосходит тот факт, что вы не теряете ни одной итерации. Я уверен, что есть способ избавиться от разделения, используя умную математику, но я не могу думать об этом прямо сейчас.
Хм, я, наверное, совершенно не понимаю вопроса, но .....
// Check if A is inside B lol
bool Contains (int a, int b)
{
return (a <= b);
}
Если вы не хотите знать, находится ли определенная последовательность чисел в другой последовательности чисел.
В этом случае преобразование его в строку БУДЕТ быстрее, чем вычисление.
Это никоим образом не отвечает на ваш вопрос, но в любом случае это совет: -)
Имя метода findMatch не очень наглядно. В этом случае у меня будет статический метод ContainerBuilder.number(int), который возвращает ContainerBuilder, в котором есть метод contains. Таким образом, ваш код становится:
boolean b = number(12345).contains(234);
Делаю советы на долгую перспективу!
О да, я хотел сказать также, что вы должны определить, что вы подразумеваете под " содержит "
Есть ли способ посчитать это в двоичном формате?Очевидно, что двоичное значение целого числа, содержащее двоичное целое число другого символа, не означает, что десятичное число делает то же самое.Однако есть ли какой-то двоичный трюк, который можно было бы использовать?Возможно, преобразуйте число, например 12345, в 0001 0010 0011 0100 0101, а затем выполните некоторый битовый сдвиг, чтобы выяснить, содержится ли там 23 (0010 0011).Поскольку ваш набор символов состоит всего из 10 символов, вы можете сократить время вычислений, сохранив значения из двух символов в одном байте.
РЕДАКТИРОВАТЬ
Немного разовьем эту идею.Если у вас есть два целых числа, A и B, и вы хотите узнать, содержит ли A B, вы сначала проверяете 2 вещи.если A меньше B, то A не может содержать B.Если А = В, то А содержит В.На этом этапе вы можете преобразовать их в строки*.Если A содержит то же количество номеров символов, что и B, то A не содержит B, если только они не равны, но нас бы здесь не было, если бы они были равны, поэтому, если обе строки имеют одинаковую длину, a не содержит b. .В этот момент длина A будет больше, чем B.Итак, теперь вы можете преобразовать строки в упакованные двоичные значения, как я отметил в первой части этого поста.Сохраните эти значения в массиве целых чисел.Теперь вы выполняете поразрядное И над целочисленными значениями в вашем массиве, и если результатом является A, то A содержит B.Теперь вы сдвигаете массив целых чисел для B на 4 бита влево и снова выполняете сравнение.Делайте это до тех пор, пока не начнете выскакивать кусочки слева от B.
*Это* в предыдущем абзаце означает, что вы можете пропустить этот шаг.Возможно, есть способ сделать это вообще без использования строк.Чтобы получить упакованное двоичное представление, которое я обсуждал в первом абзаце, можно проделать какой-нибудь причудливый бинарный трюк.Должен быть какой-нибудь двоичный трюк, который вы можете использовать, или быстрая математика, которая преобразует целое число в десятичное значение, которое я обсуждал ранее.
Могу я спросить, где вы используете эту функцию в своем коде? Может быть, есть другой способ решить проблему, которую он сейчас решает, который был бы намного быстрее. Это может быть похоже на то, когда мой друг попросил меня полностью перенастроить его гитару, и я сделал это, прежде чем понял, что мог просто опустить нижнюю строку на целый шаг и получить эквивалентный результат.
