|
массовый поиск подстрок в строке
|
|||
---|---|---|---|
#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 |
|
массовый поиск подстрок в строке
|
|||
---|---|---|---|
#18+
a_voronin, ахо-корасик - это комбинация однопроходного пратта с поиском по словарю Критично время поиска по словарю, если пренебречь временем его построения. Исходный алгоритм работал на trie (сначала переводили как бор, теперь вроде луч прижился) - старая структура 1959 года рождения. В её исходном виде преимущество состоит в совмещении общего префикса в шаблонах поиска - при наличии общего префикса в отыскиваемых строках, поиск автоматически идет по всему подмножеству элементов словаря с таким общим префиксом. Недостаток - расточительность по памяти на "современных" строках. В какой-то момент структура умерла из-за требований по памяти на расширившемся общем строковом алфавите. При неудачных реализациях может проигрывать по скорости другим вариантам организации словаря. Было несколько попыток вдохнуть вторую жизнь в эту структуру. Как просто модернизацией конструкции - типа перехода к троичному дереву, так и совмещением с идеями поразрядной сортировки. Почитай у Седжвика - он много времени этому вопросу сам посвятил. Ахо-Корасик не обязан выигрывать просто потому, что есть словарь К нему мозг в конкретной ситуации рекомендуется прикладывать... Его пригодность к работе на потоке данных без возврата к предыдущим символам потока - это как раз то, что в определенных ситуациях важнее всего остального. Потому и прикладывают... ... |
|||
:
Нравится:
Не нравится:
|
|||
21.04.2020, 18:24 |
|
массовый поиск подстрок в строке
|
|||
---|---|---|---|
#18+
a_voronin love_bach пропущено... это вообще возможно впринципе? Вы сами ахо карасика смотрели? Он за один проход работает. Построение дерева делается от исходных слов до начала прохода. я уже могу путаться, но Кнут-Моррис-Прат - точно за два если ишешь именно алгоритм, то тебе дорога в суффиксные деревья ... |
|||
:
Нравится:
Не нравится:
|
|||
21.04.2020, 18:26 |
|
массовый поиск подстрок в строке
|
|||
---|---|---|---|
#18+
a_voronin Сколько по вашему должен работать оптимальный алгоритм, тот же самый ахо-карасик? По мне так за 10 сек, если все в памяти и должен выдать массив со счетчиком вхождений. Так на сложность алгоритма смотрите. Сколько операций нужно сделать, чудес-то не бывает. У вас 35 миллионов сравнений. Разделим на 10 секунд, которые вы хотите. Значит в секунду должно отрабатывать 3.5 млн сравнений. Но это без учёта длины строк. Мы не знаем что вы там и с чём сравниваете. Скорость вычисления вхождения строки из 10 символов в строке 100 символов будет отличаться от строки из 100 символов в строке 10000 символов. Мы не знаем что у вас там за исходные данные. ... |
|||
:
Нравится:
Не нравится:
|
|||
21.04.2020, 18:39 |
|
массовый поиск подстрок в строке
|
|||
---|---|---|---|
#18+
hVostt a_voronin Сколько по вашему должен работать оптимальный алгоритм, тот же самый ахо-карасик? По мне так за 10 сек, если все в памяти и должен выдать массив со счетчиком вхождений. Так на сложность алгоритма смотрите. Сколько операций нужно сделать, чудес-то не бывает. У вас 35 миллионов сравнений. Разделим на 10 секунд, которые вы хотите. Значит в секунду должно отрабатывать 3.5 млн сравнений. Но это без учёта длины строк. Мы не знаем что вы там и с чём сравниваете. Скорость вычисления вхождения строки из 10 символов в строке 100 символов будет отличаться от строки из 100 символов в строке 10000 символов. Мы не знаем что у вас там за исходные данные. ну, он видимо про линейность сложности. а тут х..якс - вроде и линейно, но сильно высокая ... |
|||
:
Нравится:
Не нравится:
|
|||
21.04.2020, 19:02 |
|
массовый поиск подстрок в строке
|
|||
---|---|---|---|
#18+
hVostt Так на сложность алгоритма смотрите. Сколько операций нужно сделать, чудес-то не бывает Какого алгоритма? ... |
|||
:
Нравится:
Не нравится:
|
|||
21.04.2020, 19:09 |
|
массовый поиск подстрок в строке
|
|||
---|---|---|---|
#18+
love_bach hVostt Так на сложность алгоритма смотрите. Сколько операций нужно сделать, чудес-то не бывает Какого алгоритма? Ну в данном случае алгоритм -- простой перебор, строк, затем символов в строках. ... |
|||
:
Нравится:
Не нравится:
|
|||
21.04.2020, 19:19 |
|
массовый поиск подстрок в строке
|
|||
---|---|---|---|
#18+
love_bach ну, он видимо про линейность сложности. а тут х..якс - вроде и линейно, но сильно высокая Это примерно как в магазин ходить и спрашивать "а чёт так дорого-то?" :) А сколько "не дорого"? Т.е. почему мои N операций выполняются долго? Почему это "долго"? По сравнению с чем? Это ж странно. Непонятна какая задача. Достигнуть символического комфорта? 10 секунд долго, но 9 уже нормас? ... |
|||
:
Нравится:
Не нравится:
|
|||
21.04.2020, 19:22 |
|
массовый поиск подстрок в строке
|
|||
---|---|---|---|
#18+
hVostt love_bach пропущено... Какого алгоритма? Ну в данном случае алгоритм -- простой перебор, строк, затем символов в строках. hVostt - это не перебор. ТС тоже это понимает ... |
|||
:
Нравится:
Не нравится:
|
|||
21.04.2020, 19:33 |
|
массовый поиск подстрок в строке
|
|||
---|---|---|---|
#18+
a_voronin поиск 600 строк в 65000 строк идет 18 минут и это слишком медленно Попробовал посчитать скорость: допустим в каждой из 65000 строк в среднем 1000 символов (с запасом), т.е. 65 млн. символов. Один поиск идет 18 минут / 600 = 1.8 сек. Отсюда скорость поиска 65 млн. символов / 1.8 сек = 36.1 млн. символов / сек. При частоте проца 3,6 ГГц - 100 тактов на одно сравнение. Это как бы вообще тормоз. ИМХО тут что-то важное не озвучено, то на что действительно тратится время. Тут надо искать a_voronin Код: c# 1.
... |
|||
:
Нравится:
Не нравится:
|
|||
21.04.2020, 20:19 |
|
массовый поиск подстрок в строке
|
|||
---|---|---|---|
#18+
Dima T, Как бы мы тут все гадаем, как же ускорить неизвестный код с неизвестными нам данными ... |
|||
:
Нравится:
Не нравится:
|
|||
21.04.2020, 23:43 |
|
массовый поиск подстрок в строке
|
|||
---|---|---|---|
#18+
love_bach hVostt - это не перебор. ТС тоже это понимает Ну что там ещё? Вычисление интегралов? Экстраполирование? Расчёт пути в графе? ))) ... |
|||
:
Нравится:
Не нравится:
|
|||
21.04.2020, 23:43 |
|
массовый поиск подстрок в строке
|
|||
---|---|---|---|
#18+
Dima T a_voronin поиск 600 строк в 65000 строк идет 18 минут и это слишком медленно Попробовал посчитать скорость: допустим в каждой из 65000 строк в среднем 1000 символов (с запасом), т.е. 65 млн. символов. Один поиск идет 18 минут / 600 = 1.8 сек. Отсюда скорость поиска 65 млн. символов / 1.8 сек = 36.1 млн. символов / сек. При частоте проца 3,6 ГГц - 100 тактов на одно сравнение. Это как бы вообще тормоз. ИМХО тут что-то важное не озвучено, то на что действительно тратится время. Тут надо искать a_voronin Код: c# 1.
Наиболее трудоемкое для процессора действия это вызов метода. CALL. Второе по трудоемкости -- это условный переход. А если вы пишете операции со строками, то вызовом метода там немало. Все свойства это методы. Тут вопрос скорее всего не в алгоритме, а в том, чтобы найти оптимизированный, оптимально написанный код. ... |
|||
:
Нравится:
Не нравится:
|
|||
22.04.2020, 08:01 |
|
массовый поиск подстрок в строке
|
|||
---|---|---|---|
#18+
[quot hVostt#22120128] a_voronin Значит в секунду должно отрабатывать 3.5 млн сравнений. За секунду может срабатывать 3 миллиарда x 8 = 24 сравнений символов. Не вижу причин, которым нельзя работать с такой скоростью. Попробую может вечером как-нибудь в качестве спортивного интереса написать на unmanaged коде без вызова методов. Код собственно говоря выглядит вот так. Код: c# 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. 33. 34. 35. 36. 37. 38. 39. 40. 41. 42. 43. 44. 45. 46. 47. 48. 49. 50. 51. 52. 53.
В среднем в строке может встречаться 20 подстрок. Если одно вхождение конкретной строки найдено, других искать не надо. Если брекить дебаггер он как правило встает здесь. first = source.IndexOf(c0, ++first, limit - first); А вообще простая строка кода превращается в нагромождение непонятно чего. Вот на такие вызовы методов и тратятся такты. Код: sql 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14.
... |
|||
:
Нравится:
Не нравится:
|
|||
22.04.2020, 08:17 |
|
массовый поиск подстрок в строке
|
|||
---|---|---|---|
#18+
a_voronin Меня устроит полминуты. 800 строк по 10-30 символов, найти каждая входит или нет в 90000 строк от 200 до 8000 символов (в среднем 2000). … должен выдать массив со счётчиком. a_voronin Нужен механизм, которые ищет много строк массово и выдает массив вхождений. 3 8 22 66 найдены. Остальные нет. Нужен быстрый массовый поиск, потому что поиск 600 строк в 65000 строк идет 18 минут и это слишком медленно. Если вы уверены что проблема в языке/оптимизации кода то я вам помочь не могу, но и мнение ваше не разделяю. Тот код что вы смотрите и тот что выполняется на процессоре уже может отличатся и CLR наверняка заменит source.IndexOf(c0, 0, limit); на низкоуровневый cmpsw. А для оптимизации алгоритма нужно кое-что уточнить. — В чем у вас проблема? Если набор поиска и набор строк текста постоянный то запишите сразу результату поиска. Я так предполагаю что у вас или набор строк поиска или набор строк текста или оба не постоянный. Проясните что. — Текст на каком языке? — что является источником меняемого набора (поиска или текста)? a_voroninВ среднем в строке может встречаться 20 подстрок. Если одно вхождение конкретной строки найдено, других искать не надо. — любое вхождение или первое? — что нужно узнать: что вхождение есть, вхождение какой подстроки (давайте уже использовать подходящий лексикон — шаблон) или место вхождения? ... |
|||
:
Нравится:
Не нравится:
|
|||
22.04.2020, 09:40 |
|
массовый поиск подстрок в строке
|
|||
---|---|---|---|
#18+
mikron, Это анализ залогированных MDX запросов для сбора статистики об использовании показателей. Показатели постоянны, запросы разные. C# по оптимизации кода явно уступает C++. На C++ здесь вообще не было бы вызова метода. if (source[first + 1] != c1) { Код я смотрю в дебаге. По нему можно ходить дебаггером и смотреть регистры. Поэтому это явно реальный конечный код. Goto Dissasembly не заглядывали? ... |
|||
:
Нравится:
Не нравится:
|
|||
22.04.2020, 10:08 |
|
массовый поиск подстрок в строке
|
|||
---|---|---|---|
#18+
mikron — любое вхождение или первое? — что нужно узнать: что вхождение есть, вхождение какой подстроки (давайте уже использовать подходящий лексикон — шаблон) или место вхождения? если вы посмотрите на начало поста, то там сформулирована задача "Нужен механизм, которые ищет много строк массово и выдает массив вхождений. 3 8 22 66 найдены. Остальные нет." Факт наличия нескольких подстрок в строке. Даже не количество и не позиции. ... |
|||
:
Нравится:
Не нравится:
|
|||
22.04.2020, 10:09 |
|
массовый поиск подстрок в строке
|
|||
---|---|---|---|
#18+
a_voronin, А код обработки учитываете? Вместе с довольно ресурсоёмким локом-монитором? FastIndexOf содержит весьма сомнительные и нафиг не нужные оптимизации. Почему не используете StringComparison.Ordinal? ... |
|||
:
Нравится:
Не нравится:
|
|||
22.04.2020, 11:20 |
|
массовый поиск подстрок в строке
|
|||
---|---|---|---|
#18+
a_voronin, Давайте сначала уточним определения. "Факт наличия нескольких подстрок в строке. " "подстрока" - шаблон поиска. "строка" или текст, в котом происходит поиск. Таким образом у вас набор шаблонов поиска постоянный, или почти постоянный и меняется редко, верно? Ваша проблема заключается в том что поиск в динамическом наборе строк выполнятся медленно, но сам набор строк динамичен и не известен заранее. т.е. его нельзя предварительно обработать. Верно? Тепер ещё раз к постановке задачи: автор"Нужен механизм, которые ищет много строк массово и выдает массив вхождений. 3 8 22 66 найдены. Остальные нет." В среднем в строке может встречаться 20 подстрок. Если одно вхождение конкретной строки найдено, других искать не надо. Факт наличия нескольких подстрок в строке. Даже не количество и не позиции. Ваши условия противоречивы: Если вам не интересуют какие конкретно шаблоны найдены и где они найдены то что есть "массив вхождений. 3 8 22 66 найдены." "Если одно вхождение конкретной строки найдено, других искать не надо." Если 'то условие верно как понимать "Факт наличия нескольких подстрок в строке." вообше не может быть установлен так - как для 'того надо минимум совпадение двух шаблонов. Уточните пожалуйста. ... |
|||
:
Нравится:
Не нравится:
|
|||
22.04.2020, 11:32 |
|
массовый поиск подстрок в строке
|
|||
---|---|---|---|
#18+
mikron, Ищем постоянный набор строк ["яблоки", "груши", "сливы", "ананасы"] В строке поиска "В саду созрели груши и сливы" ответ ["груши", "сливы"] или [1,2] при нумерации от 0 "У нас не растут ананасы, выращивайте яблоки" ответ ["яблоки", "ананасы"] или [0,3] ... |
|||
:
Нравится:
Не нравится:
|
|||
22.04.2020, 12:37 |
|
массовый поиск подстрок в строке
|
|||
---|---|---|---|
#18+
a_voronin mikron, Ищем постоянный набор строк ["яблоки", "груши", "сливы", "ананасы"] В строке поиска "В саду созрели груши и сливы" ответ ["груши", "сливы"] или [1,2] при нумерации от 0 "У нас не растут ананасы, выращивайте яблоки" ответ ["яблоки", "ананасы"] или [0,3] Вы совсем запутали меня. Значит нас интересуют какие шаблоны найдены? Нам нужно знать все шаблоны, или только первый, или любой, или только что минимум два, или что минимум два разных, или вообще что хоть один? Я не из дотошности спрашиваю, просто это разные задачи и для них разные методы. Ищем постоянный набор строк ["яблоки", "груши", "сливы", "ивы", "ананасы"] В строке поиска "В саду росли яблоки и сливы" Ответ "шаблон найден" верный? Ответ ["яблоки"] верный? Ответ ["ивы"] верный? Ответ ["яблоки", "ивы"] верный? Ответ ["ивы", "яблоки"] верный? Ответ ["ивы", "сливы"] верный? Ответ ["яблоки", "сливы", "ивы"] верный? В строке поиска "В саду росли сливы" Ответ "шаблон найден" верный? Ответ ["ивы"] верный? Ответ ["ивы", "сливы"] верный? ... |
|||
:
Нравится:
Не нравится:
|
|||
22.04.2020, 13:04 |
|
массовый поиск подстрок в строке
|
|||
---|---|---|---|
#18+
mikron, Ищем постоянный набор строк ["яблоки", "груши", "сливы", "ивы", "ананасы"] В строке поиска "В саду росли яблоки и сливы" Ответ ["яблоки", "сливы", "ивы"] верный. Но в моей реальной задаче не будет "сливы", "ивы" все строки уникальны и ни одна не является подстрокой другой. то есть ответ Ответ ["яблоки", "сливы"] тоже устроит. Хотя, я так понимаю может быть нюанс в реализации. ... |
|||
:
Нравится:
Не нравится:
|
|||
22.04.2020, 14:22 |
|
массовый поиск подстрок в строке
|
|||
---|---|---|---|
#18+
mikron a_voronin mikron, Ищем постоянный набор строк ["яблоки", "груши", "сливы", "ананасы"] В строке поиска "В саду созрели груши и сливы" ответ ["груши", "сливы"] или [1,2] при нумерации от 0 "У нас не растут ананасы, выращивайте яблоки" ответ ["яблоки", "ананасы"] или [0,3] Вы совсем запутали меня. Значит нас интересуют какие шаблоны найдены? Нам нужно знать все шаблоны, или только первый, или любой, или только что минимум два, или что минимум два разных, или вообще что хоть один? Я не из дотошности спрашиваю, просто это разные задачи и для них разные методы . Ищем постоянный набор строк ["яблоки", "груши", "сливы", "ивы", "ананасы"] В строке поиска "В саду росли яблоки и сливы" Ответ "шаблон найден" верный? Ответ ["яблоки"] верный? Ответ ["ивы"] верный? Ответ ["яблоки", "ивы"] верный? Ответ ["ивы", "яблоки"] верный? Ответ ["ивы", "сливы"] верный? Ответ ["яблоки", "сливы", "ивы"] верный? В строке поиска "В саду росли сливы" Ответ "шаблон найден" верный? Ответ ["ивы"] верный? Ответ ["ивы", "сливы"] верный? приведи хотя бы один ... |
|||
:
Нравится:
Не нравится:
|
|||
22.04.2020, 14:31 |
|
массовый поиск подстрок в строке
|
|||
---|---|---|---|
#18+
a_voronin mikron, Ищем постоянный набор строк ["яблоки", "груши", "сливы", "ивы", "ананасы"] В строке поиска "В саду росли яблоки и сливы" Ответ ["яблоки", "сливы", "ивы"] верный. то есть ответ Ответ ["яблоки", "сливы"] тоже устроит. 1.Вариант: вариация Карп-Рабин. (условие - мин. длина шаблона 8 символов) 1.0. Подготовка к поиску 1.1. Представте шаблоны в масивы байт. 1.2. Пострийте хештаблицу на ваши шаблоны. Именно таблицу на массивах без классов блиблиотеки. особенно важно как строить. для каждого шаблона каждые 4 байта и есть хеш. т.е. 0..3, 1..4, 2..5, 3..6, 4..7, .... Сама таблица [номер шаблона << 4 + смешение начала ] 1.3. Поиск 1.4. Перевидите строку в байты. Сравнивайте с хештаблицей. Если поподание есть то проверит полное соответсвие. Сравниваите толко с 4-х кратнзч позиций. 0..3, 4..7, 8..11, ... 2. Вариант: если шаблоны короткие но длинее 3 символов. Идея как вариант1, но хеш фукция должна быстро строится и подстариватся. Я уже не помню как такой класс хеш функций называется но XOR как раз о ней. ... |
|||
:
Нравится:
Не нравится:
|
|||
22.04.2020, 16:47 |
|
массовый поиск подстрок в строке
|
|||
---|---|---|---|
#18+
a_voronin, Если у вас данные секрета не представляют, выложите тут, потренируемся на них. ... |
|||
:
Нравится:
Не нравится:
|
|||
22.04.2020, 17:55 |
|
массовый поиск подстрок в строке
|
|||
---|---|---|---|
#18+
mikron, Вот тестовые данные -- попробуйте перебить обычный цикл с Contains? Код: c# 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. 33. 34. 35. 36. 37. 38. 39. 40. 41. 42. 43. 44. 45. 46. 47. 48. 49. 50. 51. 52. 53. 54. 55. 56. 57. 58. 59. 60. 61. 62. 63. 64.
... |
|||
:
Нравится:
Не нравится:
|
|||
22.04.2020, 18:07 |
|
массовый поиск подстрок в строке
|
|||
---|---|---|---|
#18+
авторa_voronin, Вот эта быстрее всего. FastIndexOf Меня устроит полминуты. 800 строк по 10-30 символов, найти каждая входит или нет в 90000 строк от 200 до 8000 символов (в среднем 2000). Вот опят вы всё смешиваете. В ваших тестовых данных нет ни 800 шаблонов ни 10-30 символов в шаблоне, да и сами шаблоны наверняка имеет очень плохо распределение пар символов. Для ваших тестовых данных _возможно_ contains и будет самым быстрым. Из них вы можете только сделать неправильный вывод что отимизация - единственный верный путь. Мне это не интересно. К тому-же вы сравниваете время выполнения с разбиением на потоки / таски. Я такое вообще не воспринимаю серьезно. Давайте нормальные данные. ... |
|||
:
Нравится:
Не нравится:
|
|||
22.04.2020, 18:28 |
|
массовый поиск подстрок в строке
|
|||
---|---|---|---|
#18+
a_voronin Вот тестовые данные -- попробуйте перебить обычный цикл с Contains? Пока вы пытаетесь оптимизировать в лоб, экономия на спичках. Было у вас 18 минут, с FastIndexOf вы получите на десяток секунд быстрее. Распараллеливание на практике не кратно множителю. На таких объёмах нужны специальные алгоритмы поиска, подходящие для вас. А лучше, всё же, выносить подобные задачи на уровень БД. ... |
|||
:
Нравится:
Не нравится:
|
|||
22.04.2020, 22:44 |
|
массовый поиск подстрок в строке
|
|||
---|---|---|---|
#18+
hVostt a_voronin Вот тестовые данные -- попробуйте перебить обычный цикл с Contains? Пока вы пытаетесь оптимизировать в лоб, экономия на спичках. Было у вас 18 минут, с FastIndexOf вы получите на десяток секунд быстрее. Распараллеливание на практике не кратно множителю. На таких объёмах нужны специальные алгоритмы поиска, подходящие для вас. А лучше, всё же, выносить подобные задачи на уровень БД. Я уже писал выше, я попробовал два Эхо-Карасика, которых нашел в Инете и прибавки не получил. Вопрос в том, что весь эффект съедается неоптимальностью компилятора. Нужен алгоритм, который не только оптимален сам, но ещё и вызывает оптимальные код, типа одного Contains или Replace на проверку. На самом деле если эту FastInsexOf перетащить на С++ она в 10 раз ускорится. ... |
|||
:
Нравится:
Не нравится:
|
|||
23.04.2020, 07:44 |
|
массовый поиск подстрок в строке
|
|||
---|---|---|---|
#18+
mikron авторa_voronin, Вот эта быстрее всего. FastIndexOf Меня устроит полминуты. 800 строк по 10-30 символов, найти каждая входит или нет в 90000 строк от 200 до 8000 символов (в среднем 2000). Вот опят вы всё смешиваете. В ваших тестовых данных нет ни 800 шаблонов ни 10-30 символов в шаблоне, да и сами шаблоны наверняка имеет очень плохо распределение пар символов. Для ваших тестовых данных _возможно_ contains и будет самым быстрым. Из них вы можете только сделать неправильный вывод что отимизация - единственный верный путь. Мне это не интересно. К тому-же вы сравниваете время выполнения с разбиением на потоки / таски. Я такое вообще не воспринимаю серьезно. Давайте нормальные данные. mikron Я не новичек в программировании и просидел в дебаггере ни один десяток суток за свою карьеру. То что я дал схоже по характеру с реальными данными, но если вы возьмете реальный объем, то замучаетесь ждать эти 18 минут при отладке. А если увеличите длину строк, будет мало совпадений. Вы обратили внимание, что есть две константы, которые управляют количеством и длиной строк для поиска. int MAX = 10000; int MAX2 = 1000; Если хотите больше входных строк, то нетрудно дописать, что-то вроде такого. string[] strs = new string[] { "AAC00", "1248A", "1258A", "1348A", "D248A", "1D48A", "12D8A", "1248D", "A0CAD", "1048A", "0258A", "0348A", "D208A", "1D08A", "10D8A", "1240D", "A7C33", "1247A", "1257A", "13487", "D247A", "1D47A", "17D8A", "1278D", }.SelectMany(s => Enumerable.Range(0, 35).Select(n => $"{s}{n}")).ToArray(); Код: c# 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. 33. 34. 35. 36. 37. 38. 39. 40. 41. 42. 43. 44. 45. 46. 47. 48. 49. 50. 51. 52. 53. 54. 55. 56. 57. 58. 59. 60. 61. 62. 63. 64. 65.
... |
|||
:
Нравится:
Не нравится:
|
|||
23.04.2020, 07:57 |
|
массовый поиск подстрок в строке
|
|||
---|---|---|---|
#18+
a_voronin, Ну а заменить Код: c# 1. 2. 3. 4. 5. 6.
на Код: c# 1. 2. 3. 4. 5. 6.
тоже несложно. ... |
|||
:
Нравится:
Не нравится:
|
|||
23.04.2020, 07:59 |
|
массовый поиск подстрок в строке
|
|||
---|---|---|---|
#18+
эммм found[i]++ при параллельном выполнении это норм? ... |
|||
:
Нравится:
Не нравится:
|
|||
23.04.2020, 08:44 |
|
массовый поиск подстрок в строке
|
|||
---|---|---|---|
#18+
Roman Mejtes, Не норм. Но в боевом коде у меня стоит вот что Код: c# 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20.
... |
|||
:
Нравится:
Не нравится:
|
|||
23.04.2020, 09:03 |
|
массовый поиск подстрок в строке
|
|||
---|---|---|---|
#18+
достаточно использовать interlock, тем более, если речь идёт о перформансе ... |
|||
:
Нравится:
Не нравится:
|
|||
23.04.2020, 10:01 |
|
массовый поиск подстрок в строке
|
|||
---|---|---|---|
#18+
Roman Mejtes достаточно использовать interlock, тем более, если речь идёт о перформансе Это в тесте используется оператор ++. А в реальном коде совершенно иная более сложная логика с наполнение списков и т.п. Просто это все сейчас лишнее для данной темы. Вопрос в том, как быстро делать поиск, а не что делать после этого. ... |
|||
:
Нравится:
Не нравится:
|
|||
23.04.2020, 11:00 |
|
массовый поиск подстрок в строке
|
|||
---|---|---|---|
#18+
a_voronin, вообще-то желательно иметь стандартные образцы обоих файлов - с шаблонами поиска и набором строк, в которых поиск происходит. Иначе нет базы для сравнения для тех, кто захочет что-то испытывать и улучшать.... ... |
|||
:
Нравится:
Не нравится:
|
|||
23.04.2020, 12:59 |
|
массовый поиск подстрок в строке
|
|||
---|---|---|---|
#18+
a_voronin, Алгоритм, кототрый я описал может подойти для вашего случая с длиной шаблонов 10-30 символов, но не для вашего теста. booby вообще-то желательно иметь стандартные образцы обоих файлов - с шаблонами поиска и набором строк, в которых поиск происходит. Иначе нет базы для сравнения для тех, кто захочет что-то испытывать и улучшать.... Я так/же присоединяюсь, т.к. тест с Guid.NewGuid().ToString() нелзя воспроизвести. Выложите пожалуста пусть даже тестовые данные на гитхабе. Я на выходных затестирую. ... |
|||
:
Нравится:
Не нравится:
|
|||
23.04.2020, 13:10 |
|
массовый поиск подстрок в строке
|
|||
---|---|---|---|
#18+
a_voronin hVostt, Я специалист в первую очередь по базам данных и могу сказать, что полнотекстовый поиск тут не даст большего выигрыша. Зато я когда-то в стародавние времена программировал на ассемблере и могу сказать следующее, что одно ядро 3 ГГц процессора можете за 1 секунду сделать 3 миллиарда сравнений символов и поэтому если бы была бы функция ContainsAll, замапленная на оптимизированный код, то такое сравнение прошло бы за <1 минуту. Тут есть куча оверхеда в виде вызовов методов, конвертации кодировок или какой-то такой фигни. Потому что команда "rep cmpsw" может сравнивать строки со скоростью 3 миллиарда сравнений символов в секунду на одном ядре, а их у меня 8. http://faydoc.tripod.com/cpu/cmpsb.htm Тут даже надо просто оптимизировать вопрос поиска первого символа. Посыл в ассемблер в корне неверный. Он не решает задачу концептуально а просто сообщает что на таком-то примитивном уровне строковых операций можно получить +50 % выигрыша. Но на complexity алгоритма ассемблер никак не влияет. Ведь у нас кроме сравнения строк есть еще другая ЛОГИКА. Поэтому вопрос №1 за что идёт борьба. За нано-секунды (как Базист) или за улучшение алгоритма в будущем с учотом роста самих данных. Тем более что ты привел синтетический тест rep cmpsw который сильно зависит от того ка лежат данные. Если это 2 толстых строки по мильярду символов - то да. Это будет работать. Если это частые старт-стопы (это наш кейс) то никакой эффективности ты не получишь. А получишь системные промахи мимо кешей и зря потраченное время на ассемблер. Поэтому не занимайся ерундой а пиши на языках прикладного программирования и тогда есть надежда что ты успеешь выйти в продуктив. Коробочного решение по твоей проблеме - не существует. Эффективность будет зависеть от самой постановки. Ишешь префикс - строй дерево Ахо-Корасик. Ишешь суффикс - переворачивай слово. Ишешь по содержанию - строй ТРИ-Граммы. Складывай их в фильтры Блума и делай по ним поиск. Там как-раз битовые операции в ассемблере и пригодятся. Вот тебе пример для твоего примитивного тесткейса. "example1" => { "exa", "xam", "amp", "mpl", "ple", "le1" } => 010101001010100101001010100 Если вообще не хочешь связываться - покупай коробочное решение - ElasticSearch, Sphinx e.t.c. ... |
|||
:
Нравится:
Не нравится:
|
|||
23.04.2020, 13:10 |
|
массовый поиск подстрок в строке
|
|||
---|---|---|---|
#18+
a_voronin Roman Mejtes, Не норм. Но в боевом коде у меня стоит вот что Код: c# 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15. 16. 17. 18. 19. 20.
В боевом коде не пробовал обработку на found[i]++ заменить и время засечь? ... |
|||
:
Нравится:
Не нравится:
|
|||
23.04.2020, 13:28 |
|
массовый поиск подстрок в строке
|
|||
---|---|---|---|
#18+
mikron, Искомые строки выглядят вот так [Date].[Key] [Customer].[Retail Network] [Measures].[SL - ZO KG-] [Items].[SL - Item Direction] То в чем ищут выглядит вот так. SELECT NON EMPTY Hierarchize({DrilldownLevel({DrilldownLevel({[Date].[Date_YWD_standart].[All]},,,INCLUDE_CALC_MEMBERS)},[Date].[Date_YWD_standart].[Iso Year],INCLUDE_CALC_MEMBERS)}) DIMENSION PROPERTIES PARENT_UNIQUE_NAME,HIERARCHY_UNIQUE_NAME,[Date].[Date_YWD_standart].[Iso Year].[Iso Year attr],[Date].[Date_YWD_standart].[Iso Week].[Iso Week attr],[Date].[Date_YWD_standart].[Iso Week].[Iso Year] ON COLUMNS , NON EMPTY CrossJoin(Hierarchize(DrilldownMember({{DrilldownLevel({[Customer].[Cust - Channel code].[All]},,,INCLUDE_CALC_MEMBERS)}}, {[Customer].[Cust - Channel code].[Customer Channel Code].&[ДИСТ-РЫ]},,,INCLUDE_CALC_MEMBERS)), {[Measures].[SL - Qty Ordered KG],[Measures].[SL - Quantity KG],[Measures].[SL - ZO KG-],[Measures].[SL - ZO KG%]}) DIMENSION PROPERTIES PARENT_UNIQUE_NAME,HIERARCHY_UNIQUE_NAME,[Customer].[Cust - Channel code].[Customer Channel Code].[Customer Channel Code attr],[Customer].[Cust - Channel code].[code].[Address attr],[Customer].[Cust - Channel code].[code].[Code attr],[Customer].[Cust - Channel code].[code].[Country Code],[Customer].[Cust - Channel code].[code].[Cust ID],[Customer].[Cust - Channel code].[code].[Customer Group],[Customer].[Cust - Channel code].[code].[Description attr],[Customer].[Cust - Channel code].[code].[MSFO],[Customer].[Cust - Channel code].[code].[Plan ID attr],[Customer].[Cust - Channel code].[code].[Status],[Customer].[Cust - Channel code].[code].[VH],[Customer].[Cust - Channel code].[code].[Plan Retail Network],[Customer].[Cust - Channel code].[code].[Plan ID],[Customer].[Cust - Channel code].[code].[SAPCode] ON ROWS FROM (SELECT ({[Date].[Date_YWD_standart].[Iso Week].&[2019]&[49], [Date].[Date_YWD_standart].[Iso Week].&[2019]&[48], [Date].[Date_YWD_standart].[Iso Week].&[2019]&[47], [Date].[Date_YWD_standart].[Iso Week].&[2019]&[46], [Date].[Date_YWD_standart].[Iso Week].&[2019]&[45]}) ON COLUMNS , ({....,[MAN_SAP_REASONREJ].[REASONREJ TXT].&[Отсутствует GUID клиент и адрес],[MAN_SAP_REASONREJ].[REASONREJ TXT].&[Не соответсвует графику доставки],....[SalesDocs].[Hierarchy].[All],[Date].[Date].[All],[SaleDocumentType].[ID].[All],[PostStatus].[ID].[All],[SalesDocs].[Ext No].[All],[Price Group].[Promo].[All],[SalesDocs].[Shipment Date].[All],[SalesDocs].[Created Date Attr].[All],[SalesDocs].[Order Date].[All],[Items].[Dir-Segment].[All],[Items].[Mdm Sku Group].[All],[Items].[Code 1].[All],[Items].[Description attr].[All],[Items].[SAPCode].[All],[SalesDocs].[EDI Cust Order No].[All],[Items].[SL - Mdm Sku Group].[All],[Items].[SL - Therm Type].[All],[Items].[SL - Weighted].[All],[Items].[SL - Brand].[All],[Items].[SL - Segment].[All],[Items].[SL - Mdm Main Comp].[All],[Items].[SL - Mdm Place].[All],[ShippingAddress].[Retail Network].[All],....) CELL PROPERTIES VALUE, FORMAT_STRING, LANGUAGE, BACK_COLOR, FORE_COLOR, FONT_FLAGS Повторов дохрена, то есть когда первые 10 символов совпадают, а далее нет. Выложить все не смогу, так как небезопасно. На самом деле можно сначала пробить регурялкой \[[^\]]+\](\.\[[^\]]+\])+ . Больше эффекта даст. ... |
|||
:
Нравится:
Не нравится:
|
|||
23.04.2020, 13:41 |
|
массовый поиск подстрок в строке
|
|||
---|---|---|---|
#18+
a_voronin mikron, На самом деле можно сначала пробить регурялкой \[[^\]]+\](\.\[[^\]]+\])+ . Больше эффекта даст. Срезал время до 3 минут. Есть такая идея -- сделать Ахо-Карасиковое дерево и превратить его в регулярное выражение. AA AB BC (A((?<w1>A)|(?<w2>B)))|(B(?<w3>C)) Но надо пробовать . Потом посчитать определившиеся группы. (w1 w2 w3) ... |
|||
:
Нравится:
Не нравится:
|
|||
23.04.2020, 14:24 |
|
массовый поиск подстрок в строке
|
|||
---|---|---|---|
#18+
a_voronin, хороший корасик сам нечто подобное делает, выстраивая автомат переходов в дереве по несовпадению символов. Одна из причин, по которой он всё еще жив - возможность применить чуть более глубокие оптимизации в переходах по состояниям автомата по сравнению с автоматом для регулярных выражений общего назначения. И процесс такой оптимизации под конкретный состав в словаре поиска - самостоятельная тема внутри общей... ---- Вы показываете sql текст. становится важным источник текста для поиска. Если это файловая система - то понятие текущего символа во входном потоке для корасика всегда хорошо определено. А если это блоб в словарной таблице базы - то у вас могут быть проблемы со временем вовсе не обязательно в том месте, где вы их ищете... ... |
|||
:
Нравится:
Не нравится:
|
|||
23.04.2020, 14:43 |
|
массовый поиск подстрок в строке
|
|||
---|---|---|---|
#18+
Про grep, Боуер-Мур и Ахо-Корасик https://www.gnu.org/software/grep/manual/html_node/Performance.html ... |
|||
:
Нравится:
Не нравится:
|
|||
23.04.2020, 15:44 |
|
массовый поиск подстрок в строке
|
|||
---|---|---|---|
#18+
mayton Про grep, Боуер-Мур и Ахо-Корасик https://www.gnu.org/software/grep/manual/html_node/Performance.html Все-таки оптимизация состоит из двух частей правильного алгоритма и правильного компилятора. ... |
|||
:
Нравится:
Не нравится:
|
|||
23.04.2020, 16:17 |
|
массовый поиск подстрок в строке
|
|||
---|---|---|---|
#18+
Опасную тему затронул. Вот только попробуй зайди в ветку С++ со своим пониманием компиллятора... Запинают... ... |
|||
:
Нравится:
Не нравится:
|
|||
23.04.2020, 16:19 |
|
массовый поиск подстрок в строке
|
|||
---|---|---|---|
#18+
mayton, Вот есть код на C# Код: c# 1. 2. 3. 4. 5. 6. 7.
Ты видишь в нем, хоть один вызов метода? А вот в том, что накомпилировано, а насчитал их 3 штуку. Код: c# 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. 33. 34. 35. 36. 37. 38. 39. 40. 41. 42. 43. 44. 45. 46. 47. 48. 49. 50. 51.
... |
|||
:
Нравится:
Не нравится:
|
|||
23.04.2020, 16:32 |
|
массовый поиск подстрок в строке
|
|||
---|---|---|---|
#18+
a_voronin, это ты что. Мне щас основы компилляторов показываешь? ... |
|||
:
Нравится:
Не нравится:
|
|||
23.04.2020, 16:36 |
|
массовый поиск подстрок в строке
|
|||
---|---|---|---|
#18+
a_voronin Искомые строки выглядят вот так [Date].[Key] [Customer].[Retail Network] [Measures].[SL - ZO KG-] [Items].[SL - Item Direction] 1) искомые строки - в HashSet 2) то, в чем ищут - разбивается на токены (можно простой КА написать, но, наверное, проще привлечь регулярки или что-то другое готовое) - токен начинается с "[" и заканчивается на "]", то, что в середине должно быть "].[" - тоже можно проверять. И допустимость прочих символов. В общем, эта часть задачи как раз для regeх. 3) сразу по ходу токенизации (или после неё) проверяется наличие очередного токена (или всех найденных) в HashSet ... |
|||
:
Нравится:
Не нравится:
|
|||
23.04.2020, 19:56 |
|
массовый поиск подстрок в строке
|
|||
---|---|---|---|
#18+
Все это похоже на поиск в статистике SQL-запросов сервера. Код: c# 1.
И скажите зачем тут автору микро-секунды? Ему MSSQL все равно это медленнее отдаст из системных вьюшек. А насчет того как резать на токены - это вопрос без ответа пока автор не скажет что он хочет искать. Я посоветовал триграммы - но это вообще серебрянная пуля была. А если токены - это имена или алиасы полей в SQL запросе. Еще более крупная оптимизация. ... |
|||
:
Нравится:
Не нравится:
|
|||
23.04.2020, 20:06 |
|
массовый поиск подстрок в строке
|
|||
---|---|---|---|
#18+
a_voronin Ты видишь в нем, хоть один вызов метода? Я про это уже писал 22119911 , сравнение символов юникода нетривиально, это не побайтовое сравнение ... |
|||
:
Нравится:
Не нравится:
|
|||
23.04.2020, 21:35 |
|
массовый поиск подстрок в строке
|
|||
---|---|---|---|
#18+
a_voroninНаиболее трудоемкое для процессора действия это вызов метода. CALL. Второе по трудоемкости -- это условный переход. Для современного процессора самое "затратное" это давно уже промах по кешлайну. Для этих миллионов быстрых сравнений нужно сначала оптимально ваши мегабайты текста в этот процессор доставить. ... |
|||
:
Нравится:
Не нравится:
|
|||
23.04.2020, 23:15 |
|
массовый поиск подстрок в строке
|
|||
---|---|---|---|
#18+
a_voronin Все-таки оптимизация состоит из двух частей правильного алгоритма и правильного компилятора. А если у меня 1 млн. строк, которые я хочу попарно сравнить с другим 1 млн. строк. Хочу примерно за пару секунд чтобы на всё. Какой компилятор мне взять? ) ... |
|||
:
Нравится:
Не нравится:
|
|||
24.04.2020, 01:38 |
|
массовый поиск подстрок в строке
|
|||
---|---|---|---|
#18+
hVostt, Компилятор, называется голова программиста. Отсортировать обо набора и сделать merge . ... |
|||
:
Нравится:
Не нравится:
|
|||
24.04.2020, 07:49 |
|
массовый поиск подстрок в строке
|
|||
---|---|---|---|
#18+
hVostt a_voronin поиск 600 строк в 65000 строк Так у вас получается 39 миллионов поисков. Что выливается в затраты. Чистая математика. Чистая математика гласит, что 39 миллионов поисков даже в лоб на 8 3Гц ядрах и на строках 20 против 2000 должно выполняться за несколько секунд. (2000 + 2000) * 39000000 / 24000000000 = 6.5 сек 2000 -- средняя длина строки и поиск первого символа 2000 -- расходы на поиск после обнаружения первого символа ... |
|||
:
Нравится:
Не нравится:
|
|||
24.04.2020, 07:59 |
|
массовый поиск подстрок в строке
|
|||
---|---|---|---|
#18+
mayton a_voronin, это ты что. Мне щас основы компилляторов показываешь? В мои студенческие годы (начало 90х) считалось хорошим тоном для программистов знать ассемблер и смотреть во что компилируется код. ... |
|||
:
Нравится:
Не нравится:
|
|||
24.04.2020, 08:02 |
|
массовый поиск подстрок в строке
|
|||
---|---|---|---|
#18+
fixxer a_voroninНаиболее трудоемкое для процессора действия это вызов метода. CALL. Второе по трудоемкости -- это условный переход. Для современного процессора самое "затратное" это давно уже промах по кешлайну. Для этих миллионов быстрых сравнений нужно сначала оптимально ваши мегабайты текста в этот процессор доставить. Поисковые строки все в памяти. Подгрузка новой порции текста требует ничтожных затрат по сравнению с поиском. ... |
|||
:
Нравится:
Не нравится:
|
|||
24.04.2020, 08:30 |
|
массовый поиск подстрок в строке
|
|||
---|---|---|---|
#18+
a_voronin mayton a_voronin, это ты что. Мне щас основы компилляторов показываешь? В мои студенческие годы (начало 90х) считалось хорошим тоном для программистов знать ассемблер и смотреть во что компилируется код. Это очень хорошо. Но ты в курсе целей и задач для которых создавалась платформа .Net и промежуточный язык MSIL? ... |
|||
:
Нравится:
Не нравится:
|
|||
24.04.2020, 10:16 |
|
массовый поиск подстрок в строке
|
|||
---|---|---|---|
#18+
a_voronin В мои студенческие годы (начало 90х) считалось хорошим тоном для программистов знать ассемблер и смотреть во что компилируется код. Это было в прошлом столетии. Tвой скомпилированный код имеет на пути выполнения ДВА или ТРИ преобразования в то, что выполняется на железе. И приведённый ассемблерный код это не то что сделал компилятор. Бяйт - Код --> машинный код --> (+ JIT оптимизатор) --> (RISC процессора) И вполне возможно что оптимальный ассемблерный код и тот что приведён не сильно отличаются в конечном результате (RISC). Добро пожаловать на Next level. ... |
|||
:
Нравится:
Не нравится:
|
|||
24.04.2020, 10:28 |
|
массовый поиск подстрок в строке
|
|||
---|---|---|---|
#18+
a_voronin mikron, Искомые строки выглядят вот так [Date].[Key] [Customer].[Retail Network] [Measures].[SL - ZO KG-] [Items].[SL - Item Direction] То в чем ищут выглядит вот так. SELECT NON EMPTY Hierarchize({DrilldownLevel({DrilldownLevel({[Date].[Date_YWD_standart].[All]},,,INCLUDE_CALC_MEMBERS)},[Date].[Date_YWD_standart].[Iso Year],INCLUDE_CALC_MEMBERS)}) DIMENSION PROPERTIES PARENT_UNIQUE_NAME,HIERARCHY_UNIQUE_NAME,[Date].[Date_YWD_standart].[Iso Year].[Iso Year attr],[Date].[Date_YWD_standart].[Iso Week].[Iso Week attr],[Date].[Date_YWD_standart].[Iso Week].[Iso Year] ON COLUMNS , NON EMPTY CrossJoin(Hierarchize(DrilldownMember({{DrilldownLevel({[Customer].[Cust - Channel code].[All]},,,INCLUDE_CALC_MEMBERS)}}, {[Customer].[Cust - Channel code].[Customer Channel Code].&[ДИСТ-РЫ]},,,INCLUDE_CALC_MEMBERS)), {[Measures].[SL - Qty Ordered KG],[Measures].[SL - Quantity KG],[Measures].[SL - ZO KG-],[Measures].[SL - ZO KG%]}) DIMENSION PROPERTIES PARENT_UNIQUE_NAME,HIERARCHY_UNIQUE_NAME,[Customer].[Cust - Channel code].[Customer Channel Code].[Customer Channel Code attr],[Customer].[Cust - Channel code].[code].[Address attr],[Customer].[Cust - Channel code].[code].[Code attr],[Customer].[Cust - Channel code].[code].[Country Code],[Customer].[Cust - Channel code].[code].[Cust ID],[Customer].[Cust - Channel code].[code].[Customer Group],[Customer].[Cust - Channel code].[code].[Description attr],[Customer].[Cust - Channel code].[code].[MSFO],[Customer].[Cust - Channel code].[code].[Plan ID attr],[Customer].[Cust - Channel code].[code].[Status],[Customer].[Cust - Channel code].[code].[VH],[Customer].[Cust - Channel code].[code].[Plan Retail Network],[Customer].[Cust - Channel code].[code].[Plan ID],[Customer].[Cust - Channel code].[code].[SAPCode] ON ROWS FROM (SELECT ({[Date].[Date_YWD_standart].[Iso Week].&[2019]&[49], [Date].[Date_YWD_standart].[Iso Week].&[2019]&[48], [Date].[Date_YWD_standart].[Iso Week].&[2019]&[47], [Date].[Date_YWD_standart].[Iso Week].&[2019]&[46], [Date].[Date_YWD_standart].[Iso Week].&[2019]&[45]}) ON COLUMNS , ({....,[MAN_SAP_REASONREJ].[REASONREJ TXT].&[Отсутствует GUID клиент и адрес],[MAN_SAP_REASONREJ].[REASONREJ TXT].&[Не соответсвует графику доставки],....[SalesDocs].[Hierarchy].[All],[Date].[Date].[All],[SaleDocumentType].[ID].[All],[PostStatus].[ID].[All],[SalesDocs].[Ext No].[All],[Price Group].[Promo].[All],[SalesDocs].[Shipment Date].[All],[SalesDocs].[Created Date Attr].[All],[SalesDocs].[Order Date].[All],[Items].[Dir-Segment].[All],[Items].[Mdm Sku Group].[All],[Items].[Code 1].[All],[Items].[Description attr].[All],[Items].[SAPCode].[All],[SalesDocs].[EDI Cust Order No].[All],[Items].[SL - Mdm Sku Group].[All],[Items].[SL - Therm Type].[All],[Items].[SL - Weighted].[All],[Items].[SL - Brand].[All],[Items].[SL - Segment].[All],[Items].[SL - Mdm Main Comp].[All],[Items].[SL - Mdm Place].[All],[ShippingAddress].[Retail Network].[All],....) CELL PROPERTIES VALUE, FORMAT_STRING, LANGUAGE, BACK_COLOR, FORE_COLOR, FONT_FLAGS Повторов дохрена, то есть когда первые 10 символов совпадают, а далее нет. Выложить все не смогу, так как небезопасно. На самом деле можно сначала пробить регурялкой \[[^\]]+\](\.\[[^\]]+\])+ . Больше эффекта даст. Больше эффекта даст хороший алгоритм. Дайте нам данные потренироваться. Зааннонимизируте их (проведите замену по словарю. Желательно одинаковой длинны.) Я надеюсь совместными усилиями мы получим хороший результат. ... |
|||
:
Нравится:
Не нравится:
|
|||
24.04.2020, 10:37 |
|
массовый поиск подстрок в строке
|
|||
---|---|---|---|
#18+
mayton a_voronin пропущено... В мои студенческие годы (начало 90х) считалось хорошим тоном для программистов знать ассемблер и смотреть во что компилируется код. Это очень хорошо. Но ты в курсе целей и задач для которых создавалась платформа .Net и промежуточный язык MSIL? Я очень даже в курсе, ибо имел дело ещё с .NET 1.0 . И ещё я в курсе, что компилятор и оптимизатор из MSIL в конечный код ни на одной версии не давал столь оптимизированного кода как C++. Никакие optimaze code или ngen таким похвастаться не могут. Потому что C++ компилятор может превратить for(int i = 0; i < 100; i++) a[i] = 6; в три команды загрузки регистров и команду rep stosd , а MSIL компилятор будет делать условный переход. При этом задача решаемая. ... |
|||
:
Нравится:
Не нравится:
|
|||
24.04.2020, 11:01 |
|
массовый поиск подстрок в строке
|
|||
---|---|---|---|
#18+
mikron, из всего топика так и осталось неясным - есть ли у автора профиль выполнения своего приложения, или он умственно, разглядывая ассемблер, за тенями гоняется... Кроме того, хотя соображения сорта ухода от символьного сравнения на числовое косвенно высказывались, но до того важнее знать требования по сравнению - [Date].[Key] и [DATE].[kEY] - это одно и то же или нет. Это может влиять на детали реализации. Алгоритм само-собой. То, о чем здесь рассказывают - это следствие какого-то несчастного случая на таких объемах, или какой-то архитектурный подвох. Но прежде алгоритма детали требований. ... |
|||
:
Нравится:
Не нравится:
|
|||
24.04.2020, 11:06 |
|
массовый поиск подстрок в строке
|
|||
---|---|---|---|
#18+
a_voronin mayton пропущено... Это очень хорошо. Но ты в курсе целей и задач для которых создавалась платформа .Net и промежуточный язык MSIL? Я очень даже в курсе, ибо имел дело ещё с .NET 1.0 . И ещё я в курсе, что компилятор и оптимизатор из MSIL в конечный код ни на одной версии не давал столь оптимизированного кода как C++. Никакие optimaze code или ngen таким похвастаться не могут. Потому что C++ компилятор может превратить for(int i = 0; i < 100; i++) a[i] = 6; в три команды загрузки регистров и команду rep stosd , а MSIL компилятор будет делать условный переход. При этом задача решаемая. На основании своего опыта работы с базами данных и поисковыми системами я говорю тебе что ты занят не тем. И ищешь не там. Ты еще 10 лет потратишь на комбинации ассемблерных команд чтобы достигнуть цели экстенсивно (!). В то время как другой разработчик просто найдет лучше алгоритм и юзкейс. И решит задачу и получит своё вознаграждение. А тот факт что уже лет 10-15 компилляторы генерят бинарный код эффективнее человека в большинстве случаев был многократно показан. И нет никакого смысла апеллировать к ассемблеру. Строковые операции - интринзики везде. И в Java и в .Net. И обсуждение их - такой-же маветон как и в среде математиков обсуждать квадратные уравнения. Это - позорно и неловко. Поэтому имеет смысл сосредоточиться на решении задачи как таковой. И не тратить время на преждевременную оптимизацию. Надо быть сфокусированным. ... |
|||
:
Нравится:
Не нравится:
|
|||
24.04.2020, 11:10 |
|
массовый поиск подстрок в строке
|
|||
---|---|---|---|
#18+
mayton Это очень хорошо. Но ты в курсе целей и задач для которых создавалась платформа .Net и промежуточный язык MSIL? .NET кроме оверхеда при работе с памятью ещё обеспечивает безопасность, которую в низкоуровневом языке приходится делать руками. Плюс, в .NET строки это юникод. И логика работы с юникодом сложнее, чем с массивом байт. В чём смысл вот этого удивления, откуда столько всего генерится компилятором? От непонимания? ... |
|||
:
Нравится:
Не нравится:
|
|||
24.04.2020, 12:21 |
|
массовый поиск подстрок в строке
|
|||
---|---|---|---|
#18+
a_voronin Я очень даже в курсе, ибо имел дело ещё с .NET 1.0 . И ещё я в курсе, что компилятор и оптимизатор из MSIL в конечный код ни на одной версии не давал столь оптимизированного кода как C++. Никакие optimaze code или ngen таким похвастаться не могут. Потому что C++ компилятор может превратить for(int i = 0; i < 100; i++) a[i] = 6; в три команды загрузки регистров и команду rep stosd , а MSIL компилятор будет делать условный переход. При этом задача решаемая. Но вы же не видели, какой в итоге машинный код генерируется. Вы смотрите только на байт-код. И малейшего понятия не имеете, как он будет выполняться при компиляции байт-кода в машинный код. Там ведь тоже оптимизации есть и довольно существенные. Очень поверхностно смотрите. ... |
|||
:
Нравится:
Не нравится:
|
|||
24.04.2020, 12:22 |
|
массовый поиск подстрок в строке
|
|||
---|---|---|---|
#18+
booby или он умственно, разглядывая ассемблер, за тенями гоняется... premature optimization ... |
|||
:
Нравится:
Не нравится:
|
|||
24.04.2020, 12:23 |
|
массовый поиск подстрок в строке
|
|||
---|---|---|---|
#18+
a_voronin Потому что C++ компилятор может превратить for(int i = 0; i < 100; i++) a[i] = 6; в три команды загрузки регистров и команду rep stosd , а MSIL компилятор будет делать условный переход. При этом задача решаемая. Так может наконец взять в руки С++, раз там всё так хорошо, и перестать есть кактус? ... |
|||
:
Нравится:
Не нравится:
|
|||
24.04.2020, 12:40 |
|
массовый поиск подстрок в строке
|
|||
---|---|---|---|
#18+
Часто бывает что топик начался за здравие. А кончился за упокой. Потому-что изначально автор пожаловался на фрагмент кода который якобы медленно работал. Это классика строковых операцию. Сюда до кучи Кнут-Моррис-Пратт и Боуер-Мур и возможно хеширование. А потом сказал что вообще-то надо искать в теле SQL-запросов. А это уже ближе к TextSearch, Bi-Gram, Tri-Gram, Aho-Corasik. Кроме того автор любит Ассемблер. Здесь нечего добавить. Можно создать отдельный поток потока сознания на тему как быстрее и насколько быстрее можно сравнить строки в Асме. И я даже подключусь к этому. Но опять-же к второй постановке это не имеет отношения. Это просто частное желание или даже хобби. Вот хочет человек асм. Что тут поделать. ... |
|||
:
Нравится:
Не нравится:
|
|||
24.04.2020, 12:53 |
|
массовый поиск подстрок в строке
|
|||
---|---|---|---|
#18+
mikron a_voronin В мои студенческие годы (начало 90х) считалось хорошим тоном для программистов знать ассемблер и смотреть во что компилируется код. Это было в прошлом столетии. Tвой скомпилированный код имеет на пути выполнения ДВА или ТРИ преобразования в то, что выполняется на железе. И приведённый ассемблерный код это не то что сделал компилятор. Бяйт - Код --> машинный код --> (+ JIT оптимизатор) --> (RISC процессора) И вполне возможно что оптимальный ассемблерный код и тот что приведён не сильно отличаются в конечном результате (RISC). Добро пожаловать на Next level. Где вы тут увидели Next Level? Вы думаете в C++ или TurboPascal не было ByCode. Или его не было в Фортране и PL/1. оптимизация тут нужна на уровне ByteCode -> Asm -> CPU Code ... |
|||
:
Нравится:
Не нравится:
|
|||
24.04.2020, 13:23 |
|
массовый поиск подстрок в строке
|
|||
---|---|---|---|
#18+
mayton Кроме того автор любит Ассемблер. Здесь нечего добавить. Это просто один из языков программирования, который мне довелось изучить, и знание которого помогает в оптимизации кода. ... |
|||
:
Нравится:
Не нравится:
|
|||
24.04.2020, 13:25 |
|
массовый поиск подстрок в строке
|
|||
---|---|---|---|
#18+
Сон Веры Павловны a_voronin Потому что C++ компилятор может превратить for(int i = 0; i < 100; i++) a[i] = 6; в три команды загрузки регистров и команду rep stosd , а MSIL компилятор будет делать условный переход. При этом задача решаемая. Так может наконец взять в руки С++, раз там всё так хорошо, и перестать есть кактус? Я уже давно добавил 4 строки кода, откомпилированных самым неоптимальным способом. Код: c# 1. 2. 3. 4. 5.
И срезал время с 18 до 3 минут. А вот несколько сот строк Ахо-Карасика мне не помогли никак. Зато Linq over Regex явно рулез при правильном применении. Но тут же собрались такие задушевные люди, которые готовы землю перерыть ради оптимизации. ... |
|||
:
Нравится:
Не нравится:
|
|||
24.04.2020, 13:30 |
|
массовый поиск подстрок в строке
|
|||
---|---|---|---|
#18+
a_voronin Это просто один из языков программирования, который мне довелось изучить, и знание которого помогает в оптимизации кода. Вопрос только в стоимости ваших оптимизаций. ... |
|||
:
Нравится:
Не нравится:
|
|||
24.04.2020, 13:31 |
|
массовый поиск подстрок в строке
|
|||
---|---|---|---|
#18+
a_voronin mikron пропущено... Это было в прошлом столетии. Tвой скомпилированный код имеет на пути выполнения ДВА или ТРИ преобразования в то, что выполняется на железе. И приведённый ассемблерный код это не то что сделал компилятор. Бяйт - Код --> машинный код --> (+ JIT оптимизатор) --> (RISC процессора) И вполне возможно что оптимальный ассемблерный код и тот что приведён не сильно отличаются в конечном результате (RISC). Добро пожаловать на Next level. Где вы тут увидели Next Level? Я хотел этим сказать что и процессоры и ИТ технологии уже перешли на следующий уровень. ... |
|||
:
Нравится:
Не нравится:
|
|||
24.04.2020, 13:43 |
|
массовый поиск подстрок в строке
|
|||
---|---|---|---|
#18+
a_voronin Вы думаете в C++ или TurboPascal не было ByCode. Или его не было в Фортране и PL/1. И да, я так думаю. Покажите мне bytecode в C++? ... |
|||
:
Нравится:
Не нравится:
|
|||
24.04.2020, 13:47 |
|
массовый поиск подстрок в строке
|
|||
---|---|---|---|
#18+
a_voronin Но тут же собрались такие задушевные люди, которые готовы землю перерыть ради оптимизации. Я в первую очередь действую из своего спортивного интереса а не из благотворительных побуждений мецената бесплатно решить вам вашу задачу. Если наши интересы совпадают - давайте данные. ... |
|||
:
Нравится:
Не нравится:
|
|||
24.04.2020, 13:54 |
|
массовый поиск подстрок в строке
|
|||
---|---|---|---|
#18+
mikron a_voronin Но тут же собрались такие задушевные люди, которые готовы землю перерыть ради оптимизации. Я в первую очередь действую из своего спортивного интереса а не из благотворительных побуждений мецената бесплатно решить вам вашу задачу. Если наши интересы совпадают - давайте данные. Не могу я дать реальные данные -- там есть название подразделений, сотрудников и т.п. -- безопасники могут люлей отвесить. Тест с фейковыми гуидами близок по смыслу. ... |
|||
:
Нравится:
Не нравится:
|
|||
24.04.2020, 14:00 |
|
массовый поиск подстрок в строке
|
|||
---|---|---|---|
#18+
a_voronin ... А вот несколько сот строк Ахо-Карасика мне не помогли никак. Зато Linq over Regex явно рулез при правильном применении. ... Ну наконец-то. Тебе говорили - а вдруг ты не там ищещь… Корасик против Linq беспомощен и беспощадно бессмыслен. Не знаю, как топик, а корасика можно точно закрывать... ... |
|||
:
Нравится:
Не нравится:
|
|||
24.04.2020, 14:11 |
|
массовый поиск подстрок в строке
|
|||
---|---|---|---|
#18+
a_voronin Код: c# 1. 2. 3. 4. 5.
Код: plaintext 1.
а после этого - Код: plaintext
и убедиться, что ваш LINQ .Cast<Match>().Select(m => m.Value).Distinct().ToArray() не тормозит а то, может быть, оставить от этого только Код: plaintext
Код: plaintext
... |
|||
:
Нравится:
Не нравится:
|
|||
24.04.2020, 14:15 |
|
массовый поиск подстрок в строке
|
|||
---|---|---|---|
#18+
но если поиск лучше прерывать первом совпадении, то так: Код: c# 1. 2. 3. 4.
... |
|||
:
Нравится:
Не нравится:
|
|||
24.04.2020, 15:00 |
|
массовый поиск подстрок в строке
|
|||
---|---|---|---|
#18+
mikron a_voronin Вы думаете в C++ или TurboPascal не было ByCode. Или его не было в Фортране и PL/1. И да, я так думаю. Покажите мне bytecode в C++? Что вы понимаете под словом "покажи"? Компилятор его в памяти у себя формирует и никуда не сохраняет. Это .NET и JAVA его специально сохраняют. А на иных компиляторах его не сохраняли никуда. По любому есть такой этап, как сопоставление кодов неких условных конструкций с кодами процессорных команд. Этот этап присуствет в любой компиляции. Вот здесь например, упоминается некий object code для с++ между компилятором и линковкой. http://courses.washington.edu/css342/zander/css332/arch.html ... |
|||
:
Нравится:
Не нравится:
|
|||
24.04.2020, 15:44 |
|
массовый поиск подстрок в строке
|
|||
---|---|---|---|
#18+
a_voronin mikron пропущено... И да, я так думаю. Покажите мне bytecode в C++? Что вы понимаете под словом "покажи"? Компилятор его в памяти у себя формирует и никуда не сохраняет. Это .NET и JAVA его специально сохраняют. А на иных компиляторах его не сохраняли никуда. По любому есть такой этап, как сопоставление кодов неких условных конструкций с кодами процессорных команд. Этот этап присуствет в любой компиляции. Вот здесь например, упоминается некий object code для с++ между компилятором и линковкой. http://courses.washington.edu/css342/zander/css332/arch.html Ты спутал байт-код с AST. Хотя ты близок к правде. Если-б говорил про Clang. ... |
|||
:
Нравится:
Не нравится:
|
|||
24.04.2020, 15:50 |
|
массовый поиск подстрок в строке
|
|||
---|---|---|---|
#18+
А байткод java - вообще не в кассу. Он - для стековой машины а не для регистровой. Как калькулятор МК-61. Понимаешь? ... |
|||
:
Нравится:
Не нравится:
|
|||
24.04.2020, 15:51 |
|
массовый поиск подстрок в строке
|
|||
---|---|---|---|
#18+
какой смысл вообще теребить вопрос ассемблера в этом разделе? если, не жить, не быть, надо на C++ сделать, напишите библиотеку на C++, сделайте импорт и используйте на здоровье. вся эта возня на порядок повысит сложность проекта и его сопровождение, надо будет поддерживать такой код для всех поддерживаемых архитектур и отладка будет не такой уж тривиальной, думаю ваши коллеги это не оценят. есть куча решения для полнотекстового поиска в базах, в памяти и где угодно еще, вместо того, чтоб потратить кучу часов на изобретения очередного самоката с квадратными колёсами, лучше бы потратили время на поиск готовых решений. ... |
|||
:
Нравится:
Не нравится:
|
|||
24.04.2020, 16:01 |
|
массовый поиск подстрок в строке
|
|||
---|---|---|---|
#18+
mayton a_voronin пропущено... Что вы понимаете под словом "покажи"? Компилятор его в памяти у себя формирует и никуда не сохраняет. Это .NET и JAVA его специально сохраняют. А на иных компиляторах его не сохраняли никуда. По любому есть такой этап, как сопоставление кодов неких условных конструкций с кодами процессорных команд. Этот этап присуствет в любой компиляции. Вот здесь например, упоминается некий object code для с++ между компилятором и линковкой. http://courses.washington.edu/css342/zander/css332/arch.html Ты спутал байт-код с AST. Хотя ты близок к правде. Если-б говорил про Clang. Нет, это ты плохо текст прочитал The source code is translated into object code, which is similar in nature to byte code. Создание байт кода это этап любой компиляции. Называть его могут по разному. Но когда исходники разбираются по AST, то формируемые при этом данные и есть байткод, не зависимо от того, как его называют. MSIL OBJECT CODE и т.д. Уже потом байт код и сопоставляется с командами CPU. Именно на этом этапе преобразования и вылавливаются паттерны, которые могут быть преобразованы в более оптимальные команды (оптимизация). ... |
|||
:
Нравится:
Не нравится:
|
|||
24.04.2020, 16:02 |
|
массовый поиск подстрок в строке
|
|||
---|---|---|---|
#18+
L1G и убедиться, что ваш LINQ .Cast<Match>().Select(m => m.Value).Distinct().ToArray() не тормозит а то, может быть, оставить от этого только Ключевым здесь является Distinct(), именно ради него вся конструкция и напридумана. ... |
|||
:
Нравится:
Не нравится:
|
|||
24.04.2020, 16:12 |
|
массовый поиск подстрок в строке
|
|||
---|---|---|---|
#18+
a_voronin, Object Code и ByteCode имеют одно принципиальное отличие: byte code выполнятся в виртуальной машине. ПС. Хватит уже упрямого мальчишества. скучно. ... |
|||
:
Нравится:
Не нравится:
|
|||
24.04.2020, 16:13 |
|
массовый поиск подстрок в строке
|
|||
---|---|---|---|
#18+
a_voronin mayton пропущено... Ты спутал байт-код с AST. Хотя ты близок к правде. Если-б говорил про Clang. Нет, это ты плохо текст прочитал The source code is translated into object code, which is similar in nature to byte code. Это просто прекрасно. Я имею в виду "which is similar in nature to byte code." Это знаешь... как Бог создал Адама по образу и подобию. Или как Рабинович напевал Шаляпина. Я думаю что если-бы ты изучал JVM-specs, то у тебя не возникло-бы желания проводить параллели между байткодом JVM, и object code их С++. Уверяю тебя. Это очень разные вещи. Но мы отвлеклись. Я надеюсь ты согласен, что в оптимизации производительности как и в любой другой науке есть некий алгоритм или последовательность. Написание прототипа по готовому алгоритму. Симуляция нагрузки Анализ узких мест (боттлнек или хотспот). И уже после этого идут различного рода предположения. Что если данный метод переписать с Python на С++ или на Ассемблер то мы выиграем в перформансе там... +30% к примеру. Ты согласен с таким подходом? ... |
|||
:
Нравится:
Не нравится:
|
|||
24.04.2020, 16:18 |
|
массовый поиск подстрок в строке
|
|||
---|---|---|---|
#18+
Сон Веры Павловны a_voronin Потому что C++ компилятор может превратить for(int i = 0; i < 100; i++) a[i] = 6; в три команды загрузки регистров и команду rep stosd , а MSIL компилятор будет делать условный переход. При этом задача решаемая. Так может наконец взять в руки С++, раз там всё так хорошо, и перестать есть кактус? полумеры, АСМ ... |
|||
:
Нравится:
Не нравится:
|
|||
24.04.2020, 16:26 |
|
массовый поиск подстрок в строке
|
|||
---|---|---|---|
#18+
love_bach Сон Веры Павловны пропущено... Так может наконец взять в руки С++, раз там всё так хорошо, и перестать есть кактус? полумеры, АСМ Я как-то 10 лет назад решил переписать кусок кода с C++ на ассемблер. Простой код -- цикл в цикле там был с несколькими сложениями. Каково было мое удивление, когда я обнаружил, что написанный мной на ассемблере код, работает медленнее того, что выдал компилятор с++. раза в 2. Стал смотреть -- он выдал ровно тоже команды, что и я написал, но задействовал другие регистры. так что не факт, что прямой АСМ даст лучший результат, чем С++. ... |
|||
:
Нравится:
Не нравится:
|
|||
24.04.2020, 17:03 |
|
массовый поиск подстрок в строке
|
|||
---|---|---|---|
#18+
a_voronin Ключевым здесь является Distinct(), именно ради него вся конструкция и напридумана. Код: c# 1. 2.
остаётся найти пересечение двух HashSet - должно быть жутко быстрым (сравниваются в основном уже готовые хэш-суммы), но я не уверен, что HashSet.IntersectWith(IEnumerable) оптимизирован для случая, что параметром будет второй HashSet. тогда, наверное, idset.IntersectWith(searchset) будет быстрее, чем наоборот searchset.IntersectWith(idset) (но не быстрее, чем просто idset.IntersectWith(SearchStringsListOrArray) - ради интереса я бы проверил все варианты) ... |
|||
:
Нравится:
Не нравится:
|
|||
24.04.2020, 18:51 |
|
массовый поиск подстрок в строке
|
|||
---|---|---|---|
#18+
Если предположить что один из хеш-сетов - константа то задача интерсекта просто сводится к отслеживанию пересечения в фазе формирования второго хешсета. Тоесть мы по сути делаем спред тяжелой операции на набор мелких в итерации когда большая хештаблица наполняется. А наполняется она обычно из файла или из сокета или из БД а там требования к скорости ослаблены в 1000 раз примерно. Это похоже на шаблон CQRS ... |
|||
:
Нравится:
Не нравится:
|
|||
24.04.2020, 19:43 |
|
массовый поиск подстрок в строке
|
|||
---|---|---|---|
#18+
mayton, я бы параллелил вызовы функции поиска набора строк в 1 большой строке (вкупе с загрузкой этих больших строк) т.е. внутри самой функции (поиска набора строк в 1 большой строке) что-то параллелить не вижу смысла в данном конкретном случае ... |
|||
:
Нравится:
Не нравится:
|
|||
24.04.2020, 20:07 |
|
массовый поиск подстрок в строке
|
|||
---|---|---|---|
#18+
mayton Тоесть мы по сути делаем спред тяжелой операции на набор мелких в итерации когда большая хештаблица наполняется. А наполняется она обычно из файла или из сокета или из БД а там требования к скорости ослаблены в 1000 раз примерно. Это похоже на шаблон CQRS О_о ... |
|||
:
Нравится:
Не нравится:
|
|||
25.04.2020, 01:15 |
|
массовый поиск подстрок в строке
|
|||
---|---|---|---|
#18+
a_voronin L1G и убедиться, что ваш LINQ .Cast<Match>().Select(m => m.Value).Distinct().ToArray() не тормозит а то, может быть, оставить от этого только Ключевым здесь является Distinct(), именно ради него вся конструкция и напридумана. бред какой-то. Оправдать можно только временем, потраченным на разглядывание ассемблера. Обидно же будет, если, к несчастью, вдруг заработает быстрее 30 секунд, вместо правильных трёх минут. .... ... |
|||
:
Нравится:
Не нравится:
|
|||
25.04.2020, 01:54 |
|
|
start [/forum/topic.php?all=1&fid=20&tid=1398562]: |
0ms |
get settings: |
12ms |
get forum list: |
14ms |
check forum access: |
4ms |
check topic access: |
4ms |
track hit: |
159ms |
get topic data: |
13ms |
get forum data: |
3ms |
get page messages: |
143ms |
get tp. blocked users: |
2ms |
others: | 230ms |
total: | 584ms |
0 / 0 |