Atree: อิมพลีเมนต์ Tree แบบไม่มีพอยน์เตอร์ที่เรียบง่ายและมีประสิทธิภาพ

 (github.com/tlack)
10 คะแนน โดย GN⁺ 2023-12-18 | 1 ความคิดเห็น | แชร์ทาง WhatsApp
  • Apter Trees ใน C++
  • Tree ที่แสดงโครงสร้างอย่างเรียบง่ายโดยใช้เพียงเวกเตอร์สองชุดคือ [ค่าของโหนด, ดัชนีของโหนดแม่)
  • Tree ส่วนใหญ่มักอิมพลีเมนต์แบบ binary tree โดยแต่ละโหนดจะมีค่าของตัวเองและพอยน์เตอร์ไปยังโหนดลูกซ้าย/ขวา
  • โครงสร้างข้อมูลแบบนี้มักต้องอิมพลีเมนต์ด้วย recursion และอาจช้าลงได้จากพฤติกรรมของแคชและการเรียก malloc() บ่อยครั้ง
  • แนวคิดว่าใครเป็นผู้ "ครอบครอง" tree node อาจซับซ้อนขึ้นในซอฟต์แวร์แบบหลายเลเยอร์
  • Apter tree เร็วกว่ามาก เข้าใจเหตุผลได้ง่ายกว่า และอิมพลีเมนต์ได้ง่ายกว่า

วิธีการทำงาน

  • อิมพลีเมนต์ด้วยอาร์เรย์สองชุดที่มีขนาดเท่ากัน
    • เวกเตอร์ (อาร์เรย์) ของข้อมูล d
    • เวกเตอร์ของดัชนีโหนดแม่ p โดยดัชนีของเวกเตอร์ d ถูกใช้เป็นคีย์ c
    • บ่อยครั้งคีย์/ดัชนี c จะเป็นชนิดจำนวนเต็ม
  • ถ้า Coco เป็นแม่ของ Molly และ Arca และ Arca มีลูกชื่อ Cricket โครงสร้างจะเป็นดังนี้
    tree.d = ["Coco", "Molly", "Arca","Cricket"]
    tree.p = [0,0,0,2]
  • โหนดที่มี parent เป็น 0 และมีคีย์เป็น 0 คือ root node (Apter tree อาจกำหนดให้ต้องมี root node เสมอ หรือใช้ -1 เพื่อหมายถึง "ไม่มีโหนดแม่" แต่ในที่นี้จะขอข้ามไป)
  • คอมพิวเตอร์จัดการเวกเตอร์ได้รวดเร็วมาก เร็วกว่าการคำนวณพอยน์เตอร์อย่างมาก ดังนั้นการเปรียบเทียบ Big-O notation ของอัลกอริทึมจึงแทบไม่มีความหมายในทางปฏิบัติ

ทำไมจึงสำคัญ

  • วิธีอิมพลีเมนต์นี้เป็นหนึ่งในแนวทางทำ tree ที่สง่างามที่สุดเท่าที่ผู้เขียนเคยเห็น
  • หากใช้ไลบรารีสำหรับการดำเนินการกับเวกเตอร์ที่เหมาะสม จะเข้าใจง่ายและตามหาบั๊กได้ง่าย
  • ด้วยความเรียบง่าย จึงนำไปปรับใช้กับกรณีการใช้งานอื่น ๆ ได้ง่าย
  • สามารถวนซ้ำค่าต่าง ๆ ได้อย่างรวดเร็วโดยไม่ต้องสนใจเวกเตอร์ดัชนีโหนดแม่ ซึ่งคล้ายกับ Deep Map ที่ได้มาแบบฟรี ๆ
  • เป็นมิตรกับ GPU และใช้งานได้ง่ายในสภาพแวดล้อมแบบ embedded
  • สามารถดูแลความปลอดภัยได้ง่ายโดยจำกัดไม่ให้ขนาดของเวกเตอร์โตเกินค่าที่กำหนด

ที่มา

  • ผู้เขียนกำลังพยายามหาว่าใครเป็นผู้คิดค้นเทคนิคนี้ และคาดว่าน่าจะมีชื่อเรียกอยู่แล้วตั้งแต่ยุคที่แนวคิดแบบ vector-oriented แพร่หลายในช่วงทศวรรษ 1960 และ 1970
  • ผู้เขียนเห็นคำอธิบายที่สมบูรณ์ครั้งแรกจาก Apter แต่แนวคิดนี้ก็มีการบันทึกไว้อย่างกว้างขวางใน K3 เช่นกัน
  • APL อิมพลีเมนต์ tree แบบดั้งเดิม แต่ใช้เทคนิคคล้ายกันกับ vector graph
  • ผู้ใช้ J ก็คุ้นเคยกับแนวคิดนี้เช่นกัน และมีคำอธิบายเกี่ยวกับการอิมพลีเมนต์ tree ในภาษา J บน Rosetta Code
  • John Earnest อธิบายการอิมพลีเมนต์ vector tree อย่างละเอียดกว่า รวมถึงแนวทางแบบ "offset index" และการจัดการรายการที่ถูกลบ
  • แนวทางที่ซับซ้อนกว่านั้นคือการติดตามความลึกของแต่ละรายการ

การอิมพลีเมนต์ tree แบบทั่วไปอื่น ๆ

  • มีทั้งการอิมพลีเมนต์ tree ของเคอร์เนล FreeBSD, tree ของ klib, tree class ของ Ruby และ declarative tree class ของ Python เป็นต้น
  • สิ่งเหล่านี้ไม่ได้ทำงานแบบเดียวกับ Apter tree และบางแบบก็มีขนาดใหญ่กว่ามากเพราะพยายามทำให้เป็นทั่วไป

สถานะของโค้ดนี้

  • เป็นความพยายามอิมพลีเมนต์สิ่งนี้เพื่อใช้เรียนรู้ C++17
  • ยังไม่พร้อมสำหรับการใช้งานจริง และผู้เขียนยังต้องเรียนรู้ C++ เพิ่มอีกมาก

ความเห็นของ GN⁺

  • Apter Trees ช่วยทำให้โครงสร้าง tree แบบเดิมที่ซับซ้อนเรียบง่ายลง และทำให้การจัดการข้อมูลทำได้รวดเร็วและมีประสิทธิภาพ
  • การอิมพลีเมนต์ tree บนพื้นฐานของเวกเตอร์ช่วยลด memory overhead และอาจเพิ่มประสิทธิภาพได้ผ่านการเข้าถึงแบบเชิงเส้น
  • บทความนี้ชวนให้เห็นแนวทางใหม่ที่น่าสนใจต่อการออกแบบโครงสร้างข้อมูลในงานวิศวกรรมซอฟต์แวร์

บทความที่เกี่ยวข้อง

1 ความคิดเห็น

 
GN⁺ 2023-12-18
ความคิดเห็นจาก Hacker News
  • ผู้ใช้คนหนึ่งบอกว่ารู้สึกประหลาดใจที่เห็นงานของตัวเองถูกลิงก์อยู่บน Hacker News เขาสนใจโครงสร้างข้อมูลแบบอาร์เรย์ที่มีน้ำหนักเบามานาน และพูดถึงรูปแบบการติดตั้งที่มักใช้กับ node tree สำหรับการสกินโมเดล 3D โดยเฉพาะ เขาอธิบายว่า หากจัดเรียงอาร์เรย์ให้ parent node มาก่อน child node การคำนวณ world transform ใหม่สำหรับทุก node ก็ทำได้ด้วยลูปง่าย ๆ
  • ผู้ใช้อีกคนหนึ่งตอบความเห็นที่ว่าการวนลูกโหนดในต้นไม้สไตล์นี้เป็น O(N) ว่า จริง ๆ แล้วสามารถทำให้ดีไซน์ของ atree ทั่วไปขึ้นได้ง่ายมากด้วยการเพิ่มพอยน์เตอร์ที่ชี้ไปยัง first child และ next sibling นอกจากนี้ยังแนะนำให้ปรับโครงสร้างข้อมูลเพื่อรองรับงานที่ต้องการ
  • ผู้ใช้คนหนึ่งยืนยันว่าการเก็บโหนดไว้ในอาร์เรย์และใช้อินเด็กซ์แทนพอยน์เตอร์เป็นสิ่งจำเป็นสำหรับการอิมพลีเมนต์อัลกอริทึมต้นไม้ โดยเฉพาะเมื่อจำเป็นต้องเข้าถึงลูกของโหนด เขาแนะนำว่าควรพิจารณาใช้โครงสร้างแยกกันสำหรับ internal node และ leaf node เพื่อประหยัดหน่วยความจำ
  • ผู้ใช้อีกคนหนึ่งบอกว่าค่อนข้างแปลกที่วิธีแทนต้นไม้ด้วย parent array ได้รับความสนใจมากบน Hacker News และมองว่านี่แสดงให้เห็นว่าการนำเสนอที่ดีสามารถพาไอเดียพื้นฐานไปได้ไกลแค่ไหน
  • ผู้ใช้คนหนึ่งชี้ว่าโปรเจ็กต์นี้ก็แค่แทนที่ system pointer ด้วย pointer ของตัวเอง
  • ผู้ใช้อีกคนหนึ่งเสนอว่า ถ้าต้องการลด malloc และเพิ่ม data locality ลองใช้การอิมพลีเมนต์ต้นไม้แบบดั้งเดิมที่ใช้ node pool
  • มีความเห็นหนึ่งแนะนำให้อ้างอิงคำอธิบายของ Aaron Hsu ที่ใช้ APL
  • ผู้ใช้คนหนึ่งเสนอให้เปลี่ยนโครงสร้างโดยแพ็กลูกทั้งหมดของโหนดไว้ด้วยกัน แบบนี้จะสามารถหาลิสต์ลูกทั้งหมดของโหนดได้ด้วย binary search และยังมีคุณสมบัติที่เป็นมิตรกับแคช
  • มีความเห็นเกี่ยวกับการเรียกอินเด็กซ์ในอาร์เรย์ว่าเป็น handle หรือ index-handle และบอกว่าวิธีแทนต้นไม้แบบนี้ชวนให้นึกถึงโครงสร้างข้อมูลคลาสสิกอย่าง heap และ disjoint set
  • สุดท้าย มีความเห็นอธิบายว่าอินเด็กซ์ของอาร์เรย์ก็อาจถือเป็น pointer ชนิดหนึ่งได้ และเหตุผลที่การอิมพลีเมนต์ต้นไม้แบบดั้งเดิมต้องใช้ malloc ก็เพราะความจำเป็นในการเพิ่มหรือลบโหนดแบบไดนามิก หากขนาดของต้นไม้มีขีดจำกัดและไม่ได้ลบบ่อย การอิมพลีเมนต์แบบอาร์เรย์ก็อาจเหมาะสม