|
массовый поиск подстрок в строке
|
|||
---|---|---|---|
#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 |
|
|
start [/forum/topic.php?fid=20&msg=39950770&tid=1398562]: |
0ms |
get settings: |
7ms |
get forum list: |
14ms |
check forum access: |
4ms |
check topic access: |
4ms |
track hit: |
42ms |
get topic data: |
11ms |
get forum data: |
3ms |
get page messages: |
70ms |
get tp. blocked users: |
2ms |
others: | 232ms |
total: | 389ms |
0 / 0 |