Как разбить IList<T> на сегменты размером N, не создавая копий и не выделяя памяти?
У меня есть очень большая коллекция, реализующая универсальный интерфейс IList<T> и содержащая десятки миллионов элементов, и я хотел бы обрабатывать их параллельно с помощью PLINQ. Я заметил, что накладные расходы параллелизма довольно значительны, потому что обработка каждого отдельного элемента очень легкая, поэтому я ищу способы разбить обработку на части, разбивая IList<T> на небольшие сегменты. Моя цель - наконец получить что-то вроде этого:
IList<Person> source = GetAllPersons();
double averageAge = source
.Segmentate(1000) // Hypothetical operator that segmentates the source
.AsParallel()
.Select(segment => segment.Select(person => (double)person.CalculateAge()).Sum())
.Sum() / source.Count;
Я мог бы использовать оператор Batch из библиотеки MoreLinq или любой из ответов из многих связанных вопросов, но все эти решения выделяют несколько небольших массивов (или списков) и копирование исходного кода в эти контейнеры, а я этого не хочу. В моем случае у меня есть дополнительное требование, чтобы сборщик мусора как можно дольше простаивал.
Я заметил, что в .NET есть тип ArraySegment, который, кажется, идеально соответствует моим требованиям:
// Delimits a section of a one-dimensional array.
public readonly struct ArraySegment<T> : ICollection<T>, IEnumerable<T>,
IEnumerable, IList<T>, IReadOnlyCollection<T>, IReadOnlyList<T>
Я мог бы использовать этот тип для реализации оператора Segmentate без распределения следующим образом:
/// <summary>Segmentates the source array into sized segments.</summary>
public static IEnumerable<ArraySegment<T>> Segmentate<T>(this T[] source, int size)
{
for (int offset = 0; offset < source.Length; offset += size)
{
yield return new ArraySegment<T>(source, offset,
Math.Min(size, source.Length - offset));
}
}
Но я не могу использовать этот тип, потому что мой источник — это IList<T>, а не массив. И копировать его в массив на самом деле не вариант, потому что источник часто мутирует. И создание новых копий массива все время противоречит моим требованиям.
Итак, я ищу тип ListSegment<T>, но, насколько я понимаю, его нет в .NET. Должен ли я реализовать это сам? И если да, то как? Или есть другой способ сегментировать IList<T>, не вызывая распределения?
Уточнение: Моя исходная коллекция не является List<T>. Это пользовательский класс, реализующий интерфейс IList<T>.
Я получаю 350 миллисекунд для 150 000 000 записей с помощью чего-то такого простого, как: double mediumAge = source .AsParallel() .Average(p => (double)p.Age); Является ли это сфабрикованным примером, или, точнее, вопрос больше связан с концепцией нарезки вещей без распределения?
@AlexandruClonțea да, пример сфабрикован. Я добавил его только для демонстрации концепции.
@ckuri кажется, что тип Span имеет ограничения, которые делают его непригодным для моего варианта использования. Я изменил подпись своего оператора на IEnumerable<Span<T>> Segmentate<T>(... и получаю ошибку времени компиляции: CS0306 Тип «Span<T>» не может использоваться в качестве аргумента типа.
Это хорошее чтение, которое может вас заинтересовать: download.microsoft.com/download/B/C/F/… Мне кажется, что вы хотите сидеть где-то между этими двумя мирами в этом сценарии, который вы описали ( PLINQ и Parallel). Я думал об одном решении, которое дало бы части коллекции, но мне это кажется параллельным с дополнительными шагами.
@AlexandruClonțea спасибо за ссылку, я прочитаю связанный документ. Да, я хочу, чтобы мощность Parallel сочеталась с красотой и удобством PLINQ. По моему опыту, использование самых мощных перегрузок Parallel.ForEach может стать очень сложным и некрасивым...
@AlexandruClonțea, кстати, ваш компьютер должен быть в 10 раз быстрее моего, потому что усреднение 150 000 000 чисел с двойной точностью с помощью PLINQ занимает на моем ПК 3 секунды. :-)
i9-9900K xD Дело было не в этом. Я думаю, что разумно получить результат менее чем за 15 секунд, но это зависит от варианта использования. Один момент заключался в том, что правило распараллеливания № 1 — «не делать». Пункт № 2: мне не нравится заново изобретать колеса, если только я не хочу научиться делать колеса. Конечно, это интересная область для изучения, но во всех случаях, когда мне требовалось очень сложное распараллеливание, я приходил к решениям, которые «привязаны» к конкретной проблеме, а не к чему-то общеприменимому. Хотя мне нравится сама идея операции, но должна быть причина, по которой она отсутствует в SDK.
Примечание: для конкретного «синтетического» варианта использования усреднения я бы, вероятно, искал способ сделать это «на ходу» или создать для него прогностическую модель, а не всегда делать дорогостоящие вещи, особенно если мы перейдем от 150 000 000 на порядки больше :)
@AlexandruClonțea Я согласен со всеми вашими пунктами. Пример averageAge, вероятно, немного глупый, но это то, что пришло мне в голову, когда я искал пример для этого вопроса. :-)
Ответы 2
Этот ответ предполагает, что ваш конкретный IList имеет тип List. Вы можете использовать функцию GetRange, которая в значительной степени делает то, что вы хотите:
Неглубокая копия коллекции ссылочных типов или подмножества этой коллекции содержит только ссылки на элементы коллекции. Сами объекты не копируются. Ссылки в новом списке указывают на те же объекты, что и ссылки в исходном списке.
Даже ArraySegment<T> создаст какой-то ссылочный объект для хранения сегмента массива, так что вы не можете полностью избежать этого.
Если вы хотите избежать хранения ссылок (также называемых мелкими копиями), то Span будет в порядке, но ваш комментарий о том, что ваша коллекция изменяется, конфликтует с this
Элементы не должны добавляться или удаляться из списка, пока используется Span.
Таким образом, вашим единственным другим решением было бы создать его самостоятельно, как вы упомянули.
Предупреждение: есть причина, по которой такая вещь не существует встроенной. Массив имеет фиксированный размер, поэтому получение сегмента намного безопаснее. Будьте осторожны с неожиданными последствиями и побочными эффектами при создании такой конструкции. Вот почему Span предупреждает вас, что это небезопасно. Вы знаете только свои требования и то, как меняются ваши данные, поэтому ваша оболочка коллекции должна учитывать их и соответствующим образом обрабатывать.
Спасибо Афанасию за ответ, но List<T>.GetRange выделяет новый List<T>, а это именно то, чего я пытаюсь избежать!
Итак, чтобы убедиться, что я понимаю, вы просто не хотите поддерживать пространство, необходимое для хранения ссылок на одни и те же объекты?
Допустим, в моем источнике 50 000 000 элементов, и я хочу обработать их сегментами по 1000 элементов в каждом. Я не хочу выделять 50 000 одноразовых списков, по одному для каждого сегмента, просто для выполнения этого расчета. Я согласен с выделением одного объекта, перечислителя IList.
Ага, понял. GetRange вам не поможет. Проверьте обновленный ответ для деталей.
Афанасиос, чтобы уточнить, мой IList источник не мутирует во время параллельной обработки, потому что он изначально не является потокобезопасным. Он мутирует между одной параллельной обработкой и следующей.
Если каждый диапазон выполнен и ни один из них не используется при их изменении, реализация Span может работать для вас. Единственным недостатком является то, что она не реализует IEnumerable, поэтому вам придется повторять ее обычным способом.
Кстати, очень интересная реализация указателя: source.dot.net/#System.Private.CoreLib/Span.cs,d2517139cac388e8
Афанасиос Мне не повезло с типом Span. Смотрите мой ответ на комментарий ckuri под вопросом.
Таким образом, все сводится к созданию собственной реализации (с учетом приведенных выше соображений) или изменению реализации yield return и IEnumerable и передаче размера и индекса вашей функции, чтобы вернуть соответствующий сегмент. Я бы пошел со вторым решением.
Вот почему я упомянул, что вам придется выполнять итерацию обычным способом.
Запутанно... IList != IList<T> и IEnumerable != IEnumerable<T>. Так какие из них вы имеете в виду? (Неуниверсальные будут помещать каждый элемент во время перечисления, что может быть чрезвычайно дорогостоящим.)
Вам нужно реализовать эквивалент ArraySegment<T> для IList<T>. См. реализацию ниже. Для оптимальной производительности рассмотрите возможность использования промежутков.
Структура ListSegment<T>
public readonly struct ListSegment<T> : IList<T>
{
public List<T> Items { get; }
public int Offset { get; }
public int Count { get; }
public ListSegment(List<T> items, int offset, int count)
{
Items = items ?? throw new ArgumentNullException(nameof(items));
Offset = offset;
Count = count;
if (items.Count < offset + count)
{
throw new ArgumentException("List segment out of range.", nameof(count));
}
}
public void CopyTo(T[] array, int index)
{
if (Count > 0)
{
Items.CopyTo(Offset, array, index, Count);
}
}
public bool Contains(T item) => IndexOf(item) != -1;
public int IndexOf(T item)
{
for (var i = Offset; i < Offset + Count; i++)
{
if (Items[i].Equals(item))
{
return i;
}
}
return -1;
}
private T ElementAt(int index)
{
if (Count > 0)
{
return Items[Offset + index];
}
throw new ArgumentOutOfRangeException(nameof(index));
}
public ListSegmentEnumerator GetEnumerator() => new ListSegmentEnumerator(this);
#region IEnumerable<T> interface
IEnumerator<T> IEnumerable<T>.GetEnumerator() => GetEnumerator();
IEnumerator IEnumerable.GetEnumerator() => GetEnumerator();
#endregion
#region ICollection<T> interface
bool ICollection<T>.IsReadOnly => true;
void ICollection<T>.Add(T item) => throw new NotImplementedException();
bool ICollection<T>.Remove(T item) => throw new NotImplementedException();
void ICollection<T>.Clear() => throw new NotImplementedException();
#endregion
#region IList<T> interface
void IList<T>.Insert(int index, T item) => throw new NotImplementedException();
void IList<T>.RemoveAt(int index) => throw new NotImplementedException();
T IList<T>.this[int index]
{
get => ElementAt(index);
set => throw new NotImplementedException();
}
#endregion
public struct ListSegmentEnumerator : IEnumerator<T>
{
private readonly List<T> items;
private readonly int start;
private readonly int end;
private int current;
public ListSegmentEnumerator(ListSegment<T> segment)
{
items = segment.Items;
start = segment.Offset;
end = start + segment.Count;
current = start - 1;
}
public bool MoveNext()
{
if (current < end)
{
current++;
return current < end;
}
return false;
}
public T Current => items[current];
object IEnumerator.Current => Current;
void IEnumerator.Reset() => current = start - 1;
void IDisposable.Dispose() { }
}
}
Спасибо l33t за ответ! Кажется, что этот класс (близок к тому), что я ищу. Но разве public List<T> Items не следует определять как public IList<T> Items? Мой источник на самом деле не List<T>.
Вы можете изменить его на IList<T>. Я использую конкретный List<T> здесь, чтобы обеспечить строгую типизацию. Конкретный класс будет работать лучше в определенных ситуациях (например, во время перечисления, как описано здесь).
Да, я экспериментирую с вашим классом и понимаю, что все становится быстрее при работе с конкретными классами вместо интерфейсов. Я вижу, что реализация конкретного перечислителя также выгодна по сравнению с итератором, который дает результат. К сожалению, мне нецелесообразно иметь разные ListSegment-подобные классы для каждой IList<T> реализации, с которой мне приходится работать. Я намерен использовать его с PLINQ, который уже работает с интерфейсами, поэтому мне придется смириться с падением производительности (как плата за удобство).
Эта структура ListSegment<T> не использует перечислитель переменной items. Вместо этого вы можете смело использовать IList<T>. Однако, если вы перебираете общедоступное свойство Items, вы действительно увидите небольшой скачок производительности.
Вы можете создавать промежутки списка (stackoverflow.com/a/60514418/7565574), используя CollectionMarshal.AsSpan(), который аналогичен ArraySegment.