โปรแกรมสร้างโครงสร้างข้อมูลตรวจสอบอัตราการร้องขอ (Rate Limiting) ใน Python

สมมติว่าเราต้องการพัฒนาโครงสร้างข้อมูลที่สร้างขึ้นพร้อมกับเวลาหมดอายุ (expire time) และรองรับฟังก์ชันที่รับรหัสผู้ใช้ (user_id) และ timestamp ฟังก์ชันนี้จะตรวจสอบว่าคำร้องขอของผู้ใช้ในเวลาที่กำหนดล้มเหลวหรือไม่ จะล้มเหลวก็ต่อเมื่อผู้ใช้เคยมีคำร้องขอที่สำเร็จภายในเวลาหมดอายุที่กำหนด

เช่น ถ้าอินพุตคือ expire = 6 สร้างอ็อบเจกต์ obj เรียก obj.limit(0,10), obj.limit(0,16), obj.limit(0,17) และ obj.limit(1,20) ผลลัพธ์จะเป็น False, False, True, False ตามลำดับ เนื่องจากผู้ใช้ 0 เริ่มต้นไม่มีคำร้องขอ จึงเป็น False ที่เวลา 16 ยังไม่เกิน expire time 6 จากคำร้องขอครั้งล่าสุดที่ 10 แต่ที่ 17 จึงเป็น True และคำร้องขอสุดท้ายเป็นของผู้ใช้ 1 จึงเป็น False

ขั้นตอนการแก้ปัญหา

1. กำหนด Constructor รับ expire
2. สร้าง lastCall เป็น Dictionary ที่ค่าเริ่มต้นคือ -1
3. เมธอด limit(uid, timestamp):
   • last := lastCall[uid]
   • ถ้า last == -1 หรือ last + expire <= timestamp:
     • lastCall[uid] := timestamp
     • คืน False
   • มิฉะนั้นคืน True

ตัวอย่างโค้ด

from collections import defaultdict

class RateLimit:
    def __init__(self, expire):
        self.expire = expire
        self.lastCall = defaultdict(lambda: -1)

    def limit(self, uid, timestamp):
        last = self.lastCall[uid]
        if last == -1 or last + self.expire <= timestamp:
            self.lastCall[uid] = timestamp
            return False
        return True

expire = 6
obj = RateLimit(expire)
print(obj.limit(0,10))
print(obj.limit(0,16))
print(obj.limit(0,17))
print(obj.limit(1,20))

อินพุต

RateLimit(6) obj.limit(0,10) obj.limit(0,16) obj.limit(0,17) obj.limit(1,20)

เอาต์พุต

False False True False