Existe-t-il un endroit où je peux obtenir une analyse/comparaison de style Big-O de structures de données traditionnelles telles que des listes chaînées, des arbres, des hachages, etc. comme les arbres de Judy et d'autres?Structures et algorithmes de données Big-O et Cache-cache
Lisez The Art of Computer Programming livres de Don Knuth. Ils sont considérés par beaucoup comme la meilleure source d'informations sur les algorithmes.
BigO est sur la complexité d'algorhitms faisant une certaine tâche. Il existe différentes tâches disponibles sur chaque structure de données. Les plus importants sont: Trier, Rechercher (dans une structure triée) et ajouter un élément.
Alors qu'est-ce que vous cherchez est la complexité de certaines tâches pour certaines structure de données.
Pour la plupart des types de données optimal de tri algorhitm est O (n log (n)), mais gardez à l'esprit que certaines structures sont encore plus lents, par exemple le tri liste chaînée est plus lent que les tableaux athough ont tous deux n log (n) complexité
en fait,
je regarderais here pour l'analyse des arbres Judy.
Comme cela est illustré dans ces données, plus petite taille de Judy ne donne pas un avantage de vitesse énorme sur une « taille commerciale pour la vitesse » traditionnelle structure de données. Judy a reçu heures-homme innombrables en développement et débogage 20 000 lignes de code; I passé une heure ou trois à écrire un table de hachage de 200 lignes assez standard.
Si vos données sont strictement séquentielles; vous devriez utiliser un tableau régulier. Si vos données sont souvent séquentielles, ou environ séquentielle (par exemple, un séquence arithmétique stepping par 64), Judy pourrait être la meilleure structure de données à utiliser. Si vous avez besoin de garder un espace à un minimum - vous avez un grand nombre de tableaux associatifs , ou vous êtes seulement de stockage de très petites valeurs, Judy est probablement une bonne idée. Si vous avez besoin d'un itérateur trié , allez avec Judy. Sinon, une table de hachage peut être tout aussi efficace, peut-être plus rapide et beaucoup plus simple.
Avez-vous cherché dans: "Introduction aux algorithmes"
Merci, mais je pensais à quelque chose d'un peu plus compact ;-) –
Ouais ... c'était un peu langue dans la joue de moi ... – Oded
Muvan Me'alyv - Je ne sais pas si SO affichera l'hébreu ... בא נראה –