|
|
|
Supreme Being
участник
Last Login: 19.10.2008 12:14
Сообщ.: 693,
Visits: 7 081
|
|
| Имеется выпадающий список в котором около 6000 записей. Пользователь вводит некий текст и требуется с вводом каждой буквы найти определенный элемент, содержащий этот текст. Я организовываю цикл в котором перебираю все элементы до тех пор пока не нахожу в каком-то элементе подстроку равную заданной. Однако такой поиск длится иногда до 34-40 секунд. Это абсолютно неприемлемо. Подскажите, пожалуйста, как можно организовать "быстрый поиск".
Спасибо!
Евгений Боуден
|
|
|
|
|
Supreme Being
модератор
Last Login: 04.05.2008 13:32
Сообщ.: 7 240,
Visits: 65 445
|
|
| Хороший вопрос. Тут все зависит от конкретной нужды. Отсортированы данные или нет? Нужно искать в любом месте или только в начале?
|
|
|
|
|
Supreme Being
участник
Last Login: 19.10.2008 12:14
Сообщ.: 693,
Visits: 7 081
|
|
Данные отсортированы. Искать нужно в любом месте.
Спасибо!
Евгений Боуден
|
|
|
|
|
Supreme Being
модератор
Last Login: 04.05.2008 13:32
Сообщ.: 7 240,
Visits: 65 445
|
|
| Я бы попробовал создать индекс вхождения букв в строки. То есть буква А (в любом регистре) есть в таких-то строках, буква Б в таких-то и т.д. Тогда при вводе первой буквы уже будем знать номер первой позиции, при вводе второй нужно будет выполнять поиск, только в тех строках где есть первая буква (по ходу формируя массив с номерами строк где есть обе введенные буквы). При вводе третьей буквы продолжаем поиск в номерах позиций найденных в прошлом шаге. Так до момента когда будет найдено или не будет найдено полное совпадение.
|
|
|
|
|
Supreme Being
участник
Last Login: 19.10.2008 12:14
Сообщ.: 693,
Visits: 7 081
|
|
| Я неправильно ответил на вопрос "где искать. С начала или везде?". Подумал что где среди записей искать. Искать совпадения надо всегда от начала слова. А как создать индексы? Не совсем понял.
Спасибо!
Евгений Боуден
|
|
|
|
|
Supreme Being
модератор
Last Login: 04.05.2008 13:32
Сообщ.: 7 240,
Visits: 65 445
|
|
evgenybe (07.11.2006)
А как создать индексы? Не совсем понял.В данном случае индекс можно представить в виде хеш-таблицы где в качестве ключа выступает первая буква слова, а в качестве значения номера строк (в виде массива) где есть слова начинающиеся с этой буквы. Так как создание индекса тоже потребует времени, то можно подготовить его на стороне сервера. Если список не меняется или меняется очень редко, то код JavaScript для инициализации индекса можно разместить в кеше. Тогда скорость поиска должна заметно улучшиться.
|
|
|
|
|
Supreme Being
участник
Last Login: 25.04.2007 11:57
Сообщ.: 77,
Visits: 97
|
|
| В принципе если записи упорядочены по алфавиту то достаточно создать таблицу с номерами первых вхождений каждой буквы, а не всех. Всегда можно определить все как первое вхождение следующей буквы - первое вхождение текущей
|
|
|
|
|
Supreme Being
участник
Last Login: 25.04.2007 11:57
Сообщ.: 77,
Visits: 97
|
|
| Еще подумал, если страница генерируется каким то серверным приложением, а не пишется руками, то не худшей идеей будет сделать не один селект а несколько - по количеству букв в алфавите. И в зависимости от первой веденной буквы делать видимым нужный селект скриптом, а остальные - невидимыми. Вообще можно заменить индексирование через массивы и скрипты н-ным количеством селектов созданных еще на сервере или уже у пользователя скриптом чтобы не слать некоторые елементы по нескольку раз. То есть переслать пользователю скрипт который через document.write создаст это н-ное колчичество селектов. Мне почему то кажется что много елементов это лучше чем много сложных скриптов.
|
|
|
|
|
|
| | |