Я портирую код C++ на Python, и одна из структур данных является мультимножеством, но я не уверен, как моделировать это в Python.Есть ли эквивалент Python для C++ «multiset <int>»?
Пусть ms быть C++ multiset<int>
Как ms используются (постить примеры)
multiset<int>::iterator it = ms.find(x)
ms.erase(it)
ms.insert(x)
ms.end()
ms.lower_bound(x)
ms.clear()
Нет. См. Python's standard library - is there a module for balanced binary tree? для общего обсуждения эквивалентов контейнеров дерева C++ (map, set, multimap, multiset) в Python.
Ближайшим, о котором я могу думать, является использование словаря, сопоставляющего целые числа с числами (также целыми). Однако это не дает вам ключей по порядку, поэтому вы не можете искать, используя lower_bound. Альтернативой является использование упорядоченного списка, как уже было предложено другими, возможно, список (целых, числовых) кортежей? Если вам нужно только выполнить поиск после того, как вы сделали все свои вставки, вы можете использовать словарь как временную структуру для построения, построить список после того, как вы сделали все вставки, а затем использовать список для поиска.
Да, сначала код выполняет множество вставок, а затем выполняет поиск/удаление различных элементов. Оба процесса используют много нижних вызовов. – MrP
@MrP Знаете ли вы, почему во время процесса вставки возникают вызовы 'lower_bound'? Re 'lower_bound' вызывает во время процесса удаления, если у вас есть список кортежей' (integer, count), вы можете удалить элементы, уменьшив счетчик, и если счет достигнет нуля, вы можете оставить там элемент и очистить некоторое время спустя. (Вставки совершенно новых целых чисел были бы более проблематичными!) – TooTone
Вы можете сохранить список упорядоченных используя bisect функции. Например find станет
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
Вы найдете другие эквиваленты в документации. Вместо проверки на end вы получите ValueError
Или, возможно, использовать heapq. – Marcin
Существует несколько вариантов данных отсортированного списка, которые соответствуют вашим критериям. Два популярных варианта: SortedContainers и blist модулей. Каждый из этих модулей предоставляет тип данных SortedList, который автоматически поддерживает элементы в упорядоченном порядке и позволяет быстро вставлять и просматривать нижние/верхние границы. Там тоже performance comparison.
Эквивалентный код с использованием типа SortedList из модуля SortedContainers будет:
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()
Все эти операции должны эффективно работать на отсортированного типа данных списка.
Есть несколько структур данных, которые приближаются.
коллекции питона:
обеспечивается рамки Джанго:
Вы можете проверить класс 'Counter' в python: http://docs.python.org/2/library/collections.html#collections.Counter – taocp
Существуют ли эквиваленты для перечисленных мной функций/методов? – MrP
'Counter' не является эквивалентом' std :: multiset'. – juanchopanza