Как лучше всего отсортировать около 2,5 миллионов записей в памяти на С#?
Считайте, что у меня есть класс
class Employee
{
public string Id { get; set; }
public string Type { get; set; }
public string Identifier { get; set; }
public object Resume { get; set; }
public DateTime StartDate { get; set; }
public DateTime EndDate { get; set; }
}
List<Employee> employees = LoadEmployees(); //Around 2.5 million to 3 millions employees
employees = employees
.Where(x => x.Identifier != null)
.OrderBy(x => x.Identifier)
.ToArray();
У меня есть требование, когда я хочу загрузить и отсортировать около 2,5 миллионов сотрудников в памяти, но запрос Linq застревает в предложении OrderBy. Любые указатели на это? Я создал этот класс Employee только для того, чтобы упростить мою проблему.
Мой запрос застревает на var employee= employee.OrderBy(x => x.Identifier) .Where(x => x.Identifier!= null) .ToArray();
Также что такое LoadEmployees и каков тип возврата? Можете ли вы отсортировать их в источнике (например, если LoadEmployees вызывает базу данных для извлечения записей). Также можете ли вы отфильтровать в источнике и применить условие Identifier != null в источнике к возвращаемым записям?
Поставьте .Where() перед .OrderBy(). Кроме того, измените тип Employees на IEnumerable<Employee> и удалите как можно больше вызовов .ToArray(), особенно в методе LoadEmployees().
Я не получаю сотрудников из базы данных. Я разбираю его из файла
По крайней мере, вы можете поменять местами OrderBy и Where.
Что вы собираетесь делать с полученным массивом?
Это должно быть ToList, а не ToArray, если вы измените код таким образом. Или вы можете использовать новый тип.
Также рекомендуется указывать StringComparer, в данном случае возможно OrdinalIgnoreCase. Это сделает сортировку строк более эффективной.
Я хочу применить некоторую логику, а затем сохранить ее.
В этом случае не звоните ToList или ToArray. Вместо этого выполните свою логику с возвращенным IEnumerable<Employee> и сохраните его обратно в a/the Stream. Это также может ускорить все. var filteredEmployees = employees.Where(x => x.Identifier != null).OrderBy(x => x.Identifier, StringComparer.OrdinalIgnoreCase);
Методы Linq общеизвестно медленны. Попробуйте реализовать собственный алгоритм.
@JeromeBaek Я бы очень сомневался, что это так ...
Попробуйте отсортировать список на месте, используя метод List.Sort(). Это алгоритм O(log N), тогда как я считаю, что LINQ OrderBy — это алгоритм O(N log N).
@JessedeWit С какой стати вы ожидаете, что LINQ будет использовать алгоритм сортировки N ^ 2? Это не так, потому что нет веских причин делать что-то настолько глупое. Он использует быструю сортировку.
N log N, я имел в виду, что с LINQ ему придется перебирать оставшиеся записи, чтобы найти наименьшую для каждой записи. Сортировка на месте более эффективна, потому что вы можете продолжать перемещать следующий элемент в списке влево, пока он не окажется на нужном месте.
Я беру свои слова обратно: stackoverflow.com/a/1832713/3883866
Лиззи, вы можете еще раз взглянуть на ответ, так как он был обновлен с учетом лучших улучшений производительности, которые я смог сделать, и посмотреть, поможет ли это вам.
@JessedeWit Перемещение следующего элемента влево до тех пор, пока он не встанет на место, является неэффективным алгоритмом сортировки очень. Такой подход никогда не должен использоваться ни в одном производственном коде. Да, метод LINQ должен материализовать всю коллекцию, чтобы вычислить первое значение. Хотя о чем нужно знать, это не делает его менее эффективным, чем один из уже материализованных коллекций.
Добавление StringComparer.OrdinalIgnoreCase определенно помогло.
Ответы 1
Сначала я бы использовал предложение .Where(x => x.Identifier != null), поскольку оно сначала фильтрует некоторые данные, а затем выполняет OrderBy. Учитывая тот факт, что у вас Только ~2,5 миллиона записей и что это только базовые типы, такие как string и DateTime, то проблем с памятью в этом случае быть не должно.
Редактировать:
Я только что запустил ваш код в качестве образца, и это действительно вопрос нескольких секунд (например, более 15 секунд на моей машине, которая не имеет очень мощного процессора, но, тем не менее, она не зависает):
List<Employee> employees = new List<Employee>();
for(int i=0;i<2500000;i++)
{
employees.Add(new Employee
{
Id = Guid.NewGuid().ToString(),
Identifier = Guid.NewGuid().ToString(),
Type = i.ToString(),
StartDate = DateTime.MinValue,
EndDate = DateTime.Now
});
}
var newEmployees = employees
.Where(x => x.Identifier != null)
.OrderBy(x => x.Identifier)
.ToArray();
В качестве второго редактирования я только что провел несколько тестов, и кажется, что реализация с использованием Parallel Linq может быть в некоторых случаях быстрее примерно на 1,5 секунды, чем последовательная реализация:
var newEmployees1 = employees.AsParallel()
.Where(x => x.Identifier != null)
.OrderBy(x => x.Identifier)
.ToArray();
И это лучшие цифры, которые я получил:
7599 //serial implementation
5752 //parallel linq
Но параллельные тесты могут варьироваться от одной машины к другой, поэтому я предлагаю провести некоторые тесты самостоятельно, и если вы все еще обнаружите проблему с этим, то, возможно, отредактируйте вопрос/опубликуйте другой.
Используя подсказку, предложенную @Igor в комментарии ниже, параллельная реализация с StringComparer.OrdinalIgnoreCase примерно в три раза быстрее, чем простая параллельная реализация. Окончательный (самый быстрый) код выглядит так:
var employees = employees.AsParallel()
.Where(x => x.Identifier != null)
.OrderBy(x => x.Identifier, StringComparer.OrdinalIgnoreCase)
.ToArray();
StringComparer.OrdinalIgnoreCase? (.OrderBy(x => x.Identifier, StringComparer.OrdinalIgnoreCase)) вы резко сократите время.
@Igor, он действительно работает быстрее, используя StringComparer.OrdinalIgnoreCase в OrderBy. Спасибо, я обновил ответ!
Спасибо за все комментарии, я собираюсь включить все эти изменения
Что не так с тем, что у вас есть сейчас?