B-Tree ใน Factorio

 (razberry.substack.com)
4 คะแนน โดย GN⁺ 2023-11-17 | 1 ความคิดเห็น | แชร์ทาง WhatsApp

เรียนรู้เกี่ยวกับ B-Tree

  • ต้นไม้ค้นหาแบบทวิภาค (Binary Search Trees, BSTs): แต่ละโหนดมีคีย์ โดยโหนดด้านซ้ายจะมีค่าคีย์ที่ต่ำกว่า และโหนดด้านขวาจะมีค่าคีย์ที่สูงกว่า

  • BST ทำงานได้ก็ต่อเมื่อสามารถจัดเรียงคีย์ได้เท่านั้น และหากมีการเพิ่มค่าไปทางด้านเดียวอย่างต่อเนื่อง สมดุลจะเสียและประสิทธิภาพจะลดลง

  • BST ที่เสียสมดุลสามารถแก้ไขได้ด้วยการหมุนแกน (pivoting) แต่ไม่เหมาะกับพื้นที่จัดเก็บบนดิสก์ (ต้องปรับสมดุลใหม่บ่อย และโหนดที่อยู่ติดกันอาจถูกเก็บไว้คนละเพจ)

  • B-Tree: ประกอบด้วยโหนดที่มีคีย์และพอยน์เตอร์มากกว่าต้นไม้แบบทวิภาค

  • แต่ละโหนดมีหลายคีย์ และมีหลายพอยน์เตอร์ตามแต่ละคีย์ (เช่น โหนดที่มีคีย์ 17 และ 24 จะมีพอยน์เตอร์ไปยังโหนดที่มีคีย์น้อยกว่า 17, โหนดที่มีคีย์อยู่ระหว่าง 17 กับ 24, และโหนดที่มีคีย์มากกว่า 24)

การนำ B-Tree ไปใช้งานใน Factorio

  • การทำต้นไม้ค้นหาแบบทวิภาคอย่างง่ายใน Factorio (เกมสร้างโรงงาน): แต่ละโหนดประกอบด้วยกล่องไม้ (คีย์) และสองเส้นทาง (พอยน์เตอร์)
  • เนื่องจากไม่มีวิธีเปรียบเทียบมูลค่าของวัสดุได้โดยตรง จึงกำหนดลำดับขึ้นมาเองและใช้แขนกลกรองในการเปรียบเทียบ
  • การทำ B-Tree มีความซับซ้อนมากกว่า: แต่ละโหนดมีสามคีย์และพอยน์เตอร์ไปยังโหนดลูกสี่ตัว
  • B-Tree สามารถเก็บข้อมูลได้มากกว่า และแทนที่จะจัดเรียงไอเท็มด้วยมือ จึงปล่อยให้ต้นไม้ว่างไว้ก่อนจนกว่าจะหาวิธีแทนค่าได้ดีกว่านี้ในภายหลัง

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

  • ประเด็นสำคัญที่สุดของบทความนี้คือการทำความเข้าใจแนวคิดของ B-Tree และแนวทางที่สร้างสรรค์ในการลองนำไปสร้างในเกม Factorio
  • สิ่งที่น่าสนใจสำหรับผู้อ่านคือแนวทางนี้เปิดโอกาสให้เข้าใจโครงสร้างข้อมูลที่ซับซ้อนในวิทยาการคอมพิวเตอร์ได้อย่างเป็นภาพและเป็นธรรมชาติผ่านเกม
  • วิธีการเช่นนี้ทำให้การเรียนรู้สนุกและน่าดึงดูดยิ่งขึ้น และนำเสนอแนวทางใหม่ในการสำรวจแนวคิดพื้นฐานของวิศวกรรมซอฟต์แวร์ผ่านสื่อที่ไม่ดั้งเดิมอย่างเกม

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

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

 
GN⁺ 2023-11-17
ความคิดเห็นจาก Hacker News
  • การออกแบบของเกม Factorio ไม่ได้สะท้อนทฤษฎีวิทยาการคอมพิวเตอร์อย่างสมบูรณ์แบบ และให้ความสำคัญกับการสนุกกับเกมมากกว่าการเล่นที่ปรับให้เหมาะที่สุดในเชิงทฤษฎี
  • ใน Factorio ต้นไม้ทวิภาคแบบปรับสมดุลตัวเอง (2-3 tree, red-black tree, B-tree) ไม่สามารถจัดโครงสร้างใหม่ได้ จึงขาดความสามารถสำคัญที่สุดคือการปรับสมดุลตัวเอง
  • ในมุมมองด้านการเพิ่มประสิทธิภาพ inserter ใน Factorio ช้ากว่าสายพาน โดย inserter 4 ตัวจัดการได้ 12 ไอเท็มต่อวินาทีต่อสายพานหนึ่งเส้น ขณะที่ blue belt จัดการได้ 45 ไอเท็มต่อวินาที ดังนั้นหากต้องการออกแบบที่เหมาะที่สุดโดยใช้สายพานล้วน แนะนำให้ใช้ splitter
  • การผสานวิทยาการคอมพิวเตอร์เข้ากับ splitter ครอบคลุมแนวคิดของ Benes network (เครือข่ายที่ประกอบด้วย crossbar แบบ 2 อินพุต 2 เอาต์พุตเท่านั้น) และจำเป็นต้องศึกษาเรื่องนี้เพื่อออกแบบโรงงานอย่างมีประสิทธิภาพ
  • การออกแบบ mixed belt มีความสำคัญใน Factorio และการอ่านหนังสือเกี่ยวกับโครงสร้างภายในของฐานข้อมูลอาจช่วยได้
  • ต้นไม้ค้นหาแบบทวิภาค (BST) ไม่เหมาะกับสตอเรจแบบดิสก์ และการค้นหาโหนดใน B-tree เร็วกว่าการไล่ตามพอยน์เตอร์ของต้นไม้ทวิภาค แม้ความซับซ้อนของการติดตั้งใช้งานจะเพิ่มขึ้น แต่เว้นแต่จะใช้ภาษา C ก็แทบไม่ต้องลงมือสร้าง tree-based map เอง
  • มีการชี้ว่าการไม่ใช้ตัวพิมพ์ใหญ่สามารถรบกวนการอ่านบทความได้
  • การแชร์คอนเทนต์เกี่ยวกับ Factorio ทำให้เกิดความอยากกลับไปทุ่มเวลาเล่นเกมอีกหลายร้อยชั่วโมง
  • งานทั้งหมดสามารถทำได้ด้วย splitter เพียงอย่างเดียว โดยไม่จำเป็นต้องใช้ chest และ filter inserter
  • มีการชี้ว่าคาดว่าจะมีการใช้วงจรของ Factorio ในการนำไปใช้งาน แต่กลับไม่เป็นเช่นนั้น