Ho visto persone dire che gli oggetti set in python hanno O (1) -appartenenza-controllo. Come vengono implementati internamente per consentire questo? Che tipo di struttura dati usa? Quali altre implicazioni ha questa implementazione?Come viene implementato set()?
Ogni risposta qui è stata davvero illuminante, ma posso accettarne solo una, quindi andrò con la risposta più vicina alla mia domanda iniziale. Grazie a tutti per le informazioni!
Secondo this thread:
In effetti, i set di CPython sono implementate come qualcosa di simile dizionari con valori fittizi (le chiavi essendo i membri del set), con un po ' ottimizzazione (s) che sfruttano questa mancanza dei valori
Quindi, in pratica, un set utilizza una tabella hash come struttura dati sottostante. Questo spiega il controllo di appartenenza O (1), poiché la ricerca di un elemento in una tabella hash è un'operazione di tipo O (1), in media.
Se siete così inclinato si può anche navigare sul CPython source code for set che, secondo Achim Domma, è per lo più un cut-e-incolla dal dict implementazione.
Penso che sia un errore comune, la ricerca set (o la tabella hash per quella materia) non è O (1).
from the Wikipedia
Nel modello più semplice, la funzione hash è completamente non specificato e la tabella non viene ridimensionato. Per la migliore scelta possibile della funzione di hash, una tabella di dimensione n con indirizzo aperto non ha collisioni e contiene fino a n elementi, con un unico confronto per la ricerca riuscita, e una tabella di dimensione n con concatenamento e chiavi k ha il minimo (0, kn) collisioni e O (1 + k/n) confronti per la ricerca. Per la peggiore scelta della funzione hash, ogni inserimento causa una collisione e le tabelle hash degenerano in ricerca lineare, con Ω (k) confronti ammortizzati per inserimento e fino a k confronti per una ricerca riuscita.
correlati: Is a Java hashmap really O(1)?
Ma ci vuole tempo costante per cercare oggetti: python -m timeit -s "s = set (range (10))" "5 in s" 10000000 loop, meglio di 3: 0.0642 usec per loop <--> python -m timeit -s "s = set (range (10000000))" "5 in s" 10000000 loop, meglio di 3: 0,0634 usec per loop ... e questo è il set più grande che non getta MemoryErrors –
@ THC4k Tutto quello che hai provato è che la ricerca di X viene eseguita in tempo costante, ma ciò non significa che il tempo per cercare X + Y richiederà lo stesso tempo che è O (1). –
Ho pensato che significava che il tempo per eseguire una ricerca era indipendente dal numero di valori memorizzati. – intuited
Abbiamo tutti un facile accesso alle the source, dove il commento precedente set_lookkey() dice:
/* set object implementation
Written and maintained by Raymond D. Hettinger <[email protected]>
Derived from Lib/sets.py and Objects/dictobject.c.
The basic lookup function used by all operations.
This is based on Algorithm D from Knuth Vol. 3, Sec. 6.4.
The initial probe index is computed as hash mod the table size.
Subsequent probe indices are computed as explained in Objects/dictobject.c.
To improve cache locality, each probe inspects a series of consecutive
nearby entries before moving on to probes elsewhere in memory. This leaves
us with a hybrid of linear probing and open addressing. The linear probing
reduces the cost of hash collisions because consecutive memory accesses
tend to be much cheaper than scattered probes. After LINEAR_PROBES steps,
we then use open addressing with the upper bits from the hash value. This
helps break-up long chains of collisions.
All arithmetic on hash should ignore overflow.
Unlike the dictionary implementation, the lookkey function can return
NULL if the rich comparison returns an error.
*/
...
#ifndef LINEAR_PROBES
#define LINEAR_PROBES 9
#endif
/* This must be >= 1 */
#define PERTURB_SHIFT 5
static setentry *
set_lookkey(PySetObject *so, PyObject *key, Py_hash_t hash)
{
...
quando la gente dice insiemi hanno O (1) L'adesione controllo, sono parlando del medio del caso. Nel caso peggiore (quando tutti i valori hash si scontrano) il controllo dell'iscrizione è O (n). Vedi lo Python wiki on time complexity.
Il Wikipedia article dice il migliore dei casi complessità temporale per una tabella di hash che non è ridimensionare O(1 + k/n). Questo risultato non si applica direttamente ai set Python poiché i set Python usano una tabella hash che si ridimensiona.
Poco più sull'articolo Wikipedia dice che per il caso media, e assumendo una semplice funzione di hashing uniforme, la complessità temporale è O(1/(1-k/n)), dove k/n può essere delimitata da una costante c<1.
Big-O si riferisce solo al comportamento asintotico come n → ∞. Poiché k/n può essere limitato da una costante, c < 1, indipendente da n,
O(1/(1-k/n)) è non più grande di O(1/(1-c)) che equivale a O(constant) = O(1).
Quindi, supponendo un semplice hashing uniforme, su medio, il controllo di appartenenza per i set Python è O(1).
Per enfatizzare un po 'di più la differenza tra set's e dict's, ecco un estratto delle sezioni di commento setobject.c, che chiarisce la principale differenza di set contro dict.
I casi di utilizzo per insiemi differiscono considerevolmente dai dizionari in cui è più probabile che siano presenti le chiavi ricercate . Al contrario, i set sono principalmente sui test di appartenenza in cui la presenza di un elemento non è nota in anticipo . Di conseguenza, l'implementazione impostata deve ottimizzare sia per il caso trovato e non trovato.
sorgente sul github
IIRC, l'originale 'implementazione set' realtà * è *' dict' con valori fittizi, ed è ottenuto ottimizzato in seguito. – dan04
Non è grande O lo scenario peggiore? Se riesci a trovare un'istanza in cui l'ora è O (n), allora è O (n) .. Non capisco nulla in questo momento da tutti quei tutorial. –
No, il caso medio è O (1) ma il caso peggiore è O (N) per la ricerca tabella hash. –