|
массовый поиск подстрок в строке
|
|||
---|---|---|---|
#18+
господа, есть задача массово искать подстроки в строке. Существующий код, который работает через Contains делает это медленно. Код: c# 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14.
Нужен механизм, которые ищет много строк массово и выдает массив вхождений. 3 8 22 66 найдены. Остальные нет. Я в курсе про Any All ForEach Linq и т.п это все сводиться к циклическим переборам. Нужен быстрый массовый поиск, потому что поиск 600 строк в 65000 строк идет 18 минут и это слишком медленно. Можно добавить AsParallel, но не думаю, что сильно ускорит. ... |
|||
:
Нравится:
Не нравится:
|
|||
21.04.2020, 08:06 |
|
массовый поиск подстрок в строке
|
|||
---|---|---|---|
#18+
Нагуглил функцию, которая работает слегка быстрее Contains и поставил Parallel.ForEach , но ищет все равно медленно. В 2-3 раза быстрее чем было Код: sql 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20. 21. 22. 23. 24. 25. 26. 27. 28. 29. 30. 31. 32.
... |
|||
:
Нравится:
Не нравится:
|
|||
21.04.2020, 10:09 |
|
массовый поиск подстрок в строке
|
|||
---|---|---|---|
#18+
Есть какие идеи у кого? ... |
|||
:
Нравится:
Не нравится:
|
|||
21.04.2020, 10:09 |
|
массовый поиск подстрок в строке
|
|||
---|---|---|---|
#18+
a_voronin господа, есть задача массово искать подстроки в строке. Вы хотите прыгнуть выше головы? Чтобы быстро искать в строках, вам тогда нужен специальный индекс, а не способ поиска в строке. Построение индекса тоже займёт время и много памяти. Также вам нужно найти и разработать алгоритм. Почему вам с ходу тут не ответят? Потому что подобные задачи выносят на уровень баз данных, специализированных средств в базах данных, зачем изобретать велосипед? ... |
|||
:
Нравится:
Не нравится:
|
|||
21.04.2020, 11:20 |
|
массовый поиск подстрок в строке
|
|||
---|---|---|---|
#18+
a_voronin поиск 600 строк в 65000 строк Так у вас получается 39 миллионов поисков. Что выливается в затраты. Чистая математика. ... |
|||
:
Нравится:
Не нравится:
|
|||
21.04.2020, 11:21 |
|
массовый поиск подстрок в строке
|
|||
---|---|---|---|
#18+
В СУБД для подобных задач используют полнотекстовый поиск. Можно СУБД взять или подобный велосипед смастерить. Суть вкратце в следующем: для текста делается индекс {слово, расположение в тексте}, а при поиске сначала ищется слово по индексу. ... |
|||
:
Нравится:
Не нравится:
|
|||
21.04.2020, 12:45 |
|
массовый поиск подстрок в строке
|
|||
---|---|---|---|
#18+
hVostt, Я специалист в первую очередь по базам данных и могу сказать, что полнотекстовый поиск тут не даст большего выигрыша. Зато я когда-то в стародавние времена программировал на ассемблере и могу сказать следующее, что одно ядро 3 ГГц процессора можете за 1 секунду сделать 3 миллиарда сравнений символов и поэтому если бы была бы функция ContainsAll, замапленная на оптимизированный код, то такое сравнение прошло бы за <1 минуту. Тут есть куча оверхеда в виде вызовов методов, конвертации кодировок или какой-то такой фигни. Потому что команда "rep cmpsw" может сравнивать строки со скоростью 3 миллиарда сравнений символов в секунду на одном ядре, а их у меня 8. http://faydoc.tripod.com/cpu/cmpsb.htm Тут даже надо просто оптимизировать вопрос поиска первого символа. ... |
|||
:
Нравится:
Не нравится:
|
|||
21.04.2020, 12:46 |
|
массовый поиск подстрок в строке
|
|||
---|---|---|---|
#18+
a_voronin, гугли grep/ахо-корасик ... |
|||
:
Нравится:
Не нравится:
|
|||
21.04.2020, 12:57 |
|
массовый поиск подстрок в строке
|
|||
---|---|---|---|
#18+
a_voronin Я специалист в первую очередь по базам данных и могу сказать, что полнотекстовый поиск тут не даст большего выигрыша. Ну а на какой выигрышь вы рассчитываете, не пойму? Вы делаете 38 миллионов поисков, каждый из 38 миллионов это сравнение двух массивов. Если считаете, что проблема не в алгоритмах, а в оптимизации процессора, вам нужно в другой форум. В ассемблер, например. С точки зрения алгоритмов, это проблема решения в лоб. Основной способ оптимизации поиска -- индекс. Для поиска по содержимому строки, хеш не подойдёт. Значит нужно строить дерево. Разумеется это выльется в затраты по памяти. И в затраты на разработку и отладку алгоритма. a_voronin Тут даже надо просто оптимизировать вопрос поиска первого символа. Ищете волшебное заклинание? :) Строка это массив символов. Для перебора массива нужен индекс и сравнение. Что вы тут оптимизировать собрались? ) ... |
|||
:
Нравится:
Не нравится:
|
|||
21.04.2020, 14:29 |
|
массовый поиск подстрок в строке
|
|||
---|---|---|---|
#18+
a_voronin Тут есть куча оверхеда в виде вызовов методов, конвертации кодировок или какой-то такой фигни. Ну так а зачем пытаться решать проблему, которая решается на низком уровне, на высоком уровне? ... |
|||
:
Нравится:
Не нравится:
|
|||
21.04.2020, 14:31 |
|
массовый поиск подстрок в строке
|
|||
---|---|---|---|
#18+
hVostt Строка это массив символов. Для перебора массива нужен индекс и сравнение. Что вы тут оптимизировать собрались? ) Кстати можно соптимизировать сравнение, оно совсем не тривиальное в юникоде. Contains() можно попробовать с StringComparison.OrdinalIgnoreCase ... |
|||
:
Нравится:
Не нравится:
|
|||
21.04.2020, 14:37 |
|
массовый поиск подстрок в строке
|
|||
---|---|---|---|
#18+
Dima T Кстати можно соптимизировать сравнение, оно совсем не тривиальное в юникоде. Contains() можно попробовать с StringComparison.OrdinalIgnoreCase да, вот сюда подставить https://docs.microsoft.com/en-US/dotnet/api/system.string.indexof?view=netframework-4.8#System_String_IndexOf_System_String_System_Int32_System_StringComparison_ но это всё равно вызов метода же, а там у ТС лютый бой идёт за каждый тик и непонятно, какого результата он хочет. что есть "быстро" в его понимании? какой результат его устроит? и в каких условиях? ... |
|||
:
Нравится:
Не нравится:
|
|||
21.04.2020, 14:46 |
|
массовый поиск подстрок в строке
|
|||
---|---|---|---|
#18+
booby, попробовал две реализации ахо карасика https://www.toptal.com/algorithms/aho-corasick-algorithm https://gist.github.com/alexandrnikitin/e4176d6b472b39155a7e0e5d68264e65#file-ahocorasicktree-cs К сожалению, обе показали себя кране хреново. Циклу с Contains они уступают в несколько раз. Но это, скорее всего, особенности реализации авторов, которые, например, не подумали о том, конструкция return yeild крайне тормозная. ... |
|||
:
Нравится:
Не нравится:
|
|||
21.04.2020, 15:04 |
|
массовый поиск подстрок в строке
|
|||
---|---|---|---|
#18+
a_voronin К сожалению, обе показали себя кране хреново. Так а "не хреново" это как? ) Какое время вас устроит? ... |
|||
:
Нравится:
Не нравится:
|
|||
21.04.2020, 17:05 |
|
массовый поиск подстрок в строке
|
|||
---|---|---|---|
#18+
a_voronin господа, есть задача массово искать подстроки в строке. Существующий код, который работает через Contains делает это медленно. Код: c# 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14.
Нужен механизм, которые ищет много строк массово и выдает массив вхождений. 3 8 22 66 найдены. Остальные нет. Я в курсе про Any All ForEach Linq и т.п это все сводиться к циклическим переборам. Нужен быстрый массовый поиск, потому что поиск 600 строк в 65000 строк идет 18 минут и это слишком медленно. Можно добавить AsParallel, но не думаю, что сильно ускорит. если строк "example" мало - то БД и индекс видится оптимальным. если строк много - каждый очередной поиск не помнит о предыдушем, и индекс не самое оптимальное. может тогда лучше посмотреть на задачу как "все example это одна строка шаблона"? и искать решение в алгоритмах, которые для регулярок используются, ну, там, суффиксные деревья и прочий матан? ... |
|||
:
Нравится:
Не нравится:
|
|||
21.04.2020, 17:07 |
|
массовый поиск подстрок в строке
|
|||
---|---|---|---|
#18+
booby a_voronin, гугли grep/ахо-корасик + ... |
|||
:
Нравится:
Не нравится:
|
|||
21.04.2020, 17:09 |
|
массовый поиск подстрок в строке
|
|||
---|---|---|---|
#18+
love_bach, Я уже две версии кода ахтунг-карася попробовал. Не рулез. ... |
|||
:
Нравится:
Не нравится:
|
|||
21.04.2020, 17:15 |
|
массовый поиск подстрок в строке
|
|||
---|---|---|---|
#18+
hVostt, Вот эта быстрее всего. FastIndexOf Меня устроит полминуты. 800 строк по 10-30 символов, найти каждая входит или нет в 90000 строк от 200 до 8000 символов (в среднем 2000). Сколько по вашему должен работать оптимальный алгоритм, тот же самый ахо-карасик? По мне так за 10 сек, если все в памяти и должен выдать массив со счетчиком вхождений. ... |
|||
:
Нравится:
Не нравится:
|
|||
21.04.2020, 17:18 |
|
массовый поиск подстрок в строке
|
|||
---|---|---|---|
#18+
a_voronin love_bach, Я уже две версии кода ахтунг-карася попробовал. Не рулез. они там двухпроходные, если я не забыл все. за первый проход что-то типа индекса строится. если время первого прохода выбросить, то все равно медленно? ... |
|||
:
Нравится:
Не нравится:
|
|||
21.04.2020, 17:21 |
|
массовый поиск подстрок в строке
|
|||
---|---|---|---|
#18+
алгоритм Кнута, Морриса еще глянь ... |
|||
:
Нравится:
Не нравится:
|
|||
21.04.2020, 17:32 |
|
массовый поиск подстрок в строке
|
|||
---|---|---|---|
#18+
https://ru.wikipedia.org/wiki/Алгоритм_Кнута_—_Морриса_—_Пратта есть обобщения, чтобы искать не строки, а шаблоны - тоже эффективные ... |
|||
:
Нравится:
Не нравится:
|
|||
21.04.2020, 17:33 |
|
массовый поиск подстрок в строке
|
|||
---|---|---|---|
#18+
love_bach, Да там в обоих случаях два этапа -- первый построение дерева, второй скан деревом входной строки. ... |
|||
:
Нравится:
Не нравится:
|
|||
21.04.2020, 17:35 |
|
массовый поиск подстрок в строке
|
|||
---|---|---|---|
#18+
a_voronin love_bach, Да там в обоих случаях два этапа -- первый построение дерева, второй скан деревом входной строки. ну за один проход пока не придумали ... |
|||
:
Нравится:
Не нравится:
|
|||
21.04.2020, 17:39 |
|
массовый поиск подстрок в строке
|
|||
---|---|---|---|
#18+
love_bach a_voronin love_bach, Да там в обоих случаях два этапа -- первый построение дерева, второй скан деревом входной строки. ну за один проход пока не придумали это вообще возможно впринципе? ... |
|||
:
Нравится:
Не нравится:
|
|||
21.04.2020, 17:48 |
|
массовый поиск подстрок в строке
|
|||
---|---|---|---|
#18+
love_bach love_bach пропущено... ну за один проход пока не придумали это вообще возможно впринципе? Вы сами ахо карасика смотрели? Он за один проход работает. Построение дерева делается от исходных слов до начала прохода. ... |
|||
:
Нравится:
Не нравится:
|
|||
21.04.2020, 18:07 |
|
|
start [/forum/topic.php?fid=20&fpage=10&tid=1398562]: |
0ms |
get settings: |
8ms |
get forum list: |
13ms |
check forum access: |
4ms |
check topic access: |
4ms |
track hit: |
52ms |
get topic data: |
11ms |
get forum data: |
2ms |
get page messages: |
64ms |
get tp. blocked users: |
2ms |
others: | 228ms |
total: | 388ms |
0 / 0 |