ReSQL.ru
     
powered by simpleCommunicator - 2.0.61     © 2026 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Алгоритм поиска подстроки в массиве строк
12 сообщений из 12, страница 1 из 1
Алгоритм поиска подстроки в массиве строк
    #38794424
scf
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
scf
Участник
Как ни странно, гугление ничего не дало.
Итак, задача:

Есть большой (10000+ элементов) массив относительно коротких (до 50 символов) строк.
Есть входная строка из 2-5 символов.
Нужно быстро найти все элементы массива, в которых фигурирует эта входная строка.
...
Рейтинг: 0 / 0
02.11.2014, 22:41
| Ответить | Цитировать | Написать  
Алгоритм поиска подстроки в массиве строк
    #38794441
Фотография Akina
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Akina
Участник
Возможность вообще и реализация сильно зависят от среды - как программирования, так и выполнения.
...
Рейтинг: 0 / 0
02.11.2014, 23:40
| Ответить | Цитировать | Написать  
Алгоритм поиска подстроки в массиве строк
    #38794447
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
scf, если поиск идёт 1 раз - то всё равно как искать. Тебе придётся перебирать
каждый символ каждого слова. Чуть-чуть (но не сильно) помогут алгоритмы замечательных людей.
Сходу - они весьма эвристичны и основаны на оптимизации прыжков вперёд в случае
неудач. Берется также за предположение некая "текстовая" энтропия. Тоесть
мы расчитываем что ищем "слово" в "тексте" а не random() массив в другом
случайном массиве.

Если стоит задача в 10000 элементном массиве искать не 1 раз а много раз
другие слова то надо смотреть в сторону построения текстового индекса.
...
Рейтинг: 0 / 0
02.11.2014, 23:57
| Ответить | Цитировать | Написать  
Алгоритм поиска подстроки в массиве строк
    #38794487
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Этот массив в ральности что из себя представляет? Массив в памяти, таблица в БД, файл?
...
Рейтинг: 0 / 0
03.11.2014, 07:43
| Ответить | Цитировать | Написать  
Алгоритм поиска подстроки в массиве строк
    #38794488
scf
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
scf
Участник
Dima T,

Я думаю, в памяти. Если конкретнее, я хочу сделать автокомплит по справочнику из 10-20 тыс элементов, причем с поиском внутри строки, а не только префиксным.
...
Рейтинг: 0 / 0
03.11.2014, 07:45
| Ответить | Цитировать | Написать  
Алгоритм поиска подстроки в массиве строк
    #38794529
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Если в памяти, то попробуй memchr() поиск символа в блоке памяти.
Алгоритм такой: ищешь первый символ, досравниваешь последующие символы - если совпало, вычисляешь начало записи, добавляешь в результат выборки, ищешь дальше до конца блока.

Работает быстро, единственный минус memchr() регистрозависимый.
...
Рейтинг: 0 / 0
03.11.2014, 11:18
| Ответить | Цитировать | Написать  
Алгоритм поиска подстроки в массиве строк
    #38794551
Фотография Ggg_old
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Ggg_old
Участник
да делайте напрямую проверкой каждой строк массива посимвольно. при таких объемах и постановке задачи мудрить особо не надо.
если строки в массиве - слова, т.е. имеют разделитель, я бы пожалуй добавил небольшую оптимизацию - хранил бы позиции начал слов в каждой из строк, что-бы при посимвольном поиске не парсать символы слова, которое уже точнор не совпадает с искомой.
...
Рейтинг: 0 / 0
03.11.2014, 11:56
| Ответить | Цитировать | Написать  
Алгоритм поиска подстроки в массиве строк
    #38796646
alex564657498765453
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
alex564657498765453
Участник
scfDima T,

Я думаю, в памяти. Если конкретнее, я хочу сделать автокомплит по справочнику из 10-20 тыс элементов, причем с поиском внутри строки, а не только префиксным.

давай подумаем
10-20тыс

это 4 нуля. скорость микропроцессора 4 ядра - 8 потоков, 3гига герца 24 и 9 нулей...

тоесть 2 и 10 нулей ...если предположить что для обаботки одной строки (а эт оне так) надо будет 1000 циклов проца то за секунду ориентировочно, 1000 раз процесор просто обойдёт весь масив и поиск подстроки стандартный... ну если 1000 раз не обойдёт, то 10 уж точно...
...
Рейтинг: 0 / 0
05.11.2014, 18:15
| Ответить | Цитировать | Написать  
Алгоритм поиска подстроки в массиве строк
    #38820166
Lepsik
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Lepsik
Участник
суффикс tree используется для поиска в словарях. практические константное время поиска
...
Рейтинг: 0 / 0
29.11.2014, 06:09
| Ответить | Цитировать | Написать  
Алгоритм поиска подстроки в массиве строк
    #38820167
Lepsik
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Lepsik
Участник
YouTube Video
YouTube Video
...
Рейтинг: 0 / 0
29.11.2014, 06:10
| Ответить | Цитировать | Написать  
Алгоритм поиска подстроки в массиве строк
    #38833493
iskatelsql
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
iskatelsql
Участник
Думаю самое лучшее было бы использовать БД, например SQLite с таблицей в памяти + индексы
...
Рейтинг: 0 / 0
14.12.2014, 16:02
| Ответить | Цитировать | Написать  
Алгоритм поиска подстроки в массиве строк
    #38833503
JeStone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
JeStone
Участник
iskatelsql,

у меня первым, что приходит в голову - использование полнотекстового индекса. Но для этого надо испоьлзовать СУБД
...
Рейтинг: 0 / 0
14.12.2014, 16:41
| Ответить | Цитировать | Написать  
12 сообщений из 12, страница 1 из 1
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Алгоритм поиска подстроки в массиве строк
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение   Полит. конфиден.  
NoSQL.ru       Кролег: Проекты, Новости, Чат       РЕД ФОРУМ       Фотоальбом: Участники, Встречи
Закрыть
start [/forum/topic.php?fid=16&msg=38796646&tid=1341140]:
 0ms
get settings:
 10ms
get forum list:
 15ms
check forum access:
 3ms
check topic access:
 3ms
track hit:
 30ms
get topic data:
 9ms
get forum data:
 2ms
get page messages:
 50ms
get tp. blocked users:
 1ms
others: 233ms
total:  356ms
созд. / загр.: 356ms
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]