ข่าว พบอัลกอลิธึมตารางแฮชใหม่ O(log² δ⁻¹) เอาชนะข้อจำกัดที่เคยมีมา 40 ปี

[News]

ทีมวิจัยระดับปริญญาตรีนำเสนอโครงสร้างข้อมูลแบบใหม่เพื่อปรับปรุงโครงสร้างข้อมูล open-addressing hash table หรือโครงสร้างแฮชที่เก็บข้อมูลในตารางแฮชโดยตรง โดยสามารถสร้างอัลกอริทึมที่เร็วกว่า การคาดคะเนของ Andrew Yao ที่วางข้อจำกัดความเร็วของปัญหาแบบนี้ไว้ตั้งแต่ปี 1985

ทีมงานนี้ประกอบด้วย Martin Farach-Colton จากมหาวิทยาลัยนิวยอร์ค, Andrew Krapivin จากมหาวิทยาลัยเคมบริดจ์, และ William Kuszmaul จากมหาวิทยาลัยคาร์เนกีเมลลอน โดยเสนอกระบวนการแฮชรูปแบบใหม่สองแบบ คือ Elastic Hashing และ Funnel Hashing โดยตัวสำคัญคือ Funnel Hashing ที่ทนทานต่อการค้นหาข้อมูลแม้ในกรณีที่แย่ที่สุดก็ยังอยู่ที่ระดับ O(log² δ⁻¹) เท่านั้น

open-addressing hash table เป็นโครงสร้างข้อมูลที่เก็บข้อมูลไว้ในตารางแฮชโดยตรง โดยเมื่อการแฮชได้ค่าตรงกัน (hash collision) จะต้องหาทางค้นหาช่องว่างเพื่อเก็บข้อมูล (probing) ทำให้ประสิทธิภาพในการค้นหาและใส่ข้อมูลใหญ่กว่า O(1) ในกรณีที่แย่ที่สุดคือตารางเกือบเต็มแล้ว หากใช้กระบวนการค้นหาช่องว่างแบบไล่หาไปเรื่อยๆ กระบวนการค้นหาช่องว่างนี้จะใช้เวลาถึง O ตามขนาดตาราง แต่ Funnel Hashing สามารถลด Big-O ลงได้เหลือระดับ log² เท่านั้น ซึ่งเล็กลงมาก

ที่มา - Quanta Magazine

Topics:
Algorithm
Computer Science
Research
Mathematics

Continue reading...

 

ข่าว  เชิญร่วมตอบแบบสอบถาม ผลกระทบต่อผู้บริโภค หลังควบรวม True+DTAC และ AIS+3BB

ข่าว  Disney+ Hotstar ใจดีให้ดูฟรี 45 วัน จำกัดบางตอน เน้นซีรีส์เกาหลี ญี่ปุ่น และจีน