Эффективное вычисление первой 20-значной подстроки для повторения в десятичном разложении числа Пи
проблема
Pi = 3.14159 26 5358979323846 26 433... поэтому первая двузначная подстрока для повторения - 26.
Какой эффективный способ найти первую 20-значную подстроку для повторения?
Ограничения
У меня около 500 гигабайт цифр числа Пи (1 байт на цифру) и около 500 гигабайт свободного места на диске.
У меня около 5 гигабайт оперативной памяти бесплатно.
Меня интересует эффективный алгоритм, который работал бы для произвольных последовательностей, а не конкретный ответ для самого Pi. Другими словами, я не заинтересован в решении формы "print 123....456", даже если число, которое оно печатает, является правильным.
Что я пробовал
Я помещаю каждую подстроку в хеш-таблицу и сообщаю о первом столкновении.
(Хеш-таблица построена в виде массива отсортированных связанных списков. Индекс в массиве задается нижними цифрами строки (преобразуется в целое число), а значение, хранящееся в каждом узле, является местоположением в раскрытии Pi. где подстрока впервые появилась.)
Это работало нормально, пока у меня не кончилась память.
Для масштабирования на более длинные последовательности я рассмотрел:
Генерация хеша для всех подстрок начинается в определенном диапазоне, а затем продолжается поиск по оставшимся цифрам. Для этого необходимо повторно просканировать всю последовательность Пи для каждого диапазона, поэтому становится порядка N ^ 2
Bucket сортирует набор из 20-значных подстрок в несколько файлов, а затем использует хеш-таблицу, чтобы найти первый повтор в каждом файле отдельно. К сожалению, с помощью этого метода у меня заканчивается свободное место на диске, поэтому потребуется 20 проходов через данные. (Если я начну с 1000 цифр, я получу 1000 20-значных подстрок.)
Хранение 2 цифр числа Пи на байт, чтобы освободить больше памяти.
Добавление дискового хранилища резервных копий в мою хэш-таблицу. Я волнуюсь, что это будет вести себя очень плохо, так как нет очевидного месторасположения.
Есть ли лучший подход?
Обновить
Я попробовал метод qsort Адриана Маккарти, но он показался немного медленнее, чем хеширование для поиска дубликатов
Я посмотрел на предложение btilly MapReduce для распараллеливания алгоритма, но оно было сильно связано с вводом-выводом на моем одном компьютере, поэтому не подходит для меня (с моим единственным дисководом)
Я реализовал метод суперкатера, чтобы провести прошлую ночь, разбивая файлы и ища 19-значные подстроки в первых 18 млрд. Цифр.
Было найдено 16 совпадений, поэтому я использовал предложение Джарреда, чтобы перепроверить 19-значные совпадения и найти первое 20-значное совпадение.
Для поиска 18 миллиардов цифр потребовалось 3 часа, чтобы разделить файлы, и 40 минут, чтобы затем повторно просмотреть файлы в поисках совпадений.
Ответ
20-значная подстрока 84756845106452435773 находится в позициях 1,549,4062,637 и 17,601,613,330 в десятичном расширении числа Pi.
Большое спасибо всем!
4 ответа
Ваш набор данных довольно большой, поэтому необходимо будет что-то вроде "разделяй и властвуй". Я хотел бы предложить, чтобы в качестве первого шага вы поделили проблему на некоторое количество частей (например, 100). Начните с проверки наличия в файле дублированных 20-значных последовательностей, начинающихся с 00, затем посмотрите, есть ли в нем последовательности, начинающиеся с 01 и т. Д. До 99. Запустите каждый из этих "основных проходов", записав в файл все 20-значные последовательности, начинающиеся с правильного номера. Если первые две цифры постоянны, вам нужно будет выписать только последние 18; поскольку 18-значное десятичное число будет помещаться в 8-байтовый "длинный", выходной файл, вероятно, будет содержать около 5 000 000 000 чисел, занимая 40 ГБ дискового пространства. Обратите внимание, что может быть целесообразно создавать более одного выходного файла за раз, чтобы избежать необходимости читать каждый байт исходного файла 100 раз, но производительность диска может быть лучше, если вы просто читаете один файл и пишете один файл,
После того, как вы сгенерировали файл данных для определенного "основного прохода", необходимо определить, есть ли в нем дубликаты. Подразделение этого на некоторое количество меньших секций на основе битов в числах, сохраненных в нем, может быть хорошим следующим шагом. Если разделить его на 256 меньших разделов, каждый раздел будет иметь где-то около 16-32 миллионов номеров; пять гигабайт оперативной памяти, которую можно было использовать, можно использовать для буферизации миллионов номеров для каждого из 256 сегментов. Запись каждого куска из миллиона чисел потребовала бы случайного поиска на диске, но число таких записей было бы довольно разумным (вероятно, около 10 000 операций поиска на диске).
Когда данные разбиты на файлы по 16–32 миллиона номеров, просто прочитайте каждый такой файл в память и найдите дубликаты.
Описанный алгоритм, вероятно, не является оптимальным, но он должен быть достаточно близким. Наибольший интерес представляет тот факт, что сокращение вдвое числа основных проходов сократит вдвое количество операций чтения исходного файла данных, но увеличит вдвое время, необходимое для обработки каждого прохода после обработки его данных. скопировано. Я бы предположил, что использование 100 проходов через исходный файл, вероятно, не является оптимальным, но время, необходимое для всего процесса с использованием этого коэффициента разделения, будет довольно близко к времени, в котором используется оптимальный коэффициент разделения.
Это интересная проблема.
Сначала давайте вернемся к номерам конвертов. Любая конкретная последовательность из 20 цифр будет соответствовать один раз в 10 20. Если мы перейдем к n-й цифре, у нас будет примерно n 2/2 пар из 20-значных последовательностей. Таким образом, чтобы иметь хорошие шансы найти совпадение, нам, вероятно, понадобится чуть больше 10 10. Предполагая, что мы берем 40 байтов на запись, нам понадобится что-то порядка 400 ГБ данных. (На самом деле нам нужно больше данных, чем это, поэтому мы должны быть готовы к чему-то более терабайту данных.)
Это дает нам представление о необходимом объеме данных. Десятки миллиардов цифр. Сотни ГБ данных.
Теперь вот проблема. Если мы используем какую-либо структуру данных, которая требует произвольного доступа, время произвольного доступа определяется скоростью диска. Предположим, что ваш диск вращается со скоростью 6000 об / мин. Это 100 раз в секунду. В среднем нужные вам данные находятся на полпути вокруг диска. Таким образом, вы получаете в среднем 200 случайных обращений в секунду. (Это может варьироваться в зависимости от аппаратного обеспечения.) Доступ к нему 10 миллиардов раз займет 50 миллионов секунд, то есть больше года. Если вы читаете, затем пишете и в конечном итоге нуждаетесь в 20 миллиардах точек данных - вы превышаете прогнозируемый срок службы вашего жесткого диска.
Альтернативой является обработка пакета данных таким образом, чтобы вы не имели случайного доступа. Классика - делать хорошую внешнюю сортировку, такую как сортировка слиянием. Предположим, что у нас есть 1 терабайт данных, которые мы читаем 30 раз, записываем 30 раз во время сортировки. (Обе оценки выше, чем необходимо, но я рисую здесь худший случай.) Предположим, наш жесткий диск имеет постоянную пропускную способность 100 МБ / с. Затем каждый проход занимает 10 000 секунд, в течение 600 000 секунд, что немного меньше недели. Это очень выполнимо! (На практике это должно быть быстрее, чем это.)
Итак, вот алгоритм:
- Начнем с длинного списка цифр, 3141...
- Превратите это в намного больший файл, где каждая строка состоит из 20 цифр, а затем место, где это появляется в пи.
- Сортировать этот файл побольше.
- Поиск отсортированный файл для любых дубликатов.
- Если они найдены, верните первое.
- Если ничего не найдено, повторите шаги 1-3 с другим большим количеством цифр.
- Объедините это в предыдущий отсортированный файл.
- Повторите этот поиск.
Теперь это здорово, но что если мы не хотим брать неделю? Что если мы хотим запустить несколько машин? Это оказывается на удивление легко. Есть хорошо известные алгоритмы распределенной сортировки. Если мы разделим исходный файл на куски, мы можем распараллелить оба шага 1 и 4. И если после шага 4 мы не найдем совпадения, то мы можем просто повторить с начала больший входной чанк.
На самом деле этот шаблон очень распространен. Все, что действительно меняется, - это превращать исходные данные в вещи для сортировки, а затем смотреть на соответствующие группы. Это алгоритм http://en.wikipedia.org/wiki/MapReduce. И это будет хорошо работать для этой проблемы.
Trie
RBarryYoung отметил, что это превысит пределы памяти.
Структура данных Trie может быть соответствующей. За один проход вы можете создать дерево с каждым префиксом, который вы видели, до длины n (например, n = 20). Продолжая обработку, если вы когда-нибудь достигнете узла на уровне n, который уже существует, вы только что нашли дублирующую подстроку.
Суффикс соответствия
Другой подход заключается в обработке раскрытия как строки символов. Этот подход находит общие суффиксы, но вам нужны общие префиксы, поэтому начните с изменения строки. Создайте массив указателей, каждый указатель будет указывать на следующую цифру в строке. Затем сортируйте указатели, используя лексикографическую сортировку. В Си это будет что-то вроде:
qsort(array, number_of_digits, sizeof(array[0]), strcmp);
Когда qsort завершится, аналогичные подстроки будут смежными в массиве указателей. Таким образом, для каждого указателя вы можете выполнить ограниченное сравнение строк с этой строкой и строкой, на которую указывает следующий указатель. Опять же в C:
for (int i = 1; i < number_of_digits; ++i) {
if (strncmp(array[i - 1], array[i], 20) == 0) {
// found two substrings that match for at least 20 digits
// the pointers point to the last digits in the common substrings
}
}
Сортировка (обычно) O(n log_2 n), а поиск - O(n).
Этот подход был вдохновлен этой статьей.
Возможно, что-то подобное будет работать:
Поиск повторяющихся подстрок длины 2 (или небольшого базового случая), указание начала записи S = {s_i}
Для n=3..N ищите подстроки длины n из индексов в S
На каждой итерации обновляйте S с помощью подстрок длины n
при n=20 ваши первые два ответа будут вашим ответом
Возможно, вы захотите изменить начальный размер и размер шага (возможно, нет необходимости каждый раз шагать по 1)