|
|
Регистрация Восстановить пароль |
Повторная активизация e-mail |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
|
Опции темы | Поиск в этой теме |
29.09.2009, 18:14 | #1 |
Trust no one.
Старожил
Регистрация: 07.04.2009
Сообщений: 6,526
|
Оптимальный способ искать слова в текстовой (txt) базе.
Собственно имеется 3 базы слов в формате txt : G.txt S.txt P.txt
В базах соответственно содержатся Глаголы, Существительные, Прилагательные. Я ввожу слово (например в edit, причем я не указываю, что это, глагол, существительное или прилагательное) теперь мне нужно узнать строку в базе, в которой "затаилось" это слово. Причем найти его там не проблема, важно найти его с наибольшей скоростью. В общем задача - получить номер строки и тип слова. Мои наработки: 1) Я считаю неоптимальным грузить базу с помощью AssignFile и после считывать каждую строку. Долго и нудно. 2) Возможно будет быстрее грузить весь файл в StringList, затем циклом пройтись по всем строкам или попробовать поискать Pos`ом. 3) Может есть другие способы, более быстрые? P.S. Отрезок базы G.txt: Код:
SQUARY PROJECT - НАБОР БЕСПЛАТНЫХ ПРОГРАММ ДЛЯ РАБОЧЕГО СТОЛА.
МОЙ БЛОГ GRAY FUR FRAMEWORK - УДОБНАЯ И БЫСТРАЯ РАЗРАБОТКА WINAPI ПРИЛОЖЕНИЙ Последний раз редактировалось Alex Cones; 29.09.2009 в 18:19. |
29.09.2009, 18:19 | #2 |
Форумчанин
Регистрация: 10.02.2009
Сообщений: 815
|
Если грузить только слова с первой буквы , 2+3+ ? не грузить весь файл в программу а там же проходится по строкам ?
|
29.09.2009, 18:21 | #3 |
Trust no one.
Старожил
Регистрация: 07.04.2009
Сообщений: 6,526
|
Дело в том, что компьютер будет получать целую фразу, а потом выяснять все про каждое слово. Так что побуквенно... В смысле даже в готовой фразе?
P.S. Только что посчитал объем баз. В общем выходит около 1-2 мегов на базу.
SQUARY PROJECT - НАБОР БЕСПЛАТНЫХ ПРОГРАММ ДЛЯ РАБОЧЕГО СТОЛА.
МОЙ БЛОГ GRAY FUR FRAMEWORK - УДОБНАЯ И БЫСТРАЯ РАЗРАБОТКА WINAPI ПРИЛОЖЕНИЙ Последний раз редактировалось Alex Cones; 29.09.2009 в 18:33. |
30.09.2009, 00:45 | #4 |
минимакс
Участник клуба
Регистрация: 11.06.2008
Сообщений: 1,143
|
может попытаться для файла сделать дополнительный файл индексов.
Вроде, как это делают в БД. ну хотя бы примитивно. G.ind для G.txt где в G.ind А с 1-100 Б с 100 - 1200 .... Тогда читать надо будет не весь файл, а блок. Даа, вопрос - а слова в файлах отсортированны?
и это пройдет...
|
30.09.2009, 00:49 | #5 | |
Телепат с дипломом
Старожил
Регистрация: 10.06.2007
Сообщений: 4,929
|
Цитата:
The future is not a tablet with a 9" screen no more than the future was a 9" black & white screen in a box. It’s the paradigm that survives. (Kroc Camen)
Проверь себя! Онлайн тестирование | Мой блог |
|
30.09.2009, 01:04 | #6 | |
минимакс
Участник клуба
Регистрация: 11.06.2008
Сообщений: 1,143
|
Цитата:
Эдакий поиск делением списка на два по принципу - больше или меньше данное слово, чем искомое? Дык, а время на построение дерева в памяти?
и это пройдет...
|
|
30.09.2009, 01:21 | #7 | ||
Телепат с дипломом
Старожил
Регистрация: 10.06.2007
Сообщений: 4,929
|
Цитата:
Цитата:
Если загрузить список в TStringList (пару мегабайт в памяти это не страшно на сегодняшний день, правда возможно подождать пару секунд пока он грузится, нужно будет) тогда список будет проиндексированный и можно быстро переходить на нужные позиции. Загрузку можно сделать при старте программы, если такой способ с загрузкой в память не подходит, то наверное лучше отказаться от текстового файла в пользу бинарного со структурами - узлами дерева, а не просто строками, в структуре как минимум должны быть позиция левой ветки в файле, правой, и сама строка. Тогда можно будет открыть файл на чтение, и гулять по нему производя поиск, при этом без задержки на загрузку в память этого файла. Прирост скорости в сравнении с простым перебором: к примеру у вас 256 элементов в списке, если искать перебором, то в худшем случае вам понадобится 256 итераций. В аналогичном двоичном дереве чтобы добраться до крайней ветки, понадобится 8 итераций. Если же список увеличить до 65000 то время поиска перебором увеличится в тысячи раз, в дереве же нужно всего 16 итераций!
The future is not a tablet with a 9" screen no more than the future was a 9" black & white screen in a box. It’s the paradigm that survives. (Kroc Camen)
Проверь себя! Онлайн тестирование | Мой блог Последний раз редактировалось mutabor; 30.09.2009 в 01:38. |
||
30.09.2009, 03:26 | #8 |
Старожил
Регистрация: 09.01.2008
Сообщений: 26,229
|
прежде всего, размеры в несколько мегабайт это детский лепет!
вот, рекомендую ознакомится с темой Загрузка и поиск в большом файле там, кстати, несколько полезных программ (в исходниках, разумеется). Так вот, 160 МБ файл (10 000 000 строк) через TStringList.LoadFromFile загружается около 14 секунд. файл размером 32 Мб (1000000 строк) грузится около секунды... во-вторых, слова должны быть ОТСОРТИРОВАНЫ. Тогда можно воспользоваться методом поиска TSTRINGLIST.FIND (он как раз ищет только в отсортированных списках). Последний раз редактировалось Serge_Bliznykov; 30.09.2009 в 03:34. |
30.09.2009, 09:04 | #9 | ||
Trust no one.
Старожил
Регистрация: 07.04.2009
Сообщений: 6,526
|
Строки будут отсортированны в алфавитном порядке. Это раз. Насчет стринглиста я не сомневался. Это два.
Цитата:
Цитата:
SQUARY PROJECT - НАБОР БЕСПЛАТНЫХ ПРОГРАММ ДЛЯ РАБОЧЕГО СТОЛА.
МОЙ БЛОГ GRAY FUR FRAMEWORK - УДОБНАЯ И БЫСТРАЯ РАЗРАБОТКА WINAPI ПРИЛОЖЕНИЙ |
||
30.09.2009, 11:53 | #10 | |
Старожил
Регистрация: 09.01.2008
Сообщений: 26,229
|
Цитата:
Да, Вы правы, это слабое место данного способа. Варианта решения собственно два: — если слова добавляются редко (сколько при этом слов добавляется, абсолютно неважно!) - то просто пересортировывать (это всего одна строчка кода - TStringList.Sort; ) — если же добавление слов происходит достаточно часто, то надо мутить так, как это сделано в любой СУБД - добавлять индексы и при каждом изменении файла перестраивать индекс. Ну, как Вы, вероятно, догадываетесь, это намного сложнее! p.s. А Вам не кажется, что Вы занимаетесь изобретением велосипеда? Любая СУБД легко и эффективно решит Вашу задачу. Почему не хотите воспользоваться СУБД?! |
|
|
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Вывод текстовой информации из документа TXT. | soonner | PHP | 2 | 09.05.2009 21:57 |
Как удалить текст до слова, потом от слова ? | littlecoder | Общие вопросы Delphi | 7 | 29.12.2008 00:57 |
найти оптимальный план производства | Baxxter | Microsoft Office Excel | 12 | 25.09.2008 23:45 |
Какой оптимальный способ в Delphi для перевода 10 системы счисления в 16с.с | SERGOO | Общие вопросы Delphi | 5 | 25.05.2007 19:02 |