studio - Árboles binarios y diccionarios de C#

dibujar arbol binario c#

Question

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

En mi aplicación hice un pequeño experimento que usaba 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 siempre usó menos espacio de memoria. Por ejemplo, en 16809 entradas <int, float> , el diccionario usó 342 KiB, mientras que el árbol usó 723 KiB.

Pensé que se suponía que los BST eran más eficientes en memoria, pero parece que un nodo del árbol requiere más bytes que una entrada en un diccionario. ¿Lo que da? ¿Hay algún punto en el que los BST sean mejores que los diccionarios?

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

Answer 1

Pensé que se suponía que los BST eran más eficientes en memoria, pero parece que un nodo del árbol requiere más bytes que una entrada en un diccionario. ¿Lo que da? ¿Hay algún punto en el que los BST sean mejores que los diccionarios?

Personalmente 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 realmente un envoltorio elegante alrededor de una serie de listas vinculadas. Usted 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 una operación O (1). El diccionario utiliza la memoria O (internalArray.Length + n), donde n es el número de elementos de la colección.

En general, las BST se pueden implementar como:

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

Las probabilidades son que el C5 TreeDictionary se implementa utilizando arreglos, que probablemente sean los responsables del espacio desperdiciado.

¿Lo que da? ¿Hay algún punto en el que los BST sean mejores que los diccionarios?

Los diccionarios tienen algunas propiedades indeseables:

• Puede que no haya suficientes bloques continuos de memoria para guardar su diccionario, incluso si sus requisitos de memoria son mucho menores que la memoria RAM total disponible.

• La evaluación de la función hash puede llevar 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 lleva tiempo O (n), lo que significa que puede llevar un tiempo considerable para cadenas muy largas. En la mano, comparar cadenas para la desigualdad casi siempre es más rápido que el hash, 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 demora demasiado.

  • El método GetHashCode de Int32 simplemente return this , por lo que le sería difícil encontrar un caso en el que una tabla hash con teclas int sea más lenta que un diccionario de árbol.

Los árboles RB tienen algunas propiedades deseables:

• Puede encontrar / eliminar los elementos Mín y Máx en tiempo O (log n), en comparación con el tiempo O (n) utilizando un diccionario.

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

• Del mismo modo, es ridículo, fácil de escribir, versiones inmutables de árboles que admiten inserción / búsqueda / eliminación en tiempo O (log n). Los diccionarios no se adaptan bien a la inmutabilidad, ya que necesita copiar la matriz interna completa para cada operación (en realidad, he visto algunas implementaciones basadas en matrices de árboles de dedos inmutables, una especie de estructura de datos de diccionario de propósito general, pero la implementación es muy complejo).

• Puede atravesar todos los elementos de un árbol en orden ordenado en espacio constante y tiempo O (n), mientras que tendría que volcar una tabla hash en una matriz y clasificarla para obtener el mismo efecto.

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

Answer 2

Es preferible una BST equilibrada si necesita proteger su estructura de datos de picos de latencia y ataques de colisiones de hash.

Lo primero sucede cuando una estructura respaldada por una matriz crece y se redimensiona, la última es una propiedad inevitable del algoritmo de hash como una proyección desde un espacio infinito a un rango entero limitado.

Otro problema en .NET es que hay LOH, y con un diccionario lo suficientemente grande como para ejecutar una fragmentación de LOH. En este caso, puede utilizar una BST, pagando un precio de clase de complejidad algorítmica mayor.

En resumen, con un BST respaldado por el montón de asignación, se obtiene el tiempo O (log (N)) en el peor de los casos, con hashtable se obtiene el tiempo O (N) en el peor caso.

BST tiene un precio de tiempo O (log (N)), peor ubicación de caché y más asignaciones de almacenamiento dinámico, pero tiene garantías de latencia y está protegido contra ataques de diccionario y fragmentación de memoria.

Cabe destacar que BST también está sujeto a la fragmentación de la memoria en otras plataformas, no utilizando un recolector de basura compacto.

En cuanto al tamaño de la memoria, la clase .NET Dictionary`2 es más eficiente en memoria, ya que almacena los datos como una lista vinculada fuera del montón, que solo almacena información de valores y de compensación. BST tiene que almacenar el encabezado del objeto (ya que cada nodo es una instancia de clase en el montón), dos punteros y algunos datos de árboles aumentados para árboles equilibrados. Por ejemplo, un árbol rojo-negro necesitaría un booleano interpretado como color (rojo o negro). Esto es al menos 6 palabras de máquina, si no me equivoco. Entonces, cada nodo en un árbol rojo-negro en un sistema de 64 bits es un mínimo de:

3 palabras para el encabezado = 24 bytes 2 palabras para los punteros secundarios = 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 de nodo padre).

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

Answer 3

La interfaz para una tabla Árbol y Hash (que supongo en qué se basa su Diccionario) debería ser muy similar. Siempre girando en torno a las búsquedas con clave.

Siempre había pensado 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 tomé esa idea.

(Los lenguajes funcionales a menudo usan los árboles como la base de sus colecciones, ya que puede reutilizar la mayor parte del árbol si hace pequeñas modificaciones).

Answer 4

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

Lo que le sugiero es que cree una interfaz para aislar qué estructura está utilizando realmente, y luego implemente la interfaz utilizando el Diccionario (que parece funcionar mejor).

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

Answer 5

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

No esperaría 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 elemento en una BST (potencialmente) debe atravesar todo el árbol. Pero para hacer una búsqueda dictada, simplemente busque en función de la clave.

Answer 6

Tiene sentido que un nodo de á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 Dictionary<TKey, TValue> se implementa como una tabla hash que, supongo, usa una lista enlazada para cada grupo (valor más un puntero / referencia) o algún tipo de reasignación (solo el valor). Tendría que echar un vistazo a Reflector para estar seguro, pero para el propósito de esta pregunta no creo que sea tan importante.

Cuanto más dispersa es la tabla hash, menos eficiente es en términos de almacenamiento / memoria. Si crea una tabla hash (diccionario) e inicializa su capacidad a 1 millón, y solo la llena con 10,000 elementos, entonces estoy bastante seguro de que consumirá mucha más memoria que un BST con 10,000 nodos.

Sin embargo, 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é querría usar un árbol binario en lugar de una tabla hash?" Entonces, la mejor respuesta es que los árboles binarios están ordenados, mientras que las tablas hash no lo están. Solo puedes buscar en una tabla hash las claves que son exactamente iguales a algo; con un árbol, puede buscar un rango de valores, el valor más cercano, etc. Esta es una distinción muy importante si está creando un índice o algo similar.