python: оптимизация размера словаря

Question

Столкнулся со следующей проблемой:

Есть файл с записями вида:

строка:число
строка:число
...
строка:число

Мне необходимо перевести их в словарь, где строка - ключ, число - значение

Всего имею 56.280.820 записей, суммарным объёмом 1.318.795.472 байт.

И при доступных 16ГБ памяти (10, остальное остальные приложения и ОС кушают) я не могу сформировать словарь - программа падает в связи с расходом всей памяти

MemoryError

Такой вопрос - можно ли это как-то побороть в лоб, т.е. как-то манипулируя словарем? Или просто такие объёмы данных не обрабатываемы при таком объёме памяти?

P.S.

саму задачу использования таких объёмов памяти я могу решить разбивая словарь на словари меньшего объёма и подгружая и используя их последовательно

т.е. оптимизировать задачу таким способом, но хотелось бы понять, неужто сам словарь занимает так много места в памяти? (в C++ вроде для std::map каждая запись требует минимум 20 байт, но это опять означало бы расходование 1ГБ памяти, что в рамках свободных 10ГБ не так и много)

P.P.S.

словари храню в zip архивах - чтобы места меньше занимали: в качестве разделителя использую в данном случае '='

# распарсить словарь
def parse_dictionary(text, dictionary, separator = '\n'):
    data = text.split(separator)

    # распарсить данные
    size = 0

    for record in data:
        if record[:4] == "===>":
            size = int(record.split('=')[-1])

            if size not in dictionary:
                dictionary[size] = dict()
        elif size > 0:
            props = record.split('=')
            if len(props) == 2:
                dictionary[size][props[0]] = dictionary[size].get(props[0], 0) + int(props[1])

# загрузить словарь из zip файла
def zip2dictionary(path, dictionary):
    print(path)

    # загрузить данные
    with zipfile.ZipFile(path, 'r') as zip_object:
        # обработать каждый файл из архива
        for object in zip_object.filelist:
            with zip_object.open(object.filename) as file:
                # разархивировать файл
                text = file.read().decode("ansi")

                # распарсить данные
                parse_dictionary(text, dictionary)

словарь вида:

===> size=1
abate=201
accurse=133
afraid=3695
ago=3280
ah=5660
ahead=1397
aie=31
alarm-bell=3
alike=668
alive=2066
almost=8891
alone=8142
along=8532
altar=559
always=12844
among=9740
angel=1355
anger=1698
angle=535
angrily=639
another=15745
answer=12530
anything=8424
arm=11862
ask=20205
asleep=2080
avenue=785
away=21810
axe=392
back=24647
beast=2603
begin=17905

Answer 1

Для объектов, занимающих много памяти часто используют хеш объекта вместо самого объекта:

data = {}

for line in file:
    text, number = line.strip().split(":")
    data[hash(text)] = float(number)

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

при поиске тоже следует использовать хеш строки:

res = data.get(hash(string_))

Answer 2

Ну, в общем, примерно так оно и занимает, порядок цифр у меня примерно такой же получился на искусственных данных. Объекты питона весьма не маленькие:

import sys
from tqdm.auto import tqdm

n = 56_280_820
k = 10**22 - 1
m = 0
d = {}
s = 0
for _ in tqdm(range(n)):
    d[str(k)] = m
    k -= 1
    m = (m + 1) % 10
    s += 22 + 1 + 1

print(f'Размер данных в исходных символах: {s}')
dict_size = sum(sys.getsizeof(key) + sys.getsizeof(val) for key,val in d.items())
print(f'Словарь занимает: {dict_size}, элемент занимает: {dict_size//n}')
print(f'Примерный размер данных, которые должны быть в одном элементе словаря: {sum(map(sys.getsizeof, ("123", hash("123"), 1)))}')

Вывод:

Размер данных в исходных символах: 1350739680
Словарь занимает: 5549288852, элемент занимает: 98
Примерный размер данных, которые должны быть в одном элементе словаря: 116

То есть оно ещё как-то даже экономит место. Подозреваю на том, что хэш не хранится, хэш это адрес, по которому нужно данные положить. А так питон очень не экономный язык, особенно если разнородные данные в родных питоновских объектах хранить. Тут получилось, что порядка 100 байт на один элемент уходит: строка + хэш + int очень много занимает в питоне.

Answer 3

Сколько памяти нужно чтобы загрузить целиком текст из файла? Примерно два размера файла.

Еще один объём нужен чтобы затем порезать на строки.

Только потом вы начнёте строить словарь.

Файл - 1.5Gb. Лишняя память 4.5GB. Мои замеры показывают что сам словарь требует 7.6GB. В сумме вы вылезаете из 10GB.

Читайте строки напрямую. Скорость от это не пострадает, а памяти надо будет на 4.5GB меньше:

# f - открытый файл, не текст!!!
def parse_dictionary(f, dictionary):
    # распарсить данные
    size = 0

    for record in f:
        if record[:4] == "===>":
            size = int(record.split('=')[-1])

            if size not in dictionary:
                dictionary[size] = dict()
        elif size > 0:
            props = record.split('=')
            if len(props) == 2:
                dictionary[size][props[0]] = dictionary[size].get(props[0], 0) + int(props[1])

Читаем обычный файл:

with open(<filename>, 'r') as f:
    parse_dictionary(f, dictionary)

Читаем zip-архив:

with zipfile.ZipFile(zip_name, 'r') as zip_object:
    # обработать каждый файл из архива
    for obj in zip_object.filelist:
        with zip_object.open(obj.filename) as f:
            ff = (line.decode('ascii') for line in f)
            parse_dictionary(ff, dictionary)

Чтение обычного текстового файла с 56 миллионами записей требует на моём компьютере 46 секунд. Тот же файл из zip-архива читается за 93 секунды. Расход памяти одинаков - 7.6GB.

БЛОГ НА HUSL

python: оптимизация размера словаря

Ответы (3 шт):