Самый эффективный способ хранения 8M + sha256 хэшей

Во-первых, давайте посмотрим, почему это так велико.

Каждый из них имеет 32 байта. Это означает, что для хранения в двоичной форме требуется, например, 32 байта, например, для хранения bytes или объекта bytearray . Все идет нормально.

Но все объекты Python имеют заголовки, как правило, порядка 24-64 байт. С помощью быстрой проверки похоже, что объекты bytes занимают дополнительные 36 байт на 32 бита (возможно, плюс выравнивание) и 48 на 64 бита, по крайней мере, на двух версиях CPython, которые я проверил.

Итак, как вы можете избавиться от этого 150% дополнительного хранилища? Упакуйте байты в один гигантский массив, как bytes или bytearray . Тогда у вас есть 48 байт плюс плюс 32 за хэш, вместо 48 + 32 за хэш. Когда вам нужно получить доступ к хешу, если у вас есть индекс, это всего лишь срез [index*32:(index+1)*32] .

Кроме того, в зависимости от того, как вы создали bytes , может быть некоторая переполнение. Вы можете проверить, что если sys.getsizeof(s) - sys.getsizeof(b'') > len(s) , вам нужно нарезать все объекты для создания новых копий без дополнительного заполнения.

В любом случае, теперь у вас есть 8M дополнительных индексов. Если они преходящи, это нормально, но если вы храните их как int s в слотах для значений dict, то каждый из них также имеет заголовок. Из быстрого теста, поверх 4 байтов для реального хранилища (для int под 1 << 31), есть 24-байтовый заголовок как в 32, так и в 64-битных (хотя очень маленькие ints, по-видимому, могут быть переполнены в заголовок). Таким образом, все это сокращает ваши 48 байтов отходов до 28 байтов, что не очень удобно.

Вы можете использовать некоторую форму упакованного хранилища, например, модуль array . Тип массива I использует только 4 байта на целое число. Но тогда вам нужны индексы в массиве, которые … та же проблема, которую вы только что решили.

Но вам даже не нужны индексы – если вы храните ключи в массиве, индекс любого ключа уже является индексом хэша в строке байта (деленный на 32), правильно?

Это работает только в том случае, если вы можете хранить ключи в каком-то компактном массиве. Если они все вокруг одного размера, вы можете сделать это, снова используя тот же самый «гигантский трюк». И в вашем случае они – ключи – также 32-байтовые хэши. Таким образом, вам просто нужно сохранить как гигантские байтовые строки, отсортированные по ключевым значениям (см. Модуль bisect так что вам не нужно писать этот код самостоятельно).

Конечно, используя алгоритмы бинарного поиска вместо хэширования, вы делаете поиск и вставляете логарифмический, а не постоянный. И, хотя log (8M) составляет только около 16, что намного лучше, чем 8M, он по-прежнему 16x, как плохо, как 1. Но это фактически то, что вы получаете от идеально настроенной реляционной базы данных, за исключением того, что вам не нужно делать любую настройку, и это все в памяти, и нет лишних накладных расходов, поэтому это должно быть улучшение по сравнению с тем, что вы пробовали до сих пор.

Разумеется, вы могли бы создать обычную хеш-таблицу в Python, используя два гигантских байтовых массива в качестве хранилища и два array('I') качестве ваших индексов. Но это намного больше работы, поэтому я бы попробовал это в первую очередь.

Используйте библиотеку sqlite3 для хранения хешей в базе данных. Встроенная база данных sqlite позаботится об управлении памятью для вас, используя буферизацию памяти и хранение на диске, насколько это возможно, чтобы удовлетворить ваши запросы.

Достаточно простая таблица:

 import sqlite3 connection = sqlite3.connect('/tmp/hashes.db') connection.execute('CREATE TABLE hashes (key UNIQUE, value)') 

затем используйте:

 with connection: cursor = connection.cursor() sql = 'INSERT INTO hashes VALUES (?, ?)' cursor.executemany(sql, ((key1, hash1), (key2, hash2), ....)) 

и вы можете запросить базу данных с помощью:

 with connection: cursor = connection.cursor() sql = 'SELECT hash FROM hashes WHERE key=?' cursor.execute(sql, (key,)) hash = cursor.fetchone() if hash is not None: hash = hash[0] 

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

Вы можете использовать array.array или array.array для хранения ключей и значений без каких-либо накладных расходов, что означает, что 8M-записи вписываются в 488 MiB. Тогда вы можете написать хеш-таблицу поверх этого. Это довольно неудобно, поэтому, возможно, вы захотите использовать внешнюю библиотеку, например, cffi для работы с плотно упакованными структурами и массивами.

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

Я написал более сложный ответ отдельно, потому что я не уверен, что это сработает для вас, но:

dbm – это база данных с ключом, которая работает почти так же, как и dict (чьи ключи и значения представляют собой строки bytes ), за исключением того, что при необходимости они привязаны к значениям диска и страниц.

Это намного проще, чем база данных SQL, которая имеет три огромных преимущества.

• Вам не нужно изменять свой код из hash = hashes[thingy] в hash = db.execute('SELECT * FROM Hashes WHERE Thingy = ?', (thingy,)).fetchone()[0] , вы просто продолжаете использовать hashes[thingy] .

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

• Хорошая часть базы данных будет кэширована в памяти, что ускорит ее работу.

Несмотря на то, что он называется «базой данных Unix», по крайней мере одно из различных модулей модулей dbm существует на каждой платформе. См. Dbm: не только для Unix для деталей.

Так как это хэш, вы можете реализовать словарь в файле с помощью функции seek() / tell() …. Вам нужно предварительно создать файл с заданным размером (10 ГБ или что-то еще) …

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

 offset = dict_hash(in_key) dict_file.seek(offset) hashval = dict_file.read(hash_len) 

что-то вроде этого (используется для таких вещей, как это в C, не было сделано в python, но базовая поддержка файлов одинакова …)

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

Вот мои функции индексирования для Хэша

Сначала у нас есть эта функция для быстрой индексации хэша.

 ZequebaHashB[bvc_, yvc_, avc_] := {Drop[Flatten[Reap[ Module[{a34 = bvc, a35 = yvc, rt2 = avc, z75, zler}, z75 = 1; zler = Total[BCC[Re[Floor[Px[a34, a35^2]]], a35^3]]; Label[Start5629]; Sow[Denominator[zler/FiveItt[a35, z75]], yvc]; z75 = z75 + 1; If[z75 >= rt2 + 1, Goto[end5629]]; Goto[Start5629]; Label[end5629]; ];]], 1], Total[BCC[Floor[Re[Px[bvc, yvc^2]]], yvc^3]], bvc}; 

Во-вторых, у нас есть эта функция для получения индекса Rainbow хэша

 RainbowHashXG[zf_, xz_, zd_, fd_] := Column[{Table[ Flatten[Drop[ZequebaHashB[zf + xf, xz, zd], -2]], {xf, 0, fd - 1}], zf}]; 

Теперь, когда вы пытаетесь выполнить эти функции

 Table[ZequebaHashB[Hash[xu, "SHA512"], 2, 5], {xu, 1, 10}] {{{1, 2, 3, 4, 5}, 427, 

12579926171497332473039920596952835386489858401292624452730263741969 \ 1347390182282976402981790496477460666208142347425205936701161323553455 \ 43156774710409041}, {{1, 1, 1, 1, 5}, 396, 37854471215291391986149267401049113295567628473597440675968265868739 \ 3920246834469920751231286910611366704757913119360843344094113813460828 \ 6029275267369625}, {{1, 1, 1, 2, 5}, 378, 71668700870008575285238318023246235316098096074289026150051114683524 \ 8893999285271969471146596174190457020264703584540790263678736452792747 \ 5984118971455163} , {{1, 2, 3, 4, 5}, 377, 33095966240281217830184164668404219514626500609945265788213543056523 \ 6612792119604718913684957565086394439681603253709963629672412822522528 \ 4694992131191098}, {{1, 2, 1, 4, 5}, 363, 86087420302049294430262146818103852368792727362988712093781053088200 \ 5531339261473092981846995901587757487311471069416835834626804973821926 \ 684090578667825}, {{1, 1 , 3, 2, 5}, 374, 18586086601485268646467765285794047467027639305129763019055665664163 \ 2819380637 531124748570695025942793945139516664108034654512831533948189 \ 743738184270224}, {{1, 1, 3, 1, 1}, 380, 72109882448403363840259529414390721196358024901859951350044294221621 \ 3409708767088486766304397692430037767785681544787701437132358156239382 \ 5256452011168475}, {{1, 2, 3, 4, 5}, 397, 22760214977694020069971224118591466739483553732805530503408373418535 \ 1711847169063849360187954434350675389187296376543635586233555068331343 \ 3001046271103001}, { {1, 2, 1, 4, 5}, 369, 11906459655144790308170064541982556680120578173098014909650827827844 \ 2313493552143468785692756291539132782149145837942478466345517803751070 \ 21641806135272354}, {{1, 1, 3, 2, 5}, 382, ​​88155955858214177781767282869972903505820511583564376117417944351446 \ 8458315518532665921338085983977628624644833036888032312932654944528755 \

1. 5410805140620789}}

    Table[RainbowHashXG[Hash[xu, "SHA512"], 2, 5, 5], {xu, 1, 10}] 

   {{{{1, 1, 1, 1, 5}, {1, 2, 3, 4, 5}, {1, 1, 3, 2, 5}, {1, 2, 1, 4, 1} , {1, 1, 3, 1, 5}},
   (1, 2, 1, 4, 5}, {1, 1, 3, 2, 5}, {1, 2, 3, 4, 1}, {1, 1, 1, 1, 4, 5}, {1, 1, 3, 2, 5}, {1, 2, 3, 4, 1} 1, 1, 5}, {1, 2, 3, 4, 5}},
   (1, 2, 3, 4, 5}, {1, 1, 1, 1, 5}, {1, 2, 3, 4, 5}, {1, 1, 1, 1, 1, 5}, {1, 2, 3, 4, 5} 3, 2, 5}, {1, 2, 1, 4, 1}},
   (1, 2, 3, 4, 5}, {1, 1, 1, 1, 5}, {1, 2, 3, 4, 5}, {1, 1, 1, 1, 1, 1, 5}, {1, 2, 3, 4, 5}, {1, 2, 3, 4, 5} 3, 2, 1}, {1, 2, 1, 4, 5}},
   (1, 2, 3, 4, 1}, {1, 1, 3, 1, 5}, {1, 2, 1, 4, 5}, {1, 1, 1, 1, 3, 1, 5}, {1, 1, 3, 1, 5} 3, 2, 5}, {1, 1, 3, 1, 5}},
   (1, 1, 1, 1, 5}, {1, 2, 3, 4, 5}, {1, 1, 3, 2, 5}, {1, 2}, {1} 1, 4, 1}, {1, 1, 3, 1, 5}},
   (1, 2, 3, 4, 1}, {1, 1, 1, 2, 5}, {1, 2, 3, 4, 5}, {1, 2, 1, 2, 3, 4, 1}, {1, 1, 1, 2, 5}, {1, 2, 3, 4, 3, 4, 5}, {1, 1, 3, 2, 5}},
   (1, 1, 3, 1, 5}, {1, 2, 3, 4, 1}, {1, 1, 1, 2, 5}, {1, 2}, {1, 1, 3, 1, 5}, {1, 1, 1, 2, 5} 3, 4, 5}, {1, 1, 3, 1, 5}},
   (1, 1, 1, 2, 5}, {1, 2, 3, 4, 5}, {1, 1, 3, 1, 1}, {1, 2, 1, 4, 5}, {1, 2, 1, 4, 1}},
   (1, 2, 1, 4, 5}, {1, 1, 3, 1, 1}, {1, 2, 3, 4, 5}, {1, 1, 1, 1, 3, 1, 1}, {1, 2, 3, 1, 1}, {1, 2, 1, 2, 5}, {1, 2, 3, 4, 5}},
   88155955858214177781767282869972903505820511583564376117417944351446 \ 8458315518532665921338085983977628624644833036888032312932654944528755 \ 5410805140620789}}

    FiveItt[x98_, cc5_] := DifferenceRoot[ Function[{\[FormalY], \[FormalN]}, {-cc5 - cc5 \[FormalY][\[FormalN]] + \[FormalY][1 + \[FormalN]] == 0, \[FormalY][1] == 1, \[FormalY][2] == cc5}]][x98]; 

   BCC [x55_, g77_]: = Drop [Сгладить [Reap [Module [{x45 = x55, z7 = 0, z8 = 0, z9, g7 = g77, bell},

   z7 = Если [x45 / FiveItt [Length [IntegerDigits [x45, g7]], g7] <= 1, If ​​[x45 == 1, 1, Length [IntegerDigits [x45, g7]] – 1], Length [IntegerDigits [ x45, g7]]]; bell = FiveItt [z7 – 1, g7]; z9 = g7 ^ (z7 – 1);

   Этикетка [SPo]; z8 = Если [IntegerQ [x45 / g7] && x45> g7, Quotient [x45 – bell – (1 / (2 * g7)), z9], If [x45 <= g7, x45, Quotient [x45 – bell, z9 ]]]; Высевают [Z8]; x45 = x45 – (z8 * (z9)); z7 = z7 – 1; z9 = z9 / g7; bell = bell – z9;

   Если [z7 <1, Перейти к [EnD], Перейти к [SPo]];

   Этикетка [КНЦ];

   ]]], 1];

   Px = Скомпилировать [{{x1d, _Complex}, {si1d, _Real}}, Module [{x1c = x1d, si1c = si1d}, x1c + 1/2 (Floor [Re [(- 4 + si1c + Sqrt [(- 4 + si1c) ^ 2

   • 8 (-2 + si1c) (-1 + x1d)]) / (2 (-2 + si1c))]] + Этаж [Im [(- 4 + si1c + Sqrt [(- 4 + si1c) ^ 2 + 8 (-2 + si1c) (-1 + x1d)]) / (2 (-2 + si1c))]] I) (-4 + si1c – (-2 + si1c) (Floor [Re [(- 4 + si1c + Sqrt [(- 4 + si1c) ^ 2 + 8 (-2 + si1c) (-1 + x1c)]) / (2 (-2 + si1c))]] Floor [Im [(- 4 + si1c + Sqrt [(- 4 + si1c) ^ 2 + 8 (-2 + si1c) (-1 + x1c)]) / (2 (-2 + si1c))]] I))], CompilationTarget -> "C" «RuntimeOptions» -> «Скорость»];