Сортированный список против кучи: удаление элементов в середине списка Python

Question

У меня постоянно обновляется структура списка.На каждой итерации выполняются следующие шаги:

• Удалить минимальное значение в списке
• удалить n значений где-то в списке
• добавить n значений в список

Насколько я понял, куча не является хорошим решением (даже с отложенным удалением), потому что мне нужно удалить значения где-то в списке, для которого я не знаю индекса (позиции).Таким образом, эти значения нужно искать ..

Я просто использую отсортированный список для этой проблемы?Мне нужна максимальная производительность, которую я могу получить, поскольку в какой-то момент цикла список содержит до 100 000 элементов.

Answer 1

Если значения можно использовать в качестве ключей dict, тогда было бы довольно легко использовать как кучу, так и collections.Counter, чтобы отслеживать, сколько из каждого значения концептуально все еще находится в коллекции.Отсчет 0 означает, что значение было концептуально полностью удалено, хотя оно все еще может существовать в куче.

Вот эскиз (не проверено!), Где c - это экземпляр collections.Counter и h - это список, используемый в качестве кучи для операций модуля heapq:

Чтобы добавить элемент (логарифмическое время ожидаемого случая в размере кучи):

heapq.heappush(h, elt)
c[elt] += 1

Чтобы удалить элемент(постоянное время в ожидаемом случае):

if not c[elt]:
    raise ValueError("element doesn't exist")
c[elt] -= 1
if not c[elt]:
    del c[elt]

Чтобы удалить минимальный элемент (логарифмическое время в ожидаемом случае (в уменьшающемся размере кучи)) для каждого концептуально извлеченного ранее удаленного элементаиз кучи):

while True:
    if not h:
        raise ValueError("cannot find minimum in empty collection")
    elt = heapq.heappop(h)
    if c[elt]:
        c[elt] -= 1
        if not c[elt]:
            del c[elt]
        break
    # else the Counter believes it was deleted earlier

Answer 2

Вы можете избежать проблемы незнания индекса удаляемого элемента, также поддерживая словарь рядом с кучей.Значения в словаре совпадают с элементами кучи (возможно, список со значением приоритета и ссылкой на реальный элемент).Ключи словаря аналогичны реальным элементам, поэтому их легко найти.

Когда вы хотите удалить элемент, который не является минимальным, вы ищите его в словаре и помечаете его какудален (возможно, установив ссылку на элемент на None).Нет необходимости изменять список, представляющий кучу, он имеет ссылки на те же элементы, поэтому он будет видеть, что элемент был удален всякий раз, когда он подходит, чтобы быть удаленным как минимум.

Тем не менее, если выесли вы часто выполняете операцию «удалить элементы из любой точки данных», то вам лучше всего использовать обычный словарь или набор.Вы можете получить минимум с min по линейному времени, а удаление (любого элемента, включая минимум) занимает постоянное время (в среднем амортизируется).Для некоторых моделей использования это может быть быстрее, чем работа с кучей.