Инверсия словаря на месте в Python

Question

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

def invert(oldDict):
    invertedDict = {}
    for key,valuelist in oldDict.iteritems():
        for value in valuelist:
            try:
                entry = invertedDict[value]
                if key not in entry:
                    entry.append(key)
            except KeyError:
                invertedDict[value] = [key]
    return invertedDict

Оригинал - это списки, а результат - списки.Это «переворачивает» его.

test = {}
test[1] = [1999,2000,2001]
test[2] = [440,441]
test[3] = [440,2000]

print invert(test)

Это дает:

{2000: [1, 3], 2001: [1], 440: [2, 3], 441: [2], 1999: [1]}

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

Answer 1

Это не делает это на месте, но потребляет oldDict с помощью popitem ()

from collections import defaultdict
def invert(oldDict):
    invertedDict = defaultdict(list)
    while oldDict:
        key, valuelist = oldDict.popitem()
        for value in valuelist:
            invertedDict[value].append(key)
    return invertedDict

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

from collections import defaultdict
def invert(oldDict):
    invertedDict = defaultdict(list)
    i=0
    while oldDict:
        key, valuelist = oldDict.popitem()
        for value in valuelist:
            invertedDict[value].append(key)
        i+=1
        if i%1000==0: # allow the dict to release memory from time to time
            oldDict[None]=None
            del oldDict[None]
    return invertedDict

Answer 2

Вероятно, потребуется много миллионов записей, чтобы израсходовать ОЗУ на современном компьютере, если алгоритм верен.Предполагая это, вы должны использовать некоторое постоянное хранилище для данных, чтобы обрабатывать только порцию за раз.Почему бы не использовать простую таблицу базы данных с 2 столбцами для хранения dict?

key  value
1    1999
1    2000
1    2001
2    440
2    441
...

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

Answer 3

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

Если у вас недостаточно ОЗУ для запуска этого алгоритма с фактически используемым словарем, все, что я могу придумать, - это как-то избежать одновременного сохранения в памяти как исходного, так и инвертированного слова. Один из способов сделать это состоит в том, чтобы удалить элементы из исходного дикта, когда вы добавляете их к инвертированному диктату, что можно сделать так:

def invert(old_dict):
    inverted = collections.defaultdict(list)
    while old_dict:
        k,v = old_dict.popitem()
        for vi in v:
            inverted[vi].append(k)
    return inverted

(обратите внимание, что я также использовал defaultdict для упрощения кода, но если вам действительно нужен чистый dict, а не подкласс, вы можете сделать что-то похожее на то, что вы изначально использовали с try / except ) * +1010 *

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

Answer 4

У меня нет прямого ответа. Вот некоторые из моих мыслей.

1. Я думаю, то, что вы хотите сделать, можно назвать Инвертированный индекс

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