Неправильно посчитал. 62^6 это количество ключей, а одна запись в файле {ключ, хэш} это минимум 43 байта, т.е. умножай на 43 и будет ~2 Тб.

Заглянул туда, там самая большая таблица на 1.3*10 ¹⁶ ключей, а ты замахнулся на 3.2*10 ²¹ (это 62 ¹² ), оно больше в 246000 раз.

Да, как я понимаю. Например у тебя полная таблица 2 Тб, ты хочешь ужать до 2 Гб, т.е. в 1024 раза, просто делаешь размер цепочки 1024 и генеришь под нее таблицу, размер записи не меняется, сама запись состоит из {ключ первого в цепочке, хэш последнего}.


Удобнее несколько таблиц взять, чем сделать одну для ключей переменной длины. Ключ переменной длины займет дополнительное место, запись переменной длины создаст проблемы при поиске.

Я так понимаю тема не сильно популярная, поэтому берут готовый софт и таблицы качают.

Я немного поразмышлял над генератором таблиц - задача непростая. Непонятно как запараллелить.

Например имеем последовательность делим ее на цепочки по 3


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


Т.е. дополнительно надо как-то проверять что промежуточные ключи (или их хэши) не присутствуют в цепочке.
Допустим один поток считает от k1


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

Как вариант: битмап для первого миллиарда ключей, займет памяти всего 128 Мб, а дальше каждый поток стартует с очередного ключа (1,2,3 и т.д.) и пилит свою последовательность разрубая ее на цепочки нужной длины, как наткнулся на ключ меньше лярда - проверка по битмапу - не посчитано ли дальше другим потоком, т.е. синхронная проверка очень малого количества ключей. Но тут еще надо добавить контроль зацикливания и перетекания в другую цепочку, а может и не надо, хз сколько это добавит лишнего.

Нет гарантии что цепочки не сольются и разные потоки начнут считать одно и то же. Например



I/O тут очень мало, в основном расчеты. Цепочка из миллионов пар записывается в 40 байт, а считается она от секунды до нескольких минут. С сортировкой проблему можно порешать хранением в несколько файлов: накопил в map миллион записей - сбросил в файл в сортированном виде и т.д. в конце смержил все файлы в один. Или организовать файл постранично в виде дерева, как SQL-сервера хранят кластерный индекс.

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

Таким образом будут обсчитаны все последовательности для ключей до миллиарда и перекрытие цепочек будет незначительное.
Но непонятным остается вопрос: сколько дыр осталось? Т.е. сколько ключей не попало ни в одну из цепочек.
Приблизительно покрытие можно прикинуть посчитав общее количество ключей в обсчитанных цепочках.

Узкое место это проверка хэша из результата в таблице из ранее посчитанного. Это займет большее время чем сам расчет цепочки.

Это длина одной цепочки. За счет нее получается сжатие, т.е. экономия памяти, но увеличение времени расчета. Читай алгоритм 22046586 , я там это число назвал N.

Выбор конкретного значения зависит от размера ключа и желаемого размера таблицы. Пример расчета я тоже давал

Т.е. для того случая t = 4.7*10 ¹⁰

Писали, но задача была другая: выбрать уникальные строки из большого текстового файла.

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

Давай на примере: есть последовательность


т.е. взяли первый ключ, самый маленький, Berlin-1939-01-01. Посчитали его хэш (h1), затем посчитали редукцию h1 и получили какой-то ключ, например k147. Мы заранее не знаем какой ключ получим, узнаем только посчитав, но знаем что результат неизменен, т.е. редукция h1 всегда выдает k147. Затем считаем хэш k147 (h147) и т.д. у нас выстраивается цепочка нужной длины.

Пусть t=4, приведенная цепочка записывается в таблицу как {k1, h92}, ключ первого и хэш последнего, остальные три пары никуда не пишем потому что взяв k1 восстановим всю цепочку, отсюда сжатие в 4 раза.


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

Хранить обработанные ключи мы не можем даже биткартой из-за их огромного количества.

Поздравляю, ты усовершенствовал исходный алгоритм ))

Храня цепочку как {ключ первый, ключ последний} при 12 символах ключа мы займем 18 байт против 43-х, т.е. запись будет в 2.4 раза компактней.

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

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

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

Сомневаюсь что получится. Там ключ большой, как следствие гигантское количество вариантов ключа такого размера. 12 символов это всего ничего, но уже дофига для данного алгоритма 22047496

PS Я вижу только одно применение данному алгоритму, но тут это запрещено обсуждать. И примеры на радужном сайте как раз про это.

Для данного алгоритма невозможно, т.к. ключ состоит из "хэша предыдущего блока, случайного числа и суммы контрольных чисел транзакций, прошедших за последние 10 минут", т.е. значительно больше неподъемных 12 символов.

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

PS Получается что у майнеров всего 2 ³² вариантов хэшей и не факт что есть хоть один, который даст требуемое количество ноликов на конце, т.е. есть комбинации которые заведомо невозможно намайнить.