Perché la dict ha il caso peggiore O (n) per così tante operazioni?

Question

In che modo esattamente viene implementato il comando dict che ha una ricerca temporale lineare per le collisioni? Suppongo che sia implementato come un hashtable supportato da un elenco. Presumerei che una migliore implementazione sarebbe O (log (n)) per varie operazioni, usando invece una struttura ad albero per il retro della tabella. C'è qualcosa di magico dietro le quinte per mantenere vive le ricerche a tempo costante il più a lungo possibile?

mia fonte per questo, tra l'altro, è la seguente:

http://www.google.com/search?sourceid=chrome&ie=UTF-8&q=python+complexity

Answer 1

Dict è O (1) per molte operazioni, eccetto le operazioni che toccano tutti gli elementi, come iterazione e copia (in che caso, è ovviamente O (n)).

See: http://wiki.python.org/moin/TimeComplexity

Ha O (n) nel caso peggiore, perché è sempre possibile escogitare un esempio patologica in cui tutte le chiavi hanno lo stesso valore di hash.

Answer 2

Considera anche la migliore funzione di hash della galassia. C'è ancora la possibilità che tu possa risalire un giorno con un elenco di valori il cui miglior valore di funzione hash è lo stesso. Se li metti in una dict, il sistema non ha altra scelta che eseguire ricerche lineari.

Utilizzando un albero bilanciato manterrebbe il tempo nel caso peggiore giù O (log n), ma i costi di manutenzione sono piuttosto alti. Di solito, i tavoli hash funzionano piuttosto bene.

Answer 3

Suppongo che un'implementazione migliore sia O (log (n)) per varie operazioni, utilizzando invece un albero per eseguire il backup della tabella.

Alberi e tabelle hash hanno requisiti e prestazioni molto diversi.

• Gli alberi richiedono un tipo ordinato.
• Gli alberi richiedono il confronto degli ordini per trovare l'oggetto. Per alcuni oggetti, come le stringhe, ciò impedisce alcune significative ottimizzazioni: è sempre necessario eseguire un confronto tra stringhe, che è non costoso. Ciò rende il fattore costante di O (log n) piuttosto elevato.
• Le tabelle hash richiedono un tipo hashable e possono essere testate per l'uguaglianza, ma non richiedono un tipo ordinato.
• I test per l'uguaglianza possono essere ottimizzati in modo significativo. Se due stringhe sono internate, puoi verificare se sono uguali in O (1) confrontando il loro puntatore, piuttosto che O (n) confrontando l'intera stringa. Si tratta di un'ottimizzazione massiccia: in ogni foo.bar ricerca che viene tradotto in foo.__dict__["bar"], "bar" corda è un internato.
• tabelle hash sono O (n) nel caso peggiore, ma esaminare ciò che porta a quel caso peggiore: un'implementazione molto male tabella di hash (ad esempio, hai un solo secchio.), O di una funzione di hash rotto che restituisce sempre lo stesso valore. Quando si dispone di una funzione hash corretta e di un algoritmo di benna appropriato, le ricerche sono molto economiche - molto spesso si avvicina a un tempo costante.

Gli alberi non hanno vantaggi significativi:

• Essi tendono ad avere più bassi requisiti di memoria, dal momento che non c'è bisogno di preallocare secchi.L'albero più piccolo potrebbe essere 12 byte (puntatore del nodo e due puntatori figlio), dove una tabella hash tende a 128 byte o più - sys.getsizeof ({}) sul mio sistema è 136.
• Permettono l'attraversamento ordinato; è estremamente utile poter iterare su [a, b) in un set ordinato, che le tabelle di hash non consentono.

io lo considero un difetto che Python non ha un contenitore standard albero binario, ma per le caratteristiche delle prestazioni necessarie per il nucleo di Python, come __dict__ le ricerche, una tabella hash fa più senso.

Answer 4

Il punto di scelta dell'implementazione rispetto a un altro non è necessariamente relativo allo upper-bound, ma piuttosto al previsto amortized performance. Mentre i diversi algoritmi possono avere casi degenerati di solito è "migliore nella pratica" rispetto all'utilizzo di un approccio con un limite superiore inferiore dimostrabile. In alcuni casi, tuttavia, le strutture devono essere progettate per proteggersi da input patologicamente errati.

Inoltre, alcune lingue/librerie - non sono sicuro di Python - in realtà cambiano l'implementazione sottostante, ad esempio quando il numero di elementi supera un n basso. Ciò influisce sulle prestazioni ammortizzate (in alcuni casi), ma non necessariamente su big O.

E in conclusione: "Dipende".

Felice codifica.

Answer 5

fonti affidabili di informazioni relative alle funzioni di hash e la strategia di collisione risoluzione che vengono effettivamente utilizzati includono i commenti nel file sorgente dictobject.c e l'intero file dictnotes.txt