Поиск вхождения слова во всех столбцах таблицы. Вопрос какой выбрать оптимальынй алгоритмм для 100 000

[Laa911]

При решение какзалось бы простой задачи.
http://www.programmersforum.ru/showthread.php?t=110350

Из планируемого проекта
http://www.programmersforum.ru/showt...275#post599275

Выяснилось, что решить задачу достаточно не тревиально, что бы с приемлемой скоростью например обработать 100 000 столбцов.
Хотелось бы так же понять какая скорость будет считаться приемлемой.
1сек. 1 час?

Я формулировал задачку как поиск максимального переречения столбцов n*(n-1) и дальнейшее их ражирование.

Так как я не программист то на своем уровне представлял что это будет выглядеть приблизительно так

0. Загружаем в таблицу слова - каждая книга отдельный столбец (имеется ввиду слова выбранные по частоте в данной книге).
1. берем первое слово в первом столбце и пытаемся его найти в каждой книге (столбце) за каждое вхождение присваиваем +1 (если в одной книге нашел то ставим +1 если в двух +2 (т.е. некий вес - кол-ва вхождения в книги) и так по каждому слову.
2. Пробегаем так весь столбец (книгу)
3. Берем следующий столбец и повторяем
4. суммируем веса всех слов в каждом столбце
5. у столбца где сумма больше ставим первым и т.д.

Но пообщавщись выяснилось, что есть разные алгоритмы например
1. Бойера-Мура
2. Бинарные деревья..
и видимо еще много чего из того что есть :-)

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

Если таблица будет иметь размер 100 000 столбцов по 20 000 строк?

Вот такой не простой вопрос родился из простой задачки :-)
Нужна помощь зала.

[evg_m]

Зачем много много раз бегать по книгам

1. делаем пустой список
2. берем одну книгу
3. берем слово из книги
4. ищем слово в списке
5. если слова нет то добавляем
6. изменяем вес найденного (добавленного) слова
7. если есть еще слова то 3.
8. если есть еще книги то 2.
9. смотрим результаты.

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

[Laa911]

Сообщение от evg_m

Зачем много много раз бегать по книгам

1. делаем пустой список
2. берем одну книгу
3. берем слово из книги
4. ищем слово в списке
5. если слова нет то добавляем
6. изменяем вес найденного (добавленного) слова
7. если есть еще слова то 3.
8. если есть еще книги то 2.
9. смотрим результаты.

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

Не совсем понял зачем нужен пустой список :-(
1. Сортируем все столбцы от А до Z - это как я понимаю в разы позволит ускорить список?
2. Далее берем первое слово из первого столбца и ищем во всех книгах, при нахождение слова в книге/столбце вес делаем +1

П.7. и П.8 не понял :-(

вопрос остался. какой Алгоритм для поиска применить что бы в таблице 100 000 столбцов на 20 000 строк отработал за наименее возможное время?

[evg_m]

Не совсем понял зачем нужен пустой список :-(

чтобы начать его заполнять (смотри п.4)

1. Сортируем все столбцы от А до Z - это как я понимаю в разы позволит ускорить список?

сортируем не свои столбцы а тот список который заполняем.

2. Далее берем первое слово из первого столбца и ищем во всех книгах, при нахождение слова в книге/столбце вес делаем +1

задача решается ее переворачинием (полным изменением алгоритма).
не бегаем с каждым словом по ВСЕМ книгам/столбцам
а последовательно перебираем слова из столбца / книги и маркируем(заносим/изменяем значения статистик) в нашем списке

П.7. и П.8 не понял :-(

организация цикла по книгам(п.8)/столбцам(п.7) для перебора всех слов

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

смотрим (ищем) как организовать такой список.

P.S. для отсортированных массивов(читай колонок) и построения общего массива еще можно предложить такой метод как слияние (сортировка слиянием).
0. берем пустой массив (результат).
1. устанавливаем текущие позиции всех частичных массивов в начало
2. выбираем из всех текущих наименьшее значение
3. заносим (добавляем) это значение в результат
4. вычисляем значение статистик (и вносим в результат)
5. в каждом частичном массиве если текущий равен=текущий в результате, то смещаем текущую позицию(переходи к следующему)
6. повторяем с п.2 до тех пор пока не дойдем до конца во ВСЕХ частичных массивах.

[Laa911]

Я правильно нарисовал свое понимание вашего поиска?
т.е.
1. создаем пустую таблицу - Список
2. Берем первое слово из столбца 1 и ищем его в таблице Список
3. елсли находим то ставим еденичку в столбцекнига 1
4. Если не находим до добавляем
5. После каждого добавления сортируем список от A до Z (для ускорения последующего слова в таблице Список

Я правильно вас понял?

Но остался вопрос - какой алгорим заполнния таблицы Список будет самым быстрым.

P.S.
Красная стрелочка поиск и добвление слова (если его нет)
Синяя протавляем вес слова 0 или 1 в зависимости от того найдено слово или нет