อัลกอริทึมจัดเรียงหนังสือแบบใหม่ ให้ผลลัพธ์เกือบสมบูรณ์แบบ
(quantamagazine.org)- ปัญหาการจัดเรียงในห้องสมุด ไม่ได้จำกัดอยู่แค่การจัดชั้นหนังสือ แต่ยังเป็นตัวกำหนดต้นทุนของการจัดเก็บแบบลำดับในฮาร์ดไดรฟ์และฐานข้อมูล งานวิจัยใหม่ลดเวลาแทรกโดยเฉลี่ยลงได้ใกล้ขีดจำกัดทางทฤษฎีมาก
- อัลกอริทึมปี 1981 รับประกันเวลาแทรกโดยเฉลี่ยที่ ((log n)^2) ด้วยวิธีแบบ กำหนดแน่นอน (deterministic) และ ราบเรียบ (smooth) แต่ตลอดกว่า 40 ปีหลังจากนั้นก็ยังไม่มีขอบเขตบนที่ต่ำกว่านี้ออกมา
- งานวิจัยด้านขอบเขตล่างในเวลาต่อมาแสดงให้เห็นว่า อัลกอริทึมทั่วไปทำได้ดีที่สุดที่ (log n) ขณะที่ข้อจำกัดของอัลกอริทึมแบบราบเรียบและแบบกำหนดแน่นอนอยู่ที่ ((log n)^2) จึงจำเป็นต้องใช้ แนวทางแบบสุ่มและไม่ราบเรียบ
- ในปี 2022 Bender, Kuszmaul และคณะ ลดขอบเขตบนลงเหลือ ((log n)^{1.5}) ด้วยอัลกอริทึมสุ่มแบบ ไม่ขึ้นกับประวัติ (history independent) และงานวิจัยล่าสุดใช้ข้อมูลอดีตแบบจำกัดเพิ่มเติมจนทำได้ที่ ((log n)(log log n)^3)
- ช่องว่างที่เหลือคือพจน์ (log log n) และความก้าวหน้านี้อาจนำไปสู่การเพิ่มความเร็วให้แอปพลิเคชันอย่าง การจัดเก็บและประมวลผลกราฟแบบไดนามิก ที่อิงกับ list labeling
ปัญหาการจัดเรียงในห้องสมุดถามอะไร
- ปัญหาการจัดเรียงในห้องสมุด คือปัญหาการลดเวลาในการย้ายรายการให้เหลือน้อยที่สุดเมื่อแทรกรายการใหม่โดยยังคงลำดับที่เรียงไว้
- หากกองหนังสือไว้ชิดด้านใดด้านหนึ่ง เมื่อจะใส่หนังสือเล่มใหม่ตรงกลาง อาจต้องย้ายหนังสือจำนวนมากอีกครั้ง
- เมื่อเพิ่มหนังสือของ Isabel Allende อาจต้องย้ายหนังสือทั้งหมด
- ต่อมาเมื่อเพิ่มหนังสือของ Douglas Adams ก็อาจต้องทำงานแบบเดียวกันซ้ำ
- หากกระจายช่องว่างว่างไว้ทั่วชั้นหนังสืออย่างเหมาะสม จะลดต้นทุนการแทรกได้ แต่ประเด็นสำคัญคือควรเหลือพื้นที่ไว้ที่ไหนและมากเท่าใด
- ในเชิงรูปแบบมากขึ้น ปัญหานี้เรียกว่า list labeling และถูกนำเสนอในบทความปี 1981
- ขอบเขตการใช้งานขยายจากชั้นหนังสือไปถึงการจัดวางไฟล์และรายการในฮาร์ดไดรฟ์กับฐานข้อมูล
- จำนวนรายการอาจมากถึงหลายพันล้านรายการ
- การจัดวางที่ไม่มีประสิทธิภาพนำไปสู่เวลารอนานและต้นทุนการคำนวณสูง
ประสิทธิภาพเมื่อมองผ่านขอบเขตบนและขอบเขตล่าง
- ประสิทธิภาพของการจัดวางที่เรียงลำดับมักประเมินจากเวลาที่ใช้แทรกรายการใหม่หนึ่งรายการ
- เมื่อจำนวนรายการคือ (n) หากต้องย้ายหนังสือทั้งหมด เวลาแทรกจะแปรผันตาม (n)
- สิ่งนี้มองได้ว่าเป็น ขอบเขตบน ของเวลาที่อาจใช้ในการเพิ่มรายการใหม่
- บทความปี 1981 ตั้งคำถามว่าจะลดเวลาแทรกโดยเฉลี่ยให้ต่ำกว่า (n) ได้มากหรือไม่ และเสนออัลกอริทึมที่รับประกัน ((log n)^2)
- เป็นอัลกอริทึมแบบ กำหนดแน่นอน ที่ไม่พึ่งพาความสุ่ม
- มีคุณสมบัติ ราบเรียบ (smooth) ที่รายการต้องกระจายอย่างสม่ำเสมอภายในช่วงที่เกิดการแทรกหรือลบ
- นักวิจัยจะบีบช่องว่างระหว่างขอบเขตบนกับขอบเขตล่างให้แคบลง และเมื่อค่าทั้งสองตรงกัน ก็ถือว่าอัลกอริทึมนั้นเหมาะที่สุด
ข้อจำกัดจากผลลัพธ์ขอบเขตล่างเดิม
- งานวิจัยปี 2004 แสดง ขอบเขตล่างขั้นสุดท้าย ว่าในเวอร์ชันทั่วไปที่สุดของปัญหาการจัดเรียงในห้องสมุด ไม่มีอัลกอริทึมใดทำได้ดีกว่า (log n)
- ในปี 1990 มีการยืนยันว่าขอบเขตล่างของอัลกอริทึมแบบราบเรียบคือ ((log n)^2)
- ในปี 2012 มีผลลัพธ์ว่าอัลกอริทึมแบบกำหนดแน่นอนที่ไม่ใช้ความสุ่มก็มีขอบเขตล่างเดียวกันคือ ((log n)^2)
- ผลลัพธ์เหล่านี้หมายความว่า การอาศัยเพียงอัลกอริทึมแบบราบเรียบหรือแบบกำหนดแน่นอนทำให้ยากที่จะปรับปรุงขอบเขตบน ((log n)^2) จากปี 1981
- Michael Bender ตัดสินว่าเพื่อให้ได้ผลลัพธ์ที่ดีกว่า จำเป็นต้องใช้อัลกอริทึมแบบ สุ่ม และ ไม่ราบเรียบ
- วิธีแบบไม่ราบเรียบดูเสี่ยงในเชิงสัญชาตญาณ เพราะไม่ได้เว้นระยะรายการให้สม่ำเสมอ
- ยังไม่ชัดเจนด้วยว่าการเลือกแบบสุ่มจะช่วยได้อย่างไร
ปี 2022: ลดขอบเขตบนด้วยความไม่ขึ้นกับประวัติ
- Bender, William Kuszmaul และอีก 6 คน สร้างอัลกอริทึมแบบ ไม่ขึ้นกับประวัติ ไม่ราบเรียบ และสุ่มขึ้นในปี 2022
- อัลกอริทึมแบบไม่ขึ้นกับประวัติจะไม่เปิดเผยสถานะในอดีตของชั้นหนังสือ
- Kuszmaul ยกตัวอย่างว่าเมื่อหยิบหนังสือที่เคยอยู่บนชั้นออกไป คนอื่นจะไม่สามารถรู้เรื่องนั้นได้
- คุณสมบัติเช่นนี้อาจนำไปใช้ด้วยเหตุผลด้านความเป็นส่วนตัวหรือความปลอดภัย
- อัลกอริทึมนี้ลดขอบเขตบนจากปี 1981 ได้เป็นครั้งแรก ทำให้เวลาแทรกโดยเฉลี่ยลดลงเหลือ ((log n)^{1.5})
- Kuszmaul มองว่าน่าประหลาดใจที่เครื่องมือซึ่งปกติใช้เพื่อความเป็นส่วนตัวสามารถทำให้อัลกอริทึมเร็วขึ้นได้
- Helen Xu จาก Georgia Institute of Technology ประเมินว่าแนวคิดการใช้ความไม่ขึ้นกับประวัติด้วยเหตุผลอื่นนอกเหนือจากความปลอดภัย อาจส่งผลต่อปัญหาอื่น ๆ ได้ด้วย
งานวิจัยล่าสุด: ผสานข้อมูลอดีตแบบจำกัดกับความสุ่ม
- ในบทความล่าสุด Bender, Kuszmaul และคณะ ลดขอบเขตบนลงอีกครั้งจนได้ ((log n)(log log n)^3)
- ค่านี้เทียบได้กับ ((log n)^{1.000…1}) และใกล้ขอบเขตล่างขั้นสุดท้าย (log n) มาก
- แนวทางใหม่ยังคง ไม่ราบเรียบและสุ่ม แต่ครั้งนี้ใช้ การพึ่งพาประวัติ (history dependence) แบบจำกัด
- อัลกอริทึมจะดูแนวโน้มในอดีตบางส่วนเพื่อเตรียมรับการแทรกในอนาคต
- หากมีหนังสือของผู้เขียนที่นามสกุลขึ้นต้นด้วย N เข้ามาจำนวนมาก เช่น Nabokov, Neruda, Ng ก็จะเผื่อพื้นที่ว่างในโซน N ไว้มากขึ้นเล็กน้อย
- แต่หากจองพื้นที่ไว้มากเกินไป ก็อาจเกิดปัญหาเมื่อมีหนังสือของผู้เขียนที่ขึ้นต้นด้วย A เข้ามาจำนวนมาก
- Bender อธิบายว่าเขาทำให้แนวทางนี้มีประโยชน์ได้ด้วยการสุ่มเชิงกลยุทธ์ว่าจะดูอดีตมากเพียงใดเมื่อทำการตัดสินใจ
- Seth Pettie ประเมินว่างานวิจัยครั้งนี้ใช้ความสุ่มในรูปแบบที่แตกต่างอย่างสิ้นเชิงจากบทความปี 2022
ช่องว่างที่เหลือและความเป็นไปได้ในการประยุกต์ใช้
- ช่องว่างที่เหลือคือพจน์ (log log n) ขนาดเล็ก
- Bender กล่าวว่า ยังไม่รู้ว่าควรลดขอบเขตบนลงอีก หรือควรยกขอบเขตล่างขึ้น
- Pettie มองว่าเมื่อช่องว่างแคบถึงระดับนี้ และขอบเขตด้านหนึ่งดูเป็นธรรมชาติ ขณะที่อีกด้านดูไม่เป็นธรรมชาติ โดยทั่วไปด้านที่เป็นธรรมชาติมักเป็นคำตอบ
- เขาประเมินว่าการปรับปรุงในอนาคตมีแนวโน้มมากกว่าจะเป็นการลดขอบเขตบนลงถึง (log n)
- แต่ก็เสริมว่า “โลกเต็มไปด้วยความประหลาดใจแปลก ๆ”
- Brian Wheatman จาก University of Chicago มองว่าบทความเหล่านี้เป็น การปรับปรุงอย่างมาก ในเชิงทฤษฎี และมีความเป็นไปได้ที่จะปรับปรุงครั้งใหญ่ในด้านการประยุกต์ใช้ด้วย
- Helen Xu สนใจการจัดเก็บและประมวลผล กราฟแบบไดนามิก ด้วยโครงสร้างข้อมูลที่อิง list labeling ในช่วงหลัง และมองว่าความก้าวหน้านี้แทบจะแน่นอนว่าจะทำให้เร็วขึ้น
1 ความคิดเห็น
ความคิดเห็นจาก Hacker News
ผมก็แปลกใจเหมือนกันที่ “เครื่องมือที่เคยใช้เพื่อคุ้มครองความเป็นส่วนตัวสามารถให้ประโยชน์อย่างอื่นได้ด้วย”
ถ้าคิดให้ดี ประสิทธิภาพส่วนใหญ่ไม่ใช่ปัญหาแบบตรงตัวว่า “รันคำสั่งได้มากขึ้นต่อชั่วโมง” แต่ใกล้เคียงกับ การเลือกวิธีทำงานให้น้อยลง มากกว่า
ในที่นี้ คุณสมบัติด้านความปลอดภัยอย่าง history independence ก็หมายความว่า “ไม่จำเป็นต้องทำงานติดตามประวัติ และทำไม่ได้จริงๆ ด้วยซ้ำ” จึงรู้สึกเหมือนเป็นแนวทางด้านประสิทธิภาพที่น่าสนใจ คือใช้วิทยาการเข้ารหัสลับเป็นข้อจำกัดเพื่อกันไม่ให้ทำงานที่ไม่จำเป็น
เท่าที่ผมเข้าใจ โมเดลนี้อนุญาตให้ใช้เวลาในการคำนวณได้ไม่จำกัด
เช่น ถ้ารู้ว่ารายการถูกเรียงแล้ว ก็ใช้ binary search ได้ แต่บางทีการเลือกว่าจะ ละเว้นข้อมูลมากน้อยแค่ไหน ก็อาจเป็นแก่นสำคัญเหมือนกัน เพียงแต่กรณีแบบนี้พบเห็นน้อยกว่า และยังนึกตัวอย่างง่ายๆ ไม่ออกทันที
สงสัยว่ามีแค่ผมหรือเปล่าที่พยายามหาบทความวิจัยหลักที่บทความอธิบายถึง คือบทความเรื่องปัญหาดั้งเดิมและอัลกอริทึมที่เกือบเหมาะที่สุด [1], [2]
ดูเหมือนทั้งสองลิงก์จะอยู่ลึกในบทความ แต่ถ้า Quanta บังคับรวมเอกสารอ้างอิงทั้งหมดไว้ท้ายบทความ ก็น่าจะช่วยผู้อ่านได้มาก
[1] Nearly Optimal List Labeling:
https://arxiv.org/abs/2405.00807
[2] A sparse table implementation of priority queues:
https://link.springer.com/chapter/10.1007/3-540-10843-2_34
ในประโยค “This problem was introduced in a 1981 paper” คำว่า “1981 paper” ลิงก์ไปที่ https://link.springer.com/chapter/10.1007/3-540-10843-2_34 และในย่อหน้าถัดไป “Last year, in a study that was presented at the Foundations of Computer Science conference in Chicago, a team of seven researchers” คำว่า “a study” ลิงก์ไปที่ https://arxiv.org/abs/2405.00807
ทั้งสองอยู่ในย่อหน้าที่สามและสี่ของช่วงเกริ่นนำ ก่อนจะเข้าสู่รายละเอียด ประวัติ และบริบท ถ้าระดับนี้เรียกว่า “อยู่ลึกในบทความ” เกณฑ์ของคำว่า ลึก ก็คงต่างกันพอสมควร
สัปดาห์ที่แล้วผมกำลังดูปัญหานี้พอดี อยากวางรายการในตารางฐานข้อมูลไว้ในตำแหน่งใดก็ได้ แต่ถ้าเป็นไปได้ก็ไม่อยากแตะรายการอื่นในลิสต์
เช่น เมื่อผู้ใช้เพิ่มองค์ประกอบใหม่หลังรายการที่ 5 องค์ประกอบนั้นจะกลายเป็น 6 แต่รายการเดิมที่อยู่หลังหมายเลข 5 จะไม่ถูกอัปเดต จริงๆ แล้วมีอัลกอริทึมที่ซับซ้อนมากสำหรับจัดการปัญหานี้และลดขีดจำกัดเชิงทฤษฎีให้ต่ำที่สุด
แต่สำหรับเวอร์ชันเฉพาะนี้ ดูเหมือนทางออกที่ง่ายที่สุดคือใช้ fractional index แล้วจ่ายต้นทุนในการจัดเรียงลิสต์ใหม่เป็นครั้งคราว
โดยพื้นฐานแล้ว ถ้าพื้นที่ของ label ใหญ่เมื่อเทียบกับจำนวนรายการ ก็จะทำงานได้ดี ถ้าไม่ใช่ ก็ต้องใช้วิธีที่ซับซ้อนขึ้น เช่น ถ้ามี label แค่ 4 ไบต์แต่มีรายการ 1 พันล้านรายการ ก็จะเป็นปัญหา
เท่าที่จำได้ วิธีแก้จริงคือเว้นช่องว่างระหว่างองค์ประกอบ เช่น แทนที่จะเป็น 0, 1, 2 ก็ใช้ 0, 100, 200 แล้วค่อย re-index เมื่อจำเป็น น่าจะทำงานได้ดีพอ
สิ่งที่ผมนึกออกคือ fractional indexing อย่างที่พูดไป แต่การจัดการทศนิยมน่ารำคาญ เลยแทนด้วยเวกเตอร์ แล้วแสดงเป็นสตริงตัวเลขที่เรียงแบบพจนานุกรมได้
องค์ประกอบที่แทรกระหว่าง 1 กับ 2 จะได้ดัชนี 11 อะไรก็ได้ระหว่าง 11~19 ก็ใช้ได้ ถ้าอยู่ระหว่าง 1 กับ 11 ก็เป็น 101 ถ้าอยู่ระหว่าง 11 กับ 2 ก็เป็น 12 เป็นต้น แต่ดัชนีเหล่านี้ไม่ใช่ตัวเลข เป็นสตริงที่เปรียบเทียบแบบพจนานุกรม
ข้อเสียก็น่าจะมีชัดเจน เช่น การเรียงดัชนีแบบนี้จะใช้หน่วยความจำมากกว่ามาก เพราะสตริงใหญ่กว่าตัวเลขมาก และก็ดูฉลาดเกินกว่าจะไม่มีข้อเสียที่คาดไม่ถึง
ในทางปฏิบัติ ข้อจำกัดนั้นเล็กมาก แต่ถ้าไม่ได้แค่ติด label ลำดับให้คอลเลกชัน แล้วนำ label นี้ไปใช้เป็นดัชนีของอาร์เรย์โดยตรงเพื่อเก็บองค์ประกอบ ความแตกต่างนี้จะกลายเป็นปัญหาจริงๆ ฝั่งนั้นเป็นรูปแบบที่จำลองปัญหาการจัดเรียงห้องสมุดได้ตรงตัวมากกว่า
จำได้ว่าเมื่อหลายปีก่อนเคยนำเสนอปัญหาที่อิงจากอัลกอริทึม Library Sort ให้นักศึกษา
ยังจำชื่อบทความต้นฉบับได้ชัดเจน: “Insertion Sort is O(n log n)”
ชื่อค่อนข้างให้ความรู้สึก clickbait
สงสัยว่าอัลกอริทึมนี้มีเหตุผลอะไรที่ในสถานการณ์จริงจะเร็วกว่าแนวทางที่ใช้กันอยู่ตอนนี้จริง ๆ หรือไม่
ที่ที่ผมเจอปัญหานี้เป็นหลักคือ อาร์เรย์ของโหนด B-tree ซึ่งตรงนั้นผมสงสัยว่าจะเร็วกว่าการใช้
memmove()เฉย ๆ หรือเปล่า และถ้าเป็นอาร์เรย์ที่ใหญ่มากจริง ๆ ก็น่าจะใช้ B-tree ง่ายกว่าถ้าอย่างนั้นอัลกอริทึมนี้ก็เข้าข่ายประเภทที่ในเชิงเส้นกำกับแล้วเร็วกว่า แต่ย้อนแย้งตรงที่ในการใช้งานจริงกลับช้ากว่าอัลกอริทึมที่ใช้กันอยู่ ตัวอย่างคืออัลกอริทึมคูณเมทริกซ์แบบเร็วที่ช้ากว่าอัลกอริทึม O(n^3) ตามตำราที่ implement ได้ดี (GEMM)
ตัวอย่างแรกในหน้านั้นมีคำอ้างอิงที่อธิบายประโยชน์ได้ดี
“ตัวอย่างของ galactic algorithm คือ วิธีที่เร็วที่สุดเท่าที่รู้จักในการคูณเลขสองจำนวน อาศัยการแปลงฟูเรียร์ 1729 มิติ ต้องใช้การดำเนินการระดับบิตเพียง O(n log n) แต่ค่าคงที่ที่ซ่อนอยู่ในสัญกรณ์บิ๊กโอมีขนาดใหญ่ จึงไม่ถูกใช้ในทางปฏิบัติ ถึงอย่างนั้นก็ยังแสดงให้เห็นว่าอัลกอริทึมแบบนี้อาจมีประโยชน์ได้อย่างไร ผู้เขียนกล่าวว่า ‘หวังว่าการปรับปรุงเพิ่มเติมจะทำให้มันใช้งานได้จริงด้วยตัวเลขเพียงหลักพันล้านหรือหลักล้านล้านหลัก’”
ประโยคที่ว่า
ลดขอบเขตบนลงเป็น (log n) × (log log n)^3 — เทียบเท่ากับ (log n)^(1.000...1)นั้นจริงสิ่งหนึ่งที่เจ๋งเวลาเราดู ความซับซ้อนแบบบิ๊กโอ ในตระกูลที่อิงพหุนาม คือ logarithm ให้ค่าที่เป็น infinitesimal ได้ เป็นการตอบโต้คนที่บอกว่า “infinitesimal ไม่มีอยู่จริง” ได้อย่างจัง
ผมแปลกใจเมื่อรู้ว่า British Library จัดการหนังสือหลายล้านเล่มและหนังสือออกใหม่จำนวนมากทุกสัปดาห์อย่างไร
หนังสือเล่มแรกที่เข้ามาเมื่อต้นปีนี้ถูกวางไว้ที่ตำแหน่ง 2025.0000001 บนชั้น และเล่มถัดไปก็วางข้าง ๆ ที่ 2025.0000002 ส่วนที่เหลือให้แคตตาล็อกอิเล็กทรอนิกส์จัดการ
ไม่ต้องสับเปลี่ยนหนังสือใหม่ แต่เป็นวิธีแก้ที่ไม่เหมาะกับการเดินดูชั้นหนังสือเพื่อหาหนังสือ
กลับกัน ยังจงใจหลีกเลี่ยงความคล้ายกันเพื่อไม่ให้พนักงานหยิบของที่ดูคล้ายแต่ผิดชิ้น
ที่บ้านผมเองก็มักลืมว่าของที่ใช้เป็นครั้งคราวเก็บไว้ตรงไหน เช่น ใส่ใบมีดสำรองของมีด x-acto ไว้ในกล่องเก็บของใบไหนของตู้ไหน พยายามรวมของคล้ายกันไว้ด้วยกันแล้วกลายเป็นว่ากล่องหนึ่งล้น แต่อีกกล่องว่างครึ่งหนึ่ง
บางครั้งก็จินตนาการว่าถ้าติดตามของใช้ทั้งหมดด้วยสเปรดชีต บันทึกว่าอยู่ในกล่องไหน ก็คงไม่ทำของหายและใช้พื้นที่เก็บของได้มีประสิทธิภาพสูงสุด แต่แน่นอนว่าพอใส่ของใหม่เข้าไปก็คงลืมอัปเดต และมันให้ความรู้สึกเป็นวิธีที่แปลกแบบไร้ความเป็นมนุษย์ เหมือนสิ่งที่หุ่นยนต์น่าจะทำมากกว่า
เห็นแอนิเมชันด้านบนสุดของบทความแล้วอยากเอามาทำเป็น สกรีนเซฟเวอร์
กำลังพยายามทำความเข้าใจข้อจำกัดหลักอยู่ นิยามของปัญหานี้สมมติว่าเป็น อาร์เรย์ความยาวคงที่ที่จัดสรรไว้ล่วงหน้า หรือเปล่า?
insert(X),delete(X),label(X)labelจะดึงป้ายกำกับของสมาชิก X ที่เคยถูกแทรกมาก่อนและยังไม่ถูกลบออก ป้ายกำกับเป็นตัวเลขตั้งแต่ 0 ถึง n-1 โดย n คือจำนวนสมาชิกที่เก็บอยู่ในขณะนั้น