Словарь Python очень медленный

У меня есть словарь d1 и список l1.

Клавиши словаря - это строки, а значения - это объекты, которые я сам определил. Если это помогает, я могу описать объект более подробно, но на данный момент объекты имеют атрибут списка names, а некоторые из элементов name могут появляться или не отображаться в l1.

То, что я хотел сделать, это выбросить любой элемент словаря d1, в котором атрибут name объекта в указанном элементе не содержит ни одного из элементов, которые появляются в l1.

В качестве тривиального примера:

l1 = ['cat', 'dog', 'mouse', 'horse', 'elephant', 
      'zebra', 'lion', 'snake', 'fly']

d1 = {'1':['dog', 'mouse', 'horse','orange', 'lemon'],
      '2':['apple', 'pear','cat', 'mouse', 'horse'], 
      '3':['kiwi', 'lime','cat', 'dog', 'mouse'], 
      '4':['carrot','potato','cat', 'dog', 'horse'], 
      '5':['chair', 'table', 'knife']}

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

Для этого я использовал понимание вложенного списка/словаря, которое выглядело так:

d2 = {k: [a for a in l1 if a in d1[k]] for k in d1.keys()}
print(d2)

>>>>{'1': ['dog', 'mouse', 'horse'], 
     '3': ['cat', 'dog', 'mouse'], 
     '2': ['cat', 'mouse', 'horse'], 
     '5': [], 
     '4': ['cat', 'dog', 'horse']}

d2 = {k: v for k,v in d2.iteritems() if len(v)>0}
print(d2)

>>>>{'1': ['dog', 'mouse', 'horse'], 
     '3': ['cat', 'dog', 'mouse'], 
     '2': ['cat', 'mouse', 'horse'],  
     '4': ['cat', 'dog', 'horse'],}

Кажется, что это работает, но для больших словарей, 7000+ предметов, для работы требуется около 20 секунд. Само по себе не ужасно, но мне нужно сделать это внутри цикла, который будет повторяться 10 000 раз, поэтому в настоящее время это невозможно. Любые предложения о том, как это сделать быстро?

Ответ 1

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

Полный код может выглядеть так:

l1 = set(l1)
d2 = {k: [s for s in v if s in l1] for k, v in d1.iteritems()}
d2 = {k: v for k, v in d2.iteritems() if v}

Вместо двух понятий словаря также может быть предпочтительнее использовать один цикл for здесь:

l1 = set(l1)
d2 = {}
for k, v in d1.iteritems():
    v = [s for s in v if s in l1]
    if v:
        d2[k] = v

Ответ 2

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

s1 = set(l1)
d2 = {k: list(s1.intersection(v)) for k, v in d1.items()}

Ответ 3

l1 = ['cat', 'dog', 'mouse', 'horse', 'elephant', 
      'zebra', 'lion', 'snake', 'fly']

d1 = {'1':['dog', 'mouse', 'horse','orange', 'lemon'],
      '2':['apple', 'pear','cat', 'mouse', 'horse'], 
      '3':['kiwi', 'lime','cat', 'dog', 'mouse'], 
      '4':['carrot','potato','cat', 'dog', 'horse'], 
      '5':['chair', 'table', 'knife']}

def gen_items(valid_name_set, d):
    for k, v in d.iteritems():
        intersection = valid_name_set.intersection(v)
        if intersection: # not empty
            yield (k, intersection)

print dict(gen_items(set(l1), d1))

Вывод:

{'1': set(['dog', 'horse', 'mouse']),
 '2': set(['cat', 'horse', 'mouse']),
 '3': set(['cat', 'dog', 'mouse']),
 '4': set(['cat', 'dog', 'horse'])}

В качестве альтернативы:

from itertools import ifilter
from operator import itemgetter
set_l1 = set(l1)
d2 = dict(ifilter(itemgetter(1), 
                  ((k, set_l1.intersection(v)) for k, v in d1.iteritems())))

Ответ 4

Используйте set:

>>> l1 = ['cat', 'dog', 'mouse', 'horse', 'elephant',
      'zebra', 'lion', 'snake', 'fly']
>>> d1 = {'1':['dog', 'mouse', 'horse','orange', 'lemon'],
      '2':['apple', 'pear','cat', 'mouse', 'horse'],
      '3':['kiwi', 'lime','cat', 'dog', 'mouse'],
      '4':['carrot','potato','cat', 'dog', 'horse'],
      '5':['chair', 'table', 'knife']}
>>> l1_set = set(l1)
>>> d2 = dict((k, set(d1[k]) & l1_set) for k in d1.keys())
>>> d2
{'1': set(['horse', 'mouse', 'dog']), '3': set(['mouse', 'dog', 'cat']), '2': set(['horse', 'mouse', 'cat']), '5': set([]), '4': set(['horse', 'dog', 'cat'])}
>>> d2 = dict((k, v) for k,v in d2.iteritems() if v)
>>> d2
{'1': set(['horse', 'mouse', 'dog']), '3': set(['mouse', 'dog', 'cat']), '2': set(['horse', 'mouse', 'cat']), '4': set(['horse', 'dog', 'cat'])}

Ответ 5

Если вы преобразуете l1 в set и немного измените понимание dict, вы можете заставить это работать примерно в три раза быстрее:

l1 = set(['cat', 'dog', 'mouse', 'horse', 'elephant', 
      'zebra', 'lion', 'snake', 'fly'])

d1 = {'1':['dog', 'mouse', 'horse','orange', 'lemon'],
      '2':['apple', 'pear','cat', 'mouse', 'horse'], 
      '3':['kiwi', 'lime','cat', 'dog', 'mouse'], 
      '4':['carrot','potato','cat', 'dog', 'horse'], 
      '5':['chair', 'table', 'knife']}

d2 = {k: [a for a in d1[k] if a in l1] for k in d1.keys()}
print(d2)

Здесь вы можете сравнить производительность:

import timeit

t = timeit.Timer(
    "d2 = {k: [a for a in l1 if a in d1[k]] for k in d1.keys()}",
    "from __main__ import (d1, l1)",
    )
print "%.2f usec/pass" % (1000000 * t.timeit(number=100000)/100000)

t = timeit.Timer(
    'd2 = {k: [a for a in d1[k] if a in l1] for k in d1.keys()}',
    "from __main__ import (d1, l1)",
    )
print "%.2f usec/pass" % (1000000 * t.timeit(number=100000)/100000)

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