powered by simpleCommunicator - 2.0.49     © 2025 Programmizd 02
Форумы / WinForms, .Net Framework [игнор отключен] [закрыт для гостей] / массовый поиск подстрок в строке
25 сообщений из 118, страница 1 из 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
25 сообщений из 118, страница 1 из 5
Форумы / WinForms, .Net Framework [игнор отключен] [закрыт для гостей] / массовый поиск подстрок в строке
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


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