C # árboles binarios y Diccionarios

Question

Estoy luchando con el concepto de cuándo usar árboles binarios de búsqueda y cuándo usar los diccionarios.

En mi solicitud que hice un pequeño experimento que utilizó la biblioteca TreeDictionary C5 (que creo que es un árbol binario de búsqueda de color rojo-negro), y el diccionario de C #. El diccionario fue siempre más rápido en las operaciones add / descubrimiento y también siempre se utiliza menos espacio de memoria. Por ejemplo, en el 16809 entradas <int, float>, el diccionario utiliza 342 KiB, mientras que el árbol utiliza 723 KiB.

pensé que la BST se supone que de ser más eficiente de la memoria, pero parece que un nodo del árbol requiere más bytes de una entrada en un diccionario. ¿Lo que da? ¿Hay un punto en donde de BST son mejores que los diccionarios?

Además, como una cuestión lado, ¿alguien sabe si hay una memoria + más eficiente estructura de datos más rápida para almacenar pares <int, float> para acceder tipo de diccionario que cualquiera de las estructuras mencionadas?

Answer 1

  

pensé que la BST se suponía que de   ser más eficiente de la memoria, pero parece   que un nodo del árbol requiere   más bytes de una entrada en una   diccionario. ¿Lo que da? Hay un   punto en donde de BST son mejores que las   diccionarios?

he personalmente nunca oído hablar de un tal principio. Aún así, es sólo un principio general, no es un hecho categórico grabado en el tejido del universo.

En general, los diccionarios son realmente sólo un envoltorio de lujo en torno a una serie de listas enlazadas. Se inserta en el diccionario algo como:

LinkedList<Tuple<TKey, TValue>> list =
    internalArray[internalArray % key.GetHashCode()];
if (list.Exists(x => x.Key == key))
    throw new Exception("Key already exists");
list.AddLast(Tuple.Create(key, value));

Por lo que su casi O (1) operación. Los usos de diccionario O (internalArray.Length + n) de la memoria, donde n es el número de elementos de la colección.

En BSTs generales se puede implementar como:

• enlaces listas, que el uso O (n) el espacio, donde n es el número de artículos en la colección.
• arrays , que el uso O (2 ^h - n) el espacio donde h es la altura del árbol y n es el número de elementos de la colección.
  • Desde árboles rojo-negro tienen una altura limitada de O (1,44 * n), una implementación matriz debe tener un uso de memoria limitada de aproximadamente O (2 ^1.44n - n)

Las probabilidades son, el C5 TreeDictionary se implementa utilizando matrices, que es probablemente responsable del espacio perdido.

  

¿Qué ocurre? ¿Hay un punto en donde   de BST son mejores que los diccionarios?

Diccionarios tienen algunas propiedades indeseables:

• puede que no haya suficientes bloques continugous de memoria para almacenar su diccionario, incluso si sus requisitos de memoria son mucho menos de lo que la RAM total disponible.

• La evaluación de la función hash puede tomar un tiempo arbitrariamente largo periodo de tiempo. Cuerdas, por ejemplo, el uso del reflector para examinar el método System.String.GetHashCode - se dará cuenta de hash de una cadena siempre toma tiempo O (n), lo que significa que puede llevar un tiempo considerable para las cadenas muy largas. En la mano, la comparación de cadenas para la desigualdad casi siempre más rápido que el hash, ya que puede requerir mirando sólo los primeros caracteres. Su totalmente posible para las inserciones de los árboles para ser más rápido que los insertos de diccionario si la evaluación código hash toma demasiado tiempo.

  • GetHashCode método de Int32 es literalmente sólo return this, por lo que tendría hardpressed para encontrar un caso en una tabla hash con claves int es más lento que un diccionario árbol.

RB árboles tienen algunas propiedades deseables:

• Puede encontrar / eliminar los elementos mínimos y máximos en O (log n), en comparación con el tiempo O (n) usando un diccionario.

• Si un árbol se implementa como lista enlazada en lugar de una matriz, el árbol es general más espacio eficiente que un diccionario.

• Asimismo, su ridícula fácil escribir versiones inmutables de árboles que borrar soporte del inserto / lookup / en O (log n) tiempo. Diccionarios no se adaptan bien a la inmutabilidad, ya que se necesita para copiar toda la matriz interna para cada operación (en realidad, Tienes visto algunas implementaciones basadas en matrices de árboles dedos inmutables, una especie de propósito general de datos de diccionario estructura, pero la implementación es muy complejo).

• Puede recorrer todos los elementos de un árbol en forma ordenada en el espacio y el tiempo constante O (n), mientras que había necesidad de volcar una tabla hash en una matriz y especie para conseguir el mismo efecto.

Por lo tanto, la elección de la estructura de datos realmente depende de las propiedades que necesita. Si lo que desea es una bolsa desordenada y puede garantizar que su función hash evaluar de forma rápida, ir con un diccionario .Net. Si necesita una bolsa ordenada o tener una función hash que ejecuta lentamente, ir con TreeDictionary.

Answer 2

Lo hace tiene sentido que un nodo de árbol requeriría más espacio de almacenamiento de una entrada de diccionario. Un nodo necesita árbol binario para almacenar el valor y tanto los subárboles izquierdo y derecho. El Dictionary<TKey, TValue> genérica se implementa como una tabla hash, que - estoy suponiendo - o bien utiliza una lista enlazada para cada segmento (valor más un puntero / referencia) o algún tipo de reasignación (sólo el valor). Tendría que echar un vistazo en el reflector para estar seguro, pero para el propósito de esta pregunta yo no creo que sea tan importante.

La más escasa la tabla hash, la menos eficiente en términos de almacenamiento / memoria. Si crea una tabla hash (diccionario) e inicializar su capacidad de 1 millón, y sólo lo llena de 10.000 elementos, entonces estoy bastante seguro de que iba a comer un montón más memoria que un BST con 10.000 nodos.

Sin embargo, yo no se preocupe por nada de esto si la cantidad de nodos / teclas es sólo en los miles. Eso va a ser medido en los kilobytes, en comparación con gigabytes de memoria RAM física.

---

Si la pregunta es "¿por qué se desea utilizar un árbol binario en lugar de una tabla hash?" A continuación, la mejor respuesta de la OMI es que los árboles binarios se ordenan mientras que las tablas hash no lo son. Sólo se puede buscar en una tabla hash de las claves que son exactamente iguales a algo; con un árbol, se puede buscar un rango de valores, el valor más cercano, etc. Esta es una distinción muy importante si va a crear un índice o algo similar.

Answer 3

Me parece que está haciendo una optimización prematura.

Lo que me gustaría sugerir a usted es para crear una interfaz para aislar la estructura que en realidad estás usando, y luego implementar la interfaz utilizando el diccionario (que parece que funciona mejor).

Si la memoria / rendimiento se convierte en un problema (que probablemente no para 20K- números), entonces usted puede crear otras implementaciones de interfaz, y el cheque que se trabaja mejores. Usted no tendrá que cambiar casi cualquier cosa en el resto del código (excepto los que la aplicación que esté utilizando).

Answer 4

La interfaz de un árbol y una tabla hash (que yo supongo es lo que su diccionario se basa uno) debe ser muy similar. Siempre que gira en torno a las búsquedas con clave.

Yo siempre había pensado que un diccionario era mejor para la creación de las cosas una vez y luego a continuación, hacer un montón de búsquedas en él. Mientras que un árbol era mejor si estaba modificando de manera significativa. Sin embargo, no sé donde recogí esa idea a partir de.

(Los lenguajes funcionales a menudo usan árboles como base porque ellos colecciones como se puede reutilizar la mayor parte del árbol si haces pequeñas modificaciones a la misma).

Answer 5

No está comparando "manzanas con manzanas", un BST le dará una ordenada , mientras que la representación de un diccionario le permite hacer una búsqueda en un par de valores clave (en su caso).

No se puede esperar mucho de tamaño en la huella de la memoria entre el 2, pero el diccionario le dará un mucho más rápido de búsqueda. Para buscar un elemento en un BST que necesita (potencialmente) para recorrer todo el árbol. Pero para hacer una búsqueda dictnary simplemente de búsqueda basada en la clave.

Answer 6

A es equilibrada BST preferible si usted necesita para proteger su estructura de datos de los picos de latencia y de hash colisiones ataques.

El primero que sucede cuando una estructura de matriz con respaldo crece una consigue cambiar el tamaño, la última es una propiedad inevitable de algoritmo de hash como una proyección desde el espacio infinito a un rango entero limitado.

Otro problema en .NET es que hay LOH, y con un diccionario suficientemente grande se encuentra con una fragmentación LOH. En este caso se puede utilizar un BST, el pago de un precio de mayor clase de la complejidad algorítmica.

En resumen, con una BST respaldada por la asignación del montón se obtiene peor de los casos un tiempo O (log (n)), la tabla hash se obtiene O (N) peor caso el tiempo.

BST tiene un precio de O (log (n)) tiempo promedio, peor localidad caché y las asignaciones más del montón, pero no tiene garantías de latencia y está protegido de ataques de diccionario y la fragmentación de memoria.

Vale la pena destacar que la BST es también un objeto de la fragmentación de memoria en otras plataformas, no usando un recolector de basura de compactación.

En cuanto al tamaño de memoria, la clase de .NET Dictionary`2 es más eficiente de la memoria, ya que almacena datos como un lista enlazada off-montón, valor que únicamente almacena y información de desplazamiento. BST tiene que cabecera almacén de objetos (como cada nodo es una instancia de clase en el montón), dos punteros, y algunos datos aumentado a árbol para árboles de equilibrado. Por ejemplo, un árbol rojo-negro tendría un valor lógico interpretado como el color (rojo o negro). Esto es al menos 6 palabras de la máquina, si no me equivoco. Por lo tanto, cada nodo en un árbol rojo-negro en el sistema de 64 bits es un mínimo de:

3 palabras para la cabecera = 24 bytes 2 palabras para los punteros niño = 16 bytes 1 palabra para el color = 8 bytes al menos 1 palabra para el valor 8+ bytes = 24 + 16 + 8 + 8 = 56 bytes (+8 bytes si el árbol utiliza un puntero nodo padre).

Al mismo tiempo, el tamaño mínimo de la entrada del diccionario sería tan sólo 16 bytes.