Pythonで特定の条件で処理されるリクエストの数をチェックするプログラム

各リストに[uid、time_sec]などの要素が含まれているリクエストのリストがあるとします（uidはユーザーID、time_secはタイムスタンプです）。これは、IDがuidのユーザーがタイムスタンプtime_secにWebサイトに要求したことを示します。また、2つの値uとgがあります。ここで、uは、特定のuidに対して60秒未満のフレームで許可されるリクエストの最大数を示し、gは、60秒未満のフレームでグローバルに許可されるリクエストの最大数です。ここで、各リクエストを1つずつ処理し、レート制限する場合。また、複数のユーザーから同時にリクエストがあった場合は、uidの低いリクエストが最初に処理されます。それ以外の場合、そのリクエストはドロップされます。正常に処理されるリクエストの総数を見つける必要があります。

したがって、入力がrequests =[[0、1]、[1、2]、[1,3]] u =1 g =5のような場合、ユーザー0と1はで送信できるため、出力は2になります。時間1と2ですが、1人のユーザーが60秒のフレームで最大1つのリクエストを送信できるため、ユーザー1からの2番目のリクエストは処理されません。

これを解決するには、次の手順に従います-

• 最後：=空の地図
• total：=空の両端キュー
• windowtime：=60
• リクエストを時間に基づいて並べ替えます。同じ場合は、uidに基づいて並べ替えます
• 金額：=0
• リクエストのrごとに、
  • [uid、time]：=r
  • 合計のサイズ>0および合計[0]+ウィンドウ時間<=時間、実行
    • 合計の左側のアイテムを削除
  • last [uid]>0およびlast[uid、0] + windowtime <=time、do
    のサイズ
    • 最後の[uid]から左のアイテムを削除します
  • 合計のサイズ
  • 最後の[uid]の最後に時間を挿入します
  • 合計の最後に時間を挿入
  • 金額：=金額+ 1

理解を深めるために、次の実装を見てみましょう-

例

from collections import defaultdict, deque
class Solution:
   def solve(self, requests, u, g):
      last = defaultdict(deque)
      total = deque()

      windowtime = 60
      requests.sort(key=lambda x: [x[1], x[0]])

      amount = 0
      for r in requests:
         uid, time = r

         while len(total) > 0 and total[0] + windowtime <= time:
            total.popleft()

         while len(last[uid]) > 0 and last[uid][0] + windowtime <= time:
            last[uid].popleft()

         if len(total) < g and len(last[uid]) < u:
            last[uid].append(time)
            total.append(time)
            amount += 1
      return amount
     
ob = Solution()
requests = [[0, 1],[1, 2],[1,3]]
u = 1
g = 5
print(ob.solve(requests, u, g))

入力

[[0, 1],[1, 2],[1,3]], 1, 5

出力

2