การตามหารูปแบบข้อมูลที่หายไป

ตามหารูปแบบข้อมูลที่ขาดหายไป

• กราฟคือชุดของโหนดที่เชื่อมต่อกันด้วยลูกศร (เส้นเชื่อม)
• โหนดและเส้นเชื่อมสามารถเก็บข้อมูลได้
• ในวิศวกรรมซอฟต์แวร์ กราฟปรากฏอยู่ในหลายรูปแบบ เช่น การพึ่งพากันของแพ็กเกจ ลิงก์บนอินเทอร์เน็ต พื้นที่สถานะของซอฟต์แวร์ ฐานข้อมูลเชิงสัมพันธ์ linked list, binary tree, hash table เป็นต้น
• ในตรรกะทางธุรกิจก็ใช้กราฟกับสิ่งต่าง ๆ เช่น การอ้างอิงคำพูด เครือข่ายการจราจร และโซเชียลเน็ตเวิร์ก
• หากทำงานพัฒนาซอฟต์แวร์มานานพอ มีโอกาสสูงที่จะเจอกราฟได้ทุกที่

ข้อกังวลเกี่ยวกับการใช้กราฟ

• กราฟมีประโยชน์ แต่การใช้กราฟในโค้ดจริงนั้นเป็นภาระไม่น้อย
• ภาษากระแสหลักส่วนใหญ่ไม่ได้รองรับกราฟเป็นชนิดข้อมูลในตัว และแม้แต่ใน standard library ก็พบได้ไม่บ่อย รวมถึงไลบรารี third-party ที่แข็งแรงก็มีไม่มาก
• หลายครั้งจึงต้องลงมือสร้างกราฟด้วยตัวเอง
• มีช่องว่างระหว่างความถี่ที่วิศวกรซอฟต์แวร์ต้องใช้กราฟ กับระดับการรองรับในระบบนิเวศการเขียนโปรแกรม

ทำไมจึงไม่มี graph type

ตัวเลือกด้านการออกแบบมีมากเกินไป

• มีกราฟหลายประเภท เช่น กราฟมีทิศทางและไม่มีทิศทาง simple graph, multigraph, hypergraph, ubergraph เป็นต้น
• สำหรับแต่ละประเภท ยังต้องตัดสินใจอีกว่าจะกำหนด ID ให้โหนดและเส้นเชื่อมหรือไม่ รวมถึงจะเก็บข้อมูลแบบใด
• การสร้างไลบรารีกราฟที่สมบูรณ์แบบและรองรับทุกความเป็นไปได้ต้องใช้เวลามหาศาล
• ประสิทธิภาพของอัลกอริทึมกราฟมีความสำคัญมาก และกรณีเฉพาะทางก็สำคัญเช่นกัน
• อัลกอริทึมกราฟเป็นสิ่งที่สร้างให้ถูกต้องได้ยาก

ตัวเลือกด้านการสร้างมีมากเกินไป

• ต่อให้สมมติว่ารองรับเฉพาะกราฟมีทิศทางแบบง่าย ก็ยังมีหลายวิธีในการแทนกราฟภายในระบบ
• มีวิธีเก็บข้อมูลหลากหลาย เช่น edge list, adjacency list, adjacency matrix, ชุดของ struct เป็นต้น
• การดำเนินการกับกราฟแต่ละแบบให้คุณลักษณะด้านประสิทธิภาพต่างกันไปตามวิธีแทนข้อมูล
• ความโปร่งบางหรือความหนาแน่นของกราฟก็ทำให้วิธีแทนกราฟภายในที่เหมาะสมแตกต่างกัน
• การรองรับข้อมูลของโหนด ข้อมูลของเส้นเชื่อม รวมถึงโหนดและเส้นเชื่อมหลายประเภท ยิ่งทำให้ซับซ้อนขึ้น

ประสิทธิภาพสำคัญเกินไป

• อัลกอริทึมกราฟจำนวนมากเป็นปัญหาแบบ NP-complete หรือยากยิ่งกว่านั้น
• กราฟอาจกลายเป็นปัญหาขนาดใหญ่มาก และประสิทธิภาพจะแตกต่างกันมากตามรูปแบบการแทนข้อมูลและรายละเอียดการสร้างอัลกอริทึม
• จึงต้องการการควบคุมอย่างมากทั้งในด้านการแทนข้อมูลและตัวอัลกอริทึม

มุมมองที่เห็นพ้องกัน

• ความหลากหลายของประเภทกราฟ วิธีแทนข้อมูล อัลกอริทึม ความอ่อนไหวต่อประสิทธิภาพ และการรันอัลกอริทึมราคาแพงบนกราฟขนาดใหญ่ ล้วนเป็นเหตุผลที่การรองรับกราฟไม่แพร่หลาย
• สิ่งนี้อธิบายได้ว่าทำไมภาษาโปรแกรมจึงไม่รองรับกราฟใน standard library
• และอธิบายได้ว่าทำไมโปรแกรมเมอร์จึงหลีกเลี่ยงไลบรารีกราฟจาก third-party
• เพราะการใช้กราฟเป็นเรื่องยาก จึงอธิบายได้ว่าทำไมคนส่วนใหญ่ไม่อยากคิดแบบกราฟหากไม่ใช่กรณีสุดโต่งจริง ๆ

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

• บทความนี้ให้มุมมองว่าเหตุใดกราฟจึงยังไม่กลายเป็นชนิดข้อมูลพื้นฐานในภาษาโปรแกรมและไลบรารี
• graph theory เป็นสาขาสำคัญของวิทยาการคอมพิวเตอร์ และถูกประยุกต์ใช้ในหลายด้าน เช่น อัลกอริทึม การวิเคราะห์เครือข่าย และฐานข้อมูล
• หากต้องการใช้กราฟอย่างมีประสิทธิภาพ การปรับแต่งประสิทธิภาพและการเลือกโครงสร้างข้อมูลที่เหมาะสมเป็นสิ่งสำคัญ
• ไลบรารี third-party ที่ใช้ได้ เช่น NetworkX, Boost Graph Library และ Graph-tool ซึ่งช่วยแก้ปัญหากราฟได้หลากหลายรูปแบบ
• เมื่อใช้กราฟ การเลือกประเภทกราฟและอัลกอริทึมให้สอดคล้องกับลักษณะของปัญหาเป็นสิ่งสำคัญ และเชื่อมโยงโดยตรงกับประสิทธิภาพของระบบ

[GN⁺]

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

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

  • จากประสบการณ์นี้ พวกเขาจึงเจอกับ 'second-system syndrome' ในแบบของตัวเอง
  • พวกเขาตัดสินใจว่าไลบรารีกราฟควรเป็นแบบโมดูลาร์, type-safe และมีประสิทธิภาพ ซึ่งอาจเป็นอีกรูปแบบหนึ่งของคำพูดที่ว่า "ดี, เร็ว, ถูก - เลือกได้แค่สอง"
  • ความเป็นโมดูลาร์หมายถึงการต้องการเขียนชุดไลบรารีอัลกอริทึมกราฟที่พัฒนาและคอมไพล์แยกกันได้
  • type-safe หมายถึงต้องการตรวจจับข้อผิดพลาดในการเขียนโปรแกรมได้ตอนคอมไพล์ หรืออย่างช้าที่สุดคือตอนลิงก์ ไม่ต้องการข้อผิดพลาดตอนรันไทม์
  • ประสิทธิภาพหมายถึงการเข้าถึงคุณสมบัติของกราฟควรถูกพอๆ กับการเข้าถึงฟิลด์ของโครงสร้าง C
  • จะถกเถียงกันได้ว่าเป้าหมายเหล่านี้คุ้มค่าหรือไม่ แต่นั่นคือสิ่งที่พวกเขาต้องการ พวกเขาคาดหวังว่าจะขอความช่วยเหลือได้ เพราะเหล่าผู้บุกเบิก C++ ที่มีชื่อเสียงอยู่ในแล็บของพวกเขา และจึงตัดสินใจให้โอกาส C++ อีกครั้ง
  • Gordon Woodhull อดีตเด็กฝึกงานเป็นโปรแกรมเมอร์ที่เก่งมาก และได้เขียนไลบรารีกราฟลักษณะนี้ขึ้นมาด้วย template C++ โดยเผยแพร่ผ่าน sourceforge ที่ https://www.dynagraph.org/
  • คนอื่นๆ ไม่แน่ใจว่าจะเข้าใจว่าโค้ดทำงานอย่างไรได้หรือไม่ จึงมีการรีวิวโค้ดร่วมกับผู้คิดค้น C++ ที่มีชื่อเสียง และพบว่าอาจก้าวข้ามหน้าผาแห่งความซับซ้อนไปแล้ว
  • นี่ไม่ใช่ความผิดของ Gordon และเขาก็ยังคงเดินหน้าต่อ พร้อมทั้งทำงานด้าน dynamic graph layout บน Microsoft OLE ได้สำเร็จ เมื่อมองย้อนกลับไป สิ่งนี้อาจเป็นโปรเจ็กต์ซานาดูของพวกเขาเอง
  • ระหว่างที่พวกเขาหมกมุ่นอยู่กับเรื่องนี้ ก็มีเครื่องมืออีกมากเกิดขึ้น เช่น Gephi (Java), NetworkX และ NetworKit (Python)
  • John Ellson เป็นวิศวกรซอฟต์แวร์ที่มีพรสวรรค์มาก ผู้เขียนส่วนหนึ่งของ Graphviz และเป็นคนที่ปลุกความพยายามหลักให้กลับมาอีกครั้ง

• หากคุณเขียนโค้ดบน .NET อยากแนะนำให้ลองใช้ไลบรารีกราฟ Arborescence ซึ่งมีขนาดเล็กและฟีเจอร์ไม่มากนัก

  • เชื่อว่าไลบรารีนี้แยก abstraction, algorithm และ data structure ออกจากกันได้ดี
  • ผู้ใช้สามารถใช้งาน edge ที่มี ID ของตัวเอง หรือใช้ implicit graph ที่คลี่ขยายแบบ on-the-fly ก็ได้
  • ใช้ได้ทั้งอินเทอร์เฟซของ adjacency (เพื่อนบ้านขาออก) และ incidence (edge ขาออก + head)
  • ไลบรารีไม่ได้บังคับชนิดของ edge แต่มีโครงสร้างคู่ tail-head พื้นฐานให้เป็นยูทิลิตี

• กราฟไม่ใช่ data structure หรือ data type แต่เป็น abstraction

  • โดยพื้นฐานแล้ว สิ่งที่จำเป็นในการนิยามกราฟมีเพียงเซตของ vertex และฟังก์ชันเพื่อนบ้านเท่านั้น
  • อย่างอื่นทั้งหมดเป็นข้อจำกัดเฉพาะกรณี
  • ถ้าพิจารณา hypergraph กราฟก็เป็นเพียงกรณีพิเศษเท่านั้น
  • ถ้ามองจากมุมฐานข้อมูล กราฟคือปัญหาของ query optimization และ indexing

• มีคนถามบ่อยมากว่าทำไมจึงไม่มี data type สำหรับกราฟที่ฝังมากับภาษาโปรแกรมมิง

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

• อุปสรรคหลักมีดังนี้:

  • สำหรับปัญหากราฟที่เรียบง่ายและขนาดเล็ก การเขียน adjacency list แบบ vector of vectors ก็ง่ายพออยู่แล้ว
  • สำหรับปัญหากราฟที่ซับซ้อนและขนาดมหาศาล ไม่มีทางได้ประสิทธิภาพนอกจากต้องปรับแต่ง implementation ของกราฟให้เหมาะกับปัญหาโดยเฉพาะ
  • ยังไม่ชัดเจนว่าการรองรับแบบใดจากตัวภาษาจะช่วยได้จริง

• บทความนี้ตอบคำถามได้เป็นส่วนใหญ่ว่าทำไมในภาษาโปรแกรมมิงจึงยังไม่รองรับ algorithm ของกราฟได้ดีกว่านี้

  • ถ้ามองการรองรับกราฟในภาพรวม จะเห็นคำถามที่กว้างกว่านั้น เช่น ทำไม OGM จึงไม่เป็นที่นิยมเท่า ORM และทำไม JSON จึงถูกใช้แพร่หลายกว่า RDF
  • สุดท้ายแล้ว ด้วยเหตุผลทางประวัติศาสตร์และความซับซ้อนของกราฟ มันจึงไม่ขยายตัวได้ดีนักในหมู่นักพัฒนา

• เครื่องมือสำหรับวาดกราฟก็น่าผิดหวังมากเช่นกัน

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

• บทความนี้ยอดเยี่ยมจริงๆ

  • สำหรับข้อสังเกตหลักที่ว่า "มีตัวเลือก implementation มากเกินไป" นั้น จริงๆ แล้วไม่ใช่แบบนั้น
  • ในทางปฏิบัติ ไลบรารีสามารถ implement การแทนกราฟที่เหมาะสมทั้งหมดได้
  • สามารถปรับแต่งอัลกอริทึมให้เข้ากับการแทนแบบต่างๆ และแปลงจากการแทนแบบหนึ่งไปสู่อีกแบบหนึ่งได้

• Electric Clojure ใช้ Clojure เอง (s-expression) เป็นไวยากรณ์สำหรับการสร้างกราฟ

  • DSL สำหรับการสร้างกราฟต้องสามารถแสดง scope, control flow และ abstraction ได้ ซึ่งโดยเนื้อแท้แล้วก็คือภาษาโปรแกรมมิงนั่นเอง

• ยังมี data type ที่มีประโยชน์อีกแบบหนึ่งคือ table (เช่น table ในฐานข้อมูล)

  • หากให้คอมไพเลอร์เป็นผู้เลือก implementation ของ data structure เอง ก็อาจเกิดความก้าวหน้าในภาษาโปรแกรมมิงได้
  • ใช้โครงสร้างเชิงนามธรรม (sequence, map, set, table, graph ฯลฯ) แล้วให้คอมไพเลอร์เลือก implementation ที่เป็นรูปธรรมตามโปรไฟล์ของโปรแกรม