AppendOnly
1.0.0
รายการต่อท้าย C # ความเร็วสูงที่ไม่เปลี่ยนรูปเท่านั้น (อัปเดต:23 ก.ย. 67; ไม่แนะนำให้ใช้ ดูหมายเหตุด้านล่างสำหรับเหตุผลและทางเลือกอื่นๆ)
dotnet เพิ่มแพ็คเกจผนวกเท่านั้น
ประการแรก คอลเลกชันที่ไม่เปลี่ยนรูปที่มีอยู่มีช่วงเวลาที่ยากลำบากมาก ทำให้คุณสามารถเพิ่ม ลบ และอัปเดตที่ส่งคืนคอลเลกชันใหม่ได้ พวกเขาต้องคัดลอกสิ่งต่าง ๆ มากมาย หากคุณเพียงต่อท้าย LinkedList จะเป็นเพื่อนของคุณ และอาจดูเหมือน "คัดลอก" ได้ทันที
ประการที่สอง ไลบรารีที่ไม่เปลี่ยนรูปที่มีอยู่มีความซับซ้อนและใช้งานยาก พวกเขาต้องการคลาสของผู้สร้างและความเข้าใจกลไกที่แท้จริง ไม่เช่นนั้นคุณจะประสบปัญหาประสิทธิภาพการทำงานที่แย่มาก
สุดท้ายนี้: คลาสนี้ปลอดภัยอย่างยิ่งหากใช้ในลูปที่แน่นมาก แน่นที่สุดเท่าที่คุณจะทำได้
AppendOnly ใช้ A linkedList ภายใน และไม่เคยคัดลอกรายการคอลเลกชันเมื่อสร้างสำเนาที่ "ไม่เปลี่ยนรูป" ใหม่ เพียงส่งคืนคลาสคอลเลกชันใหม่ที่ใช้ linkedList ภายในที่ "ไม่แน่นอน" ร่วมกัน แต่ไม่ได้เปิดเผยวิธีการใด ๆ ในการกลายพันธุ์มัน เปิดเผยเฉพาะ interator ที่วนซ้ำผ่านรายการแรก (n) ในคอลเลกชัน
ดังนั้นเมื่อคอลเลกชันมีขนาดใหญ่ขึ้น อินสแตนซ์รุ่นก่อนหน้า (เก่ากว่า) ของคลาสคอลเลกชันจะไม่เห็นรายการใหม่ (เปิดเผยผ่านการแจงนับ) ที่ต่อท้ายรายการ หลังจากเพิ่ม "ธุรกรรม" ใหม่ 1,000 รายการลงในการผนวกธุรกรรมคอลเลกชันเท่านั้น คุณจะมี (ถ้าคุณเก็บการอ้างอิงไปยังคอลเลกชันที่สร้างขึ้นใหม่แต่ละรายการ) 1,000 พอยน์เตอร์ไปยังคอลเลกชันแต่ละรายการที่มี 1, 2, 3, 4 รายการ ฯลฯ แต่มีค่าใกล้เคียงกับศูนย์เพิ่มเติม ค่าใช้จ่ายของหน่วยความจำ
หากใช้ไลบรารีที่ไม่เปลี่ยนรูปแบบอื่นๆ กับผู้สร้าง ไลบรารีส่วนใหญ่จะให้อ็อบเจ็กต์อย่างน้อย 500,000 อินสแตนซ์แก่คุณ
ฉันอาจจะผิด มันเป็นจุดเริ่มต้น โปรดแจ้งให้เราทราบหากคุณใช้สิ่งนี้ ฉันจะสร้างคอลเลกชันเพิ่มเติมตามบรรทัดที่คล้ายกัน
var moves = new AppendOnlyList<Moves>();var new_moves = new AppendOnlyList<Moves>();Debug.Assert(moves.Length == 0);// เพิ่ม 10 ท่าสุ่มสำหรับ(int i=0; i<10 ; i++) new_moves = new_moves.Add(randomMove());// การเคลื่อนไหวดั้งเดิมยังไม่มีรายการแม้ว่า new_list จะเพิ่มรายการลงใน List.Debug.Assert(moves.Length == 0);// new_list มี 10 รายการใน collectionDebug.Assert(new_moves.Length == 10);// รายการนี้ปลอดภัยที่จะวนซ้ำหลายครั้งและเป็น threadsafe// โค้ดด้านล่างแสดงการวนซ้ำในรายการทั้งหมดสิบครั้ง ซึ่งเป็นสิ่งที่คุณปกติจะทำกับ// นับได้หากคุณแคชไว้ เช่น สร้างไฟล์ในเครื่อง copy.// ฉันรู้ว่านี่ดูเหมือนจะไม่ได้ทำอะไรมาก แต่นี่สำคัญมาก // นอกจากนี้ มันปลอดภัยที่จะทำเช่นนี้ ในขณะที่เธรดอื่นๆ กำลังยุ่งอยู่กับการเพิ่มคอลเลกชันพื้นฐานเดียวกัน // สิ่งที่ใหญ่โต NO NO ในโลกของเธรด ที่นี่ปลอดภัยโดยสิ้นเชิงfor(int i = 0; i<10; i++){foreach(var move in new_moves.Items) await DoSomethingFunkyAsync(move);} ในโค้ดด้านบน new_moves และ moves ดั้งเดิมมีรายการลิงก์ที่เหมือนกัน เมื่อมีการสร้างสำเนาใหม่ของ AppendOnlyList จะไม่มีการสร้างโคลนใหม่ มีเพียงชี้ไปที่ส่วนหัวของรายการและความยาวยังคงอยู่
นี่เป็นการทำงานที่รวดเร็วมาก เนื่องจากไม่มีการคัดลอกใดๆ ดังนั้นจึงเร็วกว่าคอลเลกชันอื่นๆ ที่ไม่เปลี่ยนรูปแบบที่สร้างสำเนา
และปลอดภัยสำหรับเธรดที่จะวนซ้ำคอลเลกชันในขณะที่กำลังแจกแจงจากเธรดอื่น! บูม! ... หรือเจาะจงกว่านั้นคือ "ไม่บูม!"
นี่คือเวอร์ชัน 0.1.3 ซึ่งหมายความว่ายังไม่พร้อมสำหรับการใช้งานจริง นี่เป็นการพิสูจน์แนวคิด และฉันจำเป็นต้องเขียนการทดสอบเธรดเพื่อพิสูจน์ข้อกล่าวอ้างข้างต้น จากนั้นขอให้เพื่อนๆ ของฉันตรวจสอบและแจ้งให้เราทราบ
ฉันยังต้องการเปรียบเทียบความเร็วระหว่างคอลเลกชันนี้กับคอลเลกชันอื่นๆ ตลอดจนการเปรียบเทียบแบบเคียงข้างกัน
ถ้าคุณชอบแพ็คเกจนี้ ลองดูการใช้งานจริงซึ่งมี 2 คลาส AppendOnlyList และ LinkedListExtensions และพวกมันมีขนาดเล็ก
แจ้งให้เราทราบว่าคุณคิดอย่างไร?
:D
คำถามใด ๆ โปรดติดต่อฉันได้ที่
Alan Hemmings, twitter : @snowcode LinkedIn : https://www.linkedin.com/in/goblinfactory www : https://goblinfactory.co.uk
...และไม่ได้ใช้มันมากนักและก็ลืมมันไป สิ่งต่างๆ (C#) มีการพัฒนาไปมากตั้งแต่ฉันเขียนบทความนี้ และถึงแม้มีการเปลี่ยนแปลงมากมายใน C# แต่ก็ไม่มีการเปลี่ยนแปลงใดที่ทำให้สิ่งต่าง ๆ ง่ายขึ้นมากนัก น่าเสียดายที่ฉันคิดว่าความคิดของฉันข้างต้นว่าเมื่อใดควรใช้แพ็คเกจนี้ เนื่องจากมีการเปลี่ยนแปลงภาษาใหม่ อาจเป็นขยะและอาจ...ค่อนข้างผิดพลาด การทดสอบมีความจำเป็นอย่างยิ่งก่อนที่จะดำเนินการใดๆ เพิ่มเติม ต่อไปนี้เป็นหมายเหตุบางส่วนจากการแชทสั้นๆ กับ AI C# Architect เพื่อแนะนำให้มีการปรับปรุงโปรเจ็กต์นี้ TBH ฉันคิดว่าโครงการนี้อาจยังคงได้รับการรับประกัน แต่อาจเป็นตัวห่อหุ้ม 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 pool = ArrayPool<int>.Shared;int[] array = pool.Rent(1,000); // ขออาร์เรย์จากพูล// ผนวกและจัดการข้อมูลของคุณที่ herepool.Return(array); //กลับลงสระน้ำเมื่อเสร็จแล้ว
ValueListBuilder<T> (จาก System.Buffers)
มอบวิธีที่มีประสิทธิภาพในการสร้างคอลเลกชันในรูปแบบการจัดสรรแบบสแต็ก
มีประโยชน์อย่างยิ่งเมื่อคุณรู้ว่าขนาดข้อมูลมีขอบเขต และต้องการประสิทธิภาพสูงโดยไม่ต้องมีการจัดสรรฮีป
ช่วง <int> InitialSpan = stackalloc int [16]; var valueListBuilder = ใหม่ ValueListBuilder<int>(initialSpan);valueListBuilder.Append(1);valueListBuilder.Append(2);ReadOnlySpan<int> span = valueListBuilder.AsSpan();
Sequence<T> จาก System.IO.Pipelines
เหมาะสำหรับการจัดการลำดับข้อมูลอย่างมีประสิทธิภาพในลักษณะผนวกเท่านั้น
เหมาะสำหรับสถานการณ์ที่ต้องการการดำเนินการ I/O ที่มีประสิทธิภาพสูงและการสตรีมข้อมูล
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>
ความไม่มีประสิทธิภาพของแคช : โหนด LinkedList<T> จะกระจัดกระจายไปทั่วฮีป ซึ่งต่างจากอาร์เรย์หรือ List<T> ที่ถูกจัดเก็บไว้ในหน่วยความจำที่อยู่ติดกัน ซึ่งทำให้เป็นมิตรกับแคชน้อยลง ส่งผลให้การวนซ้ำและเวลาในการเข้าถึงช้าลง
ประสิทธิภาพการแจงนับ : แม้ว่า LinkedList<T> จะมีประสิทธิภาพสำหรับการดำเนินการผนวก ( O(1) สำหรับการเพิ่มที่ส่วนท้าย) แต่ประสิทธิภาพการแจงนับมักจะช้ากว่าอาร์เรย์หรือรายการเนื่องจากไม่มีข้อได้เปรียบในแคช
LinkedList<T> :เมื่อคุณต้องการแทรกหรือลบบ่อยๆ ที่ปลายทั้งสองข้างหรือตรงกลาง
หากคุณต้องการหลีกเลี่ยงการขยับองค์ประกอบเช่นใน List<T>
LinkedList<T> สามารถใช้สำหรับสถานการณ์แบบผนวกเท่านั้น แต่โดยทั่วไปจะไม่ใช่ตัวเลือกที่มีประสิทธิภาพที่สุดสำหรับการแจงนับหรือการใช้หน่วยความจำ เมื่อเปรียบเทียบกับ List<T> หรือโครงสร้างข้อมูลสมัยใหม่อื่นๆ
