Подтвердить что ты не робот

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

У меня есть большая коллекция строк (до 1 М) в алфавитном порядке. Я экспериментировал с запросами 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, Dictionary и т.д. реализуют поиск с использованием поиска двоичного дерева вместо стандартного перечисления. Каковы мои возможности для высокопроизводительных запросов LINQ в расширенные типы коллекций?

4b9b3361

ОТВЕТЫ

Ответ 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);
    }

}

Ответ 2

Уверен, у вас есть индекс в столбце, поэтому 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++;
    }
}

Ответ 3

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

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

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

Ответ 4

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

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

О LINQ для объектов в целом. Это не редкость для снижения скорости по сравнению с SQL. Сеть замусорена статьями, анализируя ее производительность.

Ответ 5

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

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 (в случае индексов), и это будет просто дублированием усилий с вашей стороны.

Ответ 6

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

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

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

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