ReSQL.ru
     
powered by simpleCommunicator - 2.0.49     © 2025 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / WinForms, .Net Framework [игнор отключен] [закрыт для гостей] / массовый поиск подстрок в строке
25 сообщений из 118, страница 4 из 5
  4  все
массовый поиск подстрок в строке
    #39950770
Фотография hVostt
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
hVostt
Участник
a_voronin
Все-таки оптимизация состоит из двух частей правильного алгоритма и правильного компилятора.


А если у меня 1 млн. строк, которые я хочу попарно сравнить с другим 1 млн. строк.
Хочу примерно за пару секунд чтобы на всё.

Какой компилятор мне взять? )
...
Рейтинг: 0 / 0
24.04.2020, 01:38
| Ответить | Цитировать | Написать  
массовый поиск подстрок в строке
    #39950795
Фотография a_voronin
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
a_voronin
Участник
hVostt,

Компилятор, называется голова программиста. Отсортировать обо набора и сделать merge .
...
Рейтинг: 0 / 0
24.04.2020, 07:49
| Ответить | Цитировать | Написать  
массовый поиск подстрок в строке
    #39950799
Фотография a_voronin
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
a_voronin
Участник
hVostt
a_voronin
поиск 600 строк в 65000 строк


Так у вас получается 39 миллионов поисков. Что выливается в затраты. Чистая математика.


Чистая математика гласит, что 39 миллионов поисков даже в лоб на 8 3Гц ядрах и на строках 20 против 2000 должно выполняться за несколько секунд.


(2000 + 2000) * 39000000 / 24000000000 = 6.5 сек

2000 -- средняя длина строки и поиск первого символа
2000 -- расходы на поиск после обнаружения первого символа
...
Рейтинг: 0 / 0
24.04.2020, 07:59
| Ответить | Цитировать | Написать  
массовый поиск подстрок в строке
    #39950800
Фотография a_voronin
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
a_voronin
Участник
mayton
a_voronin, это ты что. Мне щас основы компилляторов показываешь?


В мои студенческие годы (начало 90х) считалось хорошим тоном для программистов знать ассемблер и смотреть во что компилируется код.
...
Рейтинг: 0 / 0
24.04.2020, 08:02
| Ответить | Цитировать | Написать  
массовый поиск подстрок в строке
    #39950802
Фотография a_voronin
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
a_voronin
Участник
fixxer
a_voroninНаиболее трудоемкое для процессора действия это вызов метода. CALL. Второе по трудоемкости -- это условный переход.


Для современного процессора самое "затратное" это давно уже промах по кешлайну. Для этих миллионов быстрых сравнений нужно сначала оптимально ваши мегабайты текста в этот процессор доставить.

Поисковые строки все в памяти. Подгрузка новой порции текста требует ничтожных затрат по сравнению с поиском.
...
Рейтинг: 0 / 0
24.04.2020, 08:30
| Ответить | Цитировать | Написать  
массовый поиск подстрок в строке
    #39950838
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
a_voronin
mayton
a_voronin, это ты что. Мне щас основы компилляторов показываешь?


В мои студенческие годы (начало 90х) считалось хорошим тоном для программистов знать ассемблер и смотреть во что компилируется код.

Это очень хорошо. Но ты в курсе целей и задач для которых создавалась платформа .Net и промежуточный язык MSIL?
...
Рейтинг: 0 / 0
24.04.2020, 10:16
| Ответить | Цитировать | Написать  
массовый поиск подстрок в строке
    #39950846
mikron
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mikron
Участник
a_voronin

В мои студенческие годы (начало 90х) считалось хорошим тоном для программистов знать ассемблер и смотреть во что компилируется код.


Это было в прошлом столетии. Tвой скомпилированный код имеет на пути выполнения ДВА или ТРИ преобразования в то, что выполняется на железе. И приведённый ассемблерный код это не то что сделал компилятор.
Бяйт - Код --> машинный код --> (+ JIT оптимизатор) --> (RISC процессора)
И вполне возможно что оптимальный ассемблерный код и тот что приведён не сильно отличаются в конечном результате (RISC).
Добро пожаловать на Next level.
...
Рейтинг: 0 / 0
24.04.2020, 10:28
| Ответить | Цитировать | Написать  
массовый поиск подстрок в строке
    #39950854
mikron
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mikron
Участник
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 символов совпадают, а далее нет.
Выложить все не смогу, так как небезопасно.

На самом деле можно сначала пробить регурялкой \[[^\]]+\](\.\[[^\]]+\])+ . Больше эффекта даст.



Больше эффекта даст хороший алгоритм. Дайте нам данные потренироваться.
Зааннонимизируте их (проведите замену по словарю. Желательно одинаковой длинны.)
Я надеюсь совместными усилиями мы получим хороший результат.
...
Рейтинг: 0 / 0
24.04.2020, 10:37
| Ответить | Цитировать | Написать  
массовый поиск подстрок в строке
    #39950874
Фотография a_voronin
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
a_voronin
Участник
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 компилятор будет делать условный переход. При этом задача решаемая.
...
Рейтинг: 0 / 0
24.04.2020, 11:01
| Ответить | Цитировать | Написать  
массовый поиск подстрок в строке
    #39950877
booby
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
booby
Участник
mikron,

из всего топика так и осталось неясным - есть ли у автора профиль выполнения своего приложения,
или он умственно, разглядывая ассемблер, за тенями гоняется...

Кроме того, хотя соображения сорта ухода от символьного сравнения на числовое косвенно высказывались, но до того важнее знать требования по сравнению - [Date].[Key] и [DATE].[kEY] - это одно и то же или нет.
Это может влиять на детали реализации.

Алгоритм само-собой. То, о чем здесь рассказывают - это следствие какого-то несчастного случая на таких объемах, или какой-то архитектурный подвох.
Но прежде алгоритма детали требований.
...
Рейтинг: 0 / 0
24.04.2020, 11:06
| Ответить | Цитировать | Написать  
массовый поиск подстрок в строке
    #39950879
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
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. И обсуждение их - такой-же маветон как и в среде математиков обсуждать
квадратные уравнения. Это - позорно и неловко.

Поэтому имеет смысл сосредоточиться на решении задачи как таковой. И не тратить время
на преждевременную оптимизацию. Надо быть сфокусированным.
...
Рейтинг: 0 / 0
24.04.2020, 11:10
| Ответить | Цитировать | Написать  
массовый поиск подстрок в строке
    #39950921
Фотография hVostt
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
hVostt
Участник
mayton
Это очень хорошо. Но ты в курсе целей и задач для которых создавалась платформа .Net и промежуточный язык MSIL?


.NET кроме оверхеда при работе с памятью ещё обеспечивает безопасность, которую в низкоуровневом языке приходится делать руками.

Плюс, в .NET строки это юникод. И логика работы с юникодом сложнее, чем с массивом байт.

В чём смысл вот этого удивления, откуда столько всего генерится компилятором? От непонимания?
...
Рейтинг: 0 / 0
24.04.2020, 12:21
| Ответить | Цитировать | Написать  
массовый поиск подстрок в строке
    #39950923
Фотография hVostt
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
hVostt
Участник
a_voronin
Я очень даже в курсе, ибо имел дело ещё с .NET 1.0 . И ещё я в курсе, что компилятор и оптимизатор из MSIL в конечный код ни на одной версии не давал столь оптимизированного кода как C++. Никакие optimaze code или ngen таким похвастаться не могут.

Потому что C++ компилятор может превратить for(int i = 0; i < 100; i++) a[i] = 6; в три команды загрузки регистров и команду rep stosd , а MSIL компилятор будет делать условный переход. При этом задача решаемая.


Но вы же не видели, какой в итоге машинный код генерируется.
Вы смотрите только на байт-код.
И малейшего понятия не имеете, как он будет выполняться при компиляции байт-кода в машинный код.
Там ведь тоже оптимизации есть и довольно существенные.

Очень поверхностно смотрите.
...
Рейтинг: 0 / 0
24.04.2020, 12:22
| Ответить | Цитировать | Написать  
массовый поиск подстрок в строке
    #39950924
Фотография hVostt
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
hVostt
Участник
booby
или он умственно, разглядывая ассемблер, за тенями гоняется...


premature optimization
...
Рейтинг: 0 / 0
24.04.2020, 12:23
| Ответить | Цитировать | Написать  
массовый поиск подстрок в строке
    #39950930
Сон Веры Павловны
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Сон Веры Павловны
Участник
a_voronin
Потому что C++ компилятор может превратить for(int i = 0; i < 100; i++) a[i] = 6; в три команды загрузки регистров и команду rep stosd , а MSIL компилятор будет делать условный переход. При этом задача решаемая.

Так может наконец взять в руки С++, раз там всё так хорошо, и перестать есть кактус?
...
Рейтинг: 0 / 0
24.04.2020, 12:40
| Ответить | Цитировать | Написать  
массовый поиск подстрок в строке
    #39950938
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Часто бывает что топик начался за здравие. А кончился за упокой.

Потому-что изначально автор пожаловался на фрагмент кода который
якобы медленно работал. Это классика строковых операцию.
Сюда до кучи Кнут-Моррис-Пратт и Боуер-Мур и возможно
хеширование.

А потом сказал что вообще-то надо искать в теле SQL-запросов.
А это уже ближе к TextSearch, Bi-Gram, Tri-Gram, Aho-Corasik.

Кроме того автор любит Ассемблер. Здесь нечего добавить.
Можно создать отдельный поток потока сознания на тему как быстрее
и насколько быстрее можно сравнить строки в Асме. И я даже
подключусь к этому. Но опять-же к второй постановке это не имеет
отношения. Это просто частное желание или даже хобби. Вот
хочет человек асм. Что тут поделать.
...
Рейтинг: 0 / 0
24.04.2020, 12:53
| Ответить | Цитировать | Написать  
массовый поиск подстрок в строке
    #39950948
Фотография a_voronin
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
a_voronin
Участник
mikron
a_voronin

В мои студенческие годы (начало 90х) считалось хорошим тоном для программистов знать ассемблер и смотреть во что компилируется код.


Это было в прошлом столетии. Tвой скомпилированный код имеет на пути выполнения ДВА или ТРИ преобразования в то, что выполняется на железе. И приведённый ассемблерный код это не то что сделал компилятор.
Бяйт - Код --> машинный код --> (+ JIT оптимизатор) --> (RISC процессора)
И вполне возможно что оптимальный ассемблерный код и тот что приведён не сильно отличаются в конечном результате (RISC).
Добро пожаловать на Next level.


Где вы тут увидели Next Level? Вы думаете в C++ или TurboPascal не было ByCode. Или его не было в Фортране и PL/1.

оптимизация тут нужна на уровне ByteCode -> Asm -> CPU Code
...
Рейтинг: 0 / 0
24.04.2020, 13:23
| Ответить | Цитировать | Написать  
массовый поиск подстрок в строке
    #39950950
Фотография a_voronin
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
a_voronin
Участник
mayton

Кроме того автор любит Ассемблер. Здесь нечего добавить.


Это просто один из языков программирования, который мне довелось изучить, и знание которого помогает в оптимизации кода.
...
Рейтинг: 0 / 0
24.04.2020, 13:25
| Ответить | Цитировать | Написать  
массовый поиск подстрок в строке
    #39950956
Фотография a_voronin
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
a_voronin
Участник
Сон Веры Павловны
a_voronin
Потому что C++ компилятор может превратить for(int i = 0; i < 100; i++) a[i] = 6; в три команды загрузки регистров и команду rep stosd , а MSIL компилятор будет делать условный переход. При этом задача решаемая.

Так может наконец взять в руки С++, раз там всё так хорошо, и перестать есть кактус?



Я уже давно добавил 4 строки кода, откомпилированных самым неоптимальным способом.

Код: c#
1.
2.
3.
4.
5.
        static Regex idMatch = new Regex("\\[[^\\]]+\\](\\.\\[[^\\]]+\\])+", RegexOptions.Compiled);

            var MDX_upper = query.MDX.ToUpper();
            var ids = idMatch.Matches(MDX_upper).Cast<Match>().Select(m => m.Value).Distinct().ToArray();
            var text = string.Join(",", ids);


И срезал время с 18 до 3 минут. А вот несколько сот строк Ахо-Карасика мне не помогли никак. Зато Linq over Regex явно рулез при правильном применении.

Но тут же собрались такие задушевные люди, которые готовы землю перерыть ради оптимизации.
...
Рейтинг: 0 / 0
24.04.2020, 13:30
| Ответить | Цитировать | Написать  
массовый поиск подстрок в строке
    #39950959
Фотография hVostt
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
hVostt
Участник
a_voronin
Это просто один из языков программирования, который мне довелось изучить, и знание которого помогает в оптимизации кода.


Вопрос только в стоимости ваших оптимизаций.
...
Рейтинг: 0 / 0
24.04.2020, 13:31
| Ответить | Цитировать | Написать  
массовый поиск подстрок в строке
    #39950969
mikron
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mikron
Участник
a_voronin
mikron
пропущено...


Это было в прошлом столетии. Tвой скомпилированный код имеет на пути выполнения ДВА или ТРИ преобразования в то, что выполняется на железе. И приведённый ассемблерный код это не то что сделал компилятор.
Бяйт - Код --> машинный код --> (+ JIT оптимизатор) --> (RISC процессора)
И вполне возможно что оптимальный ассемблерный код и тот что приведён не сильно отличаются в конечном результате (RISC).
Добро пожаловать на Next level.


Где вы тут увидели Next Level?


Я хотел этим сказать что и процессоры и ИТ технологии уже перешли на следующий уровень.
...
Рейтинг: 0 / 0
24.04.2020, 13:43
| Ответить | Цитировать | Написать  
массовый поиск подстрок в строке
    #39950972
mikron
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mikron
Участник
a_voronin
Вы думаете в C++ или TurboPascal не было ByCode. Или его не было в Фортране и PL/1.

И да, я так думаю. Покажите мне bytecode в C++?
...
Рейтинг: 0 / 0
24.04.2020, 13:47
| Ответить | Цитировать | Написать  
массовый поиск подстрок в строке
    #39950983
mikron
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mikron
Участник
a_voronin
Но тут же собрались такие задушевные люди, которые готовы землю перерыть ради оптимизации.


Я в первую очередь действую из своего спортивного интереса а не из благотворительных побуждений мецената бесплатно решить вам вашу задачу.

Если наши интересы совпадают - давайте данные.
...
Рейтинг: 0 / 0
24.04.2020, 13:54
| Ответить | Цитировать | Написать  
массовый поиск подстрок в строке
    #39950990
Фотография a_voronin
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
a_voronin
Участник
mikron
a_voronin
Но тут же собрались такие задушевные люди, которые готовы землю перерыть ради оптимизации.


Я в первую очередь действую из своего спортивного интереса а не из благотворительных побуждений мецената бесплатно решить вам вашу задачу.

Если наши интересы совпадают - давайте данные.


Не могу я дать реальные данные -- там есть название подразделений, сотрудников и т.п. -- безопасники могут люлей отвесить.

Тест с фейковыми гуидами близок по смыслу.
...
Рейтинг: 0 / 0
24.04.2020, 14:00
| Ответить | Цитировать | Написать  
массовый поиск подстрок в строке
    #39950998
booby
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
booby
Участник
a_voronin
... А вот несколько сот строк Ахо-Карасика мне не помогли никак. Зато Linq over Regex явно рулез при правильном применении.
...

Ну наконец-то.
Тебе говорили - а вдруг ты не там ищещь…
Корасик против Linq беспомощен и беспощадно бессмыслен.

Не знаю, как топик, а корасика можно точно закрывать...
...
Рейтинг: 0 / 0
24.04.2020, 14:11
| Ответить | Цитировать | Написать  
25 сообщений из 118, страница 4 из 5
  4  все
Форумы / WinForms, .Net Framework [игнор отключен] [закрыт для гостей] / массовый поиск подстрок в строке
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение
NoSQL.ru       Новости, Чат       Фотоальбом: Участники, Встречи
Закрыть
start [/forum/topic.php?fid=20&msg=39950846&tid=1398562]:
 0ms
get settings:
 7ms
get forum list:
 10ms
check forum access:
 3ms
check topic access:
 3ms
track hit:
 161ms
get topic data:
 9ms
get forum data:
 2ms
get page messages:
 66ms
get tp. blocked users:
 1ms
others: 12ms
total:  274ms
созд. / загр.: 274ms
x
x
Закрыть


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