Python bisect key=: ค้นช่วงในข้อมูลเรียงโดยไม่เรียก key ซ้ำเกินจำเป็น

binary search ดูเหมือนจบที่ O(log n) แต่ระบบจริงอาจเสียเวลาในฟังก์ชันแปลง key มากกว่าการเปรียบเทียบครับ โมดูล bisect รองรับพารามิเตอร์ key เพื่อค้นรายการ object โดยไม่ต้องเขียน loop เอง ทว่า key ถูกเรียกซ้ำและผลไม่ถูกเก็บข้ามการค้น

WHY: แยกค่าที่ค้นจาก object ที่จัดเก็บ

bisect_left หา insertion point ทางซ้ายสุดที่ยังรักษาลำดับ จุดละเอียดคือ key ใช้กับสมาชิกใน list แต่ค่า x ที่ส่งเข้าไปต้องเป็นค่าใน key-space แล้ว ไม่ใช่ object ที่หวังให้ฟังก์ชัน key แปลงให้อีกที

มอง list เป็นชั้นหนังสือที่เรียงตามวันเผยแพร่ หนังสือคือ object แต่ป้ายที่ใช้เทียบคือวันที่ เมื่อถามตำแหน่ง เราต้องยื่นวันที่ ไม่ใช่หนังสืออีกเล่ม

HOW: ทำ contract ให้เห็นใน test

import unittest
from bisect import bisect_left


def first_at_or_after(rows, timestamp):
    return bisect_left(rows, timestamp, key=lambda row: row["at"])


def first_with_precomputed_keys(rows, keys, timestamp):
    index = bisect_left(keys, timestamp)
    return rows[index:]


class BisectTests(unittest.TestCase):
    def setUp(self):
        self.rows = [
            {"at": 10, "name": "a"},
            {"at": 20, "name": "b"},
            {"at": 20, "name": "c"},
            {"at": 40, "name": "d"},
        ]

    def test_left_boundary_with_duplicates(self):
        self.assertEqual(first_at_or_after(self.rows, 20), 1)

    def test_missing_value_returns_insertion_point(self):
        self.assertEqual(first_at_or_after(self.rows, 30), 3)

    def test_precomputed_keys_for_repeated_queries(self):
        keys = [row["at"] for row in self.rows]
        self.assertEqual(
            [row["name"] for row in first_with_precomputed_keys(self.rows, keys, 20)],
            ["b", "c", "d"],
        )


if __name__ == "__main__":
    unittest.main()

การค้นใช้ O(log n) comparisons แต่การ insert ลง list ยัง O(n) เพราะต้องเลื่อนสมาชิก ดังนั้น bisect เหมาะกับข้อมูลที่อ่านมากกว่าเขียน หากมี update ถี่และข้อมูลใหญ่ ควรพิจารณา database index หรือโครงสร้าง tree

เลือก optimization ให้ตรง workload

ค้นครั้งเดียวใช้ key ตรง ๆ อ่านง่ายสุด ค้นซ้ำบน list เดิมและ key แพงให้สร้าง list ของ keys คู่กัน ซึ่งใช้ memory O(n) แต่หลีกเลี่ยงการแปลงซ้ำ functools.cache เหมาะเมื่อ object/hash key มีความคงที่และ lifecycle ของ cache ชัดเจน แต่เสี่ยงโตไม่จำกัดหรือคืนค่าค้างหลัง object เปลี่ยน

อย่าแก้ list ระหว่างค้นจากหลาย thread โดยไม่มี synchronization เอกสารระบุว่าพฤติกรรมไม่รับประกันเมื่อ sequence ถูกแก้พร้อมกัน และต้องรักษา invariant ว่า list เรียงตาม key หลังทุก mutation

Recap

• key ใช้กับสมาชิก ส่วน x ต้องอยู่ใน key-space
• bisect_left เลือกขอบซ้าย จึงจัดการค่าซ้ำได้คาดเดา
• precompute keys เมื่อค้นซ้ำและ key มีต้นทุนสูง
• การ insert ยัง O(n); อย่าใช้แทน index สำหรับ write-heavy workload
• ปกป้อง sorted invariant และ concurrent mutation

วัดจำนวน query ต่อ snapshot ก่อนเพิ่ม cache เพราะ optimization ที่ดีต้องตอบ workload จริง ไม่ใช่แค่ Big-O บรรทัดเดียวครับ