tableau Judy pour les langues gérées

Question

tableau Judy est une structure de données rapide qui peut représenter un tableau clairsemé ou un ensemble de valeurs. Y at-il sa mise en œuvre pour les langues gérées comme C #? Merci

Answer 1

Il convient de noter que ces derniers sont souvent appelés arbres Judy ou Judy si vous Essaie googler pour eux.

Je recherche également une implémentation .Net mais rien trouvé. Il convient également de noter que:

La mise en œuvre est fortement conçu autour de l'utilisation du cache efficace, car ces détails de mise en œuvre peuvent dépendre fortement de la taille de certaines constructions utilisées dans les sous-structures. Un .Net geres mise en œuvre peut être quelque peu différente à cet égard.

Il y a des obstacles importants à ce que je peux voir (et il y a probablement plus que mon bref examen manqué)

• L'API a quelques aspects OO assez anti-(par exemple un pointeur NULL est considéré comme un arbre vide) si simpliste, déplacez le pointeur d'état à la LHS et de faire la conversion des méthodes d'instance de fonctions C ++ ne fonctionnerait pas.
• La mise en œuvre des sous structures I étudié l'utilisation alourdie de pointeurs. Je ne vois pas ces efficacement être traduits à des références dans les langues gérées.
• La mise en œuvre est une distillation de beaucoup d'idées très complexes qui dément la simplicité du api public.
• Le code de base est d'environ 20K lignes (la plus grande partie complexe), cela ne me paraît pas un port facile.

Vous pouvez prendre la bibliothèque et envelopper le code C en C ++ / CLI (probablement la simple détention interne un pointeur qui est le c api et ayant tous Trie les appels c pointent vers celui-ci). Cela fournirait une mise en œuvre simpliste, mais les bibliothèques liées à la mise en œuvre native peut être problématique (comme pourrait l'allocation de mémoire). Vous auriez besoin aussi probablement pour faire face à la conversion de chaînes .Net à l'ancien octet ordinaire * sur la transition aussi bien (ou tout simplement travailler avec des octets directement)

Answer 2

Judy ne vraiment cadre pas bien avec des langues gérées. Je ne pense pas que vous serez en mesure d'utiliser quelque chose comme SWIG et obtenir la première couche fait automatiquement.

J'ai écrit PyJudy et je fini par avoir à faire quelques modifications de l'API non triviales pour bien cadrer en Python. Par exemple, je l'ai écrit dans la documentation:

  

tableaux de JudyL mots machine carte à   mots machine. En pratique, les mots   stocker des entiers non signés ou des pointeurs.   PyJudy prend en charge les quatre applications comme   classes distinctes.

• pyjudy.JudyLIntInt - carte non signée clés entières à entier non signé valeurs
• pyjudy.JudyLIntObj - carte non signée clés entières de valeurs d'objets python
• pyjudy.JudyLObjInt - carte Python Les clés d'objet entier non signé à valeurs
• pyjudy.JudyLObjObj - carte Python clés d'objet à des valeurs d'objet Python

Je ne l'ai pas regardé le code pendant quelques années pour que mes souvenirs à ce sujet sont assez brumeux. Ce fut ma première bibliothèque d'extension de Python, et je me souviens que je piraté ensemble une sorte de système de modèle pour la génération de code. Aujourd'hui, je voudrais utiliser quelque chose comme genshi.

Je ne peux pas pointer vers des alternatives à Judy - qui est l'une des raisons pour laquelle je suis à la recherche Stackoverflow

.

Edit:. On m'a dit que mes numéros de synchronisation dans la documentation sont hors de ce que la documentation de Judy suggère que Judy est développé pour les lignes de cache 64 bits et mon PowerBook était seulement 32 bits

D'autres liens:

• Patricia tente ( http://www.csse.monash .edu.au / ~ lloyd / tildeAlgDS / Arbre / PATRICIA / )
• tente Double-Array ( http://linux.thai.net/~thep /datrie/datrie.html )
• HAT-Trie ( http://members.optusnet.com.au/~ askitisn / index.html )

Le dernier a des chiffres de comparaison pour différentes implémentations TRIE haute performance.

Answer 3

Cela se révèle plus compliqué que je pensais. PyJudy pourrait être en valeur un regard, comme serait Tie :: Judy . Il y a quelque chose sur Softpedia , et quelque chose Ruby-ish . Le problème est, aucun d'entre eux sont spécifiquement .NET.