Questo fa essenzialmente la stessa cosa la fa SortedCollection recipe che il bisect documentation menzioni nella Vedi anche: sezione alla fine, che supporta una funzione chiave.
Cosa si sta facendo è un separato ordinato keys elenco è mantenuto in parallelo con l'ordinato data lista per migliorare le prestazioni (è più veloce rispetto alla creazione della lista chiavi prima di ogni inserimento, ma mantenendo intorno e l'aggiornamento non è strettamente necessario) . La ricetta di ActiveState ha racchiuso questo per te all'interno di una classe, ma nel codice sottostante sono solo due elenchi indipendenti separati da passare (quindi sarebbe più facile per loro di uscire dalla sincronizzazione di quanto sarebbe se fossero entrambi tenuti in un'istanza della classe della ricetta).
from bisect import bisect_left
def insert(seq, keys, item, keyfunc=lambda v: v):
"""Insert an item into a sorted list using a separate corresponding
sorted keys list and a keyfunc() to extract the key from each item.
Based on insert() method in SortedCollection recipe:
http://code.activestate.com/recipes/577197-sortedcollection/
"""
k = keyfunc(item) # Get key.
i = bisect_left(keys, k) # Determine where to insert item.
keys.insert(i, k) # Insert key of item to keys list.
seq.insert(i, item) # Insert the item itself in the corresponding place.
# Initialize the sorted data and keys lists.
data = [('red', 5), ('blue', 1), ('yellow', 8), ('black', 0)]
data.sort(key=lambda r: r[1]) # Sort data by key value
keys = [r[1] for r in data] # Initialize keys list
print(data) # -> [('black', 0), ('blue', 1), ('red', 5), ('yellow', 8)]
insert(data, keys, ('brown', 7), keyfunc=lambda x: x[1])
print(data) # -> [('black', 0), ('blue', 1), ('red', 5), ('brown', 7), ('yellow', 8)]
Follow-on domanda:
Può bisect.insort_left essere usato?
No, non è possibile utilizzare semplicemente la funzione bisect.insort_left() perché non è stata scritta in un modo che supporta una funzione chiave, ma confronta solo l'intero elemento passato ad essa per inserire, x, con uno degli elementi interi nell'array nella sua istruzione if a[mid] < x:. Puoi vedere cosa intendo guardando la sorgente del modulo bisect in Lib/bisect.py.
Ecco il brano in questione:
def insort_left(a, x, lo=0, hi=None):
"""Insert item x in list a, and keep it sorted assuming a is sorted.
If x is already in a, insert it to the left of the leftmost x.
Optional args lo (default 0) and hi (default len(a)) bound the
slice of a to be searched.
"""
if lo < 0:
raise ValueError('lo must be non-negative')
if hi is None:
hi = len(a)
while lo < hi:
mid = (lo+hi)//2
if a[mid] < x: lo = mid+1
else: hi = mid
a.insert(lo, x)
è possibile modificare quanto sopra per accettare un argomento-tasto funzione opzionale e usarlo:
def my_insort_left(a, x, lo=0, hi=None, keyfunc=lambda v: v):
x_key = keyfunc(x) # Get and save value comparison value.
. . .
if keyfunc(a[mid]) < x_key: # Compare key values.
lo = mid+1
. . .
... e chiamarlo in questo modo:
In realtà, se hai intenzione di scrivere una funzione personalizzata, per maggiore efficienza a scapito di generalità non necessaria, è possibile fare a meno dell'aggiunta di un argomento di funzione chiave generico e basta eseguire l'hardcode di tutto per utilizzare la modalità necessaria con il formato dei dati che si ha. Ciò eviterà il sovraccarico di più chiamate a una funzione chiave durante gli inserimenti.
def my_insort_left(a, x, lo=0, hi=None):
x_key = x[1] # Key on second element of each item in sequence.
. . .
if a[mid][1] < x_key: lo = mid+1 # Compare second element to key.
. . .
... chiamati in questo modo, senza passare keyfunc:
my_insort_left(data, ('brown', 7))
Qual è la tua domanda? – BrenBarn
Stai attento a questo è un'operazione O (N), controlla se ne hai veramente bisogno prima. Avete considerato 'heapq' o semplicemente chiamato' list.sort' prima di stampare se l'elenco non è ordinato – jamylak
Sì, heapq non funziona bene per rimuovere un nodo mid tree. quindi, questo potrebbe essere il migliore per me – Merlin