C# Árboles binarios y diccionarios

Question

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

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

Pensé que se suponía que las BST debían ser más eficientes en cuanto a la memoria, pero parece que un nodo del árbol requiere más bytes que una entrada en un diccionario. ¿Lo que da? ¿Hay un momento en que las BST son mejores que los diccionarios?

Además, como una pregunta complementaria, ¿alguien sabe si existe una estructura de datos más rápida + más eficiente en cuanto a la memoria para almacenar <int, float> pares de acceso de tipo diccionario que cualquiera de las estructuras mencionadas?

Answer 1

pensé que BST de se suponía que 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 donde BST es mejor que diccionarios?

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

En general, los diccionarios son en realidad un envoltorio elegante sobre una variedad 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)); 

Así que es casi O (1) operación. El diccionario usa memoria O (internalArray.Length + n), donde n es el número de elementos en la colección.

En BSTs generales se puede implementar como:

• -listas enlazadas, que utilizan O espacio (n), donde n es el número de artículos en la colección.
• arrays, que usan O (2 ^h - n) espacio donde h es la altura del árbol yn es el número de elementos en 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 que el TreeDictionary C5 se implementa mediante matrices, que es probablemente responsable del espacio desperdiciado.

¿Qué ofrece? ¿Hay algún punto en el que BST sean 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.

• Evaluar la función hash puede tomar un tiempo arbitrariamente largo. Las cadenas, por ejemplo, usan Reflector para examinar el método System.String.GetHashCode - notará que el hashing de una cadena siempre toma O (n) tiempo, lo que significa que puede tomar un tiempo considerable para cadenas muy largas. Por otro lado, la comparación de cadenas de desigualdad casi siempre es más rápida que el hashing, ya que puede requerir mirar solo los primeros caracteres. Es totalmente posible que las inserciones de árbol sean más rápidas que las inserciones de diccionario si la evaluación del código hash toma demasiado tiempo. Método

  • de Int32 GetHashCode 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.

árboles RB tienen algunas propiedades deseables:

• Puede encontrar tiempo/eliminar los elementos mínimo y máximo en O (log n) el tiempo, en comparación con el O (n) utilizando una diccionario.

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

• Asimismo, es ridícula la facilidad de escribir versiones inmutables de árboles que admiten inserción/búsqueda/eliminación en el tiempo O (log n). Los diccionarios no se adaptan bien a la inmutabilidad, ya que necesita copiar toda la matriz interna para cada operación (de hecho, I tiene visto algunas implementaciones basadas en matrices de árboles de dedo inmutables, un tipo de estructura de datos de diccionario de propósito general, pero la implementación es muy complejo).

• Puede recorrer todos los elementos de un árbol en orden en espacio constante y O (n) tiempo, mientras que debe volcar una tabla hash en una matriz y ordenarla para obtener el mismo efecto.

Por lo tanto, la elección de la estructura de datos realmente depende de las propiedades que necesite. Si solo desea una bolsa desordenada y puede garantizar que su función de hash evalúe rápidamente, vaya con un .Net Dictionary. Si necesita una bolsa ordenada o tiene una función hash lenta, vaya con TreeDictionary.

Answer 2

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

Lo que sugeriría es crear una interfaz para aislar qué estructura está usando en realidad, y luego implementar la interfaz usando el Diccionario (que parece funcionar mejor).

Si la memoria/el rendimiento se convierte en un problema (que probablemente no será para 20k-números), entonces puede crear otras implementaciones de interfaz y comprobar cuál funciona mejor. No necesitará cambiar casi nada en el resto del código (excepto qué implementación está usando).

Answer 3

Tiene sentido que un nodo árbol requiera más almacenamiento que una entrada de diccionario. Un nodo de árbol binario necesita almacenar el valor y los subárboles izquierdo y derecho. El Dictionary<TKey, TValue> genérico se implementa como una tabla hash que, supongo, utiliza una lista vinculada para cada segmento (valor más un puntero/referencia) o algún tipo de reasignación (solo el valor). Tendría que echar un vistazo en Reflector para estar seguro, pero para el propósito de esta pregunta, no creo que sea tan importante.

Cuanto menor es la tabla hash, menos eficiente en términos de almacenamiento/memoria. Si creas una tabla hash (diccionario) e inicializas su capacidad a 1 millón, y solo la llenas con 10,000 elementos, entonces estoy bastante seguro de que se comería mucha más memoria que una BST con 10,000 nodos.

Aún así, no me preocuparía nada de esto si la cantidad de nodos/claves es solo de miles. Eso se medirá en kilobytes, en comparación con los gigabytes de RAM física.

---

Si la pregunta es "¿por qué quieres usar un árbol binario en lugar de una tabla hash?" Entonces, la mejor respuesta IMO es que los árboles binarios están ordenados, mientras que las tablas hash no lo son. Solo puede buscar en una tabla hash claves que sean exactamente iguales a algo; con un árbol, puede buscar un rango de valores, el valor más cercano, etc. Esta es una distinción bastante importante si está creando un índice o algo similar.

Answer 4

La interfaz para una tabla Tree y una tabla hash (que supongo que es sobre lo que se basa su Dictionary) debería ser muy similar. Siempre en torno a las búsquedas con clave.

Siempre pensé que un diccionario era mejor para crear cosas una vez y luego hacer muchas búsquedas en él. Mientras que un Árbol era mejor si lo estabas modificando significativamente. Sin embargo, no sé de dónde elegí esa idea.

(Los lenguajes funcionales a menudo usan árboles como base para las colecciones ya que puede reutilizar la mayor parte del árbol si realiza pequeñas modificaciones).

Answer 5

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

No esperaba mucho tamaño en la huella de memoria entre los 2, pero el diccionario le dará una búsqueda mucho más rápida. Para encontrar un ítem en una BST, (potencialmente) necesitas atravesar todo el árbol. Pero para hacer una búsqueda dictnaria simplemente busca según la clave.