AppendOnly
1.0.0
Высокоскоростной неизменяемый список C# только для добавления. (обновление: 23 сентября; не рекомендуется использовать. Обоснование и альтернативы см. в примечаниях внизу.)
dotnet добавить пакет AppendOnly
Во-первых, существующие неизменяемые коллекции с трудом позволяют добавлять, удалять и обновлять, возвращая новые коллекции. Они буквально ДОЛЖНЫ копировать вещи, МНОГО. Если вы только добавляете, LinkedList — ваш друг, и может показаться, что он «скопирован» мгновенно.
Во-вторых, существующие неизменяемые библиотеки сложны и сложны в использовании. Они требуют классов строителя и хорошего понимания реальной механики, иначе у вас возникнут серьезные проблемы с производительностью.
И наконец: этот класс совершенно безопасно использовать в действительно очень узких циклах. То есть настолько туго, насколько это возможно.
AppendOnly использует A linkedList внутри себя и никогда не копирует элементы коллекции при создании новой «неизменяемой» копии. Он просто возвращает новый класс коллекции, который использует тот же внутренний «изменяемый» linkedList, но не предоставляет никаких методов для его изменения, а предоставляет только интератор, который выполняет итерацию по первым (n) элементам коллекции.
Таким образом, по мере того, как коллекция становится больше, более ранние (более старые) экземпляры класса коллекции никогда не увидят (отобразят через перечислитель) новые записи, добавленные в конец списка. После добавления 1000 новых «транзакций» в транзакционную коллекцию addOnly вы фактически имеете (если вы сохранили ссылки на каждую вновь созданную коллекцию) 1000 указателей на коллекции, каждая из которых содержит 1, 2, 3, 4 и т. д. элемента, но с почти нулевыми дополнительными элементами. накладные расходы на память.
Если использовать другие неизменяемые библиотеки со сборщиками, большинство из них дадут вам как минимум 500 000 экземпляров объектов.
Возможно, я ошибаюсь, это отправная точка, дайте мне знать, если вы это используете. Я буду создавать больше коллекций в том же духе.
var moving = new AppendOnlyList<Moves>();var new_moves = new AppendOnlyList<Moves>();Debug.Assert(moves.Length == 0);// добавляем 10 случайных ходов for(int i=0; i<10 ; i++) new_moves = new_moves.Add(randomMove());// исходные ходы по-прежнему не содержат элементов, хотя new_list добавил элемент в список List.Debug.Assert(moves.Length == 0);// new_list имеет 10 элементов в коллекцииDebug.Assert(new_moves.Length == 10);// этот список можно безопасно перебирать несколько раз, и он является потокобезопасным// код ниже показывает итерацию по всему списку десять раз, что вы обычно делаете только с // перечислимым объектом, если вы его кэшировали, т. е. создали локальный copy.// Я знаю, что это не выглядит так уж много, но это действительно важно. // Кроме того, это безопасно делать, ПОКА другие потоки заняты добавлением в ту же базовую коллекцию, // что является массовым НЕТ-НЕТ в мире потоков. Здесь это совершенно безопасно.for(int i = 0; i<10; i++){foreach(var move in new_moves.Items) await DoSomethingFunkyAsync(move);} В приведенном выше коде new_moves и исходные moves используют один и тот же связанный список. Когда создается новая копия AppendOnlyList, новых клонов НЕ создается, сохраняется только точка в заголовке списка и длина.
Это ОЧЕНЬ БЫСТРО, т. е. НЕТ КОПИИ, поэтому это бесконечно быстрее, чем любая другая неизменяемая коллекция, создающая копии.
И перебор коллекции является потокобезопасным, ВО ВРЕМЯ ее перечисления из других потоков! БУМ! ... или точнее «нет Бум!».
это версия 0.1.3 , что означает, что она не готова к использованию в производстве. Это доказательство концепции, и мне нужно написать несколько тестов потоков, чтобы доказать приведенные выше утверждения, а затем попросить своих коллег просмотреть и сообщить мне.
Я также хочу провести сравнение скорости между этой и другими коллекциями, а также параллельное сравнение.
Если вам нравится этот пакет, взгляните на фактическую реализацию, это буквально два класса, AppendOnlyList и LinkedListExtensions , и они крошечные.
дайте мне знать, что вы думаете?
:D
Если есть вопросы, свяжитесь со мной,
Alan Hemmings, twitter : @snowcode LinkedIn : https://www.linkedin.com/in/goblinfactory www : https://goblinfactory.co.uk
...и не особо им пользовался, и вообще забыл о нем. С тех пор, как я написал это, вещи (C#) сильно изменились, и хотя в C# произошло много изменений, ни одно из них не сильно упростило ситуацию. К сожалению, я думаю, что мои мысли выше о том, когда использовать этот пакет в свете новых языковых изменений, могут быть чушью и, возможно, быть... весьма ошибочными. Тест ОПРЕДЕЛЕННО необходим, прежде чем делать что-либо дальше. Вот несколько заметок из краткой беседы с архитектором AI C#, в которой предлагается пересмотреть этот проект. Честно говоря, я думаю, что этот проект все еще может быть оправдан, но, возможно, как оболочка DSL (своего рода простой фабричный класс) вокруг различных способов правильного создания структур типов, состоящих только из приложений. Нафф сказал; вот отзыв;
(черновики, необходимо протестировать и подтвердить!)
Да, в C# вы можете использовать System.Collections.Generic.ArrayBuffer<T> или System.Buffers.ArrayPool<T> для более эффективных структур только для добавления и эффективного использования памяти, которые можно эффективно перечислять. Однако если вам нужна более практичная и эффективная структура, допускающая только добавление, рассмотрите следующие варианты:
ImmutableArray<T>.Builder
Структура, доступная только для добавления, предоставляемая пакетом System.Collections.Immutable .
Он обеспечивает эффективное добавление и является изменяемым во время сборки, но становится неизменным после преобразования в ImmutableArray<T> .
var builder = ImmutableArray.CreateBuilder<int>();builder.Add(1);builder.Add(2);var immutableArray = builder.ToImmutable();
Memory<T> и Span<T> с ArrayPool<T>
Эффективен для обработки больших блоков данных с минимальным выделением памяти.
Вы сами управляете памятью, что позволяет избежать частых перераспределений по сравнению с List<T> .
Подходит, если вам нужен больший контроль над использованием памяти, но требуется тщательное управление.
var пул = ArrayPool<int>.Shared;int[] array =pool.Rent(1000); // Запрашиваем массив из пула // Добавляем и управляем своими данными здесьpool.Return(array); // Возвращаемся в пул, когда закончим
ValueListBuilder<T> (из System.Buffers)
Предоставляет эффективный способ создания коллекций с распределением по стеку.
Особенно полезно, когда вы знаете, что размер данных ограничен, и вам нужна высокая производительность без выделения кучи.
Span<int> InitialSpan = stackalloc int[16]; вар valueListBuilder = новый ValueListBuilder<int>(initialSpan);valueListBuilder.Append(1);valueListBuilder.Append(2);ReadOnlySpan<int> span = valueListBuilder.AsSpan();
Sequence<T> из System.IO.Pipelines
Подходит для эффективной обработки последовательности данных только с добавлением.
Подходит для сценариев, требующих высокопроизводительных операций ввода-вывода и потоковой передачи данных.
List<T> : подходит для добавления (амортизированный O(1) ) и обеспечивает быстрое перечисление благодаря непрерывной памяти.
ImmutableArray<T>.Builder : эффективен для добавления и последующего создания неизменяемого.
Memory<T> с ArrayPool<T> : отлично подходит для сокращения выделения памяти.
ValueListBuilder<T> : эффективное построение на основе стека, когда размер известен. На основе стека, подходит для временных и эффективных коллекций.
Sequence<T> : для сценариев с высокой пропускной способностью, требующих эффективного добавления.
Выбирайте в зависимости от ваших конкретных требований к производительности и памяти.
ChatGPT сказал;
LinkedList<T> в C# — это вариант структуры памяти, предназначенной только для добавления, но он, как правило, менее эффективен с точки зрения использования памяти и медленнее выполняет перечисление по сравнению с другими структурами по следующим причинам:
LinkedList<T> : Издержки памяти : каждый узел в LinkedList<T> содержит ссылки как на следующий, так и на предыдущий узлы, что приводит к значительным издержкам памяти по сравнению со смежными структурами, такими как массивы или List<T> .
Неэффективность кэша . В отличие от массивов или List<T> , которые хранятся в непрерывной памяти, узлы LinkedList<T> разбросаны по куче. Это делает его менее удобным для кэширования, что приводит к замедлению итераций и времени доступа.
Производительность перечисления . Хотя LinkedList<T> эффективен для операций добавления ( O(1) для добавления в конец), его производительность перечисления обычно ниже, чем у массивов или списков, поскольку ему не хватает преимущества локальности кэша.
LinkedList<T> :Когда вам нужны частые вставки или удаления на обоих концах или в середине.
Если вы хотите избежать смещения элементов, как в List<T> .
LinkedList<T> можно использовать только для сценариев добавления, но, как правило, это не самый эффективный выбор для перечисления или использования памяти по сравнению с List<T> или другими современными структурами данных.
