algorithm - flujo - busqueda binaria pseint

¿Por qué usar la búsqueda binaria si hay búsqueda ternaria? (15)

¡Casi todos los libros de texto y sitios web en árboles binarios de búsqueda realmente no hablan de árboles binarios! ¡Te muestran árboles de búsqueda ternarios! Los árboles binarios verdaderos almacenan datos en sus hojas, no en los nodos internos (a excepción de las teclas para navegar). Algunos llaman a estos árboles de hojas y hacen la distinción entre árboles de nodos que se muestran en los libros de texto:

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

Lo siguiente acerca de esto es del libro de Peter Brass sobre estructuras de datos.

2.1 Dos modelos de árboles de búsqueda

En el esquema que acabamos de exponer, suprimimos un punto importante que al principio parece trivial, pero de hecho lleva a dos modelos diferentes de árboles de búsqueda, cualquiera de los cuales se puede combinar con gran parte del material siguiente, pero uno de los cuales es muy preferible.

Si comparamos en cada nodo la clave de consulta con la clave contenida en el nodo y seguimos 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, ¿qué ocurre si son iguales? Los dos modelos de árboles de búsqueda son los siguientes:

Tome la rama izquierda si la clave de consulta es más pequeña que la clave de nodo; de lo contrario, toma la rama derecha, hasta que alcances una hoja del árbol. Las claves en el nodo interior del árbol son solo para comparar; todos los objetos están en las hojas.
Tome la rama izquierda si la clave de consulta es más pequeña que la clave de nodo; tomar la rama derecha si la clave de consulta es más grande que la clave del nodo; y toma el objeto contenido en el nodo 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 árbol es realmente un nodo ternario con un vecino medio especial.

{En el modelo 1, cada nodo interior tiene un subárbol izquierdo y uno derecho (cada uno posiblemente un nodo hoja del árbol), mientras que en el modelo 2, tenemos que permitir los nodos incompletos, donde puede faltar el subárbol izquierdo o derecho, y solo el objeto de comparación y la clave están garantizados para existir.

Entonces, la estructura de un árbol de búsqueda del modelo 1 es más regular que la de un árbol del modelo 2; esto es, al menos para la implementación, una clara ventaja.

{En el modelo 1, atravesar un nodo interior solo requiere una comparación, mientras que en el modelo 2, necesitamos dos comparaciones para verificar las tres posibilidades.

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

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

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

{En el modelo 1, las claves en los nodos interiores sirven solo para comparaciones y pueden reaparecer en las hojas para la identificación de los objetos. En el modelo 2, cada tecla aparece solo una vez, junto con su objeto.

Incluso es posible en el modelo 1 que haya claves usadas para la comparación que no pertenecen a ningún objeto, por ejemplo, si el objeto ha sido eliminado. Al separar conceptualmente estas funciones de comparación e identificación, esto no es sorprendente, y en las estructuras posteriores incluso podríamos necesitar definir pruebas artificiales que no correspondan a ningún objeto, solo para obtener una buena división del espacio de búsqueda. Todas las claves utilizadas para la comparación son necesariamente distintas porque en un árbol modelo 1, cada nodo interior tiene subárboles no vacíos izquierdo y derecho. De modo que cada tecla aparece como máximo dos veces, una como clave de comparación y una como clave de identificación en la hoja.

El modelo 2 se convirtió en la versión preferida del libro de texto porque en la mayoría de los libros de texto no se hace la distinción entre el objeto y su clave: la clave es el objeto. Entonces se vuelve antinatural duplicar la clave en la estructura del árbol. Pero en todas las aplicaciones reales, la distinción entre clave y objeto es bastante importante. Uno casi nunca desea hacer un seguimiento de solo un conjunto de números; los números normalmente están asociados con más información, que a menudo es mucho más grande que la clave misma.

Hace poco escuché sobre la búsqueda ternaria en la que dividimos una matriz en 3 partes y la comparamos. Aquí habrá dos comparaciones pero reduce la matriz a n / 3. ¿Por qué la gente no usa tanto?

¿Qué te hace pensar que la búsqueda terciaria debería ser más rápida?

Promedio 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).

El 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).

Entonces parece que la búsqueda ternaria es peor.

Acabo de publicar un blog sobre la búsqueda ternaria y he mostrado algunos resultados. También proporcioné algunas implementaciones de nivel inicial en mi git repo. Estoy totalmente de acuerdo con todos sobre la parte teórica de la búsqueda ternaria, pero ¿por qué no intentarlo? Según la implementación, esa parte es bastante fácil si tiene tres años de experiencia en codificación. Descubrí que si tienes un enorme conjunto de datos y necesitas buscarlo muchas veces la búsqueda ternaria tiene una ventaja. Si crees que puedes mejorar con una búsqueda ternaria, ve por ello.

Además, tenga en cuenta que esta secuencia se generaliza a la búsqueda lineal si continuamos

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

Entonces, en una búsqueda n-aria, tendremos "un solo COMPARE" que podría tomar hasta comparaciones reales.

Aquí hay alguna evidencia experimental al azar que no he probado en absoluto mostrando que es más lenta que la búsqueda binaria.

Aunque obtiene la misma complejidad de gran O (ln n) en ambos árboles de búsqueda, la diferencia está en las constantes. Debe hacer más comparaciones para un árbol de búsqueda ternario en cada nivel. Entonces la diferencia se reduce a k / ln (k) para un árbol de búsqueda k-ary. Esto tiene un valor mínimo en e = 2.7 y k = 2 proporciona el resultado óptimo.

En realidad, las personas sí usan árboles k-ary para arbitraria k.

Esto es, sin embargo, una compensación.

Para encontrar un elemento en un árbol k-ary, necesita operaciones k * ln (N) / ln (k) (recuerde la fórmula de cambio de base). Cuanto más grande sea tu k, más operaciones generales necesitarás.

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

Es posible que haya escuchado la búsqueda ternaria que se utiliza en los enigmas que implican pesar cosas en escalas. Esas escalas pueden devolver 3 respuestas: izquierda es más clara, ambas son iguales, o izquierda es más pesada. Entonces en una búsqueda ternaria, solo toma 1 comparación. Sin embargo, las computadoras usan lógica booleana, que solo tiene 2 respuestas. Para hacer la búsqueda ternaria, en realidad tendrías que hacer 2 comparaciones en lugar de 1. Supongo que hay algunos casos en que esto es más rápido que los anteriores, pero puedes ver que la búsqueda ternaria no siempre es mejor, y es más confuso y menos natural de implementar en una computadora.

Guau. Las mejores respuestas votadas pierden el bote en este caso, creo.

Su CPU no es compatible con la lógica ternaria como una sola operación; rompe la lógica ternaria en varios pasos de lógica binaria. El código más óptimo para la CPU es la lógica binaria. Si los chips fueran comunes que admitieran la lógica ternaria como una sola operación, estarías en lo cierto.

B-Trees puede tener múltiples ramas en cada nodo; un árbol B de orden 3 es una lógica ternaria. Cada paso hacia abajo del árbol tomará dos comparaciones en lugar de una, y esto probablemente hará que sea más lento en tiempo de CPU.

B-Trees, sin embargo, son bastante comunes. Si supone que cada nodo del árbol se almacenará en algún lugar por separado en el disco, va a pasar la mayor parte del tiempo leyendo desde el disco ... y la CPU no será un cuello de botella, pero sí lo será el disco. Entonces tomas un B-tree con 100,000 hijos por nodo, o cualquier otra cosa que apenas cabe en un bloque de memoria. B-trees con ese tipo de factor de ramificación raramente tendría más de tres nodos de alto, y solo tendrías tres lecturas de disco, tres paradas en un cuello de botella, para buscar un enorme y enorme conjunto de datos.

Revisando:

Los árboles ternarios no son compatibles con el hardware, por lo que funcionan menos rápidamente.
B-tress con órdenes mucho, mucho, mucho más alto que 3 son comunes para la optimización de disco de grandes conjuntos de datos; una vez que haya pasado 2, vaya más alto que 3.

La única forma en que una búsqueda ternaria puede ser más rápida que una búsqueda binaria es si se puede hacer una determinación de partición de 3 vías por menos de aproximadamente 1.55 veces el costo de una comparación bidireccional. Si los artículos se almacenan en una matriz ordenada, la determinación tridireccional será, en promedio, 1,66 veces más costosa que una determinación bidireccional. Sin embargo, si la información se almacena en un árbol, el costo para obtener información es alto en comparación con el costo de comparar realmente, y la ubicación del caché significa que el costo de obtener aleatoriamente un par de datos relacionados no es mucho peor que el costo de buscar un solo datum, un árbol ternario o n-way puede mejorar la eficiencia en gran medida.

La búsqueda "terciaria" (¿terciaria?) Es más eficiente en el mejor de los casos, lo que implicaría buscar el primer elemento (o tal vez el último, según la comparación que haga primero). Para los elementos más lejanos al final, primero se está comprobando, mientras que dos comparaciones reducirían la matriz en 2/3 cada vez, las mismas dos comparaciones con la búsqueda binaria reducirían el espacio de búsqueda en 3/4.

Añadir a eso, la búsqueda binaria es más simple. Simplemente compare y obtenga una mitad o la otra, en lugar de comparar, si es menor que obtener el primer tercio, de lo contrario compare, si es menor que obtener el segundo tercio, sino obtenga el último tercio.

La búsqueda de artículos ordenados por mil millones (un billón de dólares de EE. UU. - 1,000,000,000) tomaría un promedio de aproximadamente 15 comparaciones con la búsqueda binaria y aproximadamente 9 comparaciones con una búsqueda ternaria, lo cual no es una gran ventaja. Y tenga en cuenta que cada "comparación ternaria" podría implicar 2 comparaciones reales.

La búsqueda ternaria se puede usar efectivamente en arquitecturas paralelas: FPGA y ASIC. Por ejemplo, si la memoria FPGA interna requerida para la búsqueda es menos de la mitad del recurso FPGA, puede crear un bloque de memoria duplicado. Esto permitiría acceder simultáneamente a dos direcciones de memoria diferentes y hacer todas las comparaciones en un solo ciclo de reloj. Esta es una de las razones por las que 100MHz FPGA a veces puede superar a la CPU de 4GHz :)

Teóricamente, el mínimo de k/ln(k) se alcanza en ey dado que 3 está más cerca de e que de 2, requiere menos comparaciones. Puede verificar que 3/ln(3) = 2.73.. y 2/ln(2) = 2.88.. La razón por la cual la búsqueda binaria podría ser más rápida es que el código tendrá menos ramas y se ejecutará más rápido en las CPU modernas .

Una búsqueda ternaria aún le dará el mismo tiempo de búsqueda O (log N) de complejidad asintótica y agrega complejidad a la implementación.

Se puede decir el mismo argumento para explicar por qué no desea una búsqueda cuádruple u otra orden superior.