Производительность LINQ для больших коллекций

Question

У меня есть большая коллекция строк (до 1M) в алфавитном порядке. Я экспериментировал с запросами LINQ против этой коллекции, используя HashSet, SortedDictionary и Dictionary. Я статический кеширование коллекции, размер до 50 МБ, и я всегда вызываю запрос LINQ к кешированной коллекции. Моя проблема заключается в следующем:

Независимо от типа сбора, производительность намного беднее, чем SQL (до 200 мс). При выполнении аналогичного запроса с базовыми таблицами SQL производительность намного быстрее (5-10 мс). Я выполнил свои запросы LINQ следующим образом:

public static string ReturnSomething(string query, int limit) 
{ 
    StringBuilder sb = new StringBuilder(); 
    foreach (var stringitem in MyCollection.Where(
     x => x.StartsWith(query) && x.Length > q.Length).Take(limit)) 
    { 
     sb.Append(stringitem); 
    } 

    return sb.ToString(); 
} 

Это мое понимание того, что HashSet, словарь и т.д. осуществлять поиски с использованием двоичного дерева поиска вместо стандартного перечисления. Каковы мои возможности для высокопроизводительных запросов LINQ в расширенные типы коллекций?

Answer 1

В текущем коде не использовать какие-либо из специальных особенностей Dictionary/SortedDictionary/HashSet коллекций, вы их используете один и тот же путь, что вы использовали бы List. Вот почему вы не видите разницы в производительности.

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

Я написал нижеприведенный класс, чтобы проверить это. Если я заполнил его миллионными строками и выполнил поиск с восемью символьными строками, он прорвется через все возможные совпадения примерно за 3 мс. Поиск с одной символьной строкой является наихудшим случаем, но он находит первые 1000 матчей примерно за 4 мс. Поиск всех совпадений для строк одного символа занимает около 25 мс.

Класс создает индексы для 1, 2, 4 и 8 символов. Если вы посмотрите на свои данные и то, что ищете, вы сможете выбрать, какие индексы создавать, чтобы оптимизировать его для ваших условий.

public class IndexedList { 

    private class Index : Dictionary<string, List<string>> { 

     private int _indexLength; 

     public Index(int indexLength) { 
      _indexLength = indexLength; 
     } 

     public void Add(string value) { 
      if (value.Length >= _indexLength) { 
       string key = value.Substring(0, _indexLength); 
       List<string> list; 
       if (!this.TryGetValue(key, out list)) { 
        Add(key, list = new List<string>()); 
       } 
       list.Add(value); 
      } 
     } 

     public IEnumerable<string> Find(string query, int limit) { 
      return 
       this[query.Substring(0, _indexLength)] 
       .Where(s => s.Length > query.Length && s.StartsWith(query)) 
       .Take(limit); 
     } 

    } 

    private Index _index1; 
    private Index _index2; 
    private Index _index4; 
    private Index _index8; 

    public IndexedList(IEnumerable<string> values) { 
     _index1 = new Index(1); 
     _index2 = new Index(2); 
     _index4 = new Index(4); 
     _index8 = new Index(8); 
     foreach (string value in values) { 
      _index1.Add(value); 
      _index2.Add(value); 
      _index4.Add(value); 
      _index8.Add(value); 
     } 
    } 

    public IEnumerable<string> Find(string query, int limit) { 
     if (query.Length >= 8) return _index8.Find(query, limit); 
     if (query.Length >= 4) return _index4.Find(query,limit); 
     if (query.Length >= 2) return _index2.Find(query,limit); 
     return _index1.Find(query, limit); 
    } 

} 

Answer 2

Если вы начинаете с «начинается с», вам не обойтись только с порядковыми сравнениями, и вы можете отсортировать коллекцию (снова в порядковом порядке), тогда я предлагаю вам иметь значения в списке. Затем вы можете найти двоичный поиск, чтобы найти первое значение, которое начинается с правого префикса, затем перейдите в список, линейно дающий результаты до первого значения, которое не начните с правого префикса.

Фактически, вы могли бы сделать еще один двоичный поиск для первого значения, которое не начинается с префикса, поэтому у вас есть начало и конечная точка. Тогда вам просто нужно применить критерий длины к этой соответствующей части. (Надеюсь, что если это разумные данные, сопоставление префикса позволит избавиться от большинства значений кандидата.) Способ найти первое значение, которое не начинается с префикса, - это поиск значения лексикографически-первого значения, которое нет - например с префиксом «ABC», найдите «ABD».

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

Answer 3

Просто глядя на свой код, я бы сказал, что вы должны изменить порядок сравнения, чтобы воспользоваться короткого замыкания при использовании логических операторов:

foreach (var stringitem in MyCollection.Where(
    x => x.Length > q.Length && x.StartsWith(query)).Take(limit)) 

Сравнение длины всегда собирается быть O (1) (поскольку длина сохраняется как часть строки, она не засчитывает каждый символ каждый раз), тогда как вызов StartsWith будет выполнять операцию O (N), где N - длина запроса (или длина строки, в зависимости от того, что меньше).

Помещая сравнение длины перед вызовом StartsWith, если это сравнение не удастся, вы сэкономите себе дополнительные циклы, которые могут складываться при обработке большого количества элементов.

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

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

Однако в этот момент вы действительно просто воссоздаете то, что делает SQL Server (в случае индексов), и это будет просто дублированием усилий с вашей стороны.

Answer 4

Уверен, что у вас есть индекс в столбце, поэтому SQL-сервер может выполнять сравнение в операциях O (log (n)), а не O (n).Чтобы имитировать поведение сервера SQL, используйте отсортированную коллекцию и найдите все строки s, такие как s> = query, а затем посмотрите значения до тех пор, пока не найдете значение, которое не начинается с s, а затем сделайте дополнительный фильтр для значений. Это то, что называется сканированием диапазона (Oracle) или поиском индекса (SQL-сервер).

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

// Note, list must be sorted before being passed to this function 
IEnumerable<string> FindStringsThatStartWith(List<string> list, string query) { 
    int low = 0, high = list.Count - 1; 
    while (high > low) { 
     int mid = (low + high)/2; 
     if (list[mid] < query) 
      low = mid + 1; 
     else 
      high = mid - 1; 
    } 

    while (low < list.Count && list[low].StartsWith(query) && list[low].Length > query.Length) 
     yield return list[low]; 
     low++; 
    } 
} 

Answer 5

Если вы пытаетесь оптимизировать отрываясь список строк с заданным префиксом Вы могли бы хотеть, чтобы взглянуть на реализацию Trie (не путать с обычной tree) структуры данных в C#.

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

О LINQ to Objects в целом. Это не редкость для снижения скорости по сравнению с SQL. Чистая стоимость составляет littered with articles.

Answer 6

Я думаю, проблема в том, что Linq не имеет возможности использовать тот факт, что ваша последовательность уже отсортирована. Особенно он не может знать, что применение функции StartsWith сохраняет порядок.

Я бы предложил использовать метод List.BinarySearch вместе с IComparer<string>, что делает только сравнение первых символов запроса (это может быть сложно, так как не ясно, если строка запроса всегда будет первым или вторым параметром ()).

Вы даже можете использовать стандартное сравнение строк, поскольку BinarySearch возвращает отрицательное число, которое вы можете дополнить (используя ~), чтобы получить индекс первого элемента, который больше вашего запроса.

Затем вы должны начать с возвращаемого индекса (в обоих направлениях!), Чтобы найти все элементы, соответствующие вашей строке запроса.