Экспертная система Delphi.int.ru

Сообщество программистов
Общение, помощь, обмен опытом

Здравствуйте, уважаемые эксперты!
Извините конечно за столь простой вопрос, но он меня поставил в тупик. Как организовать фильтрованный поиск строки в TSringList по первому слову (!)?
Я делал второй лист по первому, содержащую только первые слова, отделенные с разделителем пробелом от первого, потом уже осущетвляя поиск слова (символа) по второму листу, а затем брал строку из первого, соответвующую индексу найденой строки второго. Звучит довольно запутанно и работает очень медленно, есть ли более простой и быстрый способ?
Заранее спасибо.

Вопрос задал: Phoenix (статус: Посетитель) Вопрос отправлен: 18 августа 2007, 17:06 Состояние вопроса: решён, ответов: 2.

Ответ #1. Отвечает эксперт: Вадим К

Здравствуйте, Phoenix!
Для поиска строки в массиве других строк есть десятки алгоритмов. Если бы вы привели пример, как вы делаете.
Я предполагаю, что для каждого поиска вы заново формируете лист с списком слов. Это конечно медленно. Но можно немного ускорить, если задать свойство Capacity равное количеству строк первого списка. Таким образом память будет сразу выделена и на больших массивах (в тысячи элементов) будет некоторый прирост.
Если список редко меняется, а поиск нужно проводить часто, но есть смысл воспользоваться хеш таблицами. В таком случае поиск на больших массивах может увеличиться в десятки а то и сотни раз.
Как это сделать?
Для начала обявляем структуру вида
type
ToneWord = record
hash:DWORD;
numbers:array of DWORD;
end;
Эта структура будет хранить хеш слова и список строк, где оно встречается.
Так, обясню, что такое хеш. Хеш - это такое преобразование, когда в соответсвие одному элементу, обычно большому (у нас это строка) ставиться меньший (у нас это 4 байта). Но так как нет гарантии, что для двух объектов не будет одинакового хеша (это называется колизией хеш функции), то мы и заводим массив номеров, которым соответствует хеш.
Какой хеш взять? можно взять сложный, тогда есть большая гарантия, что он будет уникальный. Но сложный долго вычисляется. Можно взять попроще, тогда будет быстрей вычисляться, но могут быть больше списки. Поэтому нужно эксперементировать. Примеры сложных хешей - MD5, SHA1. пример простого CRC32. Пример очень простого - сумма аски кодов всех символов. Недостаток этого способа очевиден - не весь диапазон занимается - даже если у нас слово с 16 букв "я", то это будет только число 255*16 тоесть даже в два байта влазим. Но эта функция быстро считается и в данном случае может дать хорошие результаты.
Теперь следующий этап. Обявим массив вида
list:array of ToneWord;
Теперь нужно заполнить. я думаю с этим уже справитесь. Намечу только алгоритм. Считаем хеш очередной строки (в вашем случае только первого слова). дальше делаем поиск по массиву на присутствие подобного хеша. Если есть - то добавим в его список новую строку, если нет, то добавим ещё один хеш.
Этот алгоритм можно модифицировать и прийти к деревьям, но до этого надо ещё созреть.
Можно конечно хеш свести до одного байта и массив сразу завести на 256 элементов. Если у вас 1000 слов, то это будет по 4-5 слов на один хеш - тоже не плохо.
Теперь, как искать. Берём заданное слово и считаем от него хеш. Потом ищем в таблице нужный хеш. если табличка с хешами отсортирована, то это происходит очень быстро. А если вы сделали упрощение и массив на 256 элементов - то вообще просто - нужно просто посмотреть нужную ячейку. Теперь вместо 1000 слов мы имеем 4-5 слов. а среди них поиск можно провести и банальными методами.
Кстати, подобным образом работают многие базы данных

Ответ отправил: Вадим К (статус: Академик) Время отправки: 18 августа 2007, 17:52 Оценка за ответ: 5 Комментарий к оценке: За теорию отдельное спасибо! Честно говоря не ожидал такого сложного решения.

Ответ #2. Отвечает эксперт: Косолапов Дмитрий Юрьевич

Здравствуйте, Phoenix!
Использовать два стринглиста так, как Вы сделали, совершенно ни к чему, можно же в просто в цикле пройти по листу и анализировать начало каждой строки на совпадение. Набросок кода в приложении, lst - StringList, в котором ищем.

Ответ отправил: Косолапов Дмитрий Юрьевич (статус: 8-ой класс) Время отправки: 18 августа 2007, 23:20 Оценка за ответ: 5 Комментарий к оценке: Спасибо, все действительно оказалось просто...

Мини-форум вопроса

31 января 2011, 19:29: Статус вопроса изменён на решённый (изменил модератор Ерёмин А.А.): Автоматическая обработка (2 и более ответов с оценкой 5)

Чтобы оставлять сообщения в мини-форумах, Вы должны авторизироваться на сайте.