Judy array per le lingue gestite

Question

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

Answer 1

Vale la pena notare che questi sono spesso chiamati Judy Trees o Judy Tries se si sta cercando su Google.

Ho anche cercato un'implementazione .Net ma non ho trovato nulla. Vale la pena notare che:

L'implementazione è fortemente progettata intorno all'utilizzo efficiente della cache, in quanto tali specifiche di implementazione possono dipendere in larga misura dalla dimensione di determinati costrutti utilizzati all'interno delle sottostrutture. Un'implementazione gestita .Net può essere alquanto diversa a questo riguardo.

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 (ad esempio un puntatore nullo è visto come un albero vuoto) in modo semplicistico, spostare il puntatore di stato su LHS e rendere la conversione di metodi di istanza di funzioni in C++ non funzionerebbe.
• L'implementazione delle sottostrutture che ho esaminato ha fatto un uso pesante dei puntatori. Non riesco a vederli essere efficacemente tradotti in riferimenti nei linguaggi gestiti.
• L'implementazione è una distillazione di molte idee molto complesse che smentiscono la semplicità dell'API pubblica.
• La base di codice è di circa 20 K linee (la maggior parte complesse), questo non mi sembra una porta facile.

Si potrebbe prendere la libreria e avvolgere il codice C in C++/CLI (probabilmente semplicemente tenendo internamente un puntatore che è il c api trie e avendo tutte le chiamate c puntano a questo). Ciò fornirebbe un'implementazione semplicistica ma le librerie collegate per l'implementazione nativa potrebbero essere problematiche (come potrebbe allocare la memoria). Probabilmente dovresti anche avere a che fare con la conversione di stringhe .Net in plain old byte * sulla transizione (o semplicemente lavorare con byte direttamente)

Answer 2

Questo si sta rivelando più complicato di quanto pensassi. PyJudy potrebbe valere la pena dare un'occhiata, come lo sarebbe Tie::Judy. C'è qualcosa su Softpedia e qualcosa da Ruby-ish. Il problema è, nessuno di questi è. NET in particolare.

Answer 3

Judy non si adatta molto bene ai linguaggi gestiti. Non penso che sarete in grado di utilizzare qualcosa come SWIG e ottenere automaticamente il primo livello.

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

Gli array JudyL mappano le parole della macchina alle parole della macchina . In pratica le parole memorizzano numeri interi o puntatori senza segno. PyJudy supporta tutti e quattro i mapping come classi distinte .

• pyjudy.JudyLIntInt - mappa non firmate chiavi intere per intero senza segno valori
• pyjudy.JudyLIntObj - carta firmate chiavi intere per oggetto Python valori
• pyjudy.JudyLObjInt - map pitone chiavi oggetto per intero senza segno valori
• pyjudy.JudyLObjObj - map pitone chiavi oggetto per oggetto Python valori

Non ho guardato il codice per alcuni anni, quindi i miei ricordi a riguardo sono piuttosto confusi. Era la mia prima libreria di estensioni Python e ricordo che ho hackerato una sorta di template per la generazione di codice. Al giorno d'oggi vorrei usare qualcosa come genshi.

Non riesco a indicare alternative a Judy: questa è una delle ragioni per cui sto cercando StackOverflow.

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

Alcuni altri link:

• Patricia prova (http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Tree/PATRICIA/)
• doppio Array tentativi (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 diverse implementazioni di trie ad alte prestazioni.