Sto trasferendo un codice C++ in Python e una delle strutture dati è un multiset, ma non sono sicuro di come modellarlo in Python.Esiste un equivalente Python per C++ "multiset <int>"?
Let ms essere i C++ multiset<int>
Come ms viene utilizzato (che inviano alcuni esempi)
multiset<int>::iterator it = ms.find(x)
ms.erase(it)
ms.insert(x)
ms.end()
ms.lower_bound(x)
ms.clear()
Non c'è. Vedere Python's standard library - is there a module for balanced binary tree? per una discussione generale sugli equivalenti dei contenitori di albero C++ (map, set, multimap, multiset) in Python.
Il più vicino a cui riesco a pensare è quello di utilizzare un dizionario che mappa gli interi in conteggi (anche interi). Tuttavia, questo non ti dà le chiavi in ordine, quindi non puoi cercare usando lower_bound. Un'alternativa è quella di usare una lista ordinata, come già suggerito da altri, forse un elenco di tuple (integer, count)? Se devi eseguire la ricerca solo dopo aver eseguito tutti gli inserimenti, puoi utilizzare il dizionario come struttura temporanea per la costruzione, creare l'elenco dopo aver eseguito tutti gli inserimenti, quindi utilizzare l'elenco per la ricerca.
Sì, il codice esegue prima molti inserimenti, quindi ricerca/rimuove vari elementi in seguito. Entrambi i processi utilizzano molte chiamate low_bound. – MrP
@MrP Sapete perché ci sono chiamate 'lower_bound' durante il processo di inserimento? Chiamando Re 'lower_bound' durante il processo di rimozione, se avessi una lista di tuple' (integer, count) ', potresti rimuovere gli elementi diminuendo il conteggio, e se un conteggio ha raggiunto lo zero, potresti lasciare l'oggetto lì e ripulire qualche tempo dopo. (Inserimenti di interi completamente nuovi sarebbe più un problema!) – TooTone
È possibile mantenere una lista ordinata utilizzando le bisect funzioni. Per esempio find diventerà
def index(a, x):
'Locate the leftmost value exactly equal to x'
i = bisect_left(a, x)
if i != len(a) and a[i] == x:
return i
raise ValueError
troverete altri equivalenti nella documentazione. Invece di verificare contro end ora riceverai un ValueError
Oppure usa un heapq, forse. – Marcin
Esistono alcune implementazioni di tipi di dati di elenchi ordinati che corrisponderebbero ai vostri criteri. Due scelte popolari sono i moduli SortedContainers e blist. Ciascuno di questi moduli fornisce un tipo di dati SortedList che mantiene automaticamente gli elementi in ordine ordinato e consentirebbe l'inserimento rapido e le ricerche con limite inferiore/superiore. C'è anche un performance comparison che è utile.
Il codice equivalente utilizzando il tipo SortedList dal modulo SortedContainers sarebbe:
from sortedcontainers import SortedList
sl = SortedList()
# Start index of `x` values
start = sl.bisect_left(x)
# End index of `x` values
end = sl.bisect_right(x)
# Iterator for those values
iter(sl[start:end])
# Erase an element
del sl[start:end]
# Insert an element
sl.add(x)
# Iterate from lower bound
start = sl.bisect_left(x)
iter(sl[x] for x in range(start, len(sl)))
# Clear elements
sl.clear()
Tutte queste operazioni dovrebbe funzionare in modo efficiente su un tipo di elenco di dati ordinati.
Ci sono un paio di strutture di dati che si avvicinano.
collezioni pitone:
fornito da quadro django:
È possibile selezionare la classe 'Counter' in python: http://docs.python.org/2/library/collections.html#collections.Counter – taocp
Esistono equivalenti per le funzioni/metodi che ho elencato? – MrP
'Counter' non è equivalente a' std :: multiset'. – juanchopanza