Новые сообщения [новые:0]
Дайджест
Горячие темы
Избранное [новые:0]
Форумы
Пользователи
Статистика
Статистика нагрузки
Мод. лог
Поиск
|
|
02.11.2014, 22:41
|
|||
|---|---|---|---|
Алгоритм поиска подстроки в массиве строк |
|||
|
#18+
Как ни странно, гугление ничего не дало. Итак, задача: Есть большой (10000+ элементов) массив относительно коротких (до 50 символов) строк. Есть входная строка из 2-5 символов. Нужно быстро найти все элементы массива, в которых фигурирует эта входная строка. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
02.11.2014, 23:40
|
|||
|---|---|---|---|
Алгоритм поиска подстроки в массиве строк |
|||
|
#18+
Возможность вообще и реализация сильно зависят от среды - как программирования, так и выполнения. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
02.11.2014, 23:57
|
|||
|---|---|---|---|
Алгоритм поиска подстроки в массиве строк |
|||
|
#18+
scf, если поиск идёт 1 раз - то всё равно как искать. Тебе придётся перебирать каждый символ каждого слова. Чуть-чуть (но не сильно) помогут алгоритмы замечательных людей. Сходу - они весьма эвристичны и основаны на оптимизации прыжков вперёд в случае неудач. Берется также за предположение некая "текстовая" энтропия. Тоесть мы расчитываем что ищем "слово" в "тексте" а не random() массив в другом случайном массиве. Если стоит задача в 10000 элементном массиве искать не 1 раз а много раз другие слова то надо смотреть в сторону построения текстового индекса. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
03.11.2014, 07:43
|
|||
|---|---|---|---|
Алгоритм поиска подстроки в массиве строк |
|||
|
#18+
Этот массив в ральности что из себя представляет? Массив в памяти, таблица в БД, файл? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
03.11.2014, 07:45
|
|||
|---|---|---|---|
Алгоритм поиска подстроки в массиве строк |
|||
|
#18+
Dima T, Я думаю, в памяти. Если конкретнее, я хочу сделать автокомплит по справочнику из 10-20 тыс элементов, причем с поиском внутри строки, а не только префиксным. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
03.11.2014, 11:18
|
|||
|---|---|---|---|
Алгоритм поиска подстроки в массиве строк |
|||
|
#18+
Если в памяти, то попробуй memchr() поиск символа в блоке памяти. Алгоритм такой: ищешь первый символ, досравниваешь последующие символы - если совпало, вычисляешь начало записи, добавляешь в результат выборки, ищешь дальше до конца блока. Работает быстро, единственный минус memchr() регистрозависимый. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
03.11.2014, 11:56
|
|||
|---|---|---|---|
Алгоритм поиска подстроки в массиве строк |
|||
|
#18+
да делайте напрямую проверкой каждой строк массива посимвольно. при таких объемах и постановке задачи мудрить особо не надо. если строки в массиве - слова, т.е. имеют разделитель, я бы пожалуй добавил небольшую оптимизацию - хранил бы позиции начал слов в каждой из строк, что-бы при посимвольном поиске не парсать символы слова, которое уже точнор не совпадает с искомой. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
05.11.2014, 18:15
|
|||
|---|---|---|---|
|
|||
Алгоритм поиска подстроки в массиве строк |
|||
|
#18+
scfDima T, Я думаю, в памяти. Если конкретнее, я хочу сделать автокомплит по справочнику из 10-20 тыс элементов, причем с поиском внутри строки, а не только префиксным. давай подумаем 10-20тыс это 4 нуля. скорость микропроцессора 4 ядра - 8 потоков, 3гига герца 24 и 9 нулей... тоесть 2 и 10 нулей ...если предположить что для обаботки одной строки (а эт оне так) надо будет 1000 циклов проца то за секунду ориентировочно, 1000 раз процесор просто обойдёт весь масив и поиск подстроки стандартный... ну если 1000 раз не обойдёт, то 10 уж точно... ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
29.11.2014, 06:09
|
|||
|---|---|---|---|
Алгоритм поиска подстроки в массиве строк |
|||
|
#18+
суффикс tree используется для поиска в словарях. практические константное время поиска ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
29.11.2014, 06:10
|
|||
|---|---|---|---|
Алгоритм поиска подстроки в массиве строк |
|||
|
#18+
... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
14.12.2014, 16:02
|
|||
|---|---|---|---|
|
|||
Алгоритм поиска подстроки в массиве строк |
|||
|
#18+
Думаю самое лучшее было бы использовать БД, например SQLite с таблицей в памяти + индексы ... |
|||
|
:
Нравится:
Не нравится:
|
|||
|
|
|
start [/forum/topic.php?fid=16&mobile=1&tid=1341140]: |
0ms |
get settings: |
8ms |
get forum list: |
15ms |
check forum access: |
3ms |
check topic access: |
3ms |
track hit: |
153ms |
get topic data: |
11ms |
get forum data: |
2ms |
get page messages: |
43ms |
get tp. blocked users: |
1ms |
| others: | 211ms |
| total: | 450ms |
| 0 / 0 |
