LINQ Performance для больших коллекций
Это позволяет использовать те же функции, что и ROW_NUMBER () AND PARTITION BY в MySQL
SELECT @row_num := IF(@prev_value=GENDER,@row_num+1,1) AS RowNumber
FirstName,
Age,
Gender,
@prev_value := GENDER
FROM Person,
(SELECT @row_num := 1) x,
(SELECT @prev_value := '') y
ORDER BY Gender, Age DESC
6 ответов
В Вашем текущем коде Вы не используете ни одной из специальных функций Dictionary / SortedDictionary / HashSet наборы, Вы используете их тот же способ, которым Вы использовали бы a List. Именно поэтому Вы не видите разницы в производительности.
Если Вы используете словарь в качестве индекса, где первые несколько символов строки являются ключом, и список строк является значением, Вы можете из строки поиска выбирать небольшую часть всего набора строк, который имеет возможные соответствия.
Я записал класс ниже для тестирования этого. Если я заполняю его с миллионом строк и поиск с восемью символьными строками, это разрывается через все возможные соответствия приблизительно в 3 мс. Поиск с одной символьной строкой является худшим случаем, но это находит первые 1 000 соответствий приблизительно в 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);
}
}
Я держал пари, что у Вас есть индекс на столбце, таким образом, SQL-сервер может сделать сравнение в O (журнал (n)) операции, а не O (n). Для подражания поведению SQL-сервера используйте отсортированный набор и найдите все строки s таким образом что s> = запрос и затем посмотрите на значения, пока Вы не находите значение, которое не запускается с 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++;
}
}
Если Вы делаете, "запускается с", Вы только заботитесь о порядковых сравнениях, и у Вас может быть отсортированный набор (снова в порядковом порядке) затем, я предложил бы, чтобы у Вас были значения в списке. Вы можете затем двоичный поиск для нахождения первого значения, которое запускается с правильного префикса, затем спуститесь по списку, линейно приводящему к результатам до первого значения, которое не запускается с правильного префикса.
На самом деле Вы могли, вероятно, сделать другой двоичный поиск первого значения, которое не запускается с префикса, таким образом, у Вас были бы запуск и конечная точка. Затем просто необходимо применить критерий длины к той части соответствия. (Я надеялся бы, что, если это - разумные данные, префикс, соответствующий, собирается избавиться от большинства значений кандидата.) Способ найти первое значение, которое не запускается с префикса, состоит в том, чтобы искать лексикографически первое значение, которое не делает - например, с префиксом "ABC", поиск "ABD".
Ни одно из этого не использует LINQ, и это все очень характерно для Вашего особого случая, но это должно работать. Сообщите мне, не имеет ли какое-либо из этого смысла.
При попытке оптимизировать поиск списка строк с данным префиксом, Вы могли бы хотеть смотреть на реализацию Trie (чтобы не быть ошибочными с регулярным деревом) структура данных в C#.
Попытки предлагают очень быстрые поиски префикса и имеют очень маленькую память наверху по сравнению с другими структурами данных для этого вида операции.
О LINQ к Объектам в целом. Весьма обычно иметь сокращение скорости по сравнению с SQL. Сеть замусорена статьями, анализируя ее производительность.
Я думаю, что проблема состоит в том, что Linq не имеет никакого способа использовать то, что Ваша последовательность уже отсортирована. Особенно это не может знать, то применение StartsWith функция сохраняет порядок.
Я предложил бы использовать List.BinarySearch метод вместе с a IComparer<string> это делает только сравнение первых символов запроса (это могло бы быть хитро, так как не ясно, если строка запроса всегда будет первой или второй параметр к ()).
Вы могли даже использовать стандартное сравнение строк, так как BinarySearch возвращает отрицательное число, которое можно дополнить (использующий ~) для получения индекса первого элемента, который больше, чем запрос.
Необходимо затем запустить с возвращенного индекса (в обоих направлениях!) для нахождения всех элементов, соответствующих строке запроса.
Просто смотря на Ваш код, я сказал бы, что необходимо переупорядочить сравнение для использования в своих интересах замыкания накоротко при использовании булевых операторов:
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 (в случае индексов), и это просто было бы дублированием усилия с Вашей стороны.