Задать вопрос
@xperious

Как найти все палиндромы в терабайтном файле?

здравствуйте, подскажите алгоритм поиска всех слов-палиндромов в файлах большого размера? ну или хотя бы уникальных чисел в гигантском массиве(который не влезает в оперативную память)
  • Вопрос задан
  • 261 просмотр
Подписаться 1 Простой 6 комментариев
Пригласить эксперта
Ответы на вопрос 4
DanilBaibak
@DanilBaibak
Machine Learning engineer
Для Python можно использовать библиотеку pandas. Pandas позволяет загружать файл итеративно. Выглядит примерно так:

import pandas as pd

chunks = pd.read_csv('path_to_file',  chunksize=150000)
for chunk in chunks:
    # do whatever you want
    pass
Ответ написан
Комментировать
@MadridianFox
Web-программист, многостаночник
В большинстве ЯП поддерживается чтение некоторого количества байт с определённого места из файла.
Т.е. можно открыть файл (не считать его весь, а только открыть), после этого в цикле читать по N байт и итерировать по ним. Дальше уже дело за алгоритмом, который принимает по одному символу и пытается в потоке символов вычислить палиндром. Т.е. это машина состояний. Думаю там нужен стэк ограниченного размера с выталкиванием самых старых символов при поступлении новых.
// псевдокод
file = open("my_big_file.txt","r");
buffer = byte[1024];
palindrome_scanner = new PalindromeScanner(4, 64); // min and max palindrome size
while(canRead($file)){
    buffer = fread(file, &buffer);
    for(int i=0; i<2024; i++){
        palindrome_scanner->next(buffer[i]);
    }
}
Ответ написан
Комментировать
sgjurano
@sgjurano
Разработчик
Если слова в вашем файле записаны построчно, то вам нужно просто читать файл построчно, таким образом в памяти всегда будет только одно слово.

Проверка слова на палиндром производиться сравнением слова с ним же, но инвертированным.

Если слово является палиндромом - пишем его в другой файл.

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

На практике алгоритм можно сильно ускорить если читать и писать строки не по одной, а батчами - ценой будет увеличенное потребление памяти.
Ответ написан
Комментировать
@SeptiM
https://arxiv.org/abs/1506.04862

Там структура данных, линейная по памяти с суффиксным бором и деревом. Очень эффективная. Остается, правда, придумать, как ее на терабайт отмасштабировать.
Ответ написан
Комментировать
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Похожие вопросы