Esiste un modulo per AVL o Red-Black o qualche altro tipo di albero binario bilanciato nella libreria standard di Python? Ho provato a trovarne uno, ma senza successo (sono relativamente nuovo a Python).Libreria standard di Python - Esiste un modulo per l'albero binario bilanciato?
No, non c'è un albero binario bilanciato nello stdlib. Tuttavia, dai tuoi commenti, sembra che tu possa avere alcune altre opzioni:
O(log n). Se la ricerca è completa e i dati sono già ordinati, il modulo bisect fornisce un algoritmo di ricerca binaria per gli elenchi.Se nessuna delle due soluzioni funziona correttamente, è necessario passare a un modulo di terze parti o implementare le proprie.
Grazie mille! L'utilizzo di un set ha risolto il mio problema. Non avevo idea di avere le ricerche O (1) in Python (ho sempre pensato che l'intero set dovesse essere attraversato prima di trovare il giusto valore - ma come ho detto, sono nuovo di Python). Grazie anche per la spiegazione delle solite strutture dati in Python. – aeter
non c'è niente di questo tipo in stdlib, as far as I can see, ma quick look at pypi brings up a few alternative:
Esiste anche un'implementazione rapida-come-C ma pura-Python chiamata [ordinati contenitori] (http://www.grantjenks.com/docs/sortedcontainers /) I documenti hanno un buon [confronto delle prestazioni] (http://www.grantjenks.com/docs/sortedcontainers/performance.html) con le alternative che elenchi. – GrantJ
No, ma c'è AVL Tree Objects for Python e (molto vecchio!) un progetto (chiuso) su SourceForge - avl-trees for Python.
Ci sono stati alcuni casi in cui ho trovato che lo heapq package (nella libreria stadndard) sia utile, specialmente se in qualsiasi momento si desidera O (1) tempo di accesso all'elemento più piccolo della propria raccolta.
Per quanto mi riguarda, tenevo traccia di una raccolta di timer e di solito mi interessava solo verificare se il tempo più breve (quello da eseguire per primo) era già pronto per partire.
C'è un nuovo pacchetto chiamato "bintrees" che supporta alberi ubalanced, AVL e RB. Lo puoi trovare here.
Ho installato il modulo bintrees (2.0.1), ma quando lo importa, ottengo il messaggio: 'Attenzione: FastBinaryTree non disponibile, utilizzando la versione di Python BinaryTree. Qualche idea su come risolvere questo problema? Ho installato Cython, ma continua a dare quell'errore durante l'importazione. – yaraju
Mi spiace, non ho idea :( –
Ho capito che - Su Windows, le versioni FastXTree hanno bisogno di un compilatore C installato come MSVC o Mingw32. Non l'ho provato - perché probabilmente implementerò un albero personalizzato per il mio scopo – yaraju
Controlla anche il progetto Sorted Containers.
Ecco un discorso PyCon su di esso: https://www.youtube.com/watch?v=7z2Ki44Vs4E
mi basta usare set o dizionari. Se ho bisogno di usare una routine di hashing migliore, definisco '__hash __()'. Hai bisogno di qualcosa di più creativo? Se è così, perché? BTW, se non riesci a trovarlo in docs.python.org, probabilmente non è un modulo standard. –
@Mike - Sto provando a risolvere un compito da Project Euler. Penso che usare un albero di ricerca binario bilanciato invece di un elenco per uno dei miei contenitori di dati acceleri l'algoritmo con il rapporto logaritmico (a causa delle ricerche O (logn)), che risolverebbe l'attività senza surriscaldare il mio computer. Inoltre, ero solo curioso. – aeter
Che dire di un set per O (1) lookup – Mark