![]() |
|
|
Регистрация Восстановить пароль |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
![]() |
|
Опции темы | Поиск в этой теме |
![]() |
#1 |
Заблокирован
Регистрация: 17.08.2010
Сообщений: 39
|
![]()
При решение какзалось бы простой задачи.
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 строк? Вот такой не простой вопрос родился из простой задачки :-) Нужна помощь зала. Последний раз редактировалось Laa911; 24.08.2010 в 23:57. |
![]() |
![]() |
![]() |
#2 |
Старожил
Регистрация: 20.04.2008
Сообщений: 5,542
|
![]()
Зачем много много раз бегать по книгам
1. делаем пустой список 2. берем одну книгу 3. берем слово из книги 4. ищем слово в списке 5. если слова нет то добавляем 6. изменяем вес найденного (добавленного) слова 7. если есть еще слова то 3. 8. если есть еще книги то 2. 9. смотрим результаты. главное правильно организовать один список (см. п.1,4) чтобы поиск по нему был быстрым для ускорения поисков список должен быть упорядочен (отсортирован) по удобному для поиска алгоритму и добавление элементов (п.4) - быть быстрым - не должно нарушать заведенный порядок
программа — запись алгоритма на языке понятном транслятору
|
![]() |
![]() |
![]() |
#3 | |
Заблокирован
Регистрация: 17.08.2010
Сообщений: 39
|
![]() Цитата:
1. Сортируем все столбцы от А до Z - это как я понимаю в разы позволит ускорить список? 2. Далее берем первое слово из первого столбца и ищем во всех книгах, при нахождение слова в книге/столбце вес делаем +1 П.7. и П.8 не понял :-( вопрос остался. какой Алгоритм для поиска применить что бы в таблице 100 000 столбцов на 20 000 строк отработал за наименее возможное время? |
|
![]() |
![]() |
![]() |
#4 | ||||
Старожил
Регистрация: 20.04.2008
Сообщений: 5,542
|
![]() Цитата:
Цитата:
Цитата:
не бегаем с каждым словом по ВСЕМ книгам/столбцам а последовательно перебираем слова из столбца / книги и маркируем(заносим/изменяем значения статистик) в нашем списке Цитата:
вот организация списка (не столбцов/книг по которым пройдем лишь раз) имеет большое значение нужно: 1. быстрый поиск (в сортированном списке можно применять разные быстрые поиски (двоичный/бинарный, другие) 2. быстрые операции добавления внутрь списка (чтобы не нарушалась сортировка) сортированный + расширяемый (добавление новых элементов) выполнение в виде дерева или связанного списка смотрим (ищем) как организовать такой список. P.S. для отсортированных массивов(читай колонок) и построения общего массива еще можно предложить такой метод как слияние (сортировка слиянием). 0. берем пустой массив (результат). 1. устанавливаем текущие позиции всех частичных массивов в начало 2. выбираем из всех текущих наименьшее значение 3. заносим (добавляем) это значение в результат 4. вычисляем значение статистик (и вносим в результат) 5. в каждом частичном массиве если текущий равен=текущий в результате, то смещаем текущую позицию(переходи к следующему) 6. повторяем с п.2 до тех пор пока не дойдем до конца во ВСЕХ частичных массивах.
программа — запись алгоритма на языке понятном транслятору
Последний раз редактировалось evg_m; 25.08.2010 в 13:25. |
||||
![]() |
![]() |
![]() |
#5 |
Заблокирован
Регистрация: 17.08.2010
Сообщений: 39
|
![]()
Я правильно нарисовал свое понимание вашего поиска?
т.е. 1. создаем пустую таблицу - Список 2. Берем первое слово из столбца 1 и ищем его в таблице Список 3. елсли находим то ставим еденичку в столбцекнига 1 4. Если не находим до добавляем 5. После каждого добавления сортируем список от A до Z (для ускорения последующего слова в таблице Список Я правильно вас понял? Но остался вопрос - какой алгорим заполнния таблицы Список будет самым быстрым. P.S. Красная стрелочка поиск и добвление слова (если его нет) Синяя протавляем вес слова 0 или 1 в зависимости от того найдено слово или нет |
![]() |
![]() |
![]() |
![]() |
||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Найти произведение всех чётных чисел от -100 до 100. | Makcumqa | Помощь студентам | 8 | 18.03.2010 22:31 |
Организовать поиск всех вхождений заданного слова в загруженном тексте | s2dentishe | Помощь студентам | 0 | 21.11.2009 18:53 |
Какой линукс выбрать для конкретных целей? | Mixasik | Операционные системы общие вопросы | 9 | 04.10.2009 10:03 |
Какой язык выбрать для изучения? | titan-prog | Свободное общение | 17 | 16.07.2008 21:43 |
Какой компонент выбрать для вывода таблицы картинок ICO | Comer_Jus | Мультимедиа в Delphi | 3 | 21.05.2008 20:35 |