AppendOnly
1.0.0
Hochgeschwindigkeitsliste für unveränderliche C#-Anhänge. (Aktualisierung: 23. 24. September; die Verwendung wird nicht empfohlen. Gründe und Alternativen finden Sie in den Anmerkungen unten.)
dotnet fügt das Paket AppendOnly hinzu
Erstens ist es für bestehende unveränderliche Sammlungen wirklich schwierig, Hinzufügungen, Löschungen und Aktualisierungen vorzunehmen, die neue Sammlungen zurückgeben. Sie MÜSSEN buchstäblich Sachen kopieren, und zwar VIEL. Wenn Sie nur anhängen, ist LinkedList Ihr Freund und es kann so aussehen, als ob es sofort „kopiert“ wird.
Zweitens sind die vorhandenen unveränderlichen Bibliotheken komplex und schwer zu verwenden. Sie erfordern Builder-Klassen und ein gutes Verständnis der tatsächlichen Mechanik, sonst kommt es zu ernsthaften Leistungsproblemen.
Zu guter Letzt: Diese Klasse kann absolut sicher in sehr, sehr engen Schleifen verwendet werden. So eng wie möglich.
AppendOnly verwendet intern eine verknüpfte Liste und kopiert niemals die Sammlungselemente, wenn eine neue „unveränderliche“ Kopie erstellt wird. Es gibt einfach eine neue Sammlungsklasse zurück, die dieselbe interne „veränderbare“ verknüpfte Liste verwendet, aber keine Methoden zu ihrer Mutation verfügbar macht, sondern lediglich einen Interator verfügbar macht, der die ersten (n) Elemente in der Sammlung durchläuft.
Wenn also die Sammlung größer wird, werden frühere (ältere) Instanzen der Sammlungsklasse die neuen Einträge, die am Ende der Liste angehängt werden, nie sehen (über den Enumerator verfügbar machen). Nachdem Sie 1000 neue „Transaktionen“ zu einer appendOnly-Transaktionssammlung hinzugefügt haben, verfügen Sie effektiv (wenn Sie die Verweise auf jede neu erstellte Sammlung beibehalten haben) über 1000 Zeiger auf Sammlungen, die jeweils 1, 2, 3, 4 usw. Elemente enthalten, jedoch nahezu null zusätzliche Speicheraufwand.
Wenn Sie die anderen unveränderlichen Bibliotheken mit Buildern verwenden, erhalten Sie bei den meisten mindestens 500.000 Instanzen von Objekten.
Ich kann mich irren, es ist ein Ausgangspunkt. Lassen Sie es mich wissen, wenn Sie dies verwenden. Ich werde weitere Sammlungen in ähnlicher Weise erstellen.
var goes = new AppendOnlyList<Moves>();var new_moves = new AppendOnlyList<Moves>();Debug.Assert(moves.Length == 0);// 10 zufällige Züge hinzufügen for(int i=0; i<10 ; i++) new_moves = new_moves.Add(randomMove());// originale Moves haben immer noch keine Elemente, obwohl new_list ein Element hinzugefügt hat List.Debug.Assert(moves.Length == 0);// new_list hat 10 Elemente in seiner SammlungDebug.Assert(new_moves.Length == 10);// diese Liste kann sicher mehrmals iteriert werden und ist threadsicher// Der folgende Code zeigt, wie die gesamte Liste zehnmal durchlaufen wird, etwas, das Sie normalerweise nur gegen // eine Aufzählung tun würden, wenn Sie sie zwischengespeichert, also eine lokale Kopie erstellt haben.// Das weiß ich Es sieht nicht so aus, als würde es viel bewirken, aber das ist wirklich wichtig. // außerdem ist es sicher, dies zu tun, WÄHREND andere Threads damit beschäftigt sind, der gleichen zugrunde liegenden Sammlung etwas hinzuzufügen, // was in der Threading-Welt ein gewaltiges NEIN NEIN ist. Hier ist es völlig sicher.for(int i = 0; i<10; i++){foreach(var move in new_moves.Items) waiting DoSomethingFunkyAsync(move);} Im obigen Code verwenden new_moves und die ursprünglichen moves dieselbe zugrunde liegende verknüpfte Liste. Wenn eine neue Kopie der AppendOnlyList erstellt wird, werden KEINE neuen Klone erstellt, sondern nur ein Punkt auf den Kopf der Liste und die Länge bleibt erhalten.
Dies ist EXTREM SCHNELL, da KEINE KOPIE erstellt wird, also ist es unendlich schneller als jede andere unveränderliche Sammlung, die Kopien erstellt.
Und es ist threadsicher, über die Sammlung zu iterieren, WÄHREND sie von anderen Threads aufgezählt wird! BOOM! ... oder genauer gesagt „no Boom!“.
Dies ist Version 0.1.3 was bedeutet, dass sie nicht für den Produktionseinsatz bereit ist. Es handelt sich um einen Proof of Concept, und ich muss einige Threading-Tests schreiben, um die oben genannten Behauptungen zu beweisen, und dann meine Kollegen bitten, sie zu überprüfen und mir Bescheid zu geben.
Ich möchte auch einen Geschwindigkeitsvergleich zwischen dieser und anderen Sammlungen sowie einen direkten Vergleich durchführen.
Wenn Ihnen dieses Paket gefällt, schauen Sie sich die tatsächliche Implementierung an. Sie besteht buchstäblich aus zwei Klassen, AppendOnlyList und LinkedListExtensions , und sie sind winzig.
Lass mich wissen, was du denkst?
:D
Bei Fragen kontaktieren Sie mich unter:
Alan Hemmings, twitter : @snowcode LinkedIn : https://www.linkedin.com/in/goblinfactory www : https://goblinfactory.co.uk
...und habe es nicht oft benutzt, und nun ja, ich habe es vergessen. Die Dinge (C#) haben sich stark weiterentwickelt, seit ich dies geschrieben habe, und obwohl es in C# viele Änderungen gibt, hat keine davon die Dinge wirklich stark vereinfacht. Leider denke ich, dass meine obigen Überlegungen darüber, wann dieses Paket angesichts neuer Sprachänderungen verwendet werden sollte, möglicherweise Unsinn sind und möglicherweise ... ziemlich fehlerhaft waren. Tests sind UNBEDINGT erforderlich, bevor weitere Maßnahmen ergriffen werden. Hier sind einige Notizen aus einem kurzen Chat mit einem AI C#-Architekten, der eine erneute Betrachtung dieses Projekts vorschlägt. Ehrlich gesagt denke ich, dass dieses Projekt immer noch gerechtfertigt sein könnte, aber vielleicht als DSL-Wrapper (eine Art einfache Factory-Klasse) für die verschiedenen Möglichkeiten, appendonly-Typstrukturen ordnungsgemäß zu erstellen. Nuff sagte; Hier ist das Feedback.
(Notizentwurf, muss getestet und bestätigt werden!)
Ja, in C# können Sie System.Collections.Generic.ArrayBuffer<T> oder System.Buffers.ArrayPool<T> für effizientere Nur-Append- und speichereffizientere Strukturen verwenden, die effizient aufgezählt werden können. Wenn Sie jedoch eine praktischere und effizientere Nur-Anhang-Struktur wünschen, sollten Sie die folgenden Optionen in Betracht ziehen:
ImmutableArray<T>.Builder
Eine reine Anhängestruktur, die vom System.Collections.Immutable -Paket bereitgestellt wird.
Es ermöglicht effizientes Anhängen und ist beim Erstellen veränderbar, wird jedoch unveränderlich, sobald es in ein ImmutableArray<T> konvertiert wird.
var builder = ImmutableArray.CreateBuilder<int>();builder.Add(1);builder.Add(2);var immutableArray = builder.ToImmutable();
Memory<T> und Span<T> mit ArrayPool<T>
Effizient für die Verarbeitung großer Datenblöcke mit minimaler Speicherzuweisung.
Sie verwalten den Speicher selbst, wodurch häufige Neuzuweisungen im Vergleich zu List<T> vermieden werden.
Geeignet, wenn Sie mehr Kontrolle über die Speichernutzung wünschen, aber eine sorgfältige Verwaltung benötigen.
var pool = ArrayPool<int>.Shared;int[] array = pool.Rent(1000); // Fordern Sie ein Array vom Pool an// Hängen Sie Ihre Daten hier an und verwalten Sie siepool.Return(array); // Wenn fertig, zum Pool zurückkehren
ValueListBuilder<T> (Aus System.Buffers)
Bietet eine effiziente Möglichkeit, Sammlungen auf stapelzugeordnete Weise zu erstellen.
Besonders nützlich, wenn Sie wissen, dass die Datengröße begrenzt ist und Sie eine hohe Leistung ohne Heap-Zuweisungen wünschen.
Span<int> initialSpan = stackalloc int[16]; var valueListBuilder = new ValueListBuilder<int>(initialSpan);valueListBuilder.Append(1);valueListBuilder.Append(2);ReadOnlySpan<int> span = valueListBuilder.AsSpan();
Sequence<T> aus System.IO.Pipelines
Geeignet für die effiziente Verarbeitung einer Datensequenz im Nur-Anhang-Verfahren.
Gut für Szenarien, die leistungsstarke E/A-Vorgänge und Streaming-Daten erfordern.
List<T> : Gut zum Anhängen (amortisiertes O(1) ) und bietet aufgrund des zusammenhängenden Speichers eine schnelle Aufzählung.
ImmutableArray<T>.Builder : Effizient zum Anhängen und anschließenden Unveränderlichmachen.
Memory<T> mit ArrayPool<T> : Ideal zum Reduzieren von Zuweisungen.
ValueListBuilder<T> : Effizientes stapelbasiertes Erstellen, wenn die Größe bekannt ist. Stapelbasiert, geeignet für temporäre, effiziente Sammlungen.
Sequence<T> : Für Szenarien mit hohem Durchsatz, die ein effizientes Anhängen erfordern.
Wählen Sie basierend auf Ihren spezifischen Leistungs- und Speicheranforderungen.
ChatGPT sagte;
LinkedList<T> in C# ist eine Option für eine Nur-Anhänge-Speicherstruktur, ist jedoch aus folgenden Gründen im Allgemeinen weniger speichereffizient und langsamer für die Aufzählung im Vergleich zu anderen Strukturen:
LinkedList<T> : Speicheraufwand : Jeder Knoten in einer LinkedList<T> enthält Verweise sowohl auf den nächsten als auch auf den vorherigen Knoten, was im Vergleich zu zusammenhängenden Strukturen wie Arrays oder List<T> zu einem erheblichen Speicheraufwand führt.
Cache-Ineffizienz : Im Gegensatz zu Arrays oder List<T> , die im zusammenhängenden Speicher gespeichert werden, sind LinkedList<T> -Knoten über den Heap verteilt. Dies macht es weniger Cache-freundlich, was zu langsameren Iterations- und Zugriffszeiten führt.
Aufzählungsleistung : Während LinkedList<T> für Anhängevorgänge effizient ist ( O(1) für das Hinzufügen am Ende), ist die Aufzählungsleistung normalerweise langsamer als bei Arrays oder Listen, da der Vorteil der Cache-Lokalität fehlt.
LinkedList<T> verwendet werden sollte:Wenn Sie häufige Einfügungen oder Löschungen an beiden Enden oder in der Mitte benötigen.
Wenn Sie das Verschieben von Elementen wie in List<T> vermeiden möchten.
LinkedList<T> für reine Anhängeszenarien verwendet werden kann, im Vergleich zu List<T> oder anderen modernen Datenstrukturen jedoch im Allgemeinen nicht die effizienteste Wahl für die Aufzählung oder Speichernutzung ist.
