Нахождение числовых подстрок математически, без сравнения строк
С массивами NumPy вы можете использовать довольно удобные методы индексации, что является особенностью NUMPY частей, которые называются причудливой индексации .
Давайте попробуем это с небольшим примером 2D-массива:
import numpy as np
a=np.arange(48).reshape(6, 8)
print(a)
#[[ 0 1 2 3 4 5 6 7]
# [ 8 9 10 11 12 13 14 15]
# [16 17 18 19 20 21 22 23]
# [24 25 26 27 28 29 30 31]
# [32 33 34 35 36 37 38 39]
# [40 41 42 43 44 45 46 47]]
Если вы сейчас хотите проиндексировать, например, В строках 2 и 3 и столбцах с 3 по 6 вы можете просто записать это в виде срезов, независимо от того, по константам или переменным:
r1 = 2; r2 = 4
print(a[r1:r2, 3:7])
#[[19 20 21 22]
# [27 28 29 30]]
Вы можете прочитать здесь: https: / /docs.scipy.org/doc/numpy/user/basics.indexing.html
10 ответов
Это приезжает строка 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 собственного компонента был быстрее, чем код Java с примитивами. Таким образом, моя цель не состояла в том, чтобы найти что-то, что я думал, было быстрее, чем собственный метод, названный огромным количеством времен на всем протяжении кода Java.
OP прояснил, что это не было производственной проблемой и больше вроде неактивного любопытства, таким образом, мой ответ решает то любопытство. Мое предположение было то, что скорость была проблемой, когда он пытался решить ее в производстве, но поскольку неактивное любопытство, "Этот метод не будут называть миллионами и миллионы времен" больше, применяется. Как он должен был объяснить одному плакату, он больше не преследуется как производственный код, таким образом, сложность больше не имеет значения.
Плюс он обеспечивает единственную реализацию на странице, которой удается найти "123" в "551241238", поэтому если правильность не является посторонним беспокойством, это обеспечивает это. Также пространство решения "алгоритма, который решает проблему математически с помощью примитивов Java, но удары оптимизировали собственный код", могло бы быть ПУСТЫМ.
Плюс, не ясно из Вашего комментария, сравнили ли Вы яблоки с яблоками. Функциональная спецификация является f (интервал, интервал)-> булевская переменная, не f (Строка, Строка)-> булевская переменная (который является видом домена indexOf). Таким образом, если Вы не протестировали что-то вроде этого (который мог все еще разбить мой, и я не буду ужасно удивлен.) дополнительные издержки могли бы съесть некоторые из тех избыточных 40%.
boolean findMatch( int a, int b ) {
String s_a = "" + a;
String s_b = "" + b;
return s_a.indexOf( s_b ) > -1;
}
Это делает те же основные шаги. log10 (a) кодирующий + log10 (b) кодирующий + на самом деле нахождение соответствия, которое является также O (n), где n является самым большим логарифмом.
Похож на Вашу функцию, на самом деле делает вполне прилично, но маленькое улучшение:
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, не достойно, продолжает смотреть, не так ли? Удача и сообщение, если Вы находите решение!
Единственная оптимизация, о которой я могу думать, должна сделать преобразование, чтобы представить в виде строки самостоятельно и сравнить цифры (справа налево), как Вы делаете преобразование. Сначала преобразуйте все цифры b, затем преобразуйте справа на, пока Вы не найдете соответствие на первой цифре b (от права). Сравните до всех соответствий b или Вы поражаете несоответствие. Если Вы поражаете несоответствие, отслеживаете в обратном порядке до такой степени, когда Вас запуск, соответствующий первой цифре b, усовершенствования в a, и запускаетесь.
IndexOf должен будет сделать в основном тот же задний алгоритм отслеживания, кроме слева. В зависимости от фактических чисел это может быть быстрее. Я думаю, случайны ли числа, это должно быть, так как должно быть много раз, когда это не должно преобразовывать все a.
Это должна быть более быстрая строка путь, потому что Ваша проблема является текстовой, не математической. Заметьте, что Ваш "содержит" отношения, не говорит ничто о числах, они только говорят что-то об их десятичных представлениях.
Заметьте также, что функция, которую Вы хотите записать, будет нечитабельна - другой разработчик никогда не будет понимать то, что Вы делаете. (См. то, что беспокоит Вас, имел с этим здесь.) Строковая версия, с другой стороны, совершенно ясна.
Umm, я, вероятно, полностью неправильно понимаю вопрос, но.....
// Check if A is inside B lol
bool Contains (int a, int b)
{
return (a <= b);
}
Если Вы не хотите знать, ли конкретная последовательность чисел в другой последовательности чисел.
В этом случае преобразование его к строке будет быстрее, чем выполнение математики для понимания его.
Это - интересная проблема. Многими функциями String.class является на самом деле собственная Строка избиения создания трудное суждение. Но вот некоторые помощники:
ПОДСКАЗКА 1: Различные простые целочисленные операции имеют различные скорости.
Быстрыми вычислениями в примерах программ показал:
% ~ T
* ~ 4T
/ ~ 7T
Таким образом, Вы хотите использовать как можно меньше подразделения в пользу умножения или по модулю. Не показанный вычитание, дополнение и причина операторов сравнения, они уносят все их из воды. Кроме того, использование "финала" как можно больше позволяет JVM делать определенную оптимизацию. Ускорение Вас функция "getLength":
private static int getLength(final int b) {
int len = 0;
while (b > exponents[len]) {
len++;
}
return len + 1
}
Это дает о 7x улучшение функции. Вы получаете 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;
}
Кроме того, обратите внимание, что я изменил нижний цикл с условием продолжения, чтобы также включать "<= b". Я не протестировал это и не уверенный, если штраф на повторение бьет то, что Вы не тратите впустую повторений. Я уверен, что существует способ избавиться от подразделения с помощью умной математики, но я не могу думать о нем прямо сейчас.
Это никоим образом не отвечает на Ваш вопрос, безотносительно, но это - совет так или иначе :-)
Имя метода findMatch не является очень описательным. В этом случае у меня был бы статический метод ContainerBuilder.number(int), который возвратил a ContainerBuilder, который имеет метод contains на нем. Таким образом Ваш код становится:
boolean b = number(12345).contains(234);
Выступы некоторый совет в течение длительного периода!
Ах да я означал говорить также, необходимо определить то, под чем Вы подразумеваете, "содержит"
Там какой-либо путь состоит в том, чтобы вычислить это в двоичном файле? Очевидно, двоичное значение целого числа, содержащего двоичное целое число другого символа, не означает, что decical делает то же. Однако есть ли некоторый двоичный обман, который мог использоваться? Возможно, преобразуйте numer как от 12345 до 0001 0010 0011 0100 0101 и затем сделайте некоторый бит, смещающийся, чтобы выяснить, содержится ли 23 (0010 0011) там. Поскольку Ваш набор символов является только 10 символами, Вы могли сократить время вычисления хранилищем 2 значения символов в единственном байте.
Править
Подробно останавливаясь на этой идее немного. если Вы имеете 2 целых числа, A и B, и хотите знать, содержит ли A B, Вы проверяете 2 вещи сначала. если A является меньше, чем B, то A не может содержать B. Если = B затем A содержит B. В этой точке можно преобразовать их в strings*. Если A содержит то же количество чисел символов как B, то A не содержит B, если они не равны, но мы не были бы здесь, если они равны, поэтому если обе строки являются той же длиной, не содержат b. На данном этапе длина A будет длиннее, чем B. Так, теперь можно преобразовать строки в их упакованные двоичные значения, как я отметил в первой части этого сообщения. Сохраните эти значения в массиве целых чисел. Теперь Вы делаете поразрядное И целочисленных значений в Вашем массиве, и если результатом является A, то A содержит B. Теперь Вы смещаете массив целых чисел для B, к левым 4 битам, и делаете сравнение снова. Сделайте это, пока Вы не начнете выталкивать биты от левых B.
*Что * в предыдущем абзаце означает, что Вы можете пропускать этот шаг. Может быть способ сделать это, не используя строки вообще. Мог бы быть некоторый необычный двоичный прием, который можно сделать для получения упакованного двоичного представления, которое я обсудил в первом абзаце. Должен быть некоторый двоичный прием, который можно использовать, или некоторая быстрая математика, которая преобразует целое число в десятичное значение, которое я обсудил прежде.
Я могу спросить, где Вы используете эту функцию в своем коде? Возможно, существует другой способ решить проблему, которую он в настоящее время решает, который был бы намного быстрее. Это могло быть похожим, когда мой друг попросил, чтобы я полностью повторно настроил его гитару, и я сделал это прежде, чем понять, что я, возможно, просто понизил нижнюю строку целым шагом и получил эквивалентный результат.