powered by simpleCommunicator - 2.0.49     © 2025 Programmizd 02
Форумы / WinForms, .Net Framework [игнор отключен] [закрыт для гостей] / массовый поиск подстрок в строке
118 сообщений из 118, показаны все 5 страниц
массовый поиск подстрок в строке
    #39949185
Фотография a_voronin
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
господа, есть задача массово искать подстроки в строке.

Существующий код, который работает через Contains делает это медленно.
Код: c#
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
public void MyMethod(string param)
{
    var myList = new string[] 
    {
        "example1",
        "example2",
        "example3"
    };
    foreach (var item in myList)
    {
        if (!param.Contains(item)) continue;
        //Do something here
    }
}


Нужен механизм, которые ищет много строк массово и выдает массив вхождений. 3 8 22 66 найдены. Остальные нет.

Я в курсе про Any All ForEach Linq и т.п это все сводиться к циклическим переборам. Нужен быстрый массовый поиск, потому что поиск 600 строк в 65000 строк идет 18 минут и это слишком медленно. Можно добавить AsParallel, но не думаю, что сильно ускорит.
...
Рейтинг: 0 / 0
массовый поиск подстрок в строке
    #39949217
Фотография a_voronin
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Нагуглил функцию, которая работает слегка быстрее 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.
static int FastIndexOf(string source, string pattern) {
  if (pattern == null) throw new ArgumentNullException();
  if (pattern.Length == 0) return 0;
  if (pattern.Length == 1) return source.IndexOf(pattern[0]);
 bool found;
  int limit = source.Length - pattern.Length + 1;
  if (limit < 1) return -1;
 // Store the first 2 characters of "pattern"
  char c0 = pattern[0];
  char c1 = pattern[1];
 // Find the first occurrence of the first character
  int first = source.IndexOf(c0, 0, limit);
 while (first != -1) {
   // Check if the following character is the same like
    // the 2nd character of "pattern"
    if (source[first + 1] != c1) {
      first = source.IndexOf(c0, ++first, limit - first);
      continue;
    }
   // Check the rest of "pattern" (starting with the 3rd character)
    found = true;
    for (int j = 2; j < pattern.Length; j++)
      if (source[first + j] != pattern[j]) {
        found = false;
        break;
      }
   // If the whole word was found, return its index, otherwise try again
    if (found) return first;
    first = source.IndexOf(c0, ++first, limit - first);
  }
  return -1;
}
...
Рейтинг: 0 / 0
массовый поиск подстрок в строке
    #39949218
Фотография a_voronin
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Есть какие идеи у кого?
...
Рейтинг: 0 / 0
массовый поиск подстрок в строке
    #39949246
Фотография hVostt
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
a_voronin
господа, есть задача массово искать подстроки в строке.


Вы хотите прыгнуть выше головы?
Чтобы быстро искать в строках, вам тогда нужен специальный индекс, а не способ поиска в строке.
Построение индекса тоже займёт время и много памяти.
Также вам нужно найти и разработать алгоритм.

Почему вам с ходу тут не ответят? Потому что подобные задачи выносят на уровень баз данных, специализированных средств в базах данных, зачем изобретать велосипед?
...
Рейтинг: 0 / 0
массовый поиск подстрок в строке
    #39949247
Фотография hVostt
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
a_voronin
поиск 600 строк в 65000 строк


Так у вас получается 39 миллионов поисков. Что выливается в затраты. Чистая математика.
...
Рейтинг: 0 / 0
массовый поиск подстрок в строке
    #39949298
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
В СУБД для подобных задач используют полнотекстовый поиск. Можно СУБД взять или подобный велосипед смастерить.

Суть вкратце в следующем: для текста делается индекс {слово, расположение в тексте}, а при поиске сначала ищется слово по индексу.
...
Рейтинг: 0 / 0
массовый поиск подстрок в строке
    #39949300
Фотография a_voronin
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
hVostt,

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

Зато я когда-то в стародавние времена программировал на ассемблере и могу сказать следующее, что одно ядро 3 ГГц процессора можете за 1 секунду сделать 3 миллиарда сравнений символов и поэтому если бы была бы функция ContainsAll, замапленная на оптимизированный код, то такое сравнение прошло бы за <1 минуту. Тут есть куча оверхеда в виде вызовов методов, конвертации кодировок или какой-то такой фигни.

Потому что команда "rep cmpsw" может сравнивать строки со скоростью 3 миллиарда сравнений символов в секунду на одном ядре, а их у меня 8.

http://faydoc.tripod.com/cpu/cmpsb.htm

Тут даже надо просто оптимизировать вопрос поиска первого символа.
...
Рейтинг: 0 / 0
массовый поиск подстрок в строке
    #39949303
booby
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
a_voronin,

гугли grep/ахо-корасик
...
Рейтинг: 0 / 0
массовый поиск подстрок в строке
    #39949360
Фотография hVostt
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
a_voronin
Я специалист в первую очередь по базам данных и могу сказать, что полнотекстовый поиск тут не даст большего выигрыша.


Ну а на какой выигрышь вы рассчитываете, не пойму?
Вы делаете 38 миллионов поисков, каждый из 38 миллионов это сравнение двух массивов.

Если считаете, что проблема не в алгоритмах, а в оптимизации процессора, вам нужно в другой форум. В ассемблер, например.

С точки зрения алгоритмов, это проблема решения в лоб.
Основной способ оптимизации поиска -- индекс.

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

a_voronin
Тут даже надо просто оптимизировать вопрос поиска первого символа.


Ищете волшебное заклинание? :)

Строка это массив символов. Для перебора массива нужен индекс и сравнение. Что вы тут оптимизировать собрались? )
...
Рейтинг: 0 / 0
массовый поиск подстрок в строке
    #39949362
Фотография hVostt
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
a_voronin
Тут есть куча оверхеда в виде вызовов методов, конвертации кодировок или какой-то такой фигни.


Ну так а зачем пытаться решать проблему, которая решается на низком уровне, на высоком уровне?
...
Рейтинг: 0 / 0
массовый поиск подстрок в строке
    #39949367
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
hVostt
Строка это массив символов. Для перебора массива нужен индекс и сравнение. Что вы тут оптимизировать собрались? )

Кстати можно соптимизировать сравнение, оно совсем не тривиальное в юникоде. Contains() можно попробовать с StringComparison.OrdinalIgnoreCase
...
Рейтинг: 0 / 0
массовый поиск подстрок в строке
    #39949376
Фотография hVostt
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
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_

но это всё равно вызов метода же, а там у ТС лютый бой идёт за каждый тик

и непонятно, какого результата он хочет.
что есть "быстро" в его понимании?
какой результат его устроит? и в каких условиях?
...
Рейтинг: 0 / 0
массовый поиск подстрок в строке
    #39949390
Фотография a_voronin
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
booby,

попробовал две реализации ахо карасика

https://www.toptal.com/algorithms/aho-corasick-algorithm
https://gist.github.com/alexandrnikitin/e4176d6b472b39155a7e0e5d68264e65#file-ahocorasicktree-cs

К сожалению, обе показали себя кране хреново. Циклу с Contains они уступают в несколько раз.

Но это, скорее всего, особенности реализации авторов, которые, например, не подумали о том, конструкция return yeild крайне тормозная.
...
Рейтинг: 0 / 0
массовый поиск подстрок в строке
    #39949463
Фотография hVostt
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
a_voronin
К сожалению, обе показали себя кране хреново.


Так а "не хреново" это как? )
Какое время вас устроит?
...
Рейтинг: 0 / 0
массовый поиск подстрок в строке
    #39949466
love_bach
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
a_voronin
господа, есть задача массово искать подстроки в строке.

Существующий код, который работает через Contains делает это медленно.
Код: c#
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
public void MyMethod(string param)
{
    var myList = new string[] 
    {
        "example1",
        "example2",
        "example3"
    };
    foreach (var item in myList)
    {
        if (!param.Contains(item)) continue;
        //Do something here
    }
}


Нужен механизм, которые ищет много строк массово и выдает массив вхождений. 3 8 22 66 найдены. Остальные нет.

Я в курсе про Any All ForEach Linq и т.п это все сводиться к циклическим переборам. Нужен быстрый массовый поиск, потому что поиск 600 строк в 65000 строк идет 18 минут и это слишком медленно. Можно добавить AsParallel, но не думаю, что сильно ускорит.


если строк "example" мало - то БД и индекс видится оптимальным. если строк много - каждый очередной поиск не помнит о предыдушем, и индекс не самое оптимальное. может тогда лучше посмотреть на задачу как "все example это одна строка шаблона"? и искать решение в алгоритмах, которые для регулярок используются, ну, там, суффиксные деревья и прочий матан?
...
Рейтинг: 0 / 0
массовый поиск подстрок в строке
    #39949467
love_bach
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
booby
a_voronin,

гугли grep/ахо-корасик


+
...
Рейтинг: 0 / 0
массовый поиск подстрок в строке
    #39949472
Фотография a_voronin
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
love_bach,

Я уже две версии кода ахтунг-карася попробовал. Не рулез.
...
Рейтинг: 0 / 0
массовый поиск подстрок в строке
    #39949477
Фотография a_voronin
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
hVostt,

Вот эта быстрее всего. FastIndexOf

Меня устроит полминуты. 800 строк по 10-30 символов, найти каждая входит или нет в 90000 строк от 200 до 8000 символов (в среднем 2000).

Сколько по вашему должен работать оптимальный алгоритм, тот же самый ахо-карасик? По мне так за 10 сек, если все в памяти и должен выдать массив со счетчиком вхождений.
...
Рейтинг: 0 / 0
массовый поиск подстрок в строке
    #39949481
love_bach
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
a_voronin
love_bach,

Я уже две версии кода ахтунг-карася попробовал. Не рулез.


они там двухпроходные, если я не забыл все. за первый проход что-то типа индекса строится. если время первого прохода выбросить, то все равно медленно?
...
Рейтинг: 0 / 0
массовый поиск подстрок в строке
    #39949491
love_bach
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
алгоритм Кнута, Морриса еще глянь
...
Рейтинг: 0 / 0
массовый поиск подстрок в строке
    #39949494
love_bach
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
https://ru.wikipedia.org/wiki/Алгоритм_Кнута_—_Морриса_—_Пратта
есть обобщения, чтобы искать не строки, а шаблоны - тоже эффективные
...
Рейтинг: 0 / 0
массовый поиск подстрок в строке
    #39949496
Фотография a_voronin
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
love_bach,

Да там в обоих случаях два этапа -- первый построение дерева, второй скан деревом входной строки.
...
Рейтинг: 0 / 0
массовый поиск подстрок в строке
    #39949502
love_bach
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
a_voronin
love_bach,

Да там в обоих случаях два этапа -- первый построение дерева, второй скан деревом входной строки.


ну за один проход пока не придумали
...
Рейтинг: 0 / 0
массовый поиск подстрок в строке
    #39949511
love_bach
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
love_bach
a_voronin
love_bach,

Да там в обоих случаях два этапа -- первый построение дерева, второй скан деревом входной строки.


ну за один проход пока не придумали


это вообще возможно впринципе?
...
Рейтинг: 0 / 0
массовый поиск подстрок в строке
    #39949528
Фотография a_voronin
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
love_bach
love_bach
пропущено...


ну за один проход пока не придумали


это вообще возможно впринципе?


Вы сами ахо карасика смотрели? Он за один проход работает. Построение дерева делается от исходных слов до начала прохода.
...
Рейтинг: 0 / 0
массовый поиск подстрок в строке
    #39949537
booby
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
a_voronin,

ахо-корасик - это комбинация однопроходного пратта с поиском по словарю
Критично время поиска по словарю, если пренебречь временем его построения.

Исходный алгоритм работал на trie (сначала переводили как бор, теперь вроде луч прижился) - старая структура 1959 года рождения.

В её исходном виде преимущество состоит в совмещении общего префикса в шаблонах поиска -
при наличии общего префикса в отыскиваемых строках,
поиск автоматически идет по всему подмножеству элементов словаря с таким общим префиксом.
Недостаток - расточительность по памяти на "современных" строках.
В какой-то момент структура умерла из-за требований по памяти на расширившемся общем строковом алфавите.

При неудачных реализациях может проигрывать по скорости другим вариантам организации словаря.

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

Ахо-Корасик не обязан выигрывать просто потому, что есть словарь
К нему мозг в конкретной ситуации рекомендуется прикладывать...

Его пригодность к работе на потоке данных без возврата к предыдущим символам потока - это как раз то,
что в определенных ситуациях важнее всего остального.
Потому и прикладывают...
...
Рейтинг: 0 / 0
массовый поиск подстрок в строке
    #39949539
love_bach
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
a_voronin
love_bach
пропущено...


это вообще возможно впринципе?


Вы сами ахо карасика смотрели? Он за один проход работает. Построение дерева делается от исходных слов до начала прохода.


я уже могу путаться, но Кнут-Моррис-Прат - точно за два
если ишешь именно алгоритм, то тебе дорога в суффиксные деревья
...
Рейтинг: 0 / 0
массовый поиск подстрок в строке
    #39949546
Фотография hVostt
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
a_voronin
Сколько по вашему должен работать оптимальный алгоритм, тот же самый ахо-карасик? По мне так за 10 сек, если все в памяти и должен выдать массив со счетчиком вхождений.


Так на сложность алгоритма смотрите. Сколько операций нужно сделать, чудес-то не бывает.

У вас 35 миллионов сравнений.
Разделим на 10 секунд, которые вы хотите.
Значит в секунду должно отрабатывать 3.5 млн сравнений.
Но это без учёта длины строк.
Мы не знаем что вы там и с чём сравниваете.

Скорость вычисления вхождения строки из 10 символов в строке 100 символов будет отличаться от строки из 100 символов в строке 10000 символов.

Мы не знаем что у вас там за исходные данные.
...
Рейтинг: 0 / 0
массовый поиск подстрок в строке
    #39949569
love_bach
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
hVostt
a_voronin
Сколько по вашему должен работать оптимальный алгоритм, тот же самый ахо-карасик? По мне так за 10 сек, если все в памяти и должен выдать массив со счетчиком вхождений.


Так на сложность алгоритма смотрите. Сколько операций нужно сделать, чудес-то не бывает.

У вас 35 миллионов сравнений.
Разделим на 10 секунд, которые вы хотите.
Значит в секунду должно отрабатывать 3.5 млн сравнений.
Но это без учёта длины строк.
Мы не знаем что вы там и с чём сравниваете.

Скорость вычисления вхождения строки из 10 символов в строке 100 символов будет отличаться от строки из 100 символов в строке 10000 символов.

Мы не знаем что у вас там за исходные данные.


ну, он видимо про линейность сложности. а тут х..якс - вроде и линейно, но сильно высокая
...
Рейтинг: 0 / 0
массовый поиск подстрок в строке
    #39949580
love_bach
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
hVostt
Так на сложность алгоритма смотрите. Сколько операций нужно сделать, чудес-то не бывает


Какого алгоритма?
...
Рейтинг: 0 / 0
массовый поиск подстрок в строке
    #39949586
Фотография hVostt
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
love_bach
hVostt
Так на сложность алгоритма смотрите. Сколько операций нужно сделать, чудес-то не бывает


Какого алгоритма?


Ну в данном случае алгоритм -- простой перебор, строк, затем символов в строках.
...
Рейтинг: 0 / 0
массовый поиск подстрок в строке
    #39949588
Фотография hVostt
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
love_bach
ну, он видимо про линейность сложности. а тут х..якс - вроде и линейно, но сильно высокая


Это примерно как в магазин ходить и спрашивать "а чёт так дорого-то?" :)

А сколько "не дорого"?

Т.е. почему мои N операций выполняются долго?
Почему это "долго"? По сравнению с чем?

Это ж странно. Непонятна какая задача. Достигнуть символического комфорта?

10 секунд долго, но 9 уже нормас?
...
Рейтинг: 0 / 0
массовый поиск подстрок в строке
    #39949594
love_bach
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
hVostt
love_bach
пропущено...


Какого алгоритма?


Ну в данном случае алгоритм -- простой перебор, строк, затем символов в строках.


hVostt - это не перебор. ТС тоже это понимает
...
Рейтинг: 0 / 0
массовый поиск подстрок в строке
    #39949617
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.
        //Do something here

...
Рейтинг: 0 / 0
массовый поиск подстрок в строке
    #39949769
Фотография hVostt
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Dima T,

Как бы мы тут все гадаем, как же ускорить неизвестный код с неизвестными нам данными
...
Рейтинг: 0 / 0
массовый поиск подстрок в строке
    #39949770
Фотография hVostt
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
love_bach
hVostt - это не перебор. ТС тоже это понимает


Ну что там ещё? Вычисление интегралов? Экстраполирование? Расчёт пути в графе? )))
...
Рейтинг: 0 / 0
массовый поиск подстрок в строке
    #39949853
Фотография a_voronin
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
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.
        //Do something here



Наиболее трудоемкое для процессора действия это вызов метода. CALL. Второе по трудоемкости -- это условный переход. А если вы пишете операции со строками, то вызовом метода там немало. Все свойства это методы.

Тут вопрос скорее всего не в алгоритме, а в том, чтобы найти оптимизированный, оптимально написанный код.
...
Рейтинг: 0 / 0
массовый поиск подстрок в строке
    #39949856
Фотография a_voronin
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
[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.
static object parallelLock = new object(); 
        internal void AddUsage(TraceRecord query)
        {
            int i = 0; 
            var MDX_upper = query.MDX.ToUpper(); -- строка 500-8000 символов. 
            if (true)
            {
                Parallel.ForEach(cubeElements, cubeElement =>
                {
                    if (FastIndexOf(MDX_upper, cubeElement.NameUpper) > 0) -- NameUpper строка 10-30 символов 
                    {
                        lock (parallelLock)
                        {
// обработка ....
                        }
                    }
                }
                );
            }
}

static int FastIndexOf(string source, string pattern) {
  if (pattern == null) throw new ArgumentNullException();
  if (pattern.Length == 0) return 0;
  if (pattern.Length == 1) return source.IndexOf(pattern[0]);
 bool found;
  int limit = source.Length - pattern.Length + 1;
  if (limit < 1) return -1;
 // Store the first 2 characters of "pattern"
  char c0 = pattern[0];
  char c1 = pattern[1];
 // Find the first occurrence of the first character
  int first = source.IndexOf(c0, 0, limit);
 while (first != -1) {
   // Check if the following character is the same like
    // the 2nd character of "pattern"
    if (source[first + 1] != c1) {
      first = source.IndexOf(c0, ++first, limit - first);
      continue;
    }
   // Check the rest of "pattern" (starting with the 3rd character)
    found = true;
    for (int j = 2; j < pattern.Length; j++)
      if (source[first + j] != pattern[j]) {
        found = false;
        break;
      }
   // If the whole word was found, return its index, otherwise try again
    if (found) return first;
    first = source.IndexOf(c0, ++first, limit - first);
  }
  return -1;
}



В среднем в строке может встречаться 20 подстрок. Если одно вхождение конкретной строки найдено, других искать не надо.

Если брекить дебаггер он как правило встает здесь.

first = source.IndexOf(c0, ++first, limit - first);

А вообще простая строка кода превращается в нагромождение непонятно чего. Вот на такие вызовы методов и тратятся такты.

Код: sql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
                if (source[first + 1] != c1)
00B59EF3  mov         edx,dword ptr [ebp-54h]  
00B59EF6  inc         edx  
00B59EF7  mov         ecx,dword ptr [ebp-3Ch]  
00B59EFA  cmp         dword ptr [ecx],ecx  
00B59EFC  call        67C33ED0  
00B59F01  mov         dword ptr [ebp-0A0h],eax  
00B59F07  mov         eax,dword ptr [ebp-0A0h]  
00B59F0D  cmp         eax,dword ptr [ebp-50h]  
00B59F10  setne       al  
00B59F13  movzx       eax,al  
00B59F16  mov         dword ptr [ebp-6Ch],eax  
00B59F19  cmp         dword ptr [ebp-6Ch],0  
00B59F1D  je          00B59F4F 
...
Рейтинг: 0 / 0
массовый поиск подстрок в строке
    #39949870
mikron
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
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 подстрок. Если одно вхождение конкретной строки найдено, других искать не надо.


— любое вхождение или первое?
— что нужно узнать: что вхождение есть, вхождение какой подстроки (давайте уже использовать подходящий лексикон — шаблон) или место вхождения?
...
Рейтинг: 0 / 0
массовый поиск подстрок в строке
    #39949880
Фотография a_voronin
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mikron,

Это анализ залогированных MDX запросов для сбора статистики об использовании показателей.

Показатели постоянны, запросы разные. C# по оптимизации кода явно уступает C++.

На C++ здесь вообще не было бы вызова метода.

if (source[first + 1] != c1) {

Код я смотрю в дебаге. По нему можно ходить дебаггером и смотреть регистры. Поэтому это явно реальный конечный код. Goto Dissasembly не заглядывали?
...
Рейтинг: 0 / 0
массовый поиск подстрок в строке
    #39949881
Фотография a_voronin
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mikron


— любое вхождение или первое?
— что нужно узнать: что вхождение есть, вхождение какой подстроки (давайте уже использовать подходящий лексикон — шаблон) или место вхождения?


если вы посмотрите на начало поста, то там сформулирована задача

"Нужен механизм, которые ищет много строк массово и выдает массив вхождений. 3 8 22 66 найдены. Остальные нет."

Факт наличия нескольких подстрок в строке. Даже не количество и не позиции.
...
Рейтинг: 0 / 0
массовый поиск подстрок в строке
    #39949909
Фотография hVostt
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
a_voronin,

А код обработки учитываете? Вместе с довольно ресурсоёмким локом-монитором?

FastIndexOf содержит весьма сомнительные и нафиг не нужные оптимизации.

Почему не используете StringComparison.Ordinal?
...
Рейтинг: 0 / 0
массовый поиск подстрок в строке
    #39949916
mikron
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
a_voronin,

Давайте сначала уточним определения. "Факт наличия нескольких подстрок в строке. "
"подстрока" - шаблон поиска.
"строка" или текст, в котом происходит поиск.

Таким образом у вас набор шаблонов поиска постоянный, или почти постоянный и меняется редко, верно?

Ваша проблема заключается в том что поиск в динамическом наборе строк выполнятся медленно, но сам набор строк динамичен и не известен заранее. т.е. его нельзя предварительно обработать. Верно?

Тепер ещё раз к постановке задачи:

автор"Нужен механизм, которые ищет много строк массово и выдает массив вхождений. 3 8 22 66 найдены. Остальные нет."
В среднем в строке может встречаться 20 подстрок. Если одно вхождение конкретной строки найдено, других искать не надо.
Факт наличия нескольких подстрок в строке. Даже не количество и не позиции.


Ваши условия противоречивы:
Если вам не интересуют какие конкретно шаблоны найдены и где они найдены то что есть "массив вхождений. 3 8 22 66 найдены."

"Если одно вхождение конкретной строки найдено, других искать не надо." Если 'то условие верно как понимать "Факт наличия нескольких подстрок в строке." вообше не может быть установлен так - как для 'того надо минимум совпадение двух шаблонов.

Уточните пожалуйста.
...
Рейтинг: 0 / 0
массовый поиск подстрок в строке
    #39949956
Фотография a_voronin
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mikron,

Ищем постоянный набор строк

["яблоки", "груши", "сливы", "ананасы"]

В строке поиска

"В саду созрели груши и сливы"
ответ ["груши", "сливы"] или [1,2] при нумерации от 0

"У нас не растут ананасы, выращивайте яблоки"
ответ ["яблоки", "ананасы"] или [0,3]
...
Рейтинг: 0 / 0
массовый поиск подстрок в строке
    #39949970
mikron
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
a_voronin
mikron,

Ищем постоянный набор строк

["яблоки", "груши", "сливы", "ананасы"]

В строке поиска

"В саду созрели груши и сливы"
ответ ["груши", "сливы"] или [1,2] при нумерации от 0

"У нас не растут ананасы, выращивайте яблоки"
ответ ["яблоки", "ананасы"] или [0,3]


Вы совсем запутали меня. Значит нас интересуют какие шаблоны найдены?

Нам нужно знать все шаблоны,
или только первый,
или любой,
или только что минимум два,
или что минимум два разных,
или вообще что хоть один?

Я не из дотошности спрашиваю, просто это разные задачи и для них разные методы.

Ищем постоянный набор строк
["яблоки", "груши", "сливы", "ивы", "ананасы"]

В строке поиска
"В саду росли яблоки и сливы"

Ответ "шаблон найден" верный?
Ответ ["яблоки"] верный?
Ответ ["ивы"] верный?
Ответ ["яблоки", "ивы"] верный?
Ответ ["ивы", "яблоки"] верный?
Ответ ["ивы", "сливы"] верный?
Ответ ["яблоки", "сливы", "ивы"] верный?

В строке поиска
"В саду росли сливы"

Ответ "шаблон найден" верный?
Ответ ["ивы"] верный?
Ответ ["ивы", "сливы"] верный?
...
Рейтинг: 0 / 0
массовый поиск подстрок в строке
    #39950000
Фотография a_voronin
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mikron,

Ищем постоянный набор строк
["яблоки", "груши", "сливы", "ивы", "ананасы"]

В строке поиска
"В саду росли яблоки и сливы"

Ответ ["яблоки", "сливы", "ивы"] верный.

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

то есть ответ Ответ ["яблоки", "сливы"] тоже устроит.

Хотя, я так понимаю может быть нюанс в реализации.
...
Рейтинг: 0 / 0
массовый поиск подстрок в строке
    #39950005
love_bach
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mikron
a_voronin
mikron,

Ищем постоянный набор строк

["яблоки", "груши", "сливы", "ананасы"]

В строке поиска

"В саду созрели груши и сливы"
ответ ["груши", "сливы"] или [1,2] при нумерации от 0

"У нас не растут ананасы, выращивайте яблоки"
ответ ["яблоки", "ананасы"] или [0,3]


Вы совсем запутали меня. Значит нас интересуют какие шаблоны найдены?

Нам нужно знать все шаблоны,
или только первый,
или любой,
или только что минимум два,
или что минимум два разных,
или вообще что хоть один?

Я не из дотошности спрашиваю, просто это разные задачи и для них разные методы .

Ищем постоянный набор строк
["яблоки", "груши", "сливы", "ивы", "ананасы"]

В строке поиска
"В саду росли яблоки и сливы"

Ответ "шаблон найден" верный?
Ответ ["яблоки"] верный?
Ответ ["ивы"] верный?
Ответ ["яблоки", "ивы"] верный?
Ответ ["ивы", "яблоки"] верный?
Ответ ["ивы", "сливы"] верный?
Ответ ["яблоки", "сливы", "ивы"] верный?

В строке поиска
"В саду росли сливы"

Ответ "шаблон найден" верный?
Ответ ["ивы"] верный?
Ответ ["ивы", "сливы"] верный?


приведи хотя бы один
...
Рейтинг: 0 / 0
массовый поиск подстрок в строке
    #39950070
mikron
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
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 как раз о ней.
...
Рейтинг: 0 / 0
массовый поиск подстрок в строке
    #39950103
mikron
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
a_voronin,

Если у вас данные секрета не представляют, выложите тут, потренируемся на них.
...
Рейтинг: 0 / 0
массовый поиск подстрок в строке
    #39950111
Фотография a_voronin
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
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.
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ConsoleApp4
{
    class Program
    {
        static void Main(string[] args)
        {
            string[] strs = new string[] {
                "AAC00", "1248A", "1258A", "1348A", "D248A", "1D48A", "12D8A", "1248D",
                "A0C", "1048A", "0258A", "0348A", "D208A", "1D08A", "10D8A", "1240D",
                "A7C", "1247A", "1257A", "13487", "D247A", "1D47A", "17D8A", "1278D",
            };

            int MAX = 10000;
            int MAX2 = 1000;
            var texts = Enumerable.Range(1, MAX).Select(
                g => string.Join("", Enumerable.Range(1, MAX2).Select(
                    gg => Guid.NewGuid().ToString().ToUpper()).ToArray())
                ).ToList();

            Int64[] found = new Int64[strs.Length];
            InitFound(strs, found);
            var sw0 = new Stopwatch();
            sw0.Start();
            Parallel.ForEach(texts, text =>
            {
                for (int i = 0; i < strs.Length; i++)
                    if (text.Contains(strs[i]))
                        found[i]++;
            });
            sw0.Stop();
            Debug.WriteLine(string.Join(",", found.Select(x => x).ToArray()));

            InitFound(strs, found);
            var sw1 = new Stopwatch();
            sw1.Start();
            Parallel.ForEach(texts, text =>
            {
                for (int i = 0; i < strs.Length; i++)
                    if (text.Contains(strs[i]))
                        found[i]++;
            });
            sw1.Stop();
            Debug.WriteLine(string.Join(",", found.Select(x => x).ToArray()));


            Console.WriteLine($"time0 = {sw0.ElapsedMilliseconds} time1 = {sw1.ElapsedMilliseconds}");
            Console.ReadKey();
        }

        private static void InitFound(string[] strs, long[] found)
        {
            for (int i = 0; i < strs.Length; i++)
                found[i] = 0;
        }

    }
}
...
Рейтинг: 0 / 0
массовый поиск подстрок в строке
    #39950133
mikron
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
авторa_voronin,

Вот эта быстрее всего. FastIndexOf

Меня устроит полминуты. 800 строк по 10-30 символов, найти каждая входит или нет в 90000 строк от 200 до 8000 символов (в среднем 2000).


Вот опят вы всё смешиваете. В ваших тестовых данных нет ни 800 шаблонов ни 10-30 символов в шаблоне, да и сами шаблоны наверняка имеет очень плохо распределение пар символов.
Для ваших тестовых данных _возможно_ contains и будет самым быстрым. Из них вы можете только сделать неправильный вывод что отимизация - единственный верный путь. Мне это не интересно.

К тому-же вы сравниваете время выполнения с разбиением на потоки / таски. Я такое вообще не воспринимаю серьезно.

Давайте нормальные данные.
...
Рейтинг: 0 / 0
массовый поиск подстрок в строке
    #39950220
Фотография hVostt
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
a_voronin
Вот тестовые данные -- попробуйте перебить обычный цикл с Contains?


Пока вы пытаетесь оптимизировать в лоб, экономия на спичках.
Было у вас 18 минут, с FastIndexOf вы получите на десяток секунд быстрее.
Распараллеливание на практике не кратно множителю.

На таких объёмах нужны специальные алгоритмы поиска, подходящие для вас.
А лучше, всё же, выносить подобные задачи на уровень БД.
...
Рейтинг: 0 / 0
массовый поиск подстрок в строке
    #39950293
Фотография a_voronin
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
hVostt
a_voronin
Вот тестовые данные -- попробуйте перебить обычный цикл с Contains?


Пока вы пытаетесь оптимизировать в лоб, экономия на спичках.
Было у вас 18 минут, с FastIndexOf вы получите на десяток секунд быстрее.
Распараллеливание на практике не кратно множителю.

На таких объёмах нужны специальные алгоритмы поиска, подходящие для вас.
А лучше, всё же, выносить подобные задачи на уровень БД.


Я уже писал выше, я попробовал два Эхо-Карасика, которых нашел в Инете и прибавки не получил. Вопрос в том, что весь эффект съедается неоптимальностью компилятора. Нужен алгоритм, который не только оптимален сам, но ещё и вызывает оптимальные код, типа одного Contains или Replace на проверку.

На самом деле если эту FastInsexOf перетащить на С++ она в 10 раз ускорится.
...
Рейтинг: 0 / 0
массовый поиск подстрок в строке
    #39950294
Фотография a_voronin
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
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.
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ConsoleApp4
{
    class Program
    {
        static void Main(string[] args)
        {
            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();

            int MAX = 10000;
            int MAX2 = 1000;
            var texts = Enumerable.Range(1, MAX).Select(
                g => string.Join("", Enumerable.Range(1, MAX2).Select(
                    gg => Guid.NewGuid().ToString().ToUpper()).ToArray())
                ).ToList();

            Int64[] found = new Int64[strs.Length];
            InitFound(strs, found);
            var sw0 = new Stopwatch();
            sw0.Start();
            Parallel.ForEach(texts, text =>
            {
                for (int i = 0; i < strs.Length; i++)
                    if (text.Contains(strs[i]))
                        found[i]++;
            });
            sw0.Stop();
            Debug.WriteLine(string.Join(",", found.Select(x => x).ToArray()));

            InitFound(strs, found);
            var sw1 = new Stopwatch();
            sw1.Start();
            Parallel.ForEach(texts, text =>
            {
                for (int i = 0; i < strs.Length; i++)
                    if (text.Contains(strs[i]))
                        found[i]++;
            });
            sw1.Stop();
            Debug.WriteLine(string.Join(",", found.Select(x => x).ToArray()));


            Console.WriteLine($"time0 = {sw0.ElapsedMilliseconds} time1 = {sw1.ElapsedMilliseconds}");
            Console.ReadKey();
        }

        private static void InitFound(string[] strs, long[] found)
        {
            for (int i = 0; i < strs.Length; i++)
                found[i] = 0;
        }

       
    }
}
...
Рейтинг: 0 / 0
массовый поиск подстрок в строке
    #39950296
Фотография a_voronin
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
a_voronin,

Ну а заменить

Код: c#
1.
2.
3.
4.
5.
6.
Parallel.ForEach(texts, text =>
            {
                for (int i = 0; i < strs.Length; i++)
                    if (text.Contains(strs[i]))
                        found[i]++;
            });


на

Код: c#
1.
2.
3.
4.
5.
6.
texts.ForEach(text =>
            {
                for (int i = 0; i < strs.Length; i++)
                    if (text.Contains(strs[i]))
                        found[i]++;
            });



тоже несложно.
...
Рейтинг: 0 / 0
массовый поиск подстрок в строке
    #39950303
Roman Mejtes
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
эммм found[i]++ при параллельном выполнении это норм?
...
Рейтинг: 0 / 0
массовый поиск подстрок в строке
    #39950309
Фотография 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.
static object parallelLock = new object(); 
        internal void AddUsage(TraceRecord query)
        {
            int i = 0; 
            var MDX_upper = query.MDX.ToUpper(); -- строка 500-8000 символов. 
            if (true)
            {
                Parallel.ForEach(cubeElements, cubeElement =>
                {
                    if (FastIndexOf(MDX_upper, cubeElement.NameUpper) > 0) -- NameUpper строка 10-30 символов 
                    {
                        lock (parallelLock)
                        {
// обработка ....
                        }
                    }
                }
                );
            }
}
...
Рейтинг: 0 / 0
массовый поиск подстрок в строке
    #39950325
Roman Mejtes
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
достаточно использовать interlock, тем более, если речь идёт о перформансе
...
Рейтинг: 0 / 0
массовый поиск подстрок в строке
    #39950346
Фотография a_voronin
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Roman Mejtes
достаточно использовать interlock, тем более, если речь идёт о перформансе


Это в тесте используется оператор ++. А в реальном коде совершенно иная более сложная логика с наполнение списков и т.п.

Просто это все сейчас лишнее для данной темы. Вопрос в том, как быстро делать поиск, а не что делать после этого.
...
Рейтинг: 0 / 0
массовый поиск подстрок в строке
    #39950413
booby
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
a_voronin,

вообще-то желательно иметь стандартные образцы обоих файлов - с шаблонами поиска и набором строк, в которых поиск происходит.
Иначе нет базы для сравнения для тех, кто захочет что-то испытывать и улучшать....
...
Рейтинг: 0 / 0
массовый поиск подстрок в строке
    #39950424
mikron
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
a_voronin,

Алгоритм, кототрый я описал может подойти для вашего случая с длиной шаблонов 10-30 символов, но не для вашего теста.

booby


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


Я так/же присоединяюсь, т.к. тест с Guid.NewGuid().ToString() нелзя воспроизвести.

Выложите пожалуста пусть даже тестовые данные на гитхабе. Я на выходных затестирую.
...
Рейтинг: 0 / 0
массовый поиск подстрок в строке
    #39950425
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
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.
...
Рейтинг: 0 / 0
массовый поиск подстрок в строке
    #39950444
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
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.
static object parallelLock = new object(); 
        internal void AddUsage(TraceRecord query)
        {
            int i = 0; 
            var MDX_upper = query.MDX.ToUpper(); -- строка 500-8000 символов. 
            if (true)
            {
                Parallel.ForEach(cubeElements, cubeElement =>
                {
                    if (FastIndexOf(MDX_upper, cubeElement.NameUpper) > 0) -- NameUpper строка 10-30 символов 
                    {
                        lock (parallelLock)
                        {
// обработка ....
                        }
                    }
                }
                );
            }
}


В боевом коде не пробовал обработку на found[i]++ заменить и время засечь?
...
Рейтинг: 0 / 0
массовый поиск подстрок в строке
    #39950458
Фотография 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
массовый поиск подстрок в строке
    #39950493
Фотография a_voronin
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
a_voronin
mikron,


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


Срезал время до 3 минут.

Есть такая идея -- сделать Ахо-Карасиковое дерево и превратить его в регулярное выражение.

AA
AB
BC

(A((?<w1>A)|(?<w2>B)))|(B(?<w3>C))

Но надо пробовать . Потом посчитать определившиеся группы. (w1 w2 w3)
...
Рейтинг: 0 / 0
массовый поиск подстрок в строке
    #39950508
booby
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
a_voronin,

хороший корасик сам нечто подобное делает, выстраивая автомат переходов в дереве по несовпадению символов.
Одна из причин, по которой он всё еще жив - возможность применить чуть более глубокие оптимизации в переходах по состояниям
автомата по сравнению с автоматом для регулярных выражений общего назначения.
И процесс такой оптимизации под конкретный состав в словаре поиска - самостоятельная тема внутри общей...
----
Вы показываете sql текст.
становится важным источник текста для поиска.
Если это файловая система - то понятие текущего символа во входном потоке для корасика всегда хорошо определено.
А если это блоб в словарной таблице базы - то у вас могут быть проблемы со временем вовсе не обязательно в том месте, где вы их ищете...
...
Рейтинг: 0 / 0
массовый поиск подстрок в строке
    #39950552
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Про grep, Боуер-Мур и Ахо-Корасик

https://www.gnu.org/software/grep/manual/html_node/Performance.html
...
Рейтинг: 0 / 0
массовый поиск подстрок в строке
    #39950583
Фотография a_voronin
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mayton
Про grep, Боуер-Мур и Ахо-Корасик

https://www.gnu.org/software/grep/manual/html_node/Performance.html


Все-таки оптимизация состоит из двух частей правильного алгоритма и правильного компилятора.
...
Рейтинг: 0 / 0
массовый поиск подстрок в строке
    #39950584
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Опасную тему затронул. Вот только попробуй зайди в ветку С++ со своим пониманием
компиллятора... Запинают...
...
Рейтинг: 0 / 0
массовый поиск подстрок в строке
    #39950589
Фотография a_voronin
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mayton,
Вот есть код на C#
Код: c#
1.
2.
3.
4.
5.
6.
7.
             found = true;
                for (int j = 2; j < pattern.Length; j++)
                    if (source[first + j] != pattern[j])
                    {
                        found = false;
                        break;
                    }



Ты видишь в нем, хоть один вызов метода?

А вот в том, что накомпилировано, а насчитал их 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.
                found = true;
009AA447  mov         eax,1  
009AA44C  and         eax,0FFh  
009AA451  mov         dword ptr [ebp-44h],eax  
                for (int j = 2; j < pattern.Length; j++)
009AA454  mov         dword ptr [ebp-70h],2  
009AA45B  nop  
009AA45C  jmp         009AA4AE  
                    if (source[first + j] != pattern[j])
009AA45E  mov         edx,dword ptr [ebp-54h]  
009AA461  add         edx,dword ptr [ebp-70h]  
009AA464  mov         ecx,dword ptr [ebp-3Ch]  
009AA467  cmp         dword ptr [ecx],ecx  
009AA469  call        67C33ED0  
009AA46E  mov         dword ptr [ebp-0ACh],eax  
009AA474  mov         ecx,dword ptr [ebp-40h]  
009AA477  mov         edx,dword ptr [ebp-70h]  
009AA47A  cmp         dword ptr [ecx],ecx  
009AA47C  call        67C33ED0  
009AA481  mov         dword ptr [ebp-0B0h],eax  
009AA487  mov         eax,dword ptr [ebp-0ACh]  
009AA48D  cmp         eax,dword ptr [ebp-0B0h]  
009AA493  setne       al  
009AA496  movzx       eax,al  
009AA499  mov         dword ptr [ebp-74h],eax  
009AA49C  cmp         dword ptr [ebp-74h],0  
009AA4A0  je          009AA4AB  
                    {
009AA4A2  nop  
                        found = false;
009AA4A3  xor         edx,edx  
009AA4A5  mov         dword ptr [ebp-44h],edx  
                        break;
009AA4A8  nop  
009AA4A9  jmp         009AA4E6  
                for (int j = 2; j < pattern.Length; j++)
009AA4AB  inc         dword ptr [ebp-70h]  
009AA4AE  mov         eax,dword ptr [ebp-70h]  
009AA4B1  mov         dword ptr [ebp-0A4h],eax  
009AA4B7  mov         ecx,dword ptr [ebp-40h]  
009AA4BA  cmp         dword ptr [ecx],ecx  
009AA4BC  call        676C8460  
009AA4C1  mov         dword ptr [ebp-0A8h],eax  
009AA4C7  mov         eax,dword ptr [ebp-0A4h]  
009AA4CD  cmp         eax,dword ptr [ebp-0A8h]  
009AA4D3  setl        al  
009AA4D6  movzx       eax,al  
009AA4D9  mov         dword ptr [ebp-78h],eax  
009AA4DC  cmp         dword ptr [ebp-78h],0  
009AA4E0  jne         009AA45E  
                    }
...
Рейтинг: 0 / 0
массовый поиск подстрок в строке
    #39950597
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
a_voronin, это ты что. Мне щас основы компилляторов показываешь?
...
Рейтинг: 0 / 0
массовый поиск подстрок в строке
    #39950689
L1G
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
a_voronin
Искомые строки выглядят вот так

[Date].[Key]
[Customer].[Retail Network]
[Measures].[SL - ZO KG-]
[Items].[SL - Item Direction]
Ну сразу же напрашивается:
1) искомые строки - в HashSet
2) то, в чем ищут - разбивается на токены (можно простой КА написать, но, наверное, проще привлечь регулярки или что-то другое готовое) - токен начинается с "[" и заканчивается на "]", то, что в середине должно быть "].[" - тоже можно проверять. И допустимость прочих символов.
В общем, эта часть задачи как раз для regeх.
3) сразу по ходу токенизации (или после неё) проверяется наличие очередного токена (или всех найденных) в HashSet
...
Рейтинг: 0 / 0
массовый поиск подстрок в строке
    #39950694
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Все это похоже на поиск в статистике SQL-запросов сервера.

Код: c#
1.
SELECT NON EMPTY Hierarchize({DrilldownLevel({DrilldownLevel({[Date].[Date_YWD_standart].[All]},,,INCLUDE_CALC_MEMBERS)},[Date].[Date_YWD_standart].[Iso Year],INCLUDE_CALC_MEMBERS)}) .......



И скажите зачем тут автору микро-секунды? Ему MSSQL все равно это медленнее отдаст
из системных вьюшек.

А насчет того как резать на токены - это вопрос без ответа пока автор не скажет что он хочет
искать. Я посоветовал триграммы - но это вообще серебрянная пуля была. А если токены - это
имена или алиасы полей в SQL запросе. Еще более крупная оптимизация.
...
Рейтинг: 0 / 0
массовый поиск подстрок в строке
    #39950719
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
a_voronin
Ты видишь в нем, хоть один вызов метода?

Я про это уже писал 22119911 , сравнение символов юникода нетривиально, это не побайтовое сравнение
...
Рейтинг: 0 / 0
массовый поиск подстрок в строке
    #39950750
Фотография fixxer
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
a_voroninНаиболее трудоемкое для процессора действия это вызов метода. CALL. Второе по трудоемкости -- это условный переход.


Для современного процессора самое "затратное" это давно уже промах по кешлайну. Для этих миллионов быстрых сравнений нужно сначала оптимально ваши мегабайты текста в этот процессор доставить.
...
Рейтинг: 0 / 0
массовый поиск подстрок в строке
    #39950770
Фотография hVostt
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
a_voronin
Все-таки оптимизация состоит из двух частей правильного алгоритма и правильного компилятора.


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

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

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


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


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


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

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


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


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

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


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

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

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


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

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

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

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


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

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

В чём смысл вот этого удивления, откуда столько всего генерится компилятором? От непонимания?
...
Рейтинг: 0 / 0
массовый поиск подстрок в строке
    #39950923
Фотография 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
массовый поиск подстрок в строке
    #39950924
Фотография hVostt
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
booby
или он умственно, разглядывая ассемблер, за тенями гоняется...


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

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

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

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

Кроме того автор любит Ассемблер. Здесь нечего добавить.
Можно создать отдельный поток потока сознания на тему как быстрее
и насколько быстрее можно сравнить строки в Асме. И я даже
подключусь к этому. Но опять-же к второй постановке это не имеет
отношения. Это просто частное желание или даже хобби. Вот
хочет человек асм. Что тут поделать.
...
Рейтинг: 0 / 0
массовый поиск подстрок в строке
    #39950948
Фотография 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
массовый поиск подстрок в строке
    #39950950
Фотография a_voronin
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mayton

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


Это просто один из языков программирования, который мне довелось изучить, и знание которого помогает в оптимизации кода.
...
Рейтинг: 0 / 0
массовый поиск подстрок в строке
    #39950956
Фотография 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
массовый поиск подстрок в строке
    #39950959
Фотография hVostt
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
a_voronin
Это просто один из языков программирования, который мне довелось изучить, и знание которого помогает в оптимизации кода.


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


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


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


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

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


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

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


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

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


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

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

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

Не знаю, как топик, а корасика можно точно закрывать...
...
Рейтинг: 0 / 0
массовый поиск подстрок в строке
    #39951002
L1G
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
a_voronin
Код: 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); // ВОТ ЭТО УЖЕ ЛИШНЕЕ

и осталось перед этим сделать
Код: plaintext
1.
var searchset = new HashSet<String>();
foreach (var s in SearchStrings) searchset.Add(s.ToUpper());

а после этого -
Код: plaintext
foreach (var id in ids) if (searchset.Contains(id)) return id; 

и убедиться, что ваш LINQ .Cast<Match>().Select(m => m.Value).Distinct().ToArray() не тормозит
а то, может быть, оставить от этого только
Код: plaintext
var ids = idMatch.Matches(MDX_upper);
и потом
Код: plaintext
foreach (var id in ids) if (searchset.Contains(id.Value)) return id.Value; 
...
Рейтинг: 0 / 0
массовый поиск подстрок в строке
    #39951025
L1G
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
но если поиск лучше прерывать первом совпадении, то так:
Код: c#
1.
2.
3.
4.
Match match = idMatch.Match(MDX_upper);
while (match.Success && !searchset.Contains(match.Value))
    match = match.NextMatch();
return match.Success ? match.Value : ""; // "" - ничего не нашли
...
Рейтинг: 0 / 0
массовый поиск подстрок в строке
    #39951053
Фотография a_voronin
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mikron
a_voronin
Вы думаете в C++ или TurboPascal не было ByCode. Или его не было в Фортране и PL/1.

И да, я так думаю. Покажите мне bytecode в C++?


Что вы понимаете под словом "покажи"? Компилятор его в памяти у себя формирует и никуда не сохраняет. Это .NET и JAVA его специально сохраняют. А на иных компиляторах его не сохраняли никуда.

По любому есть такой этап, как сопоставление кодов неких условных конструкций с кодами процессорных команд. Этот этап присуствет в любой компиляции.

Вот здесь например, упоминается некий object code для с++ между компилятором и линковкой.

http://courses.washington.edu/css342/zander/css332/arch.html
...
Рейтинг: 0 / 0
массовый поиск подстрок в строке
    #39951056
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
a_voronin
mikron
пропущено...

И да, я так думаю. Покажите мне bytecode в C++?


Что вы понимаете под словом "покажи"? Компилятор его в памяти у себя формирует и никуда не сохраняет. Это .NET и JAVA его специально сохраняют. А на иных компиляторах его не сохраняли никуда.

По любому есть такой этап, как сопоставление кодов неких условных конструкций с кодами процессорных команд. Этот этап присуствет в любой компиляции.

Вот здесь например, упоминается некий object code для с++ между компилятором и линковкой.

http://courses.washington.edu/css342/zander/css332/arch.html

Ты спутал байт-код с AST.

Хотя ты близок к правде. Если-б говорил про Clang.
...
Рейтинг: 0 / 0
массовый поиск подстрок в строке
    #39951059
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
А байткод java - вообще не в кассу. Он - для стековой машины а не для регистровой.
Как калькулятор МК-61. Понимаешь?
...
Рейтинг: 0 / 0
массовый поиск подстрок в строке
    #39951067
Roman Mejtes
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
какой смысл вообще теребить вопрос ассемблера в этом разделе?
если, не жить, не быть, надо на C++ сделать, напишите библиотеку на C++, сделайте импорт и используйте на здоровье.
вся эта возня на порядок повысит сложность проекта и его сопровождение, надо будет поддерживать такой код для всех поддерживаемых архитектур и отладка будет не такой уж тривиальной, думаю ваши коллеги это не оценят.
есть куча решения для полнотекстового поиска в базах, в памяти и где угодно еще, вместо того, чтоб потратить кучу часов на изобретения очередного самоката с квадратными колёсами, лучше бы потратили время на поиск готовых решений.
...
Рейтинг: 0 / 0
массовый поиск подстрок в строке
    #39951069
Фотография a_voronin
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
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. Именно на этом этапе преобразования и вылавливаются паттерны, которые могут быть преобразованы в более оптимальные команды (оптимизация).
...
Рейтинг: 0 / 0
массовый поиск подстрок в строке
    #39951075
Фотография a_voronin
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
L1G


и убедиться, что ваш LINQ .Cast<Match>().Select(m => m.Value).Distinct().ToArray() не тормозит
а то, может быть, оставить от этого только


Ключевым здесь является Distinct(), именно ради него вся конструкция и напридумана.
...
Рейтинг: 0 / 0
массовый поиск подстрок в строке
    #39951078
mikron
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
a_voronin,

Object Code и ByteCode имеют одно принципиальное отличие: byte code выполнятся в виртуальной машине.

ПС. Хватит уже упрямого мальчишества. скучно.
...
Рейтинг: 0 / 0
массовый поиск подстрок в строке
    #39951081
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
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% к примеру.

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

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


полумеры, АСМ
...
Рейтинг: 0 / 0
массовый поиск подстрок в строке
    #39951098
Фотография a_voronin
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
love_bach
Сон Веры Павловны
пропущено...

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


полумеры, АСМ


Я как-то 10 лет назад решил переписать кусок кода с C++ на ассемблер. Простой код -- цикл в цикле там был с несколькими сложениями.

Каково было мое удивление, когда я обнаружил, что написанный мной на ассемблере код, работает медленнее того, что выдал компилятор с++. раза в 2. Стал смотреть -- он выдал ровно тоже команды, что и я написал, но задействовал другие регистры.

так что не факт, что прямой АСМ даст лучший результат, чем С++.
...
Рейтинг: 0 / 0
массовый поиск подстрок в строке
    #39951148
L1G
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
a_voronin
Ключевым здесь является Distinct(), именно ради него вся конструкция и напридумана.
тогда я бы еще попробовал так:
Код: c#
1.
2.
var idset = new HashSet<String>();
foreach (var match in idMatch.Matches(MDX_upper)) idset.Add(match.Value.ToUpper()); //в idset окажутся уникальные


остаётся найти пересечение двух HashSet - должно быть жутко быстрым (сравниваются в основном уже готовые хэш-суммы), но я не уверен, что HashSet.IntersectWith(IEnumerable) оптимизирован для случая, что параметром будет второй HashSet.
тогда, наверное, idset.IntersectWith(searchset) будет быстрее, чем наоборот searchset.IntersectWith(idset)
(но не быстрее, чем просто idset.IntersectWith(SearchStringsListOrArray) - ради интереса я бы проверил все варианты)
...
Рейтинг: 0 / 0
массовый поиск подстрок в строке
    #39951168
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Если предположить что один из хеш-сетов - константа то задача интерсекта
просто сводится к отслеживанию пересечения в фазе формирования второго
хешсета.

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

Это похоже на шаблон CQRS
...
Рейтинг: 0 / 0
массовый поиск подстрок в строке
    #39951171
L1G
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mayton,
я бы параллелил вызовы функции поиска набора строк в 1 большой строке (вкупе с загрузкой этих больших строк)
т.е. внутри самой функции (поиска набора строк в 1 большой строке) что-то параллелить не вижу смысла в данном конкретном случае
...
Рейтинг: 0 / 0
массовый поиск подстрок в строке
    #39951236
Фотография hVostt
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mayton
Тоесть мы по сути делаем спред тяжелой операции на набор мелких в итерации
когда большая хештаблица наполняется. А наполняется она обычно из файла или
из сокета или из БД а там требования к скорости ослаблены в 1000 раз примерно.

Это похоже на шаблон CQRS


О_о
...
Рейтинг: 0 / 0
массовый поиск подстрок в строке
    #39951247
booby
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
a_voronin
L1G


и убедиться, что ваш LINQ .Cast<Match>().Select(m => m.Value).Distinct().ToArray() не тормозит
а то, может быть, оставить от этого только


Ключевым здесь является Distinct(), именно ради него вся конструкция и напридумана.

бред какой-то.
Оправдать можно только временем, потраченным на разглядывание ассемблера.
Обидно же будет, если, к несчастью, вдруг заработает быстрее 30 секунд, вместо правильных трёх минут.
....
...
Рейтинг: 0 / 0
массовый поиск подстрок в строке
    #39951259
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
L1G,

Тут нужен эксперимент. Если мы 1 потоком утилизируем канал памяти то запуск 2,3,4 потока уже не даёт эффекта.
...
Рейтинг: 0 / 0
118 сообщений из 118, показаны все 5 страниц
Форумы / WinForms, .Net Framework [игнор отключен] [закрыт для гостей] / массовый поиск подстрок в строке
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


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