พจนานุกรมอัลกอริทึมและโครงสร้างข้อมูล (Dictionary of Algorithms and Data Structures)

• อัลกอริทึม, เทคนิคเชิงอัลกอริทึม, โครงสร้างข้อมูล, ปัญหาแบบคลาสสิก และนิยามที่เกี่ยวข้อง ถูกรวบรวมและจัดระเบียบไว้ในพจนานุกรมออนไลน์
• มีรายการ อัลกอริทึม ที่รวมฟังก์ชันที่ใช้กันทั่วไป เช่น Ackermann's function
• มีรายการ ปัญหาแบบคลาสสิก เช่น traveling salesman, Byzantine generals
• บางรายการมีลิงก์ไปยัง implementation และข้อมูลเพิ่มเติม พร้อมจัดทำดัชนีตามหมวด area และ type
• มุ่งเน้นที่ อัลกอริทึมและโครงสร้างข้อมูล "ทั่วไป(general)" โดยไม่นับรวมสาขาเฉพาะอย่าง business data processing, AI, graphics

---

ภาพรวมเว็บไซต์และหน่วยงานผู้ดูแล

• โฮสต์โดย Software and Systems Division ภายใต้ Information Technology Laboratory ของ NIST
• การพัฒนาพจนานุกรมเริ่มต้นในปี 1998 ภายใต้การบรรณาธิการของ Paul E. Black
• อยู่ในรูปแบบพจนานุกรมที่ครอบคลุม อัลกอริทึม, เทคนิคเชิงอัลกอริทึม, โครงสร้างข้อมูล, ปัญหาแบบคลาสสิก และนิยามที่เกี่ยวข้อง

โครงสร้างของรายการที่บรรจุ

• รายการ อัลกอริทึม มีฟังก์ชันที่ใช้กันทั่วไป เช่น Ackermann's function
• รายการปัญหาประกอบด้วย traveling salesman, Byzantine generals
• บางรายการมีลิงก์ไปยัง implementation และข้อมูลเพิ่มเติม
• หน้าดัชนีแสดงรายการตาม area และ type
• two-level index มีขนาดดาวน์โหลดรวมเพียง 1/20 ของหน้านี้

แนวทางการใช้งาน

• ห้ามใช้เพื่อการทุจริตหรือโกง (cheat) และมีคำแนะนำให้ครูติดต่อเข้ามาหากต้องการความช่วยเหลือ
• ข้อเสนอแนะ การแก้ไข และความคิดเห็น ให้ติดต่อ Paul Black

ขอบเขตที่ไม่ครอบคลุม

• ปัจจุบันยังไม่รวมอัลกอริทึมเฉพาะทางในสาขาต่อไปนี้
  • business data processing, communications, operating systems หรือ distributed algorithms
  • programming languages, AI, graphics, numerical analysis
• จำกัดขอบเขตเพราะแม้เฉพาะ อัลกอริทึมและโครงสร้างข้อมูล "ทั่วไป(general)" ก็ครอบคลุมได้ยากเพียงพออยู่แล้ว

ดัชนีและหมายเหตุอ้างอิง

• คำที่มีตัวแปรนำหน้า เช่น n-way, m-dimensional, p-branching จะถูกจัดไว้ใต้หัวข้อ k-
• สามารถดูรายการที่เป็นประโยชน์ได้จาก A Glossary of Computer Oriented Abbreviations and Acronyms

[GN⁺]

ความคิดเห็นจาก Hacker News

• บทความเก่าที่เกี่ยวข้อง:
  Dictionary of Algorithms and Data Structures (1998) - https://news.ycombinator.com/item?id=12758176 - ตุลาคม 2016 (18 ความคิดเห็น)
  Dictionary of Algorithms and Data Structures - https://news.ycombinator.com/item?id=8905348 - มกราคม 2015 (4 ความคิดเห็น)
  Dictionary of Algorithms and Data Structures - https://news.ycombinator.com/item?id=5525893 - เมษายน 2013 (15 ความคิดเห็น)
  Dictionary of Algorithms and Data Structures - https://news.ycombinator.com/item?id=2496539 - เมษายน 2011 (16 ความคิดเห็น)
  Dictionary of Algorithms and Data Structures - https://news.ycombinator.com/item?id=2351074 - มีนาคม 2011 (1 ความคิดเห็น)

• อยากจะชอบแหล่งข้อมูลนี้นะ แต่ในบรรดาสิ่งที่ผมรู้จัก มันไม่มี Fenwick tree กับ อัลกอริทึม/โครงสร้างข้อมูล union-find
  ที่ที่ผมเห็น Fenwick tree ครั้งแรกคือที่นี่: https://www.youtube.com/watch?v=uSFzHCZ4E-8&t=479s
  ส่วน union-find ผมน่าจะเห็นจากที่นี่: https://www.youtube.com/watch?v=PGZ64ob440I
  แต่เท่าที่จำได้ มันเป็น implementation แบบ dictionary/hashmap ไม่ใช่อาร์เรย์ขนาดคงที่

  • ดูเหมือนจะขาดไปค่อนข้างเยอะเลย ผมนึกว่า Fenwick อย่างน้อยน่าจะมีในชื่ออื่น แต่ก็ไม่เห็น และการไม่มี union-find ยิ่งแปลกกว่า มันเป็นโครงสร้างข้อมูลที่ยอดเยี่ยมและมีประโยชน์มาก จนผมนึกชื่ออื่นที่มันอาจถูกซ่อนไว้ไม่ออก
    สิ่งที่นึกออกทันทีแล้วหาไม่เจอคือ sqrt decomposition, heavy-light decomposition และ range minimum query (Range Minimum Query) โดยรวม ส่วนตัวแล้วผมถือว่า range minimum query เป็นหนึ่งในโจทย์ทั่วไปที่ชอบที่สุด และในฐานะชุดเทคนิคที่ควรใช้เวลาศึกษาอย่างจริงจัง ผมว่ามันน่าสนใจกว่าการเรียงลำดับมาก
    โครงสร้างข้อมูล union-find มักถูกแสดงด้วยอาร์เรย์ขนาดคงที่ เพราะแบบนั้นทำให้การวิเคราะห์อัลกอริทึมน่าสนใจขึ้น ถ้าต้นทุนการค้นหาเกิน O(1) ส่วนที่น่าสนใจในการวิเคราะห์ก็จะถูกกลบไป แน่นอนว่าโครงสร้างข้อมูลเองทำงานได้ดีไม่ว่าจะใช้วิธีไหน
  • มันเป็นชุดรวบรวมที่มีขอบเขตจำกัด ดังนั้นแทบทุกอย่างย่อมต้องขาดไปอยู่แล้ว ไม่มีทั้ง soft heap หรือ finger tree และโครงสร้างข้อมูลแบบ purely functional ที่ Okasaki กล่าวถึงก็ขาดไปอีกมาก

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

  • https://www.redblobgames.com/ เป็นแหล่งข้อมูลที่ดีมาก ให้บริบทเยอะโดยไม่หลีกเลี่ยงรายละเอียดทางเทคนิค
  • ผมเคยเขียนในแนวคล้ายกันไว้ ไม่ใช่เรื่องการประยุกต์ใช้โดยตรงนัก แต่เป็นคู่มือ/decision tree สำหรับเลือกว่าจะใช้ โครงสร้างข้อมูลหรือแนวทางอัลกอริทึม แบบใดกับโจทย์แบบไหน จากสิ่งที่เรียนรู้ระหว่างทำชุดโจทย์ Blind 75
    ผมยังไม่ใช่ผู้เชี่ยวชาญ จึงไม่ใช่แหล่งข้อมูลที่มีอำนาจอ้างอิง แต่ก็น่าจะน่าสนใจ: https://sebinsua.com/algorithmic-bathwater#what-kind-of-prob...
  • จากประสบการณ์ของผม ในชั้นเรียนก็ทำแบบนั้นอยู่แล้ว แก่นคือ ความซับซ้อนด้านเวลา·พื้นที่ ของฟังก์ชันที่กำหนดและการวิเคราะห์
  • ผมจำได้ว่า Skiena เคยบรรยายหัวข้อนี้ได้ดี
  • ถ้ารู้บริบทและประวัติ ก็ทำให้น่าสนใจขึ้นอย่างชัดเจน และโดยปกติก็ช่วยในการเรียนรู้ด้วย

• รายการหนึ่งที่สะดุดตา: Marlena
  https://xlinux.nist.gov/dads/HTML/marlena.html
  มีใครรู้ไหมว่ามันหมายถึงอะไร?

  • น่าจะมีคนที่รักภรรยามาก ๆ ใส่ไว้
    รายการนี้ก็อ้างถึงชื่อนั้นด้วย: https://xlinux.nist.gov/dads/HTML/antisymmetric.html

• ผมไม่แน่ใจว่ารายการอัลกอริทึมที่เรียงตามตัวอักษรเป็นจุดเริ่มต้นที่ดีสำหรับผู้เรียนหรือไม่
  สำหรับคนที่เพิ่งเริ่ม หรือคนที่อยากเชี่ยวชาญหัวข้อนี้จริง ๆ ผมว่าหนังสือคลาสสิกเล่มนี้คือมาตรฐาน[1]
  ถ้าเป้าหมายคือเติบโตเป็นนักพัฒนาและผ่าน coding interview ของ FAANG นี่อาจเป็นคานงัดที่ทรงพลังที่สุดก็ได้
  [1] https://books.google.com/books/about/Introduction_To_Algorit...

  • มีโอกาสสูงว่าไม่ใช่จุดเริ่มต้น แต่ในฐานะ เอกสารอ้างอิง นั้นยอดเยี่ยม

• ผมสงสัยว่าควรทำ reverse search กับรายการนี้อย่างไร
  เช่น บางครั้งอธิบายคร่าว ๆ ได้ว่าอัลกอริทึมหนึ่งทำงานอย่างไร แต่ไม่รู้ชื่อ และอยากรู้ว่ามีอยู่ในรายการนี้ไหม สมัยนี้อาจเขียนเป็น pseudocode แล้วส่งให้ ChatGPT ถามชื่อได้ แต่ถ้าเป็นวิธีอื่นก็ไม่ค่อยแน่ใจ

  • ลองไปถามใน Discord ก็น่าจะมีคนบอกได้

• ถ้ารับ pull request ได้ก็คงดี รายการพื้นฐานอย่าง acceleration structure ยังขาดอยู่

• เป็นแหล่งข้อมูลที่เจ๋งจริง ๆ หวังว่าจะรอดผ่านอะไรอย่างการตัดงบประมาณไปได้ และควร เก็บถาวร ไว้