Python bisect กับ key: แทรก record ลงลิสต์เรียงโดยไม่สร้าง key list ใหม่

เรามักเก็บ record เรียงตามเวลา คะแนน หรือ priority แล้วต้องหาแถวแทรกของชิ้นใหม่ การสร้างลิสต์ key ทุกครั้งแล้ว binary search ทำงานได้แต่ copy ข้อมูลซ้ำ โมดูล bisect รับ key= เพื่อดึงค่าจาก record ระหว่างค้นหาได้โดยตรง จุดที่ชวนงงคือฟังก์ชันค้นหาใช้ key กับสมาชิกในลิสต์ แต่ ไม่ใช้ key กับค่า x ที่ส่งเข้า bisect_left ครับ

WHY: ชั้นเรียงตามป้าย ไม่ได้เรียงตามตัวการ์ดทั้งใบ

ให้นึกถึงแฟ้มที่เรียงตามตัวเลข priority บนสันแฟ้ม ตอนหาช่อง เราถือเลข priority ไปเทียบกับป้ายบนแฟ้ม ไม่ได้เอาแฟ้มใหม่ทั้งใบไปเทียบ นี่คือสัญญาของ bisect_left(records, priority, key=lambda r: r.priority)

ส่วน insort_left/right ต่างออกไป: มันใช้ key กับ x เพื่อค้นหา แล้วแทรก record x จริงเข้า list ความต่างนี้ทำให้ wrapper ที่ตั้งชื่อ parameter ชัดช่วยได้มาก

HOW: หา range และแทรก record ที่ key ซ้ำ

import unittest
from bisect import bisect_left, bisect_right, insort_right
from dataclasses import dataclass


@dataclass(frozen=True)
class Job:
    priority: int
    name: str


def equal_priority_range(jobs: list[Job], priority: int) -> tuple[int, int]:
    by_priority = lambda job: job.priority
    return (
        bisect_left(jobs, priority, key=by_priority),
        bisect_right(jobs, priority, key=by_priority),
    )


class BisectKeyTests(unittest.TestCase):
    def test_finds_all_jobs_with_same_priority(self):
        jobs = [Job(1, "lint"), Job(3, "test"), Job(3, "build"), Job(8, "ship")]
        self.assertEqual(equal_priority_range(jobs, 3), (1, 3))

    def test_insort_right_places_new_equal_key_after_existing_items(self):
        jobs = [Job(1, "lint"), Job(3, "test"), Job(3, "build"), Job(8, "ship")]
        insort_right(jobs, Job(3, "scan"), key=lambda job: job.priority)
        self.assertEqual([job.name for job in jobs], ["lint", "test", "build", "scan", "ship"])

    def test_empty_list(self):
        self.assertEqual(equal_priority_range([], 4), (0, 0))


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

bisect_left คืนขอบซ้ายก่อนค่าที่เท่ากัน ส่วน bisect_right คืนขอบขวาหลังค่าที่เท่ากัน คู่กันจึงหา range ของ key ซ้ำได้โดยไม่ scan ทั้งลิสต์ insort_right ใช้ขอบขวา จึงวาง record ใหม่หลังกลุ่มเดิมตามตัวอย่าง แต่คำว่า right ไม่ได้สร้าง guarantee เพิ่มเรื่อง stability หาก key หรือ list ถูกแก้ระหว่างทำงาน

O(log n) ไม่ได้แปลว่าแทรกเร็วทั้งก้อน

การหา index เป็น O(log n) แต่การ list.insert ต้องเลื่อนสมาชิกท้ายและเป็น O(n) เอกสาร Python ย้ำว่าขั้น insert มักครองต้นทุน ถ้ามี insertion ถี่มากหรือข้อมูลหลักล้านรายการ ให้พิจารณา heap สำหรับ priority queue, database index, tree/sorted collection หรือสะสม batch แล้ว sort ครั้งเดียว

key อาจถูกเรียกซ้ำระหว่างค้นหาและผลไม่ได้ cache อัตโนมัติ จึงควรเป็น pure function ที่เร็ว อย่าอ่านไฟล์, network หรือคำนวณหนักใน key ถ้าคำนวณแพง ให้เก็บ key ไว้ใน record หรือ maintain ลิสต์ key คู่กันโดยมี invariant และ test ชัดเจน

Sorted invariant สำคัญกว่าตัวฟังก์ชัน

bisect ไม่ตรวจว่าลิสต์เรียงอยู่จริง ถ้าแก้ priority ของ object ที่อยู่ใน list ผลค้นหาอาจผิดแบบไม่มี exception ตัวอย่างใช้ dataclass แบบ frozen เพื่อกันการเปลี่ยน field หลังแทรก ถ้าต้องแก้ priority ให้ลบ record แล้วแทรกใหม่

เอกสารยังบอกว่าฟังก์ชันในโมดูลนี้ไม่ thread-safe สำหรับลิสต์เดียวกัน หากหลาย thread แทรกพร้อมกัน sorted invariant อาจพัง ต้องล็อกทั้งช่วง “หา index + insert” หรือให้ owner thread เดียวจัดคิว

Recap

• bisect_left/right ใช้ key กับสมาชิก แต่ x คือค่า key ที่ค้น
• insort ใช้ key กับ record ที่จะแทรก
• รักษา sorted invariant และอย่าแก้ key ของสมาชิกในที่เดิม
• จำว่า search O(log n) แต่ insertion ใน list O(n)
• ทำ key ให้เร็ว, pure และล็อก operation ทั้งชุดเมื่อแชร์ข้าม thread

ถ้าต้อง query มากกว่า insert ลิสต์เรียงกับ bisect เรียบง่ายและคุ้มครับ แต่ถ้า insert เป็นงานหลัก ให้ benchmark โครงสร้างอื่นก่อนผูก API เข้ากับ production