Эффективное вычисление первой 20-значной подстроки для повторения в десятичном расширении Pi

Ответ 1

Ваш набор данных довольно большой, поэтому вам потребуется какое-то "разделение и победа". Я бы предположил, что в качестве первого шага вы разделите проблему на некоторое количество частей (например, 100). Начните с просмотра, если файл имеет дублированные 20-значные последовательности, начинающиеся с 00, а затем посмотрите, есть ли у него начало с 01 и т.д. До 99. Запустите каждый из этих "основных проходов", записав в файл все 20-значные последовательности, начинающиеся с правильного числа. Если первые две цифры являются постоянными, вам нужно будет только выписать последние 18; так как 18-значное десятичное число будет вписываться в 8-байтовый "длинный", выходной файл, вероятно, будет содержать около 5 000 000 000 номеров, занимая 40 ГБ дискового пространства. Обратите внимание, что может быть полезно создать более одного выходного файла за раз, чтобы избежать необходимости считывать каждый байт исходного файла 100 раз, но производительность диска может быть лучше, если вы просто читаете один файл и записываете один файл.

Как только вы сгенерировали файл данных для определенного "основного прохода", необходимо определить, есть ли в нем дубликаты. Разделение его на некоторое количество небольших разделов на основе бит в числах, хранящихся в нем, может быть хорошим следующим шагом. Если он подразделяется на 256 небольших разделов, каждый раздел будет содержать около 16-32 миллионов номеров; пять гигабайт оперативной памяти можно использовать для буферизации миллиона чисел для каждого из 256 кодов. Для записи каждого фрагмента в миллион номеров потребуется случайный поиск диска, но количество таких записей будет довольно разумным (вероятно, около 10 000 обращений к диску).

Как только данные будут разделены на файлы размером 16-32 миллиона номеров, просто прочитайте каждый такой файл в памяти и найдите дубликаты.

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

Ответ 2

Это интересная проблема.

Сначала позвольте сделать некоторые из номеров конвертов. Любая конкретная последовательность из 20 цифр будет совпадать один раз в 10 ²⁰. Если мы выйдем на n-ю цифру, мы получим примерно n ²/2 пары из 20-значных последовательностей. Таким образом, чтобы иметь хорошие шансы найти совпадение, нам, вероятно, потребуется немного больше 10 ¹⁰. Предполагая, что мы берем 40 байт на запись, нам понадобится что-то порядка 400 ГБ данных. (Нам действительно нужно больше данных, чем это, поэтому мы должны быть готовы к чему-то более терабайт данных.)

Это дает нам представление о требуемом объеме данных. Десятки миллиардов цифр. Сотни ГБ данных.

Теперь вот проблема. Если мы используем любую структуру данных, требующую произвольного доступа, время произвольного доступа устанавливается скоростью диска. Предположим, что ваш диск идет со скоростью 6000 об/мин. Это 100 раз в секунду. В среднем данные, которые вы хотите, находятся на полпути вокруг диска. Таким образом, вы получаете в среднем 200 случайных запросов в секунду. (Это может варьироваться в зависимости от оборудования.) Доступ к нему в 10 миллиардов раз займет 50 миллионов секунд, что составляет более года. Если вы прочтете, а затем напишите и забудете, что вам нужно 20 миллиардов точек данных, вы превысите прогнозируемый срок службы вашего жесткого диска.

Альтернативой является обработка пакета данных способом, при котором вы не произвольно получаете доступ. Классика состоит в том, чтобы делать хороший внешний вид, такой тип сортировки. Предположим, что у нас есть 1 терабайт данных, которые мы читаем 30 раз, пишем 30 раз, во время сортировки. (Обе оценки выше, чем необходимо, но я рисую худший случай здесь.) Предположим, что наш жесткий диск имеет устойчивую пропускную способность 100 МБ/с. Затем каждый проход занимает 10 000 секунд, что составляет 600 000 секунд, что немного ниже недели. Это очень удобно! (На практике это должно быть быстрее, чем это.)

Итак, вот алгоритм:

• Начните с длинного списка цифр, 3141...
• Поверните это в гораздо больший файл, где каждая строка содержит 20 цифр, а затем место, где это отображается в pi.
• Сортировка этого более крупного файла.
• Найдите отсортированный файл для любых дубликатов.
  • Если они найдены, верните первый.
  • Если ни один не найден, повторите шаги 1-3 с другим большим количеством разрядов.
  • Объединить это в предыдущий отсортированный файл.
  • Повторите этот поиск.

Теперь это здорово, но что, если мы не хотим занять неделю? Что делать, если мы хотим бросить на него несколько машин? Это оказывается на удивление легко. Известны распределенные алгоритмы сортировки. Если мы разделим начальный файл на куски, мы можем распараллелить оба шага 1 и 4. И если после шага 4 мы не найдем совпадение, то мы можем просто повторить с самого начала с большей частью ввода.

На самом деле этот шаблон очень распространен. Все, что действительно меняется, - это преобразование исходных данных в сортируемые вещи, а затем поиск подходящих групп. Это алгоритм http://en.wikipedia.org/wiki/MapReduce. И это будет прекрасно работать для этой проблемы.

Ответ 3

Trie

RBarryYoung указал, что это превысит пределы памяти.

A trie структура данных может быть подходящей. За один проход вы можете создать три с каждым префиксом, который вы видели до длины n (например, n = 20). По мере продолжения процесса, если вы когда-либо достигнете node на уровне n, который уже существует, вы только что нашли дублируемую подстроку.

Соответствие суффикса

Другой подход включает обработку расширения в виде символьной строки. Этот подход находит общие суффиксы, но вам нужны общие префиксы, поэтому начните с изменения строки. Создайте массив указателей, каждый указатель указывает на следующую цифру в строке. Затем отсортируйте указатели, используя лексикографический вид. В C это будет что-то вроде:

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).

Этот подход был вдохновлен этой статьей.

Ответ 4

Возможно, что-то вроде этого будет работать:

• Поиск повторяющихся подстрок длины 2 (или небольшого базового случая), запись начальных индексов S = {s_i}

• При n = 3..N найдите подстроки длины n из индексов в S

• Каждая итерация, обновление S с подстроками длины n

• при n = 20, первые два указателя будут вашим ответом

вам может потребоваться отрегулировать начальный размер и размер шага (для каждого шага может не потребоваться шаг 1)