ทำให้เร็วกว่า binary search ได้
(lemire.me)- เวลาใช้ค้นหาค่าในอาร์เรย์ที่เรียงลำดับแล้ว
binary searchซึ่งนิยมใช้กันนั้นจะ เปรียบเทียบได้ทีละค่าเดียว แต่ CPU รุ่นใหม่สามารถ เปรียบเทียบหลายค่าได้พร้อมกันในคำสั่งเดียว ดังนั้นหากใช้ความสามารถนี้ก็จะเพิ่มความเร็วในการค้นหาได้มาก - SIMD Quad เป็น อัลกอริทึมการค้นหาแบบลำดับชั้น ที่แบ่งอาร์เรย์ออกเป็นบล็อกละ 16 ค่า จากนั้นบีบช่วงตำแหน่งบล็อกอย่างรวดเร็วด้วย 4-ary interpolation search แล้วใช้คำสั่ง SIMD เปรียบเทียบสมาชิก 16 ตัวในบล็อกนั้นพร้อมกัน
- จากเบนช์มาร์ก บน Intel ในสภาวะ warm cache ให้ประสิทธิภาพ เร็วกว่า 2 เท่า เมื่อเทียบกับ binary search และบน Apple ในสภาวะ cold cache ก็เร็วกว่า 2 เท่าเช่นกัน อีกทั้งยังดีกว่า
std::binary_searchในทุกเงื่อนไขการวัด - แทนที่จะแบ่งแบบครึ่งหนึ่งใน binary search การใช้ 4 ทาง ทำให้จำนวนคำสั่งเพิ่มขึ้นเล็กน้อย แต่บน Intel กับอาร์เรย์ขนาดใหญ่สามารถใช้ memory-level parallelism ได้ดีกว่า จึง ปรับปรุงประสิทธิภาพใน cold cache ได้
- เนื่องจากอัลกอริทึมแบบตำราเรียนถูกออกแบบมาโดยไม่ได้ตั้งสมมติฐานเรื่อง data parallelism และ memory parallelism ของ CPU ยุคปัจจุบัน การออกแบบใหม่ให้สะท้อนคุณลักษณะของฮาร์ดแวร์จึงช่วยเพิ่มประสิทธิภาพจริงได้
แนวคิดหลัก
- binary search มีโครงสร้างที่เปรียบเทียบค่าได้เพียงทีละตัว แต่โปรเซสเซอร์ ARM 64 บิตและ x64 สมัยใหม่สามารถ เปรียบเทียบจำนวนเต็ม 16 บิตได้พร้อมกัน 8 ค่า ในคำสั่งเดียว
- เมื่อใช้ความสามารถฮาร์ดแวร์นี้ หน่วยของการค้นหาจะเปลี่ยนจากสมาชิกเดี่ยวเป็น ระดับบล็อก ทำให้ลดจำนวนครั้งในการเปรียบเทียบได้มาก
- แทนที่จะแบ่งอาร์เรย์ครึ่งหนึ่ง การใช้ 4 ส่วน (4-ary search) แม้จำนวนคำสั่งจะเพิ่มขึ้นเล็กน้อย แต่คอขวดอาจไม่ได้อยู่ที่จำนวนคำสั่ง และยังใช้ memory-level parallelism ได้ดีขึ้น
วิธีพื้นฐานของการตรวจสอบ membership ในอาร์เรย์ที่เรียงลำดับ
- วิธีที่ง่ายที่สุดในการตรวจว่ามีค่าอยู่ในอาร์เรย์ที่เรียงลำดับหรือไม่ คือ linear search ที่ไล่ดูค่าทีละตัว ซึ่งใน C++ ให้ผลเทียบเท่ากับ
std::find - สำหรับอาร์เรย์ขนาดใหญ่ binary search จะเร็วกกว่า โดยทำซ้ำกระบวนการทิ้งครึ่งบนหรือครึ่งล่างจากค่ากลางของช่วงค้นหา
std::binary_searchของ C++ จะคืนค่าแบบบูลีนว่ามีค่านั้นอยู่หรือไม่- ฟอร์แมต Roaring Bitmap ใช้อาร์เรย์จำนวนเต็ม 16 บิตขนาด 1~4096 และใช้ binary search เพื่อตรวจสอบการมีอยู่ของค่า
โครงสร้างอัลกอริทึม SIMD Quad
- แบ่งอาร์เรย์จำนวนเต็ม unsigned 16 บิตที่เรียงลำดับแล้วออกเป็น บล็อกขนาดคงที่ 16 สมาชิก
- ใช้สมาชิกตัวสุดท้ายของแต่ละบล็อกเป็น interpolation key เพื่อ จำกัดช่วงให้เหลือบล็อกเดียว ที่มีโอกาสสูงว่าจะมีค่าที่ต้องการ จากนั้นตรวจสมาชิกทั้ง 16 ตัวในบล็อกนั้นพร้อมกันด้วย SIMD
- ขั้นตอนการทำงาน:
- ถ้ามีสมาชิกน้อยกว่า 16 ตัว ให้ค้นหาแบบ linear search ทั้งหมด
- แบ่งอาร์เรย์ออกเป็นบล็อกของสมาชิกต่อเนื่อง 16 ตัว และจำนวนบล็อกรวมคือ
num_blocks = cardinality / 16 - ใช้สมาชิกตัวสุดท้ายของบล็อกเป็นคีย์ แล้วเปรียบเทียบค่าที่ต้องการกับตำแหน่ง 1/4 ของช่วงค้นหาปัจจุบัน เพื่อปรับ
base - หากเป็นบล็อกที่ใช้ได้ บน ARM จะใช้ NEON และบน x64 จะใช้ SSE2 เพื่อโหลดสมาชิก 16 ตัวแล้วทำการเปรียบเทียบความเท่ากันแบบขนาน
- สมาชิกที่เหลือซึ่งไม่อยู่ในบล็อกเต็มจะใช้ linear search
วิธีทำเบนช์มาร์ก
- สำหรับแต่ละขนาดอาร์เรย์ 2~4096 สร้างอาร์เรย์จำนวนเต็ม unsigned 16 บิตที่เรียงลำดับแล้ว 100,000 ชุด
- สำหรับแต่ละขนาด ทำ membership query 10 ล้านครั้ง ใน 2 โหมด
- cold mode: แต่ละคำขอค้นหาจะใช้อาร์เรย์คนละชุดเพื่อจำลอง cache miss
- warm mode: ค้นหาอาร์เรย์ชุดเดิมติดกัน 100 ครั้งเพื่อจำลอง cache hit
- ตัวชี้วัดคือเวลาเฉลี่ยต่อคำขอค้นหา โดยเปรียบเทียบระหว่าง linear search (
std::find), binary search (std::binary_search) และ SIMD Quad - ระบบที่ใช้วัดคือ Apple M4 (Apple LLVM) และ Intel Emerald Rapids (GCC)
ผลการวัด
- เมื่ออาร์เรย์ใหญ่ขึ้น binary search จะชนะ linear search อย่างชัดเจน และใน cold cache นั้น linear search เสียเปรียบมากกว่าเพราะมีการเข้าถึงข้อมูลมาก
- แพลตฟอร์ม Intel: ใน warm cache นั้น SIMD Quad เร็วกว่า 2 เท่า เมื่อเทียบกับ binary search ส่วนใน cold cache ได้ประโยชน์น้อยกว่า
- แพลตฟอร์ม Apple: ใน cold cache นั้น SIMD Quad เร็วกว่า 2 เท่า ส่วนใน warm cache ประโยชน์มีจำกัดกว่า
- ในทุกกรณี SIMD Quad เร็วกว่า
std::binary_search - ส่วน SIMD ช่วยลดงานด้วยคำสั่งเฉพาะทาง และมีทั้งจำนวนคำสั่งกับการแตกแขนงที่น้อยกว่า จึงอธิบายสาเหตุของความเร็วที่เพิ่มขึ้นได้ชัดเจน
ผลของการค้นหาแบบ 4 ทาง
- มีการเปรียบเทียบกับเวอร์ชัน SIMD binary ที่ยังคงการปรับแต่ง SIMD ไว้ แต่เปลี่ยน 4-ary interpolation search กลับเป็น binary search
- บนแพลตฟอร์ม Apple ผลของแนวทาง 4 ทางมีไม่มาก
- บนแพลตฟอร์ม Intel แนวทาง 4 ทางเป็นการปรับแต่งที่มีความหมายใน สถานการณ์ cold cache ของอาร์เรย์ขนาดใหญ่
- บนเซิร์ฟเวอร์ Intel การค้นหาแบบ 4 ทางใช้ memory-level parallelism ได้ดีกว่า
แกนสำคัญของการติดตั้งใช้งาน
- ฟังก์ชัน
simd_quadรับอาร์เรย์uint16_t, จำนวนสมาชิกcardinality, และค่าที่จะค้นหาposแล้วคืนค่าแบบบูลีน gapถูกกำหนดคงที่เป็น 16 และถ้าcardinality < gapก็จะค้นหาด้วยลูปธรรมดา- ลูปค้นหาบล็อกจะทำงานขณะ
n > 3โดยอ่านค่าของสมาชิกตัวสุดท้ายของบล็อกที่ตำแหน่ง 1/4, 2/4, 3/4 แล้วเลื่อนbaseตามผลรวมของการเปรียบเทียบทั้งสามครั้ง - บล็อกที่เลือกจะเปรียบเทียบสมาชิก 16 ตัวแบบขนานเป็น สองชุด ด้วย
vceqq_u16ของ ARM NEON หรือ_mm_cmpeq_epi16ของ x64 SSE2 - ช่วงสมาชิกที่เหลือจะคืนผล
v == posที่จุดซึ่งv >= pos
บทสรุป
- binary search แบบตำราเรียนเป็นอัลกอริทึมที่ดี แต่ยังทำให้เร็วขึ้นได้อย่างมีนัยสำคัญในเชิงประสิทธิภาพจริง
- อัลกอริทึมมาตรฐานจำนวนมากไม่ได้ถูกออกแบบโดยตั้งอยู่บนสมมติฐานเรื่องความขนานสูงของคอมพิวเตอร์ยุคปัจจุบัน
- SIMD Quad เป็นแนวทางที่พยายามใช้ทั้ง memory-level parallelism และ data parallelism
- ยังอาจมีอัลกอริทึมที่ดีกว่านี้ได้ และต้องการแนวทางที่สร้างสรรค์มากขึ้น
- ซอร์สโค้ด
- Faster intersections between sorted arrays with shotgun
1 ความคิดเห็น
ความเห็นจาก Hacker News
นอกเหนือจากเรื่อง การปรับแต่งฮาร์ดแวร์ระดับล่าง ที่ Daniel Lemire พูดถึงแล้ว การค้นหาแบบทวิภาคหรือรูปแบบดัดแปลงของมันจะเป็นทางเลือกที่ดีที่สุดก็ต่อเมื่อเรารู้อยู่อย่างเดียวว่าข้อมูลถูกจัดเรียง/เป็นโมโนโทนิกเท่านั้น
ถ้ามีข้อมูลล่วงหน้าเกี่ยวกับการกระจายตัวของข้อมูล ก็ใช้ข้อมูลนั้นสร้างอัลกอริทึมที่เร็วกว่าได้มาก ตัวอย่างคือการเปิดพจนานุกรมกระดาษ ที่คนสามารถกะไปยังชุดหน้าที่น่าจะใช่ได้เร็วกว่าการทำ binary search แบบล้วนๆ
ในเชิงคณิตศาสตร์ การค้นหาในลิสต์ที่เรียงแล้วคล้ายกับการใช้อัลกอริทึมควบคุมแบบวงปิดเพื่อหา ฟังก์ชันผกผันของฟังก์ชันโมโนโทนิก และยังสามารถสร้าง cost function แล้วใช้ gradient descent หรือรูปแบบเร่งอื่นๆ ได้อีกด้วย พูดให้กว้างขึ้นคือ แทนที่จะหยิบวิธีแก้จากการนิยามปัญหาแบบนามธรรมเกินไป การใช้ข้อมูลเฉพาะของปัญหาที่กำลังแก้มักจะมีประสิทธิภาพกว่าเสมอ และอาจให้การเร่งความเร็วที่ขยายผลได้มากกว่าการปรับปรุงแบบคูณค่าคงที่จากการใช้ฮาร์ดแวร์ให้ดีขึ้นเสียอีก
จำนวนรอบคงที่ดีต่อ ตัวทำนายการแตกกิ่ง และลูปหลักก็ถูกปรับจูนอย่างค่อนข้างแน่นให้เข้ากับฮาร์ดแวร์เป้าหมายโดยหลีกเลี่ยงการคูณ ความพยายามจะทำให้ฉลาดกว่านี้กลับทำให้ลูปแย่ลงและไม่ได้ประโยชน์อะไร รูปแบบอาร์เรย์ของ struct นี้มีขนาด 12 และส่วนใหญ่ N ก็เล็ก เลยยิ่งทำให้ยาก
ผมไม่ได้บุ๊กมาร์กไว้ เลยกลับไปหามันใหม่ปีละประมาณสองครั้ง
ตามตำนานเล่าว่าจนถึงตอนนี้ก็ยังหาอยู่
นั่นจึงเป็นเหตุผลที่ในฐานข้อมูล B-tree เป็นมาตรฐาน ข้อมูลจะเป็นอะไรก็ได้ และถ้ามีการนำเข้าข้อมูลแถวใหม่ครั้งใหญ่ คุณลักษณะของมันก็อาจเปลี่ยนไปมากได้ทุกเมื่อ
คุณอาจสร้างอัลกอริทึมที่เร่งการ lookup ด้วยแนวทางอย่าง gradient descent ได้ แต่ B-tree ก็เร็วมากอยู่แล้ว แถมยังมีข้อดีเรื่องประสิทธิภาพกรณีเลวร้ายสุด ปริมาณ I/O ที่คาดเดาได้ การสแกนช่วง การไล่เรียงตามลำดับ และการรองรับเงื่อนไขแบบ prefix
เราสร้างอัลกอริทึม lookup ที่มีประสิทธิภาพกว่ากับการกระจายข้อมูลเฉพาะบางแบบได้ แต่ก็มักต้องเสียคุณสมบัติสำคัญบางอย่างไป แม้อัลกอริทึมอื่นจะให้ค่าประมาณเริ่มต้นที่ใกล้กว่า ก็อาจช้ากว่าในการหา item สุดท้าย และแม้ค่าเฉลี่ยจะเร็วกว่า แต่ถ้ากรณีเลวร้ายสุดแย่เกินไปก็ใช้งานไม่ได้
แม้แต่ในพจนานุกรมกระดาษ หลังจากเดาครั้งแรกแล้ว คนก็มักใช้วิธีคล้าย binary search อยู่ดี และขั้นตอนที่ลดได้จากการเดาเริ่มต้นนั้นมีเพียงไม่กี่ครั้ง พอไปถึงชุดหน้าที่น่าจะใช่แล้ว ก็มักไล่ดูแบบเชิงเส้นเกินกว่าที่จำเป็นนิดหน่อย เพราะถึง binary search แบบเคร่งครัดอาจเร็วกว่า แต่ก็ต้องชั่งกับเวลาที่ใช้พลิกหน้า
Ed Kmett นำแนวคิดนั้นมาขัดเกลาเป็นไลบรารี discrimination[2] สำหรับ Haskell และวิดีโอพูดคุยที่เกี่ยวข้อง[3] ก็น่าสนใจมาก
[1]: https://dl.acm.org/doi/epdf/10.1145/1411203.1411220
[2]: https://hackage.haskell.org/package/discrimination
[3]: https://www.youtube.com/watch?v=cB8DapKQz-I
“การค้นหาแบบ 4 ส่วน” นี่สุดท้ายก็แค่คลี่ลูปของ binary search ออกมาหนึ่งขั้นไม่ใช่หรือ? เพื่อหาช่วงที่มีรายการอยู่ จำนวนครั้งในการเปรียบเทียบก็น่าจะพอๆ กัน แค่ดูเหมือนประมวลผลทีละ 4 แทนที่จะเป็น 2 ผมเดาว่าแค่ loop unrolling ก็น่าจะให้ผลแบบเดียวกัน
ในทางปฏิบัติ จากมุมมองของโปรเซสเซอร์ ลูปแทบทั้งหมดถูกคลี่ออกบางส่วนอยู่แล้ว เหลือเพียง overhead เล็กน้อยของตัวลูปเอง ใน binary search ต้นทุนหลักคือการดึงข้อมูลจากหน่วยความจำหรือแคช ดังนั้นโจทย์จริงคือทำอย่างไรให้คำขอข้อมูลที่จะต้องใช้ในภายหลังถูกส่งออกให้เร็วที่สุด เพื่อจะได้รอข้อมูลน้อยลง
ความต่างของอัลกอริทึมแบบ quartering search คือ แทนที่จะ prefetch ล่วงหน้าลึกๆ แค่ด้านเดียวของแต่ละกิ่ง มัน prefetch แบบตื้นสำหรับทุกความเป็นไปได้ สุดท้ายแล้ว prefetch ที่ต้องใช้จริงก็จะถูกส่งออกแน่ๆ และยังใช้แบนด์วิดท์กับข้อมูลที่ไม่อยู่บนเส้นทางจริงน้อยลงเล็กน้อย
ถ้าจะทำนายประสิทธิภาพจริงของอัลกอริทึมค้นหา “จำนวนครั้งในการเปรียบเทียบ” แทบเป็นตัวชี้วัดที่ไร้ประโยชน์ คอขวดไม่ใช่ว่าเปรียบเทียบได้มากแค่ไหน แต่คือใช้แบนด์วิดท์ของหน่วยความจำและแคชได้เต็มที่หรือไม่ ถ้าคิดการทำงานของ branch ภายในโปรเซสเซอร์สมัยใหม่ลึกพอ จะมองว่ามันเป็น loop unrolling ก็ได้
ยังไงทั้งสองแบบก็เป็น O(log N) ที่มีค่าคงที่ต่างกัน ในวิชาอัลกอริทึมค่าคงที่อาจไม่สำคัญ แต่ในโลกจริงมันมีผลมากพอสมควร
ไม่นานมานี้ผมก็เขียนบทความ[1] เกี่ยวกับ exponential search[2] ด้วย เป็นอัลกอริทึมที่ใช้ได้เมื่อ element ที่ต้องหาเองก็อยู่ในลำดับเรียงแล้ว และต้องทำ binary search ซ้ำๆ บนอาร์เรย์ ใน workload ของเราได้ความเร็วเพิ่มขึ้น 8 เท่า
[1] https://lalitm.com/post/exponential-search/
[2] https://en.wikipedia.org/wiki/Exponential_search
HEAD /users/1 -> 200 OK
HEAD /users/2 -> 200 OK
HEAD /users/4 -> 200 OK
...
HEAD /users/2048 -> 200 OK
HEAD /users/4096 -> 404 Not Found
จากนั้นก็ทำ binary search ระหว่าง 2048 กับ 4096 เพื่อหาผู้ใช้ล่าสุด และได้จำนวนผู้ใช้ไปด้วยโดยปริยาย เป็นข้อมูลที่มีประโยชน์เวลาไปสืบคู่แข่งสาย SaaS
CPU เข้าถึงทั้ง cache line ในครั้งเดียวอยู่แล้ว ซึ่งโดยทั่วไปคือ 64 ไบต์ ดังนั้นน่าจะคุ้มกว่าถ้าค้นทั้ง cache line เพราะเมื่อข้อมูลขึ้นมาอยู่ใน CPU แล้ว ต้นทุนแทบจะเป็นศูนย์
เพราะแบบนั้น ผมเลยอยากลองแนวทางที่ใน “binary” search จะตรวจทุกค่าภายใน cache line ตรงกลางก่อน แล้วถ้าไม่เจอค่าที่ตรงก็ไปซ้ายหรือขวา การค้นภายใน cache line ทำได้ด้วยคำสั่ง SIMD 512 บิตคำสั่งเดียว cache line ขนาด 64 ไบต์มีจำนวนเต็ม 16 บิตอยู่ 32 ค่า ดังนั้นมันอาจเร็วกว่า binary search ปกติได้เกือบ 32 เท่า หรืออย่างน้อยก็ลดจำนวนการเข้าถึงหน่วยความจำได้ 32 เท่า ซึ่งน่าจะเป็นปัจจัยหลักในโปรแกรมจริงส่วนใหญ่
ถ้าใช้คีย์ 4 ไบต์กับ child pointer 4 ไบต์ หรือใช้ดัชนีของอาร์เรย์ internal node จะใส่คีย์ได้ 7 ตัว child pointer 8 ตัว และ next pointer 1 ตัว พอดีเต็ม cache line 64 ไบต์ สำหรับข้อมูล 1 ล้านรายการ ความลึกของต้นไม้จะลดจากประมาณ 20 เหลือประมาณ 7 และไม่กี่ชั้นบนสุดก็น่าจะค้างอยู่ในแคชได้
ถ้าคิดต่ออีกหน่อยก็เร่งการค้นหาภายในโหนด B-tree ด้วย SIMD ได้ แต่การพึ่งพาข้อมูลยังสูงมาก
ถ้าเป็นอาร์เรย์ขนาดเล็กกว่า การค้นหาแบบเชิงเส้นที่มี sentinel value ไว้ท้ายอาร์เรย์นั้นเอาชนะได้ยากอยู่แล้ว เพียงแต่เหตุผลที่คำพูดนี้ฟังคลุมเครือคือคำว่า “เล็ก” มันกว้างเกินไปจนจับความรู้สึกยาก
โดยรวมผมชอบบทความนี้มาก มันสำรวจคำถามที่ผมเคยสงสัยได้อย่างครบถ้วน พร้อมการทดลองตัดปัจจัยที่มีประโยชน์มาก
ผมเคยลองค้นหากับอาร์เรย์เล็กๆ ประมาณ 16~32 รายการ แล้ว binary search กลับเป็นหนึ่งในวิธีที่แย่ที่สุดเพราะมี branch เยอะเกินไป สำหรับอาร์เรย์เล็ก วิธีที่เร็วที่สุดคือ linear search แบบไร้ branch
มันเป็นวิธีที่ไล่ตรวจทุก element โดยไม่หยุดลูประหว่างทาง เช่น ถ้าต้องการรู้ว่าเลขตัวหนึ่งอยู่ในอาร์เรย์ไหม ก็เอาผลการตรวจของทุกตัวมารวมกันด้วย logical OR ผมไม่ได้ใช้ SIMD แต่กับอาร์เรย์เล็กๆ branch มีราคาแพงมาก จึงเร็วกว่าเมื่อแค่ตรวจทุก element ไปเลยโดยไม่มี branch
ผมรู้สึกว่าคำอธิบายอัลกอริทึมทำให้งงนิดหน่อย
ส่วนของ SIMD ใช้เฉพาะขั้นสุดท้าย คือเวลาค้นหา 16 elements สุดท้ายเท่านั้น
ส่วน quartering search คือการตรวจ 3 จุดเพื่อแบ่งเป็น 4 เส้นทาง แต่ไม่ได้กำลังหาคีย์ที่ถูกต้องตรงๆ กำลังหาบล็อกที่ถูกต้อง
รายละเอียดน่าสนใจตรงที่ผู้เขียนใช้ element สุดท้ายของแต่ละบล็อกสำหรับ quartering search ถ้าใช้ element แรกหรือใช้ element แบบสุ่ม อัลกอริทึมจะเปลี่ยนไปอย่างไรน่าสนใจดี
แก่นของแนวคิดที่นี่คือ การเปรียบเทียบหลายค่าด้วย SIMD ดูเหมือนจะใช้ในสเกลใหญ่กว่าขั้นสุดท้ายได้ด้วย
ภาพรวมคือ: a) ใช้ gather เพื่อดึงหลาย element จาก 16 ตำแหน่งที่เว้นระยะเท่าๆ กัน b) เปรียบเทียบแบบขนานด้วยคำสั่ง SIMD c) โฟกัสไปที่บล็อกที่ถูกต้อง d) ถ้าบล็อกเล็กพอก็สลับเป็น linear search ไม่อย่างนั้นก็ทำรอบ gather/compare ซ้ำ
คำสั่ง gather อ่านจากหน่วยความจำที่ไม่ต่อเนื่อง และสำหรับ binary search ก็จะอ่านมากกว่าที่จำเป็นจริงๆ ถึงอย่างนั้น ถ้ามันเปิดทางให้เปรียบเทียบหลายทิศทางและยุบ 4 ขั้นของ binary search ลงได้ ก็น่าจะชนะในตารางขนาดใหญ่
ไม่ใช่ทุกชนิดข้อมูลที่จะทำการเปรียบเทียบครบ 16 ทางได้ เช่น การค้นหา float64 แม้บน AVX-512 ก็ยังจำกัดที่ 8 ทาง แต่ int32 กับ float32 ทำแบบ 16 ทางได้
ผมคิดว่า binary search อาจเร็วกว่าแนวทางที่ใช้ gather เสียอีก
อัลกอริทึมคอมพิวเตอร์คลาสสิกจริงๆ แล้วแทบจะถูก “ออกแบบ” มาเพื่อ CPU ที่ไม่มีความขนานเลย ไม่มีหลายคอร์ ไม่มี Hyper-threading ไม่มีคำสั่ง SIMD และเวลาเข้าถึงหน่วยความจำทุกตำแหน่งเท่ากันหมด จึงไม่มีแนวคิดอย่าง latency ของ L1/L2/L3 cache และยังตั้งสมมติฐานว่าข้อมูลเป็นแบบทั่วไป/สุ่ม
ถ้าสมมติฐานข้อใดข้อหนึ่งหลุดไป ก็จะมีจุดให้ปรับจูนเพื่อเพิ่มประสิทธิภาพได้มากมาย
อัลกอริทึมคลาสสิกจึงเป็นจุดเริ่มต้นที่ดีมาก ก่อนจะพัฒนาแนวทางที่เหมาะกว่า เมื่อเรารู้ลักษณะข้อมูลหรือคุณสมบัติ/ฟีเจอร์ของ CPU เป้าหมายมากขึ้น
เมื่อไล่ไปจนถึงปลายสุดของงาน optimization ก็มักจะลงเอยที่วิธีเก็บข้อมูลในหน่วยความจำและวิธีเข้าถึงมัน รวมถึงพิจารณาว่าการเปลี่ยนเพื่อให้จุดนี้ดีขึ้นจะไปทำร้ายขั้นถัดไปหรือไม่ ที่ทำงานเก่าของผมเคยมีคนใช้เวลาปรับแต่งโค้ดส่วนหนึ่งนานเกินไป แล้ว optimization นั้นกลับไปไล่ข้อมูลสำคัญอีกจำนวนมากออกจากแคช ทำให้ทั้งแอปพลิเคชันช้าลง
เรื่องนี้น่าจะใกล้เคียงกับกฎข้อที่ 5 ของ Rob Pike หรือพูดอีกแบบคือเป็นการกล่าวซ้ำสิ่งที่ Fred Brooks เขียนไว้ใน The Mythical Man Month ดูได้ที่: https://www.cs.unc.edu/~stotts/COMP590-059-f24/robsrules.htm...
ตอนเป็นวัยรุ่น ผมเคยใช้เวลาทั้งสุดสัปดาห์คิดว่าถ้า binary search ดีเพราะลดพื้นที่ค้นหาลงครึ่งหนึ่งทุกขั้น แบบนั้น ternary search ที่ลดเหลือหนึ่งในสามทุกขั้นก็น่าจะดีกว่าไหม
แทนที่จะเทียบค่ากลางค่าเดียว ก็เทียบค่าที่ตำแหน่ง 1/3 ก่อน แล้วถ้าต่ำเกินไปค่อยเทียบค่าที่ตำแหน่ง 2/3
แต่ผมคิดว่าทุกขั้นมันลดเหลือ 1/3 แทน 1/2 ของ binary search ก็จริง ทว่าโดยเฉลี่ยต้องเปรียบเทียบมากขึ้น 3/2 เท่า สุดท้ายเลยน่าจะพอๆ กัน
แก้ไข: พอเห็นคำตอบของ zamadatix แล้ว ที่จริงกรณี 2/3 ต้องเปรียบเทียบ 2 ครั้ง เลยกลายเป็นเฉลี่ย 5/3 เท่า
หนึ่งในสามแรก: เปรียบเทียบ 1 ครั้ง
หนึ่งในสามที่สอง: เปรียบเทียบ 2 ครั้ง
หนึ่งในสามที่สาม: เปรียบเทียบ 2 ครั้ง
(1+2+2)/3 = เฉลี่ย 5/3 ครั้ง การรู้สึกว่า “บางทีเทียบ 1 ครั้ง บางที 2 ครั้ง” เลยชวนให้คิดผิดเป็น 50% แต่จริงๆ ความน่าจะเป็นที่จะจบตั้งแต่การเปรียบเทียบแรกคือ 1/3 และโอกาสต้องเปรียบเทียบ 2 ครั้งคือ 2/3
ดังนั้นจึงแสดงได้ว่าจำนวนการเปรียบเทียบเฉลี่ยรวม ternary search แย่กว่าเล็กน้อย: 5/3*Log_3[n] = 1.052... * Log_2[n]
กล่าวคือจำนวนขั้นลดลงก็จริง แต่โดยเฉลี่ยต้องเปรียบเทียบมากขึ้นกว่าจะไปถึงท้ายสุด เรื่องนี้มักเป็นจริงกับการค้นหาแนวนี้ทั้งหมด คือกรณีที่จำนวนส่วนแบ่งมากกว่า 2 แน่นอนว่ามีสมมติฐานบางอย่าง เช่น ค่าที่ค้นหากระจายแบบสม่ำเสมอและต้นทุนการดำเนินการถูกทำให้อุดมคติ ซึ่งตรงนี้เองที่นำไปสู่ประเด็นในบทความหลัก
ไม่ใช่ในฐานะเวอร์ชัน ternary ของอัลกอริทึม binary search เพราะนั่นไม่ใช่ ternary search จริงๆ แต่ใกล้เคียงกับ binary search แบบเอนเอียงมากกว่า เนื่องจากการเปรียบเทียบมีธรรมชาติเป็นแบบสองทาง อัลกอริทึมค้นหาที่รวมการเปรียบเทียบไว้จึงล้วนเป็น binary search ในรูปแบบหนึ่ง และการเลือกค่าที่ไม่ใช่ element ตรงกลางก็มีประสิทธิภาพด้อยกว่าในแง่ความซับซ้อนของอัลกอริทึม อย่างไรก็ดี บนฮาร์ดแวร์จริงอาจดีกว่าได้ในบางเงื่อนไข ถ้าจะให้เป็น ternary search จริงๆ ต้องมี ตัวเปรียบเทียบ 3 ทาง เป็น primitive operation
จุดที่เริ่มน่าสนใจคือเมื่อพิจารณา “ประสิทธิภาพของ radix”[1] ตัวเลือกที่ดีที่สุดคือ 3 ซึ่งเป็นจำนวนธรรมชาติที่ใกล้ e มากที่สุด มันยังเชื่อมกับการค้นหาในต้นไม้ด้วย จึงเป็นไปได้ว่า ternary tree จะดีกว่า binary tree
[1] https://en.wikipedia.org/wiki/Optimal_radix_choice
ดังนั้นไอเดียนั้นอาจยังไม่สามารถทำได้จริงบน CPU ยุคนั้น แต่บน CPU ปัจจุบันอาจมีความเป็นไปได้มากขึ้น