Buscar existencia de número en una lista ordenada en tiempo constante? (Pregunta de la entrevista)

Question

que estoy estudiando para próximas entrevistas y he encontrado esta pregunta varias veces (por escrito textualmente)

Encuentra o determinar la no existencia de un número en una lista ordenada de números N, donde se extienden sobre los números M, M >> N y N lo suficientemente grandes como para abarcar múltiples discos. Algoritmo para vencer a O (log n); puntos de bonificación por algoritmo de tiempo constante.

Antes que nada, no estoy seguro si esta es una pregunta con una solución real. Mis colegas y yo hemos reflexionado sobre este problema durante semanas y parece estar mal formado (por supuesto, el hecho de que no podamos pensar en una solución no significa que no haya ninguna). Algunas preguntas que le habría hecho al entrevistador son:

• ¿Hay repeticiones en la lista ordenada?
• ¿Cuál es la relación con la cantidad de discos y N?

Un enfoque que consideré fue la búsqueda binaria en el mínimo/máximo de cada disco para determinar el disco que debería contener ese número, si existe, y luego la búsqueda binaria en el disco. Por supuesto, esto es solo una aceleración de orden de magnitud si la cantidad de discos es grande y también tiene una lista ordenada de discos. Creo que esto produciría algún tipo de tiempo O (log log n).

En cuanto a la sugerencia de M >> N, tal vez si sabe cuántos números hay en un disco y cuál es el rango, podría usar el principio de casillero para descartar algunos casos algunas veces, pero puedo ' t descifrar una mejora de orden de magnitud.

Además, "puntos de bonificación para el algoritmo de tiempo constante" me hace un poco sospechoso.

¿Alguna idea, solución o historial relevante de este problema?

Answer 1

Curiosamente, la pregunta es determinar la NO EXISTENCIA de un valor, no la existencia.

Esto puede implicar que hacen referencia a un filtro Bloom (http://en.wikipedia.org/wiki/Bloom_filter). Un filtro Bloom le puede decir si un elemento:

• no existe
• o posiblemente existe

Answer 2

Creo que se puede obtener algunas veces más rápido de búsqueda si usted se permite el uso de alguna meta -datos.

Configure una cantidad de bloques indirectos o listas cuyos elementos apuntan a bloques/listas más indirectos. Repita hasta llegar al nivel deseado de bloques directos/lista. La idea es usar algo similar a cómo algunos sistemas de archivos acceden a sus datos de archivo (bloques directos, indirectos, doblemente indirectos y triplemente indirectos). Es bastante probable que para los rangos de números que están solicitando necesite más de triple indirección.

Cada parte del número que está buscando puede referirse a un índice separado en las tablas indirectas/directas. Eventualmente, habrá roto la búsqueda lo suficiente como para que pueda leer la sección final que puede contener o no el número. Luego puede buscar esta sección final con un algoritmo de su elección.

Espero que esto ayude y tenga sentido.

Descargo de responsabilidad: Voy a almorzar en un minuto y por eso no he pensado completamente en esto, puede ser poco práctico.

Answer 3

Si solo usamos comparaciones, tenemos un límite inferior Omega (log N) (el peor de los casos) (es decir, O (1) no es posible).

Digamos que decides mirar alguna posición en la matriz, entonces tu adversario puede colocar el elemento en la parte de la matriz que es más grande.

Por lo tanto, en cada paso, tiene al menos la mitad de los elementos que quedan por considerar y, por lo tanto, Omega (logn) en el peor de los casos.

Por lo tanto, es probable que necesite alejarse de utilizar solo comparaciones para obtener mejores resultados que O (log N) en el peor de los casos.

Como se menciona en otras respuestas, podría hacer una búsqueda probabilística de tiempo constante que le proporcione la respuesta correcta con una probabilidad razonable, por ej. usando Bloom Filters.

Answer 4

Primer vistazo

M >> N no es un indicio Creo que, simplemente desalienta la creación de un mapa de bits que le diría directamente en O (1) tiempo si existe un número.

Creo que la suposición lógica con N que abarca múltiples discos duros es que puede esperar que no tenga orden de magnitutde más discos a su disposición. Como necesitaría 2 ^M espacio para el rendimiento O (1), y si N abarca múltiples discos, M abarca >> discos múltiples y 2 ^M abarca >> discos de los disponibles.

Además, se le dice que el enfoque para almacenar el falta números no sería eficiente desde entonces se tendría que almacenar números de X, donde

X = M - N => X ~ M (desde M> > N)

que es un caso peor.

De modo que a primera vista parece que puede probar que no se conoce una mejor respuesta.

EDIT: Todavía estoy en el razonamiento anterior, que también está mejor probado por la respuesta de Moron. Sin embargo, la conclusión, después de mirar el Filtro Bloom de la respuesta de Patrick, creo que el entrevistador podría haber estado mirando este y otros algoritmos probabilísticos (que deberían haber sido anotados en la pregunta de la entrevista).

Answer 5

Por la letra de la pregunta, es probable que estén buscando una búsqueda de interpolación, que es el caso promedio O (log log n). Sí, esto es O (n) en el peor de los casos, pero se puede mejorar con el conocimiento de la distribución o mediante una búsqueda bipolar de interpolación.

Esto se reproduce en la sugerencia M >> N. El análisis de casos promedio para la búsqueda de interpolación es bastante complejo, por lo que ni siquiera intentaré una modificación bajo M >> N. Pero conceptual, bajo M >> N y suponiendo una distribución uniforme, puede suponer que el valor estará delimitado por +/- 1 de la posición de búsqueda inicial, produciendo O (1).

Una implementación práctica podría hacer la interpolación inicial una vez, y si el valor de búsqueda no está limitado, retroceda a una búsqueda binaria.

No estoy seguro como discos múltiples podría ser utilizado con ventaja en este enfoque, aunque ...

Answer 6

Si todo lo que podemos hacer es comparar, a continuación, como se ha señalado por un cartel anterior, no podemos hacer nada mejor que O (log (NORTE)).

Pero, si sabemos un poco más sobre la distribución de entrada, podemos hacer más cosas. Si el entrevistador :) le dice que los números son contiguos, entonces es posible una solución O (1). La diferencia entre el primer elemento y el elemento que estamos buscando nos dará un lugar exacto en el que esperar encontrar el número.

Answer 7

Dado que la pregunta no indica en qué formato están almacenados los números, puede decirle al entrevistador que va a suponer que los números se almacenan de forma física. Por ejemplo, cada número puede escribirse en una tarjeta y cada tarjeta es propiedad de una persona.

N suficientemente grande como para abarcar varios discos

Ahora bien, si usted quiere encontrar o determinar la no existencia de un número que sólo podría hacer las personas si el número que está buscando está en el tarjeta que están sosteniendo.

Si nadie responde dentro de N segundos, entonces el número no está allí. Esto supone que todos puedan oírte y que cada persona sepa qué número tienen en su tarjeta.

no sé mucho acerca de la física (velocidad del sonido, la fricción del aire, el tiempo para cada cerebro personas a mirar su tarjeta, etc.)

Answer 8

Bueno, Según mi conocimiento. En este problema, puede aprovechar dos sugerencias. 1. Los números se ordenan y 2. N & M son muy grandes (N >> M) y M abarca varios discos

Puede utilizar un poco de aleatorización en este problema. En lugar de utilizar la búsqueda binaria, elija aleatoriamente un punto y luego verifique si x (número a buscar) es menor o mayor que el valor actual. Puede comenzar desde ambos extremos y reducir de forma iterativa el tamaño del espacio de búsqueda. En iteraciones muy pequeñas, solo puede reducirlo a un dominio pequeño y luego puede aplicar la búsqueda binaria para obtener eficiencia.

Answer 9

Probablemente sea una pregunta mal formulada.

Si los filtros Bloom son la respuesta que estaban buscando, lo cual es muy probable, no hay necesidad de confundir al candidato con un elemento potencial de algoritmo distribuido/paralelo (discos múltiples).

Suponiendo un disco

filtros Bloom son operaciones de tiempo constante una vez que el filtro está construido. Pero, para compensar los falsos positivos, uno tendrá que hacer una búsqueda binaria (o incluso una búsqueda de interpolación como alguien sugirió suponer una distribución uniforme) que contribuirá a un factor mayor que el registro constante (n) en el caso de búsqueda binaria.

por lo tanto, es O (k) + 1% * log (n). O (k) tiempo constante para verificar el filtro de floración. y luego suponiendo un porcentaje de error del 1% (falsos positivos) con filtro de floración, que muchas veces habrá que hacer una búsqueda binaria para asegurarse de que realmente existe.

No estoy seguro de que esto se pueda reducir a un tiempo constante con el análisis amortizado (no demasiado versado).

Answer 10

Dado que conocemos el rango de los números (M) podríamos realizar una búsqueda binaria interpolada. En lugar de dividir en dos el rango de búsqueda por 1/2 bisequelo por N/(HI - LO). El resultado seguirá siendo O (log N) pero con una constante menor. Esta técnica funciona mejor si sabemos que no hay duplicados en los datos, y la pregunta parece indicar que podría ser el caso, pero no es definitiva.

Véase, por ejemplo este blog: Faster than Binary Search

Answer 11

Es un hecho demostrable que cualquier algoritmo que hace compara posiblemente no puede vencer a log (n). Eso significa que una solución de tiempo constante no puede comparar números entre sí. Una solución de tiempo constante implicará engaño en todos los casos.

Teniendo en cuenta que, una solución constante de tiempo es posible con una serie de suposiciones:

• Los números se escriben secuencialmente
• Usted sabe exactamente en qué parte de la secuencia numérica comienza y dónde exactamente se termina (disco de compensación)
• Todos los discos son del mismo tamaño y tienen la misma capacidad exacta poco
• usted sabe exactamente cuántos bits se podría escribir en un disco

Dadas esas suposiciones, simplemente multiplique k veces el tamaño del bit del número. Busque en esa ubicación (O (1)) + desplazamiento y vuelva a leer la cantidad correcta de bits.

Answer 12

Un aspecto que aún no se ha mencionado es que la pregunta no es específica sobre qué tipo de computadora está usando. Es trivial hacerlo en tiempo constante si cada disco duro está conectado a su propia CPU.

Esto parece una salida de emergencia, pero si esta pregunta fue hecha por un entrevistador que hace computación distribuida, podría ser la respuesta que están buscando.

Answer 13

Sólo un pensamiento humilde.

Quizás esta sea más una pregunta de sistema que una cuestión de algoritmo, intentemos pensar desde el modo de motor de búsqueda.

Supongamos que tengo suficientes máquinas para tener todos los enteros N ordenados indexados, con cada máquina solo sosteniendo documentos de cantidad fija K que representan K de los N enteros.

De esta manera, para cualquier número X, el tiempo de red para que el servidor de consulta del cliente llegue a los nodos de búsqueda se puede tratar como tiempo constante; el tiempo para que un nodo de búsqueda busque un documento que representa el número X también es tiempo constante ya que el monto de documentos en cada nodo de búsqueda es un número fijo K.

Por lo tanto, el tiempo total es constante. Sin embargo, esto es más o menos similar a lo que Enrique mencionó.

Answer 14

La pregunta es sobre la no existencia, por lo que no es necesario buscar en los discos. Podemos verificar si el número X está fuera del rango mínimo y máximo de todos los discos en O (1). (número de discos son constantes)

bool not_exists=true 
for each disk_i in disks: 
    not_exists &&= (X <min_element(disk_i) || X > max_element(disk_i)) 
return not_exists 

si el resultado es verdadero. entonces podemos estar seguros de que no hay X en los discos. de lo contrario X 'podría estar' en los discos.

Answer 15

puede resolver esta cuestión mediante la comprobación del tamaño del archivo que contiene el número y luego crear un número cuyo tamaño es más grande que el tamaño del archivo (no hablar ABT int o lar

Answer 16

creo que el problema con claridad indica que está dado una lista de tamaño N, como

const int N = 15; 
int xs[N] = {1, 3, 7, 9, 13, 16, 17, 19, 21, 24, 25, 26, 27, 28, 30}; 

que tiene que responder una sola consulta (en menos de O(logN)) y por lo tanto realmente no se puede hacer ningún procesamiento previo. creo º La pregunta habría sido redactada de manera diferente en tal caso si pudieras ir por tiempos amortizados.

N en la práctica puede ser muy grande, por lo que incluso el número N puede necesitar muchos discos para almacenarse (la forma en que leo la pregunta:). Creo que esto solo denota que no se puede crear una matriz de búsqueda simple de tamaño M, porque M > N, por lo tanto, no tiene sentido.

Por lo tanto, realmente no se puede hacer mejor que la búsqueda binaria. Sin embargo, como conoce el valor máximo posible de los elementos, que es M (y suponiendo que los datos se distribuyen uniformemente), puede adivinar la posición inicial, donde comenzar la búsqueda binaria.

Esto es esencialmente x/M * N, en el código podría ser algo así:

double hint = static_cast<double>(x)/M; // between [0,1) 
int m = static_cast<int>(hint * N); // guess the position in xs 
// do binary search using m as initial "middle" point. 

Por lo tanto, este guessinng, dada la suposición de retención, se acelerará el algoritmo por una constante agradable. Sin embargo, la complejidad del tiempo seguirá siendo O(lgN).