Как в Python можно хранить список в памяти, чтобы он съедал меньше этой самой памяти

Question

[un1t]

Есть список или кортеж в нем храняться строки длинной от 10 до 13 символов. Таких строк несколько миллионов.
Такой список весит достаточно много. Если бы это был массив как в Си, наверно этот массив занимал бы меньше памяти. Можно ли как-то в питоне упаковать этот список подобным образом.
У списка уже известна длинна, ресайзить не нужно. Единственно что нужно, чтобы можно было по этой структуре пробежать с помощью for in или любым другим способом итерации.

И если знаете аналогичное решение для dict, мне это тожо интересно.

Comments

[rPman]

Я так понимаю in memory key-value database использовать не желаем?

p.s. в каком то старом проекте я 'с дуру навелосипедил' однотредовый сервер (не требовалось мульти) слушающий сокет (кстати пофиг что, хоть пайпы хоть unix) обрабатывающий 3-4 команды тупым case, без каких либо проверок на валидность, знающий длину строки, ожидаемую от клиента (это заметно повышает скорость) и т.п. он получился очень простым (в 1 страничку кода).

Не cмейтесь, этот мини-сервер и сам проект были оба на php, мне нужна была in memory key value database быстрее и проще любых имеющихся (помнится были неудобные проблемы с с установкой memcache на целевой сервер), я даже сделал в ней сохранение на лету данных на диск на автомате (с загрузкой при старте, позже я увидел эту фичу у redis), зато целевой проект мог быть спокойно перезапущен, не боясь потери данных.

[un1t]

>Я так понимаю in memory key-value database использовать не желаем?
Если они способны помочь то конечно желаем. Но я не вижу как Memcached или Redis могут помочь в этом вопросе.
Из БД сюда бы наверно подошла sqlite с типом базы в памяти.

Answer 1

[mrstrictly]

Может быть, если вас не пугает Си, и вы уверены, что на нем получится компактнее, его использовать его через ctypes, например? С поддержкой такого решения на *nix системах проблем не будет.
Еще один извращенный способ, который пришел в голову — подмонтировать рамдиск через fusepy, создать в рамдиске файл через zlib и ходить по нему seek-ом. :)
Ну и третий вариант — еще раз подумать. Строки у вас юникодные или ASCII? Нужно ли держать весь список в памяти (это требование производительности?) или приемлемо подгружать очередную порцию, например, фоново, когда текущая подходит к концу?

Comments

[un1t]

Строки ASCII, держать нужно все в памяти, да это требование производительности.

[mrstrictly]

Тогда можно попробовать при загрузке списка в память конвертировать элементы в числа в системе с основанием N, где N — длина вашего алфавита. Алфавит задан либо фиксировано, либо вычисляется отдельным проходом. Далее, в зависимости от задачи. Либо написать генератор, который преобразует числа обратно в строки, либо преобразовывать искомую строку в число и идти по списку.
Нашел, например, такой сниппет.
И код:

Python 2.7.4 (default, Apr 19 2013, 18:32:33) 
[GCC 4.7.3] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> import baseconv
>>> import sys
>>> 
>>> mybase = baseconv.BaseConverter('ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789abcdefghijklmnopqrstuvwxyz !,')
>>> mybase.to_decimal('hello, world!')
248148967587499711534423L
>>> sys.getsizeof(mybase.to_decimal('hello, world!'))
24
>>> mybase.from_decimal(248148967587499711534423L)
'hello, world!'
>>> sys.getsizeof(mybase.from_decimal(248148967587499711534423L))
34

То есть, задача решена. «Пожатая» с заданным алфавитом строка примерно на треть меньше строки в открытом виде. :)

Дальше можно еще пофантазировать на тему диапазонов, если ваша задача это позволяет. То есть, искать цепочки непрерывных диапазонов чисел и паковать их в такие структуры (синтаксис вымышлен): [1, 3, range(from=6, to=95), 97, ...]

[un1t]

Отличная идея! Думаю это мне подойдет, спасибо!

[JustAMan]

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

Самый дешёвый в реализации способ (однострочный) — сконвертировать list в tuple после его формирования. list резервирует память под дальнейший рост, даже если вы этого и не просили.

Answer 2

[xanep]

Мой тест показал, что 1 млн строк (10-13 символов) в питоновском списке занимает около 40 МБ в памяти. Что многовато, но не так уж плохо.

Протестировал ctypes вот так:
>>> from ctypes import *
>>> FixedSizeStr = c_char*13
>>> MillionStrings = FixedSizeStr*1000000
>>> ms = MillionStrings( *(FixedSizeStr(*str(i)) for i in xrange(1000000)))
Это +215 МБ?!..

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

Так что если вам дейстивтельно нужна оптимизация, то придется писать на С/С++ свой класс и экспортировать в питон. Все остальное будет полумерой.

Answer 3

[bogolt]

Использовать sqlite базу данных. Памяти ест мало, работает быстро ( разумеется при условии что вы ее открыли в памяти вызывав sqlite3.connect(":memory:"), а не в файле, но вам это то и нужно ).