Добавлено: 09/09/04 в 15:51

есть несколько массивов (для примера: 10 текстовых файлов).
обьем каждого массива 100мб.

нужно найти все строки которые встречается в 5ти (или более) из 10 массивов, чаще чем 3 раза в каждом.



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

Вопрос, как еще можно оптимизировать это дело ?
Интересует сам алгоритм (а не варианты с использованием баз данных типа майСКЛ)

И вообще, может кто нить подскажет какие нибудь книги типа "создание баз данных для чайников" , "поиск и индексирование информации для тупых".

Всем кто даст толковые идеи и информацию - рейтинг по максимуму ;)

Добавлено: 09/09/04 в 16:06

сорри не туда запостил
Модераторы, перенесите пожалуйста топик в "скрипты/програмирование".
спасибо.

Добавлено: 09/09/04 в 16:06

Данные хранятся в текстовых файлах или уже получены в массивы?
Варианты работы с данными разные - субд,файлы,память.
Если действительно в файлах, то гораздо проще портировать эти данные в любую субд, вычистить ненужное и все маневры произодить там.

Оптимизация алгоритмов - это уже есть там, только не тупить с запросами и все будет работать достаточно быстро.

А эту операцию нужно производить периодически или однократно?

Добавлено: 09/09/04 в 16:19

данные храняться в оптимизированных текстовых файлах.
т.е. у меня вместо СУБД - файловая система выступает (первые буквы каждой строки - имя папки к примеру).

в память такие массивы не запихнешь - там за несколько гигов в итоге база данных получится.

операцию надо будет производить каждые 10 часов примерно, и соответственно хотелось бы чтобы процесс обработки данных занимал не больше часа

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

Добавлено: 09/09/04 в 16:56

А что за информация там хранится? В смысле насколько она систематизации поддается?
И вот еще такой вопрос - информация же не может появлятся внезапно, она накапливается - может имеет смысл на этом шаге обработку вводить?

Добавлено: 09/09/04 в 18:04

В файлах те что по сто мегабайт какие символы есть помимо букв английских?

Добавлено: 09/09/04 в 18:05

Сколько времени займет построчное чтение каждого файла с созданием пустого файла, с именем прочтенной строки?

Добавлено: 09/09/04 в 18:43

в базе храняться всякие разные ссылки.
знаки соответственно абсолютно все которые используеются в урлах... включая +;:&#~/... так что насчет создания файлов с именами = строке - не получится.

Добавлено: 09/09/04 в 21:01

Есть такая превосходная книженция как "Структуры данных в С++" Уильям Топп и Уильям Форд
Если хочешь сам писать всё, используй деревья (бинарные, AVL).
Можно еще хеш-таблицу забубенить. Но тут как бы такая ситуация: тебе надо под эту таблицу отдельный файл ил несколько (а так как база большая, то имеет смысле делать хеш хешей); эм... как бы попроще, на один индекс выделяется определенное кол-во записей (по сути небольшое), то есть там само выделяется в зависимости от способа хеширования (схемы). Находишь индекс - и у тебя есть по сути прямой доступ на определенную позицию в файле (не надо читать весь файл "влоб"). На схеме деления у меня среднее время работы функции - 9нс, среднее кол-во коллизий - 16.72% (в идеале кол-во коллизий стремится к нулю), а максимальное кол-во коллизий - 33%. Это была самая быстрая функция у меня. Есть у меня программа, которая всё это дело тестирует (OspGen2), могу дать побаловаться ;)

Добавлено: 09/09/04 в 21:39

Andryxa, ок попробую поискать книгу.

а по советам.., терминологию понимаю с трудом... но в целом вроде похоже что у меня уже примерно так и сделано...

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

да, для поиска в самих файлах я использую системный grep, стоит писать под это дело свою функцию или на скорости это не скажется ?

Добавлено: 09/09/04 в 22:53

Конечно же сказывается на скорости. Лучше всего писать на ассемблере хеш-функцию и пихать ее в проект. Функция по схеме деления у меня работала за 9 наносекунд. НЕ поудмай, что здесь все так круто и работает быстро. Для начала надо найти оптимальные значение K для конкретного файла. То есть есть такие "математические аномалии", больше их никак не назовешь, когда с данной схемой лучше работают одни тексты, другие файлы - с другими схемами. Этих К надо перебирать туеву хучу, что при этом значении кол-во коллизий (одинаковых значений хеш-функции) было как можно меньше. Формула схемы деления: h(K)=K mod M, где М - т.н. модуль рассеяния (у нас по дефолту 1 или 2 байта, 255 и 65535 соотв. в зависимости от размера таблицы)
При этом сгодится и несортированные файлы. Вот нашел это заветное К, и уже пихаешь его для вычисления значения хеш-функции. То бишь вычислив значение, ты прямиком попадаешь на небольшой блок, где можно искать напрямую, но лучше же опять извратиться в целях экономии, и сделать что-нить типа односвязного списка а может даже и бинарного дерева поиска.

Лучше ищи книгу, она толстенная, на... щас скажу, 800 страниц. Там довольно много интересного материала про поиск и выбор оптимальной структуры для данной ситуации.
Короче, "Улыбок тебе дед мокар"

Добавлено: 09/09/04 в 22:59

Алгоритмом не помогу, а вот книгу могу посоветовать.
Фундаментальный труд: Дональд Э. Кнут "Искусство программирования том 3 Сортировка и поиск"

Добавлено: 09/09/04 в 23:01

Че то я туплю видимо. В каком виде оно у тебя там таки храниться и какие размеры строк?

Лучше всего просто пример нескольких строк приведи.

Реально есть много вариантов. Но не видя что оно такое, нельзя понять где именно нужно сокращать размерность.

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


Дальше, если строки по 20-30 сиволов - может иметь смысл сгенерировать для них CRC например двухбайтные, ну или другую какую функцию использовать. Я так понимаю это и называется мудреным термином "хеш преобразование" о котором говорили выше. Потом сортируешь по возрастанию тем же методом. Естественно придется проиндексировать и сортировать вместе с индексом, иначе потом не поймешь где что было... Таким образом генеришь 10 массивов этой херни из начальных 10 файлов.

Потом делаешь вот что. Берешь и читаешь первое значение из каждого массива. Сравниваешь между собой. Если нашел равенство 5 значений - проверяешь исходные строки (ибо CRC у тебя могут быть одинаковыми у разных исходных строк). Если совпадают - ну записываешь куда надо и читаешь следующие значения по тем массивам, значения из которых совпали. Если равенства не было - смотришь какое из значений было минимальным и читаешь из того массива, из которого это минимальное было взято, следующее значение, остальные не трогаешь. Опять сравниваешь между собой и так далее. Вернее, читать можно сразу из нескольких массивов начиная с минимального значения, это уже смотря по тому, сколько текущих совпадает...

Примерно так. Может что напутал, но принцип надеюсь ясен...

Бля, вдруг понял что мне проще прогу написать, чем это объяснять.

Добавлено: 09/09/04 в 23:24

Бля, действительно туплю... Если первая стадия сортировкой была сделано, нахер потом мудрить с хешами не надо, и так скорость нормальная будет.

Добавлено: 09/09/04 в 23:55

Переезжаем с скрипты..

Добавлено: 10/09/04 в 05:03

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

2. Создаешь массив индексов из двух полей
поле id - CRC строки (индекс)
поле num - номер строки в исходном массиве.

без отслеживания повторений.

3. Сортируешь массив индексов быстрым алгоритмом (типа сортировки Хора)

4. Сжимаешь массив индексов с учетом повторений, выбрасывая строки которые встречаются в исходном массиве меньше чем 3 раза (это сделать легко, так как после сортировки идентичные CRC находятся рядом). При этом для каждого прошедшего критерий индекса в массиве индексов остается только 1 запись (а не 3 и более).

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

6. Создаешь общий массив индексов из всех массивов индексов:

поле id - CRC строки (индекс)
поле indnum - номер массива индексов.
поле num - номер индекса в массиве индексов.

опять же без отслеживания повторений

7. Сортируешь.

8. Сжимаешь массив , выбрасывая индексы которые повторяются меньше чем 5 раз (это сделать опять же легко, так как после сортировки идентичные опять же CRC находятся рядом). При этом для каждого прошедшего критерий индекса в общем массиве индексов остается только 1 запись (а не 5 и более).

9. в итоге получаешь массив индексов строк со ссылками на массивы индексов, с которых можешь попасть на исходную строку, если надо.

Скоростные показатели: кроме сортировок (которых по числу массивов исходных + одна на общий массив индексов), все действия делаются в один проход.

При указаном тобой объеме это будет точно меньше часа

Скорее, минуты.

Добавлено: 10/09/04 в 15:14

Hint: CRC - это одна из схем хеширования ;)

Добавлено: 10/09/04 в 17:53

Меня осенило! Это же так называемый "конкорданс"!
Как-то давно еще читал, но не сразу вспомнил, что это оно.

цЫтата из книги:
"Обычной проблемой анализа текстов является определение частоты и расположения слов в документе. Эта информация запоминается в конкордансе, где различные слова перечислены в алфавитном порядке и каждое слово снабжено ссылками на строки текста, в которых оно встречается Рассмотрим следующую цитату.
Peter Piper picked a peck of pickled peppers. A peck of pickled peppers
Peter Piper picked. If Piter Piper picked a peck of pickled peppers, where is the peck that Peter Piper pecked?
Слово "piper" встречается здесь 4 раза в строках 1, 2 и 3. Слово "pickled" встречается 3 раза в троках 1 и 3"

По-моему, это оно. Тут применяется бинарное дерево поиска
Тут приводится эта программа, но че-т меня ломает печатать 5 страниц текста У друзей отсканю. А если нашел книгу "Стр-ры данных в С++" Уильям Топп, то беги на 525 страницу )


Результат выполнения прораммы:

a.........................................3: 1 2
if.........................................1: 2
is.........................................1: 3
of........................................3: 1 2
peck.....................................4: 1 2 3
peppers................................3: 1 2 3
peter....................................4: 1 2 3
picked..................................3: 1 3
piper....................................4: 1 2 3
that.....................................1: 3
the......................................1: 3
where..................................1: 3

Добавлено: 10/09/04 в 19:34

круто...
на всякий случай поставил всем +8
и ушел обдумывать вышесказанное.

Добавлено: 11/09/04 в 02:10

Xrenoder, респект,
но у меня есть пара поправок к алгоритму.

1. CRC -- немножко не то, согласитесь, давайте уж брать тогда MD5, который разрабатывался специально для того, чтобы иметь наименьшее количество коллизий.

2. Вообще я себе представляю это немножко по-другому.

Имеется хэш (думаю что stl map вполне устроит).
Ключ -- MD5(строки)
Значение -- структурка: количество вхождений слова и список из координат этих слов в ваших файлах.

Добавление списка слов при любом количестве будет C(N), т.к. слово добавляется за константное время. После перебором по ключам мы можем выбросить всё, что не удовлетворяет нашим потребностям. Вот в принципе и всё.

Заметьте, что при таком подходе мы не загружаем всю инфу в память и
избегаем сортировки. Точнее как-бы сортировка есть, но она быстрее сортировки Хора ( )

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

Добавлено: 11/09/04 в 05:17

Ну хоть бы тогда за активность рейтинга накинул...

Добавлено: 11/09/04 в 10:56

все заценил.
насчет
crc\md5 подумаю...

но вообще имхо crc32 в моем случае выгодней - так как длина строки намного меньше (а значит обработка быстрее)

насчет кол-ва уникальных строк - судя по предыдущему опыту будет самый максимум 8млн элементов.

если вероятность ошибки при этом будет хотябы 1\100000 - меня это устроит.

Добавлено: 17/09/04 в 18:31

http://www.kursovik.net/programming/101018.html
вот посмотри