¿Por qué utilizar binarios buscar si hay ternaria búsqueda?

https://stackoverflow.com/questions/3498382

29-09-2019
|

Pregunta

Recientemente he oído hablar ternaria búsqueda en la que se divide una matriz en 3 partes y comparar. Aquí habrá dos comparaciones pero reduce la matriz de n / 3. ¿Por qué la gente no usan tanto?

Solución

En realidad, la gente hace uso de árboles k-aria para k arbitraria.

Este es, sin embargo, una solución de compromiso.

Para encontrar un elemento en un árbol k-ario, necesita alrededor de k * ln (N) / ln (k) operaciones (recuerda la fórmula de cambio de base). Cuanto mayor sea k es, las operaciones más generales que necesita.

La extensión lógica de lo que está diciendo es "¿por qué la gente no utilizan un árbol de N-aria de elementos de datos N?". Lo cual, por supuesto, sería una matriz.

Otros consejos

A ternaria de búsqueda aún le dará la misma complejidad asintótica O (log n) tiempo de búsqueda, y añade complejidad a la aplicación.

El mismo argumento se puede decir por qué usted no quiere una búsqueda quad o cualquier otra orden superior.

Búsqueda de 1 mil millones (mil millones de US - 1000000000) ordenados artículos tomarían un promedio de alrededor de 15 se compara con la búsqueda binaria y unos 9 compara con una búsqueda ternaria - no es una gran ventaja. Y tenga en cuenta que cada 'ternaria comparar' podría implicar 2 comparaciones reales.

Wow. El más votos respuestas se pierda el tren en este caso, creo.

Su CPU no es compatible con la lógica ternaria como una sola operación; se rompe la lógica ternaria en varias etapas de la lógica binaria. El código más óptimo para la CPU es lógica binaria. Si las patatas fritas eran comunes que apoyó la lógica ternaria como una sola operación, estaríamos en lo cierto.

B-Trees puede tener múltiples ramas en cada nodo; un árbol B fin-3 es ternario lógica. Cada paso en el árbol tendrá dos comparaciones en vez de uno, y esto probablemente hará que sea más lento en tiempo de CPU.

Los árboles B, sin embargo, son bastante comunes. Si se supone que cada nodo en el árbol será almacenado en algún lugar separado en el disco, que va a pasar la mayor parte de su tiempo a la lectura desde el disco ... y la CPU no va a ser un cuello de botella, pero el disco va a ser. Así que toma un árbol B con 100.000 niños por nodo, o cualquier otra cosa que la voluntad Apenas caben en un bloque de memoria. Los árboles B con ese tipo de factor de ramificación rara vez eran más de tres nodos de alto, y tan solo te tiene tres lecturas de disco - tres paradas en un cuello de botella -. Para buscar una enorme, enorme conjunto de datos

Revisión:

árboles ternarios no son compatibles con el hardware, de manera que corran menos rápidamente.
B-árboles con las órdenes mucho, mucho, mucho más alto que 3 son comunes para el disco-optimización de grandes conjuntos de datos; una vez que haya ido más allá de 2, subir más de 3.

La única manera de una búsqueda ternario puede ser más rápido que una búsqueda binaria es si una determinación partición de 3 vías se puede hacer por menos de aproximadamente 1,55 veces el costo de una comparación de 2 vías. Si los artículos se almacenan en una matriz ordenada, la determinación de 3 vías será en promedio ser 1,66 veces más caro que una determinación de 2 vías. Si la información se almacena en un árbol, sin embargo, el costo para ir a buscar la información es alta en relación con el costo real de la comparación, y la localidad de caché significa que el costo de ir a buscar al azar un par de datos correspondiente no es mucho peor que el costo de ir a buscar un único datum, un árbol ternario o n-manera puede mejorar la eficiencia en gran medida.

¿Qué le hace pensar que la búsqueda ternario debe ser más rápido?

Número medio de comparaciones:

in ternary search = ((1/3)*1 + (2/3)*2) * ln(n)/ln(3) ~ 1.517*ln(n)
in binary search  =                   1 * ln(n)/ln(2) ~ 1.443*ln(n).

Lo peor número de comparaciones:

in ternary search = 2 * ln(n)/ln(3) ~ 1.820*ln(n)
in binary search  = 1 * ln(n)/ln(2) ~ 1.443*ln(n).

Así que parece que ternaria de búsqueda es peor.

Además, nota que esta secuencia se generaliza a búsqueda lineal Si continuamos

Binary search
Ternary search
...
...
n-ary search ≡ linear search

Por lo tanto, en una búsqueda n-aria, que tendrá "una única COMPARAR", que podría tomar hasta comparaciones reales n.

"Terinary" (ternario?) Búsqueda es más eficiente en el mejor de los casos, lo que implicaría la búsqueda del primer elemento (o tal vez la última, en función de la comparación que haces primero). Para los elementos más lejos del final está comprobando en primer lugar, mientras que dos comparaciones estrecharía la matriz por 2/3 cada vez, los mismos dos comparaciones con la búsqueda binaria sería reducir el espacio de búsqueda por 3/4.

A esto se añade, la búsqueda binaria es más simple. Que acaba de comparar y obtener un medio u otro, en lugar de comparar, si es inferior a obtener el primer tercio, de lo contrario comparar, si es menos de conseguir el segundo tercio, más tiene el último tercio.

ternario de búsqueda puede ser utilizado con eficacia en arquitecturas paralelas - FPGAs y ASICs. Por ejemplo, si la memoria FPGA interna necesaria para la búsqueda es menos de la mitad de los recursos FPGA, puede hacer que un bloque de memoria por duplicado. Esto permitiría a la vez dos direcciones de memoria de acceso diferentes y hacer todas las comparaciones en un solo ciclo de reloj. Esta es una de las razones por las cuales 100MHz FPGA a veces puede superar a la CPU de 4 GHz:)

Aquí está algunas pruebas experimentales al azar que me no han investigados en absoluto mostrando que es más lento que la búsqueda binaria.

Casi todos los libros y sitios web sobre árboles binarios de búsqueda realmente no hablar de los árboles binarios! Te muestran ternarios árboles de búsqueda! árboles binarios verdaderos almacenar datos en sus hojas no nodos internos (excepto para las teclas para navegar). Algunos llaman a estos árboles de hoja y hacer la distinción entre los árboles de nodos que se muestran en los libros de texto:

J. Nievergelt, C.-K. Wong: Alta límites para la longitud de ruta total de árboles binarios, Diario ACM 20 (1973) 1-6.

La siguiente acerca de esta es de libro de Peter cobre amarillo en las estructuras de datos.

2.1 Dos modelos de árboles de búsqueda

En el esquema que acabamos de dar, que supressed un punto importante que a primera vista parece trivial, pero de hecho se lleva a dos modelos diferentes de árboles de búsqueda, ya sea de que se pueden combinar con la mayor parte de los siguientes materiales, pero uno de los cuales es fuertemente preferible.

Si comparamos en cada nodo de la clave de consulta con la clave contenida en el nodo y seguir la rama izquierda si la clave de consulta es más pequeña y la rama derecha si la clave de consulta es más grande, entonces lo que sucede si son iguales? Los dos modelos de los árboles de búsqueda son los siguientes:

Tome rama izquierda si clave de consulta es más pequeño que el nodo clave; de lo contrario tomar la rama de la derecha, hasta llegar a una hoja del árbol. Las claves en el nodo interior del árbol son sólo para comparación; todos los objetos están en las hojas.
Tome rama izquierda si clave de consulta es más pequeño que el nodo clave; tomar la rama derecha si la clave de consulta es más grande que la clave de nodo; y tomar el objeto contenido en el nodo de si son iguales.

Este punto menor tiene una serie de consecuencias:

{En el modelo 1, el árbol subyacente es un árbol binario, mientras que en el modelo 2, cada nodo del árbol es realmente un nodo ternario con un vecino media especial.

{En el modelo 1, cada nodo interior tiene una izquierda y un subárbol derecho (cada uno, posiblemente, una hoja nodo del árbol), mientras que en el modelo 2, tenemos que permitir incompleta linfáticos, donde la izquierda o subárbol derecho podría hacer falta, y sólo el objeto de comparación y la clave están garantizados de existir.

Así que la estructura de un árbol de búsqueda del modelo 1 es más regular que la de un árbol de modelo 2; esto es, al menos para la puesta en práctica, una clara ventaja.

{En el modelo 1, atravesando un nodo interior requiere sólo una comparación, mientras que en el modelo 2, necesitamos dos comparaciones para comprobar los tres posibilidades.

De hecho, árboles de la misma altura en los modelos 1 y 2 contienen a lo sumo aproximadamente el mismo número de objetos, pero uno necesita el doble de comparaciones en el modelo 2 para llegar a los objetos más profundas del árbol. Por supuesto, en el modelo 2, también hay algunos de los objetos que se alcanzan mucho antes; el objeto en la raíz se encuentra con sólo dos comparaciones, pero casi todos los objetos están en o cerca de la más profunda nivel.

Teorema. Un árbol de la altura h y el modelo 1 contiene como máximo 2 ^ h objetos. Un árbol de la altura h y el modelo 2 contiene como máximo 2 ^ h + 1 -. 1 objetos

Esto se ve fácilmente debido a que el árbol de la altura h tiene como subárboles izquierdo y derecho de una árbol de la altura a la más h - 1 cada uno, y en el modelo 2 un objeto adicional entre ellos.

{En el modelo 1, llaves en nodos interiores servir sólo para comparaciones y puede reaparecer en las hojas para la identificación de los objetos. En el modelo 2, cada aparece la tecla una sola vez, junto con su objeto.

Es posible, incluso en el modelo 1 que hay claves utilizadas para la comparación que no pertenecen a ningún objeto, por ejemplo, si el objeto ha sido eliminado. Por conceptualmente la separación de estas funciones de comparación y de identificación, esta No es sorprendente, y en las estructuras posteriores que incluso podría necesitar definir artificial No ensayos correspondientes a cualquier objeto, sólo para obtener una buena división de la búsqueda espacio. Todas las claves utilizadas para la comparación son necesariamente distintos porque en un modelo 1 árbol, cada nodo interior tiene izquierdo no vacío y sub-estructuras adecuadas. Así que cada tecla se produce a más dos veces, una como la comparación key y una vez como clave de identificación en la hoja.

Modelo 2 se convirtió en el libro de texto de la versión preferida porque en la mayoría de libros de texto la distinción entre el objeto y su clave no se hace: la clave está en el objeto. Entonces se convierte en poco natural para duplicar la llave en la estructura de árbol. Pero en todas las aplicaciones reales, la distinción entre la llave y el objeto es bastante importante. Uno casi nunca se desea hacer un seguimiento de sólo un conjunto de números; los números están normalmente asociados con alguna información adicional, que es a menudo mucho más grande que la propia llave.

Usted puede haber oído ternaria buscar ser utilizado en esos acertijos que implican sopesar las cosas en una balanza. Esas escalas se vuelven 3 respuestas: izquierda es más ligero, ambos son el mismo o izquierda es más pesado. Así, en una búsqueda ternario, sólo se necesita 1 comparación. Sin embargo, los equipos utilizan la lógica booleana, que sólo tiene 2 respuestas. Para hacer la búsqueda ternario, usted realmente tiene que hacer comparaciones 2 en vez de 1. Creo que hay algunos casos en que esto sea aún más rápido como carteles se mencionó anteriormente, pero se puede ver que ternaria de búsqueda no es siempre mejor, y es más confuso y menos natural para implementar en un ordenador.

Teóricamente el mínimo de k/ln(k) se logra a e y desde 3 está más cerca de e de 2 requiere menos comparaciones. Se puede comprobar que 3/ln(3) = 2.73.. y 2/ln(2) = 2.88.. La razón por la búsqueda binaria podría ser más rápido es que el código para ello tendrá menos ramas y se ejecutarán más rápido en las CPU moderna.

Yo sólo han publicado un un blog sobre la búsqueda ternario y yo han mostrado algunos resultados. También he proporcionado algunas implementaciones de nivel inicial en mi git repo estoy totalmente de acuerdo con cada uno sobre la parte de la teoría la búsqueda ternario pero ¿por qué no darle una oportunidad? De acuerdo con la aplicación que se parte es bastante fácil si tiene tres años de experiencia en la codificación. He descubierto que si usted tiene gran conjunto de datos y hay que buscarla en muchas ocasiones de búsqueda ternario tiene una ventaja. Si usted cree que puede hacerlo mejor con un ternaria de la búsqueda para él.

A pesar de que se obtiene el mismo gran complejidad-O (ln n) en ambos árboles de búsqueda, la diferencia está en las constantes. Que tiene que hacer más comparaciones de un árbol de búsqueda ternario en cada nivel. Así que la diferencia se reduce a k / ln (k) para un árbol de búsqueda k-aria. Esto tiene un valor mínimo en e = 2,7 y k = 2 proporciona el resultado óptimo.

Licenciado bajo: CC-BY-SA con atribución

No afiliado a StackOverflow