Algorithms That Finish In Time: A Complexity Gut Check

คุณเขียนฟังก์ชัน รันบนข้อมูลทดสอบของคุณ และมันทำงานได้ดี แล้วมันเข้าไปยังข้อมูลการผลิต — 500,000 แถว แทนที่จะเป็น 500 — และคำขอหมดเวลา สิ่งนี้เกิดขึ้นอย่างต่อเนื่อง และเกือบทั้งหมดเป็นปัญหาความซับซ้อนที่ซ่อนตัวอยู่เบื้องหลังรหัสที่ดูสมเหตุสมผลในขนาดเล็ก

ทำไมแล็ปท็อปของคุณถึงโกหกคุณ

อัลกอริทึม O(n²) ที่ทำงานบนรายการ 100 รายการทำให้เกิด 10,000 การดำเนินการ ในเครื่องใด ๆ นั่นเป็นไปได้ทันที รันอัลกอริทึมเดียวกันบนรายการ 100,000 รายการ และคุณจะอยู่ที่ 10 พันล้านการดำเนินการ — นาทีหรือชั่วโมงแทนที่จะเป็นมิลลิวินาที การกระโดดจาก n ไป n² ไม่รู้สึกอันตรายจนกว่า n จะใหญ่ขึ้น ซึ่งเป็นเหตุผลว่าทำไมมันถึงลื่นผ่านการตรวจสอบรหัสและการทดสอบในท้องถิ่น

ตัวอย่างคลาสสิก: การตรวจหาซ้ำด้วยลูปแบบซ้อน

def has_duplicates(items):
    for i in range(len(items)):
        for j in range(i + 1, len(items)):
            if items[i] == items[j]:
                return True
    return False

นี่คือ O(n²) สลับมันเป็นชุด:

def has_duplicates(items):
    seen = set()
    for item in items:
        if item in seen:
            return True
        seen.add(item)
    return False

ตอนนี้มันคือ O(n) การค้นหาชุดเป็นค่าเฉลี่ย O(1) ดังนั้นฟังก์ชันทั้งหมดจึงปรับขนาดเชิงเส้นแทนที่จะเป็นกำลังสอง บน 10,000 รายการ นั่นคือความแตกต่างระหว่าง 100 ล้านการเปรียบเทียบและ 10,000

วัดก่อนที่คุณจะเพิ่มประสิทธิภาพ

อย่าเดา ใช้ timeit สำหรับการเปรียบเทียบขนาดเล็ก:

import timeit
timeit.timeit(lambda: has_duplicates(list(range(5000))), number=10)

สำหรับฟังก์ชันที่ใหญ่ขึ้น โปรไฟล์กับ cProfile:

python -m cProfile -s cumulative myscript.py

ดูที่คอลัมน์ cumtime ถ้าฟังก์ชันหนึ่งกินเวลารันไทม์ 90% นั่นคือเป้าหมายของคุณ การเพิ่มประสิทธิภาพรหัสที่ไม่ใช่จุดคอขวดจะเสียเวลาของคุณและเพิ่มความซับซ้อนโดยไม่ได้รับ

รูปแบบทั่วไปที่ค่อยๆ ช้าลง

การตรวจสอบการเป็นสมาชิกของรายการซ้ำแล้วซ้ำอีก if x in my_list คือ O(n) สำหรับรายการแต่ O(1) เฉลี่ยสำหรับชุดหรือ dict ถ้าคุณกำลังตรวจสอบการเป็นสมาชิกภายในลูป การตรวจสอบ O(n) นั้นในลูป O(n) ให้ O(n²) โดยรวม สลับรายการสำหรับชุดและคุณจะกลับไป O(n)

การต่อสตริงในลูป ใน Python result += chunk ในลูปบนสตริงคือ O(n²) ในกรณีที่เลวร้ายที่สุด เนื่องจากสตริงไม่เปลี่ยนรูป และการต่อสตริงแต่ละครั้งก็คัดลอกทั้งหมด ใช้ ''.join(chunks) แทน — มันสร้างสตริงเพียงครั้งเดียว

การเรียงลำดับเมื่อคุณไม่จำเป็นต้อง sorted() คือ O(n log n) ถ้าคุณเรียกมันในลูปเพื่อค้นหา max หรือ min เท่านั้นในแต่ละการทำซ้ำ ใช้ max()/min() (O(n)) หรือดีกว่านั้น ฮีป (heapq) ถ้าคุณต้องการส่วนปลายวิ่งซ้ำแล้วซ้ำอีก heapq.nlargest(k, data) คือ O(n log k) ราคาถูกกว่ามากเมื่อเปรียบเทียบกับการเรียงลำดับรายการทั้งหมดเมื่อ k มีขนาดเล็ก

ฟังก์ชันเรียกซ้ำโดยไม่มีการจดจำ Fibonacci แบบไร้เดียวพลันคือ O(2ⁿ) เพราะมันคำนวณปัญหาย่อยเดียวกันซ้ำแล้วซ้ำอีก เพิ่ม functools.lru_cache และมันลดลงเป็น O(n):

from functools import lru_cache

@lru_cache(maxsize=None)
def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

อ่าน Big O จากรหัสจริง อย่างรวดเร็ว

นับลูปแบบซ้อนของอินพุตเดียวกัน — นั่นมักจะเป็นเลขชี้กำลังของคุณ ลูปเดียวคือ O(n) ลูปในลูปคือ O(n²) เว้นแต่ช่วงของลูปด้านในจะหดตัว (เช่นในรูปแบบเหมาะสมที่สุดของฟองจัดเรียง ยังคงเป็น O(n²) กรณีที่เลวร้ายที่สุด แต่มีการเปรียบเทียบน้อยลง) การเรียกซ้ำที่แยกปัญหาออกเป็นครึ่งหนึ่ง เช่น การค้นหาแบบไบนารีหรือการรวมการเรียงลำดับ ชี้ไป O(log n) หรือ O(n log n) การเรียกซ้ำที่แยกออกเป็นหลายการเรียกต่อระดับ เช่น Fibonacci ที่ไร้เดียวพลัน ชี้ไปเวลาเลขชี้กำลัง — สัญญาณที่แข็งแกร่งว่าคุณต้องการการจดจำหรือการเขียนใหม่แบบวนซ้ำ

นิสัยที่ดี: ก่อนที่คุณจะเขียนลูปแบบซ้อนหรือการเรียกซ้ำบนข้อมูลที่หันหน้าไปหาผู้ใช้ ถามว่า n อาจเป็นอะไรได้จริงในการผลิต ไม่ใช่ในไฟล์ทดสอบของคุณ ถ้า n สามารถกระทบหกหลัก โซลูชัน O(n²) จำเป็นต้องคิดสองครั้งก่อนที่จะส่งไป

สำหรับข้อมูลเพิ่มเติมเกี่ยวกับการวิเคราะห์ความซับซ้อน อัลกอริทึมการเรียงลำดับ และเครื่องมือโปรไฟล์ ให้ตรวจสอบส่วน Python และ Computer Science บน Korra Studio