array di Judy per le lingue gestite

Question

Judy matrice è struttura dati veloce che può rappresentare un array sparso o un insieme di valori. C'è la sua attuazione per le lingue gestite come C #? Grazie

Answer 1

Vale la pena notare che questi sono spesso chiamati Judy alberi o Judy tentativi se siete googling per loro.

Ho anche guardato per un'implementazione .Net ma non trovò nulla. Vale anche la pena notare che:

L'attuazione è fortemente progettato intorno utilizzo della cache efficiente, in quanto tali specifiche di attuazione possono essere fortemente dipendente dalla dimensione di alcuni costrutti utilizzati all'interno delle strutture secondarie. Un .NET gestito implementazione può essere un po 'diversa in questo senso.

Ci sono alcuni ostacoli significativi ad esso che posso vedere (e ci sono probabilmente più che la mia scansione breve perse)

• L'API ha alcuni aspetti piuttosto anti-OO (per esempio un puntatore nullo è visto come un albero vuoto) in modo semplicistico, spostare il puntatore stato al LHS e fare la conversione metodi funzioni istanza di C ++ non funzionerebbe.
• La realizzazione delle strutture sub ho guardato fatta pesante uso di puntatori. Non riesco a vedere questi efficacemente essere tradotto per i riferimenti in lingue gestite.
• L'implementazione è un distillato di un sacco di idee molto complessi che smentisce la semplicità della API pubblica.
• Il codice di base è di circa 20K righe (la maggior parte di esso complessi), questo non mi sembra una porta semplice.

Si potrebbe prendere la biblioteca e avvolgere il codice C in C ++ / CLI (probabilmente semplicemente tenendo internamente un puntatore che è il trie API C e avere tutte le chiamate C Punto a questo). Ciò fornisce un'implementazione semplicistico, ma le librerie collegate per l'implementazione nativa può essere problematico (come allocazione della memoria potrebbe). Si sarebbe anche probabilmente bisogno di trattare con la conversione di stringhe .Net di pianura vecchio byte * sulla transizione così (o semplicemente lavorare con i byte direttamente)

Answer 2

Judy in realtà non si adatta bene con le lingue gestite. Non credo che sarete in grado di usare qualcosa come SWIG e ottenere il primo strato fatto automaticamente.

ho scritto PyJudy e ho finito per dover apportare alcune modifiche API non banali per adattarsi bene in Python. Per esempio, ho scritto nella documentazione:

  

array parole JudyL macchina mappa a   Parole macchina. In pratica le parole   memorizzare interi senza segno o puntatori.   PyJudy supporta tutte e quattro le mappature come   classi distinte.

• pyjudy.JudyLIntInt - mappa unsigned chiavi intere per intero senza segno I valori
• pyjudy.JudyLIntObj - mappa unsigned chiavi intere per valori dell'oggetto Python
• pyjudy.JudyLObjInt - mappa Python chiavi oggetto per intero senza segno I valori
• pyjudy.JudyLObjObj - mappa Python chiavi oggetto di valore degli oggetti Python

Non ho guardato il codice per alcuni anni quindi i miei ricordi a questo proposito sono piuttosto nebuloso. Era la mia prima biblioteca di estensione Python, e mi ricordo ho messo insieme una sorta di sistema di template per la generazione del codice. Oggi vorrei usare qualcosa come Genshi.

Non riesco a indicare alternative a Judy - che è uno dei motivi per cui sto cercando StackOverflow

.

Modifica:. Mi è stato detto che i miei numeri di temporizzazione nella documentazione sono fuori da quello che suggerisce la documentazione di Judy perché Judy è sviluppato per le linee di cache a 64 bit e il mio PowerBook è stato solo 32 bit

Alcuni altri link:

• Patricia prova ( http://www.csse.monash .edu.au / ~ Lloyd / tildeAlgDS / Albero / PATRICIA / )
• tentativi doppio Array ( http://linux.thai.net/~thep /datrie/datrie.html )
• HAT-trie ( http://members.optusnet.com.au/~ askitisn / index.html )

L'ultima ha numeri di confronto per le diverse implementazioni trie ad alte prestazioni.

Answer 3

Questo si sta rivelando più difficile di quanto pensassi. PyJudy potrebbe essere la pena dare un'occhiata, come sarebbe Tie :: Judy . C'è qualcosa su Softpedia , e qualcosa di Ruby-ish. Il problema è che nessuno di questi sono .Net specificamente.