Эффективная карта String-String в Python (или в)

https://stackoverflow.com/questions/4026359

26-09-2019
|

Вопрос

Мне нужна эффективная с памятью данных для хранения около миллиона пар клавишных пар, где клавиши представляют собой строки около 80 байтов, а значения представляют собой строки около 200 байт, общий ключ и размер стоимости составляет около 280 МБ. Мне также нужен эффективный поиск значений по ключу, предпочтительно хэш-карту. Настройка памяти должна быть максимально меньше, например, для 280 МБ полезных данных, структура данных не должна использовать более 300 МБ виртуальной памяти (включая malloc() накладные расходы и все остальное). Узор использования является следующим: мы начинаем с пустой структуры данных, и мы наполняем ее постепенно, никогда не меняем ключи и никогда не изменяем длину значений. Как и плюс, структура данных может поддерживать изменение длины значений, за счет на 100%-процентных накладных расходов (что означает, что для байтов значений x x Bytes может быть временно впустую в неиспользуемом буферном пространстве).

Мне нужен чистый модуль Python или встроенный модуль Python или реализация C, предпочтительно с (C) привязками Python. Я бы предпочел, если бы можно было сериализовать всю структуру данных на диск, и чтобы снова прочитать его обратно.

Просто чтобы доказать, что такая маленькая накладная возможна, я создал простой дизайн с открытая адресация, хеш-таблица из 1,25 миллиона элементов, содержащих 4-байтовые указатели на блоки данных 1 МБ, блоки данных, содержащие клавишу и длиной стоимости, как База-128 Varints. Отказ Этот дизайн имеет важное ограничение: он не позволяет удалять или изменять пары, не тратя их память. Согласно моим расчетам с 1 миллионами ключевых парных пар пары 280 байтов каждый, накладные расходы меньше на 3,6% (10 080 000 байтов). Пределы выше более щедры, они позволяют 20 000 000 байтов накладных расходов.

Я только что нашел http://www.pytables.org/ , который обеспечивает быстрый доступ и эффективную упаковку данных. Я должен проверить его более внимательно, чтобы проверить, соответствует ли он моим потребностям.

Решение 10

Поскольку я не смог найти какие-либо существующие решения, которые будут плотно упаковывать память, я решил реализовать его в C для себя. Увидеть мой дизайн с открытая адресация в вопросе.

Другие советы

Хорошо, грязный подход.

Используйте словарь Python для структуры данных. Я заполнил словарь Python с 1 миллионом случайных пар ключевых ценностей, где ключ составлял 80 символов и значение 200 символов. На моем компьютере потребовалось 360 844 КБ, который находится за пределами вашей спецификации не более 300 МБ, но я все равно предложу его в качестве решения, потому что это все еще довольно эффективно память.

Это также не дает ваше требование иметь C API. Я не уверен, что вам нужно c, но по мере того, как вопрос помечен Python и не хватает метки C, я предложу чистый Python, чтобы увидеть, просто может ли он соответствовать счет.

Относительно настойчивости. Используйте модуль CPICKLE. Это очень быстро и, опять же, грязь простая. Чтобы сохранить словарь:

cPickle.dump(mydict, "myfile.pkl")

Перезагрузить словарь:

mydict = cPickle.load("myfile.pkl")

Вторая грязь-простая идея - использовать shelve Модуль, который в основном на основе диска Python словарь. Настройка памяти очень низкая (все на диске). Но это также намного медленнее.

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

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

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

Итак, вот что вы делаете.

Вы создаете массив:

struct {
    char value[80];
    char *data;
} key;

И вы держите этот массив отсортированы.

Если вы ключи могут дублировать, то вам нужно:

struct link {
    char *data;
    link *next;
}

struct {
    char value[80];
    link *data;
} key;

(Мой C ржавый, но это сущность IT), последний имеет каждый ключ, указывающий на связанный список значений.

Тогда поиск - простой бинарный поиск. «Боль» поддерживает этот массив и вставлять / удалять ключи. Это не так болезненно, как звучит, но он экономит много памяти, особенно на 64-битных системах.

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

Итак, расходы в создании массива, копирования и памяти Compacting (если вы «знаете», у вас будет миллион строк и может принять к этому, то Malloc (1000000 * Sizeof (Key)) сразу же спасет вас Некоторые копирование во время расширения).

Но не бойся, как только он будет и работает, производительность довольно хорошая. Современные процессоры на самом деле довольно хорошо копируют 100 м блоков памяти вокруг.

Так же, как в сторону, я только что сделал что-то подобное в Java. На 64-битной JVM карта с 25м записей составляет 2 г ОЗУ. Мое решение (используя аналогичные методы к этому) имеет около 600 м). Java использует больше указателей, чем C, но предпосылка одинакова.

Вы пытались использовать простое дикт? Большинство ваших данных в строках, поэтому накладные расходы могут соответствовать вашим требованиям.

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

from random import choice
from string import letters
from hashlib import sha1

def keygen(length):
    return "".join(choice(letters) for _ in xrange(length))

def gentestdata(n=1000*1000):
    # return dict((sha1(keygen(80)).digest(), keygen(200)) for _ in xrange(n))
    d = {}
    for _ in xrange(n):
        key = sha1(keygen(80)).digest()
        assert key not in d
        value = keygen(200)
        d[key] = value
    return d

if __name__ == '__main__':
    d = gentestdata()

На моем коробке Ubuntu эта вершина на 304 МБ памяти:

2010-10-26 14:26:02 hbrown@hbrown-ubuntu-wks:~$ ps aux | grep python
[...]
hbrown   12082 78.2  7.5 307420 303128 pts/1   S+   14:20   4:47 python

Достаточно близко? Это питон, а не C.

Позже: также, если ваши данные несколько избыточны, вы можете gzip ценности. Это время против промежуточного компромисса.

Использование SQLite - хорошая идея. Быстрая реализация может сказать, если вы достаточно быстро с небольшим усилием.

Если вы решите, что вы должны катиться, я бы порекомендовал следующее:

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

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

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

Однако, если вам необходимо запустить любой CMP / Copy и т. Д. Операции на этих строках, помните, что со следующими гарантиями вы можете немного сжимать или много из этих строковых операций:

Все элементы CPU слово выровнены
Все байты Pad (например,) 0
Вы можете смело прочитать «за пределы» конца строки, если вы не пересекаете границу процессора

Хеш-таблица для индекса. Словарь тоже будет работать, но это имеет смысл только в том случае, если потенциальная деградация / перефразирование будет серьезным вопросом. Я не знаю никаких «акций» в реализации HaSthable для C, но должен быть один, верно? Правильно? Просто замените ассигнования с вызовами на аллекатор Arena.

Месторасположение памяти

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

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

Если вам нужно поддерживать «забавные персонажи» / Unicode, нормализовать свои строки, прежде чем хранить их.

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

http://docs.cython.org/library/struct.html.

Apache Portable Runtime (AKA APR) имеет хеш-таблица на базе C. Вы можете увидеть документацию в http://apr.apache.org/docs/apr/0.9/group_апрель_hash.html.

С APR_HASH_T все, что вы храните, является пустотой *. Так что это дает вам полный контроль над ценностями. Поэтому, если вы хотите, вы можете хранить указатель на 100 байт-блок вместо фактической длины строки.

Джуди должна быть эффективной памяти: http://judy.sourceforge.net/
(Ориентиры: http://www.nothings.org/computer/judy/, см. «Размер структуры данных»).
Смотрите также: http://www.dalkescientific.com/python/pyjudy.html.

Также,

Для ключей фиксированного размера есть http://panthema.net/2007/stx-btree/ В C ++ (я уверен, что с пользовательскими функциями C его можно использовать из CPYthon). Если набор данных позволяет этому, вы можете хранить клавиши переменной длины в значение и использовать хеш или префикс ключа переменной длины в качестве ключа фиксированной длины.

Тот же логика применяется к http://google-opensource.blogspot.ru/2013/01/c-containers-that-save-memory-andtime.html. и http://code.google.com/p/sparsehash/ - sttead из используя тяжелый STD :: string в качестве ключа, используйте 32-битный или 64-битный целочисленный ключ, что делает его как-то из реальной ключа переменной длины.

Лицензировано под: CC-BY-SA с атрибуция

Не связан с StackOverflow