algorithm - pseint - ¿Cuál es el algoritmo más rápido para determinar si algún número en una matriz ordenada es múltiplo de `x`?
matriz caracol en java davicotico (6)
Dado un entero positivo x y una matriz entera positiva ordenada A
¿Hay algún algoritmo más rápido que O(N) para determinar si algún elemento en A es un múltiplo de x ? No hay elementos negativos en A
Unir ingenuamente A vez es mi única idea hasta ahora, no sé si hay alguna forma de aprovechar el hecho de que A está ordenada para acelerarlo.
Creo que la respuesta a la pregunta general es no. Supongamos que la siguiente estructura para A : el elemento i ''th de A ai está dada por i*x +1 por lo que no hay elementos en A , que son múltiplos de x. Sin embargo, nunca ahorra tiempo al usar cualquiera de los "trucos" descritos anteriormente ... básicamente tiene que tomar una decisión basada en su conocimiento de A y x . Básicamente, puede elegir entre O (N) y O (K), donde K es el número de múltiplos posibles de x en A , puede lograr O (K) utilizando el hashing, de manera que i*x in A convierte en un tiempo constante Operación (en promedio ...).
Dos cosas para probar: primero encuentre el primer elemento en la matriz mayor que x. No hay necesidad de buscar la mitad inferior. Una búsqueda binaria puede hacer esto. Eso reducirá el tiempo en algunos casos, pero si el primer elemento es mayor que x, entonces obviamente no hay necesidad. Luego, habiendo identificado la sección con posibles múltiplos de x, haga una búsqueda binaria si está ejecutando un solo hilo, o si puede ejecutar varios hilos, divida la mitad superior en segmentos, y haga que cada uno busque un hilo por separado. Creo que esta puede ser la forma más eficiente, pero sujeto a las siguientes advertencias.
Si el primer elemento mayor que x es bastante bajo en la matriz, pasará más tiempo configurando la búsqueda binaria que en el escaneo lineal.
Hay un costo para hacer búsquedas binarias también. Si la matriz no es muy grande, será menos eficiente con eso que las búsquedas lineales. No estoy hablando del orden del algoritmo. Estoy considerando solo el tiempo de ejecución.
Si puede hacer varios hilos, hay un costo bastante alto involucrado en la configuración de esos también. A menos que su matriz sea obscenamente larga, puede que no obtenga ningún beneficio al hacerlo también. Sin embargo, si tiene varios millones de elementos, puede beneficiarse al dividirlo en partes más pequeñas. Yo diría que sería raro que este escenario sea de utilidad.
El comentario de HT @ tobias_k.
Puede resolverlo en ~ O(n/x) (la actualización podría ser O(N*log(N)/X^2)) . Usted hace una búsqueda binaria para todos los múltiplos de x simultáneamente. Cuando subdivides cada espacio de búsqueda en cada iteración y cuando el espacio de búsqueda no puede contener un múltiplo de x, abortas esa rama. Entonces, en lugar de buscar binarios en cada valor, busca binarios todos los valores pero solo para aquellas ramas que aún contienen un múltiplo válido dentro de su rango. Lo mejor de esto es que evita totalmente la búsqueda del mismo espacio dos veces, lo que hace que el peor de los casos sea x = 1 u O(n/1) O(n) . En el mejor de los casos sabrá que el rango no puede contener un múltiplo y abortar en O (1).
Ya que tiene garantizado un caso peor de O (n) en el que básicamente pierde cada búsqueda de caché maldita (tenga en cuenta que en términos del mundo real esto podría terminar siendo más importante que la complejidad del tiempo, por lo tanto, pruebe esas cosas). Obtendría una complejidad de tiempo teórica que podría ser mejor que O (n) pero nunca peor que eso (guardar los saltos alrededor de una matriz perderá cachés porque así es como las computadoras realmente funcionan en el mundo real).
Como se predijo, el aumento de velocidad depende mucho del valor de k (x).
Esto comienza a ir más rápido que el bucle sin procesar en k = ~ 128. (factor de división)
Truncar las ramas logra que el mundo real supere el bucle en bruto. Supongo que la cuenta n no va a importar mucho, ya que parece escalar más o menos igual, pero tal vez directamente comprobando que es mejor.
Nota: por la naturaleza de este código omitirá los dobles, que es la diferencia en los conteos.
public class MultipleSearch {
public static void main(String[] args) {
Random random = new Random();
int[] array = new int[500000000];
for (int i = 0, m = array.length; i < m; i++) {
array[i] = Math.abs(random.nextInt());
}
Arrays.sort(array);
for (int k = 1; k < 16777216; k *= 2) {
long time;
time = System.currentTimeMillis();
binaryFactorLocator(array, k);
System.out.println("Factors found multi: " + (System.currentTimeMillis() - time) + " @" + k);
time = System.currentTimeMillis();
loopFactorLocator(array, k);
System.out.println("Factors found loop: " + (System.currentTimeMillis() - time) + " @" + k);
}
}
public static void loopFactorLocator(int[] array, int k) {
int count = 0;
for (int i = 0, m = array.length; i < m; i++) {
if (array[i] % k == 0) {
count++;
//System.out.println("loop: " + array[i] + " value at index " + i + " is a proven multiple of " + k);
}
}
System.out.println(count + " items found.");
}
public static void binaryFactorLocator(int[] array, int k) {
int count = binaryFactorLocator(0, array, k, 0, array.length);
System.out.println(count + " items found.");
}
public static int binaryFactorLocator(int count, int[] array, int k, int start, int end) {
if (start >= end) { //contains zero elements. (End is exclusive)
return count;
}
int startValue = array[start]; //first value
int endValue = array[end - 1]; //last value;
if (startValue / k == endValue / k) { //if both values are contained within the same factor loop.
if (startValue % k == 0) { //check lower value for being perfect factor.
//System.out.println("multi-binary: " + startValue + " value at index " + start + " is a proven multiple of " + k);
return count + 1;
}
return count; //There can be no other factors within this branch.
}
int midpoint = (start + end) / 2; //subdivide
count = binaryFactorLocator(count, array, k, start, midpoint); //recurse.
count = binaryFactorLocator(count, array, k, midpoint, end); //recurse.
return count;
}
}
Esta implementación debe ser bastante sólida, ya que trunca el bucle dentro de los elementos start / k == end / k, debe omitir el doble (a veces, puede dividirse entre dos valores duplicados). Obviamente, la recursividad como esta probablemente no será óptima y tal vez debería ser reescrita con una pila de pila de llamadas menos.
474682772 items found.
Factors found multi: 21368 @1
500000000 items found.
Factors found loop: 5653 @1
236879556 items found.
Factors found multi: 21573 @2
250000111 items found.
Factors found loop: 7782 @2
118113043 items found.
Factors found multi: 19785 @4
125000120 items found.
Factors found loop: 5445 @4
58890737 items found.
Factors found multi: 16539 @8
62500081 items found.
Factors found loop: 5277 @8
29399912 items found.
Factors found multi: 12812 @16
31250060 items found.
Factors found loop: 5117 @16
14695209 items found.
Factors found multi: 8799 @32
15625029 items found.
Factors found loop: 4935 @32
7347206 items found.
Factors found multi: 5886 @64
7812362 items found.
Factors found loop: 4815 @64
3673884 items found.
Factors found multi: 3441 @128
3906093 items found.
Factors found loop: 4479 @128
1836857 items found.
Factors found multi: 2100 @256
1953038 items found.
Factors found loop: 4592 @256
918444 items found.
Factors found multi: 1335 @512
976522 items found.
Factors found loop: 4361 @512
459141 items found.
Factors found multi: 959 @1024
488190 items found.
Factors found loop: 4447 @1024
229495 items found.
Factors found multi: 531 @2048
243961 items found.
Factors found loop: 4114 @2048
114715 items found.
Factors found multi: 295 @4096
121964 items found.
Factors found loop: 3894 @4096
57341 items found.
Factors found multi: 195 @8192
61023 items found.
Factors found loop: 4061 @8192
28554 items found.
Factors found multi: 106 @16384
30380 items found.
Factors found loop: 3757 @16384
14282 items found.
Factors found multi: 65 @32768
15207 items found.
Factors found loop: 3597 @32768
7131 items found.
Factors found multi: 35 @65536
7575 items found.
Factors found loop: 3288 @65536
3678 items found.
Factors found multi: 17 @131072
3883 items found.
Factors found loop: 3281 @131072
1796 items found.
Factors found multi: 13 @262144
1900 items found.
Factors found loop: 3243 @262144
873 items found.
Factors found multi: 6 @524288
921 items found.
Factors found loop: 2970 @524288
430 items found.
Factors found multi: 3 @1048576
456 items found.
Factors found loop: 2871 @1048576
227 items found.
Factors found multi: 2 @2097152
238 items found.
Factors found loop: 2748 @2097152
114 items found.
Factors found multi: 1 @4194304
120 items found.
Factors found loop: 2598 @4194304
48 items found.
Factors found multi: 0 @8388608
51 items found.
Factors found loop: 2368 @8388608
En un intento anterior, intenté una búsqueda dicotómica simple pero, como se señaló, eso no lleva a ninguna parte.
Aquí está mi mejor intento. Dudo que valga la pena la molestia, e incluso podría ser más lento para los casos del mundo real, pero aquí va.
Si tiene una matriz A [0..n] de enteros positivos ordenados y desea verificar si hay un múltiplo de un entero positivo X en A [i..j], donde 0≤i
If i>j then A[i..j] ist empty and thus contains no multiple of X
Else if A[i] % X = 0 or A[j] % X = 0 then A[i..j] contains a multiple of X
Else if A[i] / X = A[j] / X then A[i..j] contains no multiple of X
Else A[i..j] contains a multiple of X iff A[i+1..(i+j)/2] or A[(i+j)/2+1..j-1] contains a multiple of X
Mi conjetura es que la complejidad sería O (n / X) ish, por lo tanto, no es realmente una mejora en el gran esquema de las cosas.
Editado para agregar: Si sus datos son realmente peculiares, esto podría ayudar. En muchos casos, podría realmente doler:
- existe la sobrecarga de administrar la pila de retorno (la primera llamada recursiva no es terminal)
- porque saltamos hacia adelante y hacia atrás a través de los datos en lugar de atravesarlos, destrozamos la localidad de caché
- Hacemos la predicción de rama más difícil para el procesador.
Esto parece depender mucho del tamaño de x y del número de elementos dentro de A , y particularmente del número de múltiplos candidatos de x dentro de A
La búsqueda binaria de un número específico dentro de A lleva tiempo O (log (n)) (siendo n el número de elementos dentro de A ), por lo que si hay k posibles múltiplos de x entre el primer y el último elemento de A , tomará O(k * log(N)) para comprobarlos todos. Si ese número es más pequeño que n , puede usar este algoritmo, de lo contrario, simplemente haga una búsqueda lineal.
(Además, es probable que haya algunas pequeñas optimizaciones para el algoritmo anterior. Por ejemplo, una vez que marcó x*i (y no lo encontró), puede usar la posición donde x*i debería haber sido como el límite inferior al buscar x*(i+1) lugar del primer elemento de la matriz.)
Resta x de A iterativamente. Detente si cualquier resultado es igual a 0.
Con respecto a las restas, lo haces 1 + {max(A) DIV x} en el peor de los escenarios de esta manera, ya que debes restar x del elemento máximo de A después de que todos los demás hayan fallado la comprobación, y una vez más (de ahí el 1) al elemento máximo en sí, que también falla la comprobación, como 7 DIV 3 = 2, por lo que en tres iteraciones:
- 7 - 3 = 4
- 4 - 3 = 1
- 1 - 3 = -2,! = 0 por lo tanto no es divisible
Esto todavía califica como O(n) , pero termina siendo rápido, haciendo una resta de enteros en una matriz.