¿Cómo buscar una gran matriz para un objeto?

Tuve una entrevista hoy, me preguntaron cómo buscar un número dentro de una matriz, dije binarysearch, él me preguntó qué tal una gran matriz que tiene miles de objetos (por ejemplo Stocks) buscando, por ejemplo, por el precio de las acciones , Dije binarysearch nuevamente, dijo que ordenar una matriz de miles tomaría mucho tiempo antes de aplicar binarysearch.¿Cómo buscar una gran matriz para un objeto?

¿Podrías por favor acompañarme y enseñarme cómo abordar este problema? gracias su ayuda es apreciada.

Fuente

2012-03-23 Majid Kamal

En general, para buscar un gran conjunto de cosas, uno utiliza algún tipo de tabla hash. –

[¿Qué es más rápido, búsqueda Hash o búsqueda binaria?] (Http://stackoverflow.com/questions/360040/which-is-faster-hash-lookup-or-binary-search) – Josh

@Josh - Pregunta engañosa. La búsqueda binaria es más rápida si todo está bien ordenado y nunca se modificará el conjunto para buscar. Pero esa no es la vida real. En la vida real, la tabla hash casi siempre gana. –

También hay otros algoritmos de clasificación más rápidos. Corto de Shell viene a la mente.

http://en.wikipedia.org/wiki/Shellsort

Fuente

2012-03-23 01:01:11 Iceman

Still NlogN el mejor de los casos. – Kevin

no estoy seguro de lo que tenía en mente.

Si solo desea encontrar la hora número uno, y no tiene garantías sobre si la matriz está ordenada, entonces no creo que pueda vencer la búsqueda lineal. En promedio, deberá buscar a la mitad de la matriz antes de encontrar el valor, es decir, el tiempo de ejecución esperado O (N); al ordenar, debe tocar cada valor al menos una vez y probablemente más que eso, es decir, el tiempo de ejecución esperado O (N log N).

Pero si necesita encontrar valores múltiples, entonces el tiempo dedicado a ordenarlo vale la pena rápidamente. Con una matriz ordenada, puede realizar búsquedas binarias en el tiempo O (log N), de modo que con seguridad en la tercera búsqueda estará adelante si invirtió el tiempo para ordenar.

Puede hacerlo aún mejor si se le permite construir diferentes estructuras de datos para ayudar con el problema. Podría construir algún tipo de índice, como una tabla hash; pero la estructura de datos del campeón para este tipo de problema probablemente sería algún tipo de estructura de árbol. Luego puede insertar nuevos valores en el árbol más rápido de lo que podría agregar nuevos valores y volver a ordenar la matriz, y la búsqueda todavía será O (log N) para encontrar cualquier valor. Hay diferentes tipos de árboles disponibles: árbol binario, árbol B, trie, etc.

Pero como dijo @Hot Licks, una tabla hash a menudo se usa para este tipo de cosas, y es bastante barato actualizar: solo añada un valor en la matriz principal y actualice la tabla hash para que apunte al nuevo valor. Y una tabla hash está muy cerca del tiempo O (1), que no se puede superar. (Una tabla hash es O (1) si no hay colisiones hash, asumiendo un buen algoritmo hash y una tabla hash suficientemente grande no habrá casi colisiones. Creo que se podría decir que una tabla hash es O (N) donde N es el número promedio de colisiones hash por "cubo". Si me equivoco al respecto espero ser corregido muy rápidamente; esto es StackOverflow!)

Fuente

2012-03-23 01:08:03 steveha

No entendí a qué se refería con una tercera búsqueda? cualquier exageración, por favor? –

Si tiene que buscar solo una vez, y luego termina, la búsqueda lineal es la más rápida. Si tiene que buscar dos veces, la búsqueda lineal puede ser más rápida que ordenar más búsqueda binaria; en promedio, la búsqueda lineal deberá atravesar aproximadamente la mitad de los valores, por lo que dos búsquedas lineales deberían, en promedio, pasar por todos los valores. Si tiene que buscar tres veces, ordenarlo una vez y luego usar la búsqueda binaria para las tres búsquedas debería ser el más rápido. Si tiene que buscar cuatro o más veces, es lo mismo que tres veces: clasifique primero y luego realice una búsqueda binaria. – steveha

Si tiene que buscar más de dos veces, probablemente sea mejor utilizar la tabla hash. –

Quicksort es bastante bueno también.

http://en.wikipedia.org/wiki/Quicksort

Fuente

2012-03-23 01:17:24

Pero sigue siendo el mejor caso de NlogN. – Kevin

creo que el entrevistador quiere analizar caso bajo diferentes sobre el estado inicial del array, lo algoritmo va a utilizar. Por causa, debe saber que puede compilar una tabla hash y luego O (1) puede encontrar el número, o cuando la matriz está ordenada (el tiempo dedicado a la clasificación puede estar relacionado), puede usar binarysearch o usar algunas otras estructuras de datos para termina el trabajo.

Fuente

2012-09-12 14:47:21 jianpx

, así que finalmente quiero decir que no hay una respuesta fija para esta pregunta. – jianpx

me pidieron un giro question.The similares fue a buscar en la ordenada y luego una serie sin clasificar .Estos fueron mis respuestas no aceptada toda

Para ordenados Me sugirió que podemos encontrar el centro y hacer una búsqueda lineal .La búsqueda binaria también funcionará aquí
Para sin clasificar, sugerí lineal nuevamente.
Luego sugerí Binary, que está un poco mal.
Se sugiere almacenar la matriz en un hashset y utilizar hash. (No se acepta desde alto espacio complexcity)
Sugerí Tree Set que es un árbol rojo negro bastante bueno para la búsqueda. (No aceptado desde alto espacio complexcity)
Copiar en Arraylist etch también se consideraron gastos generales.

Al final obtuve un voto negativo. Aunque podemos pensar que uno de los anteriores es la solución, pero seguramente hay algo especial en la búsqueda lineal que me falta.

Para tener en cuenta que la ordenación antes de buscar también es una sobrecarga, especialmente si está utilizando estructuras de datos adicionales en el medio.

Todos los comentarios fueron bienvenidos.

Fuente

2015-05-20 21:21:31 user666

¿Cómo buscar una gran matriz para un objeto?

Respuesta

Cuestiones relacionadas