tries
1.0.0
คลาสนี้เป็นพื้นฐานในการสร้างคอนเทนเนอร์ที่ใช้ Trie
ในรูปแบบพื้นฐานคลาส TTRIE สามารถใช้ในการจัดเก็บองค์ประกอบข้อมูลที่ใช้ 16, 32 และ 64 บิต
โครงสร้างให้การใช้งาน Trie เชิงลึกคงที่ซึ่งจะทำให้เกิดเวลาเท่ากันในการค้นหาลบและเพิ่มโหนด
ลำดับของโครงสร้างคือ o (d) โดยที่ d คือความลึกของ Trie ซึ่งขึ้นอยู่กับว่าสร้างค่า 16, 32 หรือ 64 บิต สำหรับ 16 บิต d = 4 สำหรับ 32 บิต d = 8 และ 64 บิต d = 16
เพื่อให้ขนาดโหนดมีขนาดเล็กเพียง 16 สาขาต่อโหนดจะถูกใช้และสถานะตัวบ่งชี้และดัชนีตัวชี้ภายในจะถูกเข้ารหัสในคำ 16 บิตและในจำนวนเต็ม 64 บิต
พอยน์เตอร์ไปยังสาขาได้รับการจัดการแบบไดนามิกดังนั้นจะมีการจัดสรรตัวชี้ลงในอาร์เรย์พอยน์เตอร์เมื่อจำเป็นต้องเพิ่มสาขาใหม่ซึ่งจะช่วยลดการสูญเสียของพอยน์เตอร์ที่จัดสรรไว้ล่วงหน้าไปยังสาขาระดับล่าง มันจะช้าลง
Leafs ได้รับการจัดสรรในสถานที่แทนที่จะเป็นโหนดแต่ละโหนดที่ชี้ไปที่โหนดสาขาสุดท้าย
ในที่สุดโหนดใบไม้สามารถควบคุมได้แบบไดนามิกโดยคลาสที่ได้จาก TTRIE ช่วยให้การใช้พจนานุกรมใช้พจนานุกรมโดยใช้ TTRIE เป็นฐานได้อย่างง่ายดาย
โดยรวมแล้วการทดสอบบางอย่างที่จัดเก็บหน่วยความจำที่จัดสรรโดย Lazarus (freepascal) จัดสรรใน Mac ให้ประสิทธิภาพการจัดเก็บประมาณ 40% ตามสัดส่วนกับขนาดของวัตถุที่เก็บไว้ซึ่งไม่เลวเลย
ชั้นเรียนยังมีวิธีแพ็คที่ใช้เพื่อเก็บรักษาไว้ในการตรวจสอบเมื่อมีการลบจำนวนมากออก
Tintegerhashtrie และ Tstringhashtrie ได้รับการจัดเตรียมเป็นลูกหลานของ Thashtrie Generic Class Thashtrie มีสองโหมดการทำงาน:
ตารางแฮชให้ประสิทธิภาพที่ดีขึ้นแน่นอน แต่ Hashtrie มีรอยเท้าหน่วยความจำที่มีประสิทธิภาพมากขึ้นเมื่อเก็บองค์ประกอบจำนวนน้อย
ทดสอบ TSTRINGHASHTRIE กับ TDICTIONARY ของ Delphi <> และ C# Dictionary <> คลาส
Tstringhashtrie เต้นทั้ง C# และ Delphi ความแตกต่างมีขนาดใหญ่ขึ้นเมื่อใช้ตารางแฮชสำหรับโหนดรูท
รอยเท้าหน่วยความจำโดยรวมสำหรับการโหลดขนาดใหญ่ก็ดีขึ้นตั้งแต่ 30% -40% ดีกว่า สำหรับองค์ประกอบจำนวนน้อยอย่างแน่นอนโดยใช้แฮชทรีบริสุทธิ์มากกว่าโหนดรูทตารางแฮชจะใช้หน่วยความจำน้อยลงอย่างมาก
การทดสอบที่รวบรวมใน Delphi 2007 ให้ผลลัพธ์ที่ดียิ่งขึ้นเนื่องจากสตริงไม่จำเป็นต้องได้รับการแปลงจาก UTF16 เป็น ANSI ก่อนที่จะแทรกลงในโครงสร้าง
TSTRINGHASHTRIE รองรับ Unicode ในรูปแบบ UTF8
