Какой тип коллекции изменяемых объектов позволит мне быстро удалять элементы в python?

Question

Предположим, я профилировал свою программу, и подавляющее большинство времени выполнения тратится на метод 'remove' of 'list' objects . Программа управляет коллекцией коллекций, и коллекции не нужно заказывать. Какой самый простой способ реализовать эти коллекции в python (желательно с использованием стандартных коллекций python), чтобы collection.remove (item) был недорогим, когда collection является внешней коллекцией и item является внутренней коллекцией, а когда collection является внутренней коллекцией, а item является просто неизменным объектом.

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

Лучшее решение, на которое я натолкнулся до сих пор, было предложено кем-то в качестве ответа здесь, который, очевидно, был удален вскоре после этого. Они предложили использовать диктовку. Это сработает, но вам придется генерировать произвольные идентификаторы для каждого элемента, так что это немного неловко. Другой альтернативой является использование связанного списка, но это также будет неудобно, поскольку связанные списки не являются частью стандартной библиотеки.

Answer 1

Если вы можете жить с равенством, определенным как идентичность, вы можете создать подтип хешируемого списка и использовать его как элементы набора для быстрого доступа / удаления:

class hlist(list):
"Hashable list"
    def __hash__(self):
        return id(self)
    def __eq__(self, other):
        return self is other
    def __ne__{self, other}:
        return self is not other

in1 = hlist([1,2,3])
in2 = hlist([4,5,6])
outer = set([in1, in2])

Answer 2

Словарь - это коллекция, которую вы хотите в этом случае, потому что в ней есть O (1) для поиска и удаления.Вам придется заплатить определенную цену: генерировать ключ для каждого объекта, когда вы хотите добавить / удалить его, но это будет значительно быстрее, чем метод O (n) сканирования списка.Генерация ключа для ваших объектов правильна в этой ситуации.Если у вас есть первичный ключ (поступил ли он из БД?), Который сведет на нет хэш-функцию при поиске свойств, и вы достигнете почти идеальной производительности.

Похоже, вы используете словарь какструктура данных в этом случае плохая вещь - это совсем не так.Цель словаря - быстро найти элементы в коллекции.Это то, что вам нужно, используйте его.

Answer 3

Они предложили использовать дикт.Это сработало бы, но вам нужно было бы генерировать произвольные идентификаторы для каждого элемента, поэтому это немного неловко.

Вы удаляете их по экземпляру?Используя подход dict, вы всегда можете использовать id() в качестве их "произвольного" идентификатора?

Один dict для групп с ключом id() в качестве ключа, внутренний dict для id() индивида,И еще один глобальный dict с индивидуумами с ключом id().

Неясно, может ли индивидуум быть в нескольких группах ... Если это так, вам нужно будет проверить, есть ли этот индивид в каком-либогруппа перед удалением.

Answer 4

Если вы тратите много времени remove -ing-элементов из списка, возможно, вам следует рассмотреть его фильтрацию вместо этого?Другими словами.создайте большой начальный список, а затем последующие генераторы, использующие элементы в списке.

Answer 5

Почему бы не иметь что-то вроде мастера list из sets, а затем другой набор, содержащий индексы в списке для набора, который вы хотите отслеживать? Конечно, это может быть немного больше работы, но вы должны быть в состоянии абстрагировать его в класс.

Answer 6

Возможно, это не совсем то, что вы просите, но collections.deque может удовлетворить некоторые ваши требования:

Запросы поддерживают поточно-ориентированные, эффективные по памяти добавления ивыскакивает с любой стороны deque с примерно одинаковой производительностью O (1) в любом направлении.