|
массовый поиск подстрок в строке
|
|||
---|---|---|---|
#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 |
|
|
start [/forum/topic.php?fid=20&msg=39950444&tid=1398562]: |
0ms |
get settings: |
10ms |
get forum list: |
16ms |
check forum access: |
4ms |
check topic access: |
4ms |
track hit: |
32ms |
get topic data: |
10ms |
get forum data: |
3ms |
get page messages: |
61ms |
get tp. blocked users: |
1ms |
others: | 15ms |
total: | 156ms |
0 / 0 |