Encontrar subcadenas numéricas matemáticamente, sin comparación de cadenas
https://stackoverflow.com/questions/231917
-
04-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPregunta
Esto originalmente era un problema que encontré en el trabajo, pero ahora es algo que solo estoy tratando de resolver por mi propia curiosidad.
Quiero saber si int 'a' contiene int 'b' de la manera más eficiente posible. Escribí un código, pero parece que no importa lo que escriba, analizarlo en una cadena y luego usar indexOf es el doble de rápido que hacerlo matemáticamente.
La memoria no es un problema (dentro de lo razonable), solo la velocidad de procesamiento.
Este es el código que he escrito para hacerlo matemáticamente:
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;
}
Aquí está el método de cadena que estoy usando, que parece superar el método matemático anterior:
private static boolean findStringMatch(int a, int b) {
return String.valueOf(a).indexOf(String.valueOf(b)) != -1;
}
Entonces, aunque esto no es realmente necesario para completar mi trabajo, me preguntaba si alguien podría pensar en alguna forma de optimizar aún más mi forma de hacerlo matemáticamente, o un enfoque completamente nuevo. Nuevamente, la memoria no es un problema, solo estoy disparando por pura velocidad.
Estoy realmente interesado en ver o escuchar cualquier cosa que alguien pueda ofrecer sobre esto.
EDITAR: Cuando digo contiene, quiero decir que puede estar en cualquier lugar, por ejemplo, findMatch (1234, 23) == verdadero
EDITAR: Para todos los que dicen que esta basura es ilegible e innecesaria: te estás perdiendo el punto. El punto era llegar a un problema interesante, no encontrar una respuesta para usar en el código de producción.
Solución
Esto está en la línea de Kibbee, pero me intrigó un poco esto antes de que publicara y resolviera esto:
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 );
Dado que 300 caracteres es demasiado poco para discutir, estoy editando esta publicación principal para responder a Pyrolistical.
A diferencia del OP, no me sorprendió que un indexOf compilado nativo fuera más rápido que el código Java con primitivas. Por lo tanto, mi objetivo no era encontrar algo que creía que era más rápido que un método nativo llamado billones de veces en todo el código Java.
El OP dejó en claro que esto no era un problema de producción y más en la línea de una curiosidad ociosa, por lo que mi respuesta resuelve esa curiosidad. Supuse que la velocidad era un problema cuando intentaba resolverlo en producción, pero como curiosidad inactiva, & "; Este método se llamará millones y millones de veces &"; ya no aplica. Como tuvo que explicar a un afiche, ya no se busca como código de producción, por lo que la complejidad ya no importa.
Además, proporciona la única implementación en la página que logra encontrar el " 123 " en & "; 551241238 &"; por lo tanto, a menos que la corrección sea una preocupación extraña, proporciona eso. También el espacio de solución de & "; Un algoritmo que resuelve el problema matemáticamente usando primitivas Java pero supera el código nativo optimizado &"; podría estar VACÍO .
Además, en su comentario no está claro si comparó o no manzanas con manzanas. La especificación funcional es f (int, int) - & Gt; booleano, no f (String, String) - > booleano (que es una especie de dominio de indexOf). Entonces, a menos que haya probado algo como esto (que aún podría vencer al mío, y no estaría muy sorprendido), la sobrecarga adicional podría consumir parte de ese exceso del 40%.
boolean findMatch( int a, int b ) {
String s_a = "" + a;
String s_b = "" + b;
return s_a.indexOf( s_b ) > -1;
}
Realiza los mismos pasos básicos. log 10 (a) codificación + log 10 (b) codificación + realmente encontrar la coincidencia, que también es O ( n ) donde < em> n es el logaritmo más grande.
Otros consejos
Es debería ser una forma de cadena más rápida, porque su problema es textual, no matemático. Observe que su & Quot; contiene & Quot; la relación no dice nada sobre los números, solo dice algo sobre sus representaciones decimales .
Observe también que la función que desea escribir será ilegible: otro desarrollador nunca entenderá lo que está haciendo. (Vea qué problemas tuvo con eso aquí.) La versión de cadena, por otro lado, es perfectamente clara.
La única optimización que se me ocurre es hacer la conversión a cadena por su cuenta y comparar los dígitos (de derecha a izquierda) a medida que realiza la conversión. Primero convierta todos los dígitos de b, luego convierta desde la derecha en a hasta que encuentre una coincidencia en el primer dígito de b (desde la derecha). Compare hasta que todas las coincidencias b o llegue a una falta de coincidencia. Si encuentra una falta de coincidencia, retroceda hasta el punto donde comience a coincidir con el primer dígito de b, avance en a y comience de nuevo.
IndexOf tendrá que hacer básicamente el mismo algoritmo de seguimiento, excepto desde la izquierda. Dependiendo de los números reales, esto puede ser más rápido. Creo que si los números son aleatorios, debería serlo, ya que debería haber muchas veces cuando no tiene que convertir todo a.
Parece que su función está funcionando bastante bien, pero una pequeña mejora:
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;
}
Solo porque una vez que a es más pequeño que b, no es digno sigue buscando, ¿no? ¡Buena suerte y publica si encuentras la solución!
Este es un problema interesante. Muchas de las funciones de String.class son en realidad nativas, por lo que vencer a String es una propuesta difícil. Pero aquí hay algunos ayudantes:
CONSEJO 1: Diferentes operaciones enteras simples tienen diferentes velocidades.
Por cálculos rápidos en programas de muestra mostró:
% ~ T
* ~ 4T
/ ~ 7T
Por lo tanto, desea utilizar la menor división posible a favor de la multiplicación o el módulo. Los operadores de sustracción, suma y comparación no se muestran porque los expulsan del agua. Además, usando & Quot; final & Quot; tanto como sea posible le permite a la JVM hacer ciertas optimizaciones. Acelerando & "; GetLength &"; función:
private static int getLength(final int b) {
int len = 0;
while (b > exponents[len]) {
len++;
}
return len + 1
}
Eso proporciona una mejora de 7x en la función. Obtiene una excepción indexOutOfBounds si b & Gt; su máximo en exponentes. Para resolver eso, puede tener:
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;
}
Eso es un poco más lento y le da una longitud incorrecta si b es demasiado grande, pero no arroja una excepción.
SUGERENCIA 2: la creación innecesaria de objetos / primitivas y las llamadas a métodos se agregan al tiempo de ejecución.
Supongo que " getLength " no se llama en ningún otro lugar, por lo que si bien sería bueno tener una función separada, desde el punto de vista de la optimización es una llamada a un método innecesario y la creación del objeto " len " ;. Podemos poner ese código justo donde lo usamos.
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;
}
Además, tenga en cuenta que cambié la parte inferior del bucle while para incluir también " a < = b " ;. No lo he probado y no estoy seguro de si la penalización por iteración supera el hecho de que no desperdicias ninguna iteración. Estoy seguro de que hay una manera de deshacerse de la división usando matemáticas inteligentes, pero no puedo pensar en eso en este momento.
Umm, probablemente estoy entendiendo totalmente mal la pregunta, pero .....
// Check if A is inside B lol
bool Contains (int a, int b)
{
return (a <= b);
}
A menos que desee saber si una secuencia particular de números está dentro de otra secuencia de números.
En ese caso, convertirlo en una cadena SERÁ más rápido que hacer los cálculos para resolverlo.
Esto de ninguna manera responde a su pregunta, pero es un consejo de todos modos :-)
El nombre del método findMatch no es muy descriptivo. En este caso, tendría un método estático ContainerBuilder.number(int), que devolvió un ContainerBuilder, que tiene el método contains. De esta manera su código se convierte en:
boolean b = number(12345).contains(234);
¡Algunos consejos a largo plazo!
Oh, sí, quería decir también que deberías definir lo que quieres decir con "contains"
¿Hay alguna forma de calcular esto en binario? Obviamente, el valor binario de un número entero que contiene el número entero binario de otro carácter no significa que el decical haga lo mismo. Sin embargo, ¿hay algún tipo de truco binario que pueda usarse? Tal vez convierta un número como 12345 a 0001 0010 0011 0100 0101, y luego realice algunos cambios de bits para determinar si 23 (0010 0011) está contenido allí. Debido a que su conjunto de caracteres tiene solo 10 caracteres, puede reducir el tiempo de cálculo almacenando valores de 2 caracteres en un solo byte.
EDITAR
Ampliando un poco esta idea. si tiene 2 enteros, A y B, y quiere saber si A contiene B, primero verifica 2 cosas. si A es menor que B, entonces A no puede contener B. Si A = B, entonces A contiene B. En este punto, puede convertirlos en cadenas *. Si A contiene el mismo número de caracteres que B, entonces A no contiene B, a menos que sean iguales, pero no estaríamos aquí si son iguales, por lo que si ambas cadenas tienen la misma longitud, a no contiene b . En este punto, la longitud de A será mayor que B. Por lo tanto, ahora puede convertir las cadenas a sus valores binarios empaquetados, como señalé en la primera parte de esta publicación. Almacene estos valores en una matriz de enteros. Ahora haces un AND Y de los valores enteros en tu matriz, y si el resultado es A, entonces A contiene B. Ahora cambias la matriz de enteros para B, a los 4 bits de la izquierda, y vuelves a hacer la comparación. Haga esto hasta que comience a hacer estallar bits a la izquierda de B.
* Eso * en el párrafo anterior significa que puede omitir este paso. Puede haber una manera de hacer esto sin usar cadenas. Puede haber algún truco binario elegante que pueda hacer para obtener la representación binaria empaquetada que discutí en el primer párrafo. Debería haber algún truco binario que pueda usar, o alguna matemática rápida que convierta un entero al valor decimal que discutí antes.
¿Puedo preguntar dónde está usando esta función en su código? Quizás haya otra forma de resolver el problema que está resolviendo actualmente, que sería mucho más rápido. Esto podría ser como cuando mi amigo me pidió que afinara completamente su guitarra, y lo hice antes de darme cuenta de que podría haber bajado la cuerda inferior en un paso completo y obtener un resultado equivalente.
