Форум программистов, компьютерный форум CyberForum.ru

Поиск слов в файлах - C++

Восстановить пароль Регистрация
 
Getter
2 / 2 / 0
Регистрация: 09.09.2010
Сообщений: 221
29.02.2012, 20:28     Поиск слов в файлах #1
Здравствуйте, у меня такая задача:
в нескольких файлах (объем в совокупности от 10 до 15 гб) надо найти примерно 1000-1500 "слов" фиксированного размера (задаются в диапазоне от 6 до 15 байт). "Слова" задаются в отдельном файле.
Каким образом можно это реализовать? Просто перебором, я думаю, он лет 10 будет искать.
Может подскажите алгоритмы или поделитесь полезными ссылочками? Буду очень признателен.
ps. если на вскидку, то сколько оно может занять по времени?

Добавлено через 2 минуты
Файлы в основном *.exe
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
29.02.2012, 20:28     Поиск слов в файлах
Посмотрите здесь:

C++ Cравнение слов в файлах.
C++ Поиск слов в файле
Поиск слов в строке C++
C++ Поиск одинаковых слов в текстовых файлах
Поиск в файлах с различными форматами C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
NoMasters
Псевдослучайный
1737 / 1080 / 69
Регистрация: 13.09.2011
Сообщений: 3,093
29.02.2012, 21:10     Поиск слов в файлах #2
grep искал одно слово в двухгиговом файле 50 секунд, очевидным образом большая часть времени приходится на io, так что для 1.5к слов в 15 гигах будет... ну минут 20. При этом у меня довольно унылый конфиг. Тебе действительно нужно что-то оптимизировать? Можно отсортировать слова и объединить сравнения на одинаковых участках.
Getter
2 / 2 / 0
Регистрация: 09.09.2010
Сообщений: 221
29.02.2012, 22:36  [ТС]     Поиск слов в файлах #3
Хм, 20 минут многовато будет, мне б минут 10 максимум для 1500.
Цитата Сообщение от NoMasters Посмотреть сообщение
большая часть времени приходится на io
Хм, а если выделить в оперативе, допустим, 256мб и программу саму разбить на два потока.
Те программа загрузила часть файла (256мб), один поток начал искать слово, как только 128мб было проверено, второй поток подгружает новый блок 128 мб вместо старого, как первый поток дошел до конца 256мб, то переходит в начало, где его ждет свежезагруженные 128мб и так далее. Или бред? (Чтоб с оперативой только работал, а не с винтом)

Добавлено через 4 минуты
Цитата Сообщение от NoMasters Посмотреть сообщение
Можно отсортировать слова и объединить сравнения на одинаковых участках.
Можно поподробнее об этом?

Добавлено через 38 минут
Возможно еще, что количество слов будет не <1500, а 21'000'000 < N < 178'000'000...
Так чтооо, искать будет лет 10.. а мне бы хоть в час уложиться
NoMasters
Псевдослучайный
1737 / 1080 / 69
Регистрация: 13.09.2011
Сообщений: 3,093
29.02.2012, 23:01     Поиск слов в файлах #4
Цитата Сообщение от Getter Посмотреть сообщение
разбить на два потока.
Цитата Сообщение от Getter Посмотреть сообщение
программа загрузила часть файла (256мб)
Упирается в скорость считывания с диска же. Такой большой буфер тоже смысла не имеет, только затык на заполнении будет.
Цитата Сообщение от Getter Посмотреть сообщение
слов будет не <1500, а 21'000'000 < N < 178'000'000...
Это по 15 байт-то? Дубли реж
Цитата Сообщение от Getter Посмотреть сообщение
Можно поподробнее об этом?
Построишь древо по совпадающим байтам, чтобы для не проверять по сто раз одно и тоже значение, а за один раз выбрать подходящее множество слов.

А что за задача вообще? Антивирус какой-то что ли?
Getter
2 / 2 / 0
Регистрация: 09.09.2010
Сообщений: 221
29.02.2012, 23:17  [ТС]     Поиск слов в файлах #5
Ну типа того, анализ фалов.
Yandex
Объявления
29.02.2012, 23:17     Поиск слов в файлах
Ответ Создать тему
Опции темы

Текущее время: 07:06. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru