пользовательский диктант, который позволяет удалять во время итерации

Question

ОБНОВЛЕНО на основании ответа Леннарта Регебро

Предположим, что вы перебираете словарь, и иногда вам нужно удалить элемент. Следующее очень эффективно:

remove = []
for k, v in dict_.items():
  if condition(k, v):
    remove.append(k)
    continue
  # do other things you need to do in this loop
for k in remove:
  del dict_[k]

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

Популярный подход к пониманию речи:

dict_ = {k : v for k, v in dict_ if not condition(k, v)}
for k, v in dict_.items():
  # do other things you need to do in this loop

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

Гораздо лучший подход - копировать только ключи, а не весь словарь:

for k in list(dict_.keys()):
  if condition(k, dict_[k]):
    del dict_[k]
    continue
  # do other things you need to do in this loop       

(Обратите внимание, что все примеры кода представлены в Python 3, поэтому keys(), items() возвращает представление, а не копию.)

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

Тем не менее, мне интересно, возможно ли избежать этого даже с помощью пользовательского словаря, который позволяет удалять во время итерации:

for k, v in dict_.items():
  if condition(k, v):
    del dict_[k]
    continue
  # do other things you need to do in this loop

Возможно, итератор всегда может смотреть в будущее, поэтому, когда вызывается __next__, итератор знает, куда идти, даже не глядя на текущий элемент (ему нужно будет смотреть на элемент только тогда, когда он впервые до него доберется) ). А если следующего элемента нет, итератор может просто установить флаг, который вызовет исключение StopIteration, возникающее при повторном вызове __next__.

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

Есть ли проблемы с этим подходом?

Одна проблема в том, что я не уверен, что это можно сделать без материальных затрат по сравнению с существующими dict; в противном случае было бы быстрее использовать list(dict_) подход!

UPDATE:

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

Мне действительно нравятся все идеи, но, поскольку мне нужно выбрать только одну, я принимаю решение для диспетчера контекста, поскольку оно позволяет использовать словарь как обычный или "расширенный" с очень небольшими изменениями кода.

Answer 1

Как вы заметили, вы можете хранить элементы для удаления где-то и отложить их удаление до более позднего периода.Тогда проблема становится , когда , чтобы очистить их, и , как , чтобы удостовериться, что метод очистки в конечном счете вызывается.Ответом на это является менеджер контекста, который также является подклассом dict.

class dd_dict(dict):    # the dd is for "deferred delete"
    _deletes = None
    def __delitem__(self, key):
        if key not in self:
            raise KeyError(str(key))
        dict.__delitem__(self, key) if self._deletes is None else self._deletes.add(key)
    def __enter__(self):
        self._deletes = set()
    def __exit__(self, type, value, tb):
        for key in self._deletes:
            try:
                dict.__delitem__(self, key)
            except KeyError:
                pass
        self._deletes = None

Использование:

# make the dict and do whatever to it
ddd = dd_dict(a=1, b=2, c=3)

# now iterate over it, deferring deletes
with ddd:
    for k, v in ddd.iteritems():
        if k is "a":
            del ddd[k]
            print ddd     # shows that "a" is still there

print ddd                 # shows that "a" has been deleted

Если вы не находитесь в блоке with,Конечно, удаление происходит немедленно;поскольку это подкласс dict, он работает так же, как обычный dict вне диспетчера контекста.

Вы также можете реализовать это как класс-оболочку для словаря:

class deferring_delete(object):
    def __init__(self, d):
        self._dict = d
    def __enter__(self):
        self._deletes = set()
        return self
    def __exit__(self, type, value, tb):
        for key in self._deletes:
            try:
                del self._dict[key]
            except KeyError:
                pass
        del self._deletes
    def __delitem__(self, key):
        if key not in self._dict:
            raise KeyError(str(key))
        self._deletes.add(key)

d = dict(a=1, b=2, c=3)

with deferring_delete(d) as dd:
    for k, v in d.iteritems():
        if k is "a":
            del dd[k]    # delete through wrapper

print d

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

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

Answer 2

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

1. Создайте копию ключей в отдельном списке и выполните итерации. Затем вы можете безопасно удалить ключи в словаре во время итерации. Это самый простой и быстрый способ, если только словарь не является огромным , и в этом случае вы должны начать думать об использовании базы данных в любом случае. Код:

   for k in list(dict_):
     if condition(k, dict_[k]):
       del dict_[k]
       continue
     # do other things you need to do in this loop
   

2. Сделайте копию не ключей, которые вы перебираете, а копии ключей, которые вы хотите удалить. Другими словами, не удаляйте эти ключи во время итерации, вместо этого добавьте их в список, а затем удалите ключи в этом списке после завершения итерации. Это немного сложнее, чем 1., но гораздо меньше, чем 3. Это также быстро. Это то, что вы делаете в своем первом примере.

   delete_these = []
   for k in dict_:
     if condition(k, dict_[k]):
       delete_these.append(k)
       continue
     # do other things you need to do in this loop
   
   for k in delete_these:
       del dict_[k]
   

3. Единственный способ избежать создания какого-либо нового списка - это, как вы предлагаете, создать специальный словарь. Но для этого требуется, чтобы при удалении ключей он фактически не удалял ключи, но пометьте их только как удаленные, а затем удаляйте их по-настоящему только после вызова метода очистки. Это требует довольно большой реализации, и есть крайние случаи, и вы обманываете себя, забывая о чистке и т. Д. Итерирование по словарю должно по-прежнему включать удаленные ключи, которые в какой-то момент укусят вас. Так что я бы не рекомендовал это. Кроме того, как бы вы ни реализовывали это в Python, вы, скорее всего, просто снова получите список вещей, которые нужно удалить , так что, скорее всего, это будет сложная и подверженная ошибкам версия 2. Если вы реализуете это в C, вы, вероятно, могли бы избежать копирования, добавив флаги непосредственно в структуру хэш-ключа. Но, как уже упоминалось, проблемы действительно затмевают выгоды.

Answer 3

Вы можете сделать это, перебирая статический список пар ключ / значение словаря, вместо перебора словаря.

По существу, перебор по list(dict_.items()) вместо dict_.items() будетработа:

for k, v in list(dict_.items()):
  if condition(k, v):
    del dict_[k]
    continue
  # do other things you need to do in this loop

Вот пример ( ideone ):

dict_ = {0: 'a', 1: 'b', 2: 'c', 3: 'd', 4: 'e', 5: 'f', 6: 'g'}
for k, v in list(dict_.items()):
    if k % 2 == 0:
        print("Deleting  ", (k, v))
        del dict_[k]
        continue
    print("Processing", (k, v))

и вывод:

Deleting   (0, 'a')
Processing (1, 'b')
Deleting   (2, 'c')
Processing (3, 'd')
Deleting   (4, 'e')
Processing (5, 'f')
Deleting   (6, 'g')

Answer 4

Python 3.2 имеет такой аргумент в stdlib:

#!/usr/bin/env python3
from collections import OrderedDict as odict

d = odict(zip(range(3), "abc"))
print(d)
for k in d:
    if k == 2:
       del d[k]
print(d)

выход

OrderedDict([(0, 'a'), (1, 'b'), (2, 'c')])
OrderedDict([(0, 'a'), (1, 'b')])

Итерация выполняется по связанному списку, см. __iter__() реализация метода . Удаление безопасно (в Python 3.2) , даже если элементы являются слабыми ссылками.

Answer 5

Наивная реализация для Python 2.x и 3.x:

import sys
from collections import deque


def _protect_from_delete(func):
    def wrapper(self, *args, **kwargs):
        try:
            self._iterating += 1
            for item in func(self, *args, **kwargs):
                yield item
        finally:
            self._iterating -= 1
            self._delete_pending()
    return wrapper

class DeletableDict(dict):
    def __init__(self, *args, **kwargs):
        super(DeletableDict, self).__init__(*args, **kwargs)
        self._keys_to_delete = deque()
        self._iterating = 0

    if sys.version_info[0] != 3:
        iterkeys = _protect_from_delete(dict.iterkeys)
        itervalues = _protect_from_delete(dict.itervalues)
        iteritems = _protect_from_delete(dict.iteritems)
    else:
        keys = _protect_from_delete(dict.keys)
        values = _protect_from_delete(dict.values)
        items = _protect_from_delete(dict.items)  
    __iter__ = _protect_from_delete(dict.__iter__)

    def __delitem__(self, key):
        if not self._iterating:
            return super(DeletableDict, self).__delitem__(key)
        self._keys_to_delete.append(key)

    def _delete_pending(self):
        for key in self._keys_to_delete:
            super(DeletableDict, self).__delitem__(key)
        self._keys_to_delete.clear()

if __name__ == '__main__':
    dct = DeletableDict((i, i*2) for i in range(15))
    if sys.version_info[0] != 3:
        for k, v in dct.iteritems():
            if k < 5:
                del dct[k]
        print(dct)
        for k in dct.iterkeys():
            if k > 8:
                del dct[k]
        print(dct)
        for k in dct:
            if k < 8:
                del dct[k]
        print(dct)
    else:
        for k, v in dct.items():
            if k < 5:
                del dct[k]
        print(dct)

При переборе ключей, элементов или значений устанавливается флаг self._iterating. В __delitem__ он проверяет возможность удаления элемента и сохраняет ключи во временной очереди. В конце итераций он удаляет все ожидающие ключи.

Это очень наивная реализация, и я бы не рекомендовал использовать ее в рабочем коде.

EDIT

Добавлена ​​поддержка Python 3 и улучшения из @ jsbueno комментариев.

Python 3 работает на Ideone.com

Answer 6

Это может сработать как компромисс между двумя примерами - две строки длиннее второго, но короче и немного быстрее первого.Python 2:

dict_ = {k : random.randint(0, 40000) for k in range(0,200000)}

dict_remove = [k for k,v in dict_.iteritems() if v < 3000]
for k in dict_remove:
    del dict_[k]

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

def dict_remove(dict_, keys):
    for k in keys:
        del dict_[k]

dict_remove(dict_, [k for k,v in dict_.iteritems() if v < 3000])

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

Answer 7

1. Вы можете сделать копию списка ключей (вам не нужно копировать значения te) в начале итерации и выполнять итерацию по ним (проверяя наличие ключа). Это неэффективно, если ключей много.
2. Вы можете встроить свой первый пример кода в класс. __iter__ и __delitem__ и другие специальные методы должны сотрудничать, чтобы сохранить список элементов, которые будут удалены во время итерации. Когда нет текущих итераций, __delitem__ может просто удалить элемент, но когда происходит хотя бы одна итерация, он должен просто добавить ключ, который будет удален, в список. Когда последняя активная итерация заканчивается, она должна удалить вещи. Это несколько неэффективно, если нужно удалить много ключей, и, разумеется, взорвется, если всегда будет хотя бы одна итерация.