Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Delphi: Для новичков > Поиск повторений в текстовом файле

Автор: Wizlight 17.2.2011, 16:55

Есть текстовый файл - база чисел рулетки 1-36,0,00.(порядка 100000 чисел)
Программа должна обработать данные файла и вывести отдельно в новый текстовый файл все "комбинации" чисел заданной длины (например комбинация из 5 чисел: 14 5 00 21 12) которая встречается 2 и больше раз в базе чисел.

Как лучше это реализировать по скорости и рациональности?

У меня есть несколько вариантов:
1) Обрабатываем текстовый файл(базу чисел) как 1 стринг, где числа отделены пробелом. Копируем с начала стринга первых 5 чисел(пусть интересует длина именно в 5 чисел), ищем через pos эту подстроку дальше в файле, если нашли - ищем дальше вдруг еще есть комбинация. После поиска во всем файле этой комбинации, начинаем искать другую комбинацию - следующие 5 чисел от начала файла(то есть от второго до 6-го числа) и так далее пока не дойдем до конца
2) Обрабатываем текстовый файл (базу чисел) как массив чисел. То есть предварительно заганяем все числа с файла в массив целых чисел, и по похожему принципу с вариантом 1 ищем повторения комбинаций. Только тут поиск как я понимаю будет проходить по сравнению сразу 5-ти индексов чисел, которые будут сравниватся со следующими 5-а индексами чисел, которые будут смещаться до конца массива на +1. После первой проверки берем следующих 5 чисел и снова проделываем даную операцию.

В дальнейшем было бы не плохо чтобы программу переделать так, чтобы выводила в файл отдельно не только идентичные комбинации, а такие например где не совпадает только одно число. Например 25 16 9 13 31 и 25 16 17 13 31. Имхо 2-м способом это проще реализировать

Буду благодарен за новые идеи, подсказки, как лучше решить мою задачу. Спасибо за внимание

Автор: Fhusy 8.3.2011, 18:23

что значит 100000 чисел? чисел то всего 38: 1-36, 0,00; и какова структура базы? каким образом там числа хранятся?

Автор: Romkin 12.3.2011, 22:45

Лучше поздно, чем никогда smile

Задача интересная, искать так - пустая трата времени процессора.
Надо:
1. прочитать файл в массив байт, с перекодировкой (прибавить смещение чтобы не было кода 0, например числа от 1 до 38).
2. в конец массива добавить нулевой байт.
3. создать массив из PAnsiChar (это ссылка) с количесивом элементов по количеству символов (100000 - легко), каждый элемент которого указывает на очередной символ, т.е. первый - на первый элемент массива, второй - на второй.
4. упорядочить этот массив строк по возрастанию
5. пройти по нему, выделяя рядом стоящие строки, начинающиеся на одинаковую комбинацию заданной длины.
6. просмотреть значения ссылок, убирая пересекающиеся последовательности. Например, если будет последовательность 1 1 1 1 1 1, а длина задана 5, то получится две последовательности из 5 единиц, вторая - со второго символа первой.

Автор: northener 13.3.2011, 03:31

Цитата(Romkin @ 12.3.2011, 22:45

)

Задача интересная, искать так - пустая трата времени процессора.
Надо:

А вы уверены, что поиск по массиву строк будет быстрее чем поиск по массиву байт по алгоритму BMH?

Автор: Romkin 14.3.2011, 11:04

Цитата(northener @ 13.3.2011, 03:31

)

А вы уверены, что поиск по массиву строк будет быстрее чем поиск по массиву байт по алгоритму BMH?

В моем варианте поиска нет. И скорее всего это быстрее, чем выполнять поиск примерно 100000 раз по массиву 100000 байт, я практически в этом уверен, да.
Массива строк тут нет, есть массив остатков, фактически память занимается на N*(SizeOf(byte)+ SizeOf(Pointer)).
И мне еще кажется, что "алгоритм BMH", если это алгоритм Бойера — Мура — Хорспула, подходит в этом варианте мало.
Стоило бы рассмотреть применение алгоритма Рабина-Карпа, с хешированием. Точнее, его идею. Например, считать хеш для заданного количества символов для каждой позиции, далее упорядочить хеши (что в данном случае можно сделать за O(n)), и исключить ложные срабатывания. Кажется, здесь время O(n) можно получить, для фиксированной длины комбинации. Затраты на память - практически те же.
В принципе, если длина комбинации мала, можно не хешировать. Но практически все варианты, что мне приходят в голову, основаны так или иначе на сортировке, именно она обычно используется в том или ином виде для поиска дубликатов.