C # binaire Arbres et dictionnaires

StackOverflow https://stackoverflow.com/questions/2151747

Question

Je me bats avec le concept de quand utiliser les arbres binaires de recherche et quand utiliser des dictionnaires.

Dans ma demande, je l'ai fait une petite expérience qui a utilisé la bibliothèque C5 TreeDictionary (qui je crois est un arbre de recherche binaire rouge-noir), et le dictionnaire C #. Le dictionnaire a toujours été plus rapide à ajouter / trouver des opérations et aussi toujours utilisé moins d'espace mémoire. Par exemple, à 16809 entrées <int, float>, le dictionnaire utilisé 342 Kio alors que l'arbre utilisé 723 Kio.

Je pensais que ce BST étaient censés être plus efficace mémoire, mais il semble qu'un nœud de l'arbre nécessite plus d'octets d'une entrée dans un dictionnaire. Ce qui donne? Y at-il un point où est BST sont meilleurs que les dictionnaires?

En outre, comme une question de côté, personne ne sait s'il y a une plus rapide + structure plus efficace des données de mémoire pour stocker des paires de <int, float> pour un accès de type dictionnaire que l'une des structures mentionnées?

Était-ce utile?

La solution

  

Je pensais que BST censé être composé de   être plus efficace de la mémoire, mais il semble   qu'un nœud de l'arbre nécessite   plusieurs octets d'une entrée dans un   dictionnaire. Ce qui donne? y a t-il   point où BST sont de mieux que   dictionnaires?

J'ai personnellement jamais entendu parler d'un tel principe. Même encore, son seul principe général, et non un fait catégorique gravé dans le tissu de l'univers.

En général, Les dictionnaires sont vraiment juste un emballage de fantaisie autour d'un tableau de listes chaînées. Vous insérez dans le dictionnaire quelque chose comme: 

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));

son presque O (1) opération. Le dictionnaire utilise O (internalArray.Length + n) de mémoire, où n est le nombre d'éléments dans la collection.

En BSTS généraux peuvent être mis en œuvre comme:

  • -listes liées, qui utilisent l'espace O (n), où n est le nombre des éléments de la collection.
  • , qui utilisent O (2 h - n) l'espace où h est la hauteur de l'arbre et n est le nombre d'éléments de la collection.
    • Puisque les arbres rouge-noir ont une hauteur limitée de O (1,44 * n), une mise en œuvre du tableau doit avoir une utilisation de la mémoire limitée d'environ O (2 1.44n - n)

Les chances sont, la C5 TreeDictionary est mis en œuvre en utilisant des tableaux, ce qui est probablement responsable de l'espace perdu.

  

Qu'est-ce qui se passe? Y at-il un point où   BST sont de mieux que les dictionnaires?

Les dictionnaires ont des propriétés indésirables:

  • Il suffit de blocs continugous mémoire ne peut être de tenir votre dictionnaire, même si ses besoins en mémoire sont beaucoup moins que le total RAM disponible.

  • L'évaluation de la fonction de hachage peut prendre une longueur arbitrairement longue. Les chaînes, par exemple, utiliser réflecteur pour examiner la méthode System.String.GetHashCode - vous remarquerez hachant une chaîne prend toujours O (n), ce qui signifie qu'il peut prendre beaucoup de temps pour de très longues chaînes. Sur la main, la comparaison des chaînes de l'inégalité presque toujours plus vite que le hachage, car il peut exiger que regarder seulement les premiers caractères. Son tout à fait possible pour les inserts d'arbres plus rapide que les inserts dictionnaire si l'évaluation du code de hachage prend trop de temps.

    • méthode de GetHashCode de Int32 est littéralement juste return this, alors vous seriez hardpressed de trouver un cas où une table de hachage avec les touches int est plus lent qu'un dictionnaire arbre.

RB Les arbres ont des propriétés souhaitables:

  • Vous pouvez trouver / supprimer les éléments Min et Max O (log n), par rapport à O (n) en utilisant un dictionnaire.

  • Si un arbre est mis en œuvre comme liste chaînée plutôt qu'un tableau, l'arbre est habituellement plus d'espace efficace qu'un dictionnaire.

  • De même, son ridicule facile d'écrire des versions immuables d'arbres qui prennent en charge insert / recherche / supprimer dans O (log n). Les dictionnaires ne sont pas bien adaptées à immuabilité, puisque vous devez copier l'ensemble du tableau interne pour chaque opération (en fait, je Vous vu certaines implémentations sur les baies d'arbres doigts immuables, une sorte de but général dictionnaire de données structure, mais la mise en œuvre est très complexe).

  • Vous pouvez parcourir tous les éléments dans un arbre dans l'ordre de tri dans l'espace constant et le temps O (n), alors que vous auriez besoin de vider une table de hachage dans un tableau et le tri pour obtenir le même effet.

Ainsi, le choix de la structure de données dépend vraiment de ce que les propriétés dont vous avez besoin. Si vous voulez juste un sac et peut garantir non ordonné que votre fonction de hachage d'évaluer rapidement, aller avec un .Net dictionnaire. Si vous avez besoin d'un sac ordonné ou avoir une fonction de hachage de marche lente, aller avec TreeDictionary.

Autres conseils

Il est logique qu'un noeud d'arbre nécessiterait plus de stockage que une entrée de dictionnaire. Un nœud d'arbre binaire doit stocker la valeur et les deux sous-arbres gauche et à droite. Le Dictionary<TKey, TValue> générique est implémenté comme une table de hachage qui - je suppose - utilise soit une liste chaînée pour chaque godet (valeur plus un pointeur / référence) ou une sorte de remappage (juste la valeur). Je dois avoir un coup d'oeil dans le réflecteur pour être sûr, mais dans le but de cette question, je ne pense pas qu'il est important.

Le clairsemés la table de hachage, moins efficace en termes de stockage / mémoire. Si vous créez une table de hachage (dictionnaire) et initialisez sa capacité à 1 million et ne remplir que avec 10.000 éléments, alors je suis sûr que ce serait manger beaucoup plus de mémoire qu'un BST avec 10.000 nœuds.

Pourtant, je ne vous inquiétez de tout cela si la quantité de nœuds / clés est seulement dans les milliers. Cela va être mesuré dans les kilo-octets, par rapport à giga-octets de RAM physique.

Si la question est « pourquoi voudriez-vous d'utiliser un arbre binaire au lieu d'une table de hachage? » Ensuite, la meilleure réponse est l'OMI que les arbres binaires sont commandés alors que des tables de hachage ne sont pas. Vous ne pouvez rechercher une table de hachage pour les clés qui sont exactement égales à quelque chose; avec un arbre, vous pouvez rechercher une plage de valeurs, valeur la plus proche, etc. Cette distinction est très important si vous créez un index ou quelque chose de similaire.

Il me semble que vous faites une optimisation prématurée.

Ce que je vous propose est de créer une interface pour isoler la structure qui vous êtes réellement en utilisant, puis implémenter l'interface en utilisant le dictionnaire (qui semble fonctionner le mieux).

Si la mémoire / performance devient un problème (qui ne sera probablement pas pour 20k- numéros), vous pouvez créer d'autres implémentations d'interface, et vérifiez que l'on travaille meilleures performances. Vous aurez pas besoin de changer quoi que ce soit presque dans le reste du code (sauf que la mise en œuvre que vous utilisez).

L'interface pour un arbre et une table de hachage (que je devine est ce que votre dictionnaire est basé un) devrait être très similaire. tournant toujours autour de recherches à clé.

J'avais toujours pensé un dictionnaire valait mieux pour créer des choses une fois, puis ensuite faire beaucoup de recherches là-dessus. Alors qu'un arbre était mieux si vous le modifier de manière significative. Cependant, je ne sais pas où je pris cette idée à partir.

(Les langages fonctionnels utilisent souvent les arbres comme base pour qu'ils collections que vous pouvez réutiliser la plupart de l'arbre si vous faites de petites modifications à elle).

Vous n'êtes pas comparer « des pommes avec des pommes », un BST vous donnera un ordonné représentation alors qu'un dictionnaire vous permet de faire une recherche sur une paire de valeurs clés (dans votre cas).

Je ne s'attendre à taille beaucoup plus dans l'empreinte mémoire entre le 2, mais le dictionnaire vous donne une recherche beaucoup plus rapide. Pour trouver un élément dans un BST vous (potentiellement) besoin de traverser l'arbre entier. Mais pour faire une dictnary Lookup vous simplement lookup basée sur la clé.

Un BST équilibré est préférable si vous avez besoin pour protéger votre structure de données à partir des pics de latence et les collisions de hachage attaques.

La première se produit quand une structure soutenue matrice-pousse une obtient redimensionnée, ce dernier est une propriété inévitable de l'algorithme de hachage comme une projection de l'espace infini à une plage de nombre entier limité.

Un autre problème dans .NET est qu'il ya LOH, et avec un dictionnaire suffisamment grand vous exécutez dans une fragmentation de LOH. Dans ce cas, vous pouvez utiliser un BST, payer un prix de classe de complexité algorithmique plus grande.

En bref, avec un BST soutenu par le tas d'allocation que vous obtenez le pire des cas O (log (n)), avec Hashtable vous obtenez O (N) le pire temps de cas.

BST vient à un prix de O (log (N)) temps moyen, localité pire cache et plus allocations de tas, mais il a des garanties de temps d'attente et est protégée contre les attaques de dictionnaire et la fragmentation de la mémoire.

A noter que BST est un sujet à la fragmentation de la mémoire sur d'autres plates-formes, ne pas utiliser un éboueur compactage.

En ce qui concerne la taille de la mémoire, la classe .NET Dictionary`2 est plus efficace de la mémoire, car il stocke les données comme une liste chaînée hors tas, dont la valeur seulement stocke et informations offset. BST doit stocker en-tête d'objet (comme chaque nœud est une instance de classe sur le tas), deux pointeurs, et quelques données sur les arbres pour les arbres équilibrés augmentée. Par exemple, un arbre rouge-noir aurait besoin d'un booléen interprété comme la couleur (rouge ou noir). Ceci est au moins 6 mots de la machine, si je ne me trompe pas. Ainsi, chaque noeud dans un arbre rouge-noir sur un système 64 bits est au minimum de:

3 mots pour l'en-tête de 24 octets = 2 mots pour les pointeurs enfant = 16 octets 1 mot pour la couleur = 8 octets au moins 1 mot pour les octets de la valeur = 16 + 24 + 8 + 8 = 56 octets (+8 octets si l'arbre utilise un pointeur de nœud parent).

En même temps, la taille minimale de l'entrée du dictionnaire serait seulement 16 octets.

Licencié sous: CC-BY-SA avec attribution
Non affilié à StackOverflow
scroll top