ปูต้นฉบับชี้จุดที่แถวก้อนหินขนาดเล็กเปลี่ยนเป็นก้อนใหญ่บนฉากสว่าง
rustslicebinary-searchtutorial

Rust partition_point: หาเส้นแบ่งใน slice ที่เรียงตามเงื่อนไข

น้องกายEngineering

ถ้ามีข้อมูลเรียงเป็น “ผ่านเงื่อนไขทั้งหมดก่อน แล้วค่อยไม่ผ่านทั้งหมด” เราไม่จำเป็นต้องเดินดูทีละช่องครับ slice::partition_point ใช้ binary search คืน index แรกของฝั่งที่ predicate เป็น false จึงทำงานในเวลา O(log n) แทน O(n)

WHY: หาเส้นแบ่ง ไม่ได้หาค่าที่เท่ากัน

นึกถึงแถวลูกค้าที่แยกคนมีคูปองไว้ด้านหน้าและไม่มีคูปองไว้ด้านหลัง เราต้องหา “คนแรกของฝั่งหลัง” ไม่ได้ถามว่าคนชื่ออะไร ฟังก์ชันนี้จึงรับ closure ที่ตอบจริง/เท็จ และต้องมีสมมติฐานสำคัญว่า slice ถูกแบ่งเป็นสองช่วงตาม closure นั้นแล้ว หากผลจริง-เท็จสลับไปมา index ที่ได้ไม่มีความหมายตามที่เราคาด

#[cfg(test)]
mod tests {
    #[test]
    fn finds_boundaries() {
        let scores = [10, 20, 20, 35, 50, 80];

        let first_at_least_35 = scores.partition_point(|&score| score < 35);
        let after_all_20s = scores.partition_point(|&score| score <= 20);

        assert_eq!(first_at_least_35, 3);
        assert_eq!(after_all_20s, 3);
        assert_eq!([1, 2, 3].partition_point(|_| false), 0);
        assert_eq!([1, 2, 3].partition_point(|_| true), 3);
        assert_eq!([0_i32; 0].partition_point(|_| true), 0);
    }
}

ผลลัพธ์อยู่ในช่วงศูนย์ถึงความยาวรวม: ได้ศูนย์เมื่อไม่มีสมาชิกใดผ่าน และได้ความยาวเมื่อผ่านทุกตัว จุดนี้ทำให้เอา index ไป split_at หรือ insert ได้สะดวก แต่การเข้าถึงสมาชิกที่ index ต้องเช็กกรณีเท่าความยาวก่อน

binary_search เหมาะเมื่อหา key ที่เท่ากันและคืนผลว่าเจอหรือ insertion index ส่วน partition_point เหมาะกับกติกาอย่าง “น้อยกว่าเกณฑ์”, “หมดอายุแล้ว” หรือ “สถานะเสร็จสิ้นอยู่ด้านหน้า” รวมถึงหา lower/upper bound ของค่าซ้ำได้ด้วย predicate แบบน้อยกว่าและน้อยกว่าหรือเท่ากับ

ข้อแลกเปลี่ยนคือ closure อาจถูกเรียกกับสมาชิกตามลำดับที่ไม่ต่อเนื่อง จึงควรเป็น pure predicate ไม่มี side effect และต้องไม่พึ่งจำนวนครั้งที่เรียก ถ้าข้อมูลยังไม่เรียงตามเงื่อนไข ให้ sort ก่อนหรือใช้ position แบบ linear ที่ซื่อสัตย์กว่า

Recap

  • predicate ต้องแบ่ง slice เป็นช่วงจริงแล้วตามด้วยเท็จ
  • index อาจเป็นศูนย์หรือเท่าความยาว
  • ใช้เงื่อนไขน้อยกว่าเพื่อหา lower bound
  • ใช้ position เมื่อข้อมูลไม่เรียงตามเงื่อนไข