172

いくつかの疑似コード、またはより良い Python を使用できます。Python IRC ボットにレート制限キューを実装しようとしていますが、部分的には機能しますが、誰かが制限よりも少ないメッセージをトリガーした場合 (たとえば、レート制限が 8 秒あたり 5 メッセージで、その人がトリガーするメッセージは 4 つだけです)、次のトリガーが 8 秒を超えている (例: 16 秒後) 場合、ボットはメッセージを送信しますが、キューがいっぱいになり、ボットは 8 秒間待機しますが、8 秒間が経過したため必要ありません。

4

10 に答える 10

259

ここで最も単純なアルゴリズムは、メッセージがあまりにも早く到着したときにメッセージをドロップしたい場合（キューに入れるのではなく、キューが任意に大きくなる可能性があるため、理にかなっています）：

rate = 5.0; // unit: messages
per  = 8.0; // unit: seconds
allowance = rate; // unit: messages
last_check = now(); // floating-point, e.g. usec accuracy. Unit: seconds

when (message_received):
  current = now();
  time_passed = current - last_check;
  last_check = current;
  allowance += time_passed * (rate / per);
  if (allowance > rate):
    allowance = rate; // throttle
  if (allowance < 1.0):
    discard_message();
  else:
    forward_message();
    allowance -= 1.0;

このソリューションにはデータ構造やタイマーなどはなく、正常に機能します:)これを確認するには、「許容値」は最大で1秒あたり5/8ユニット、つまり8秒あたり最大5ユニットの速度で増加します。転送されるすべてのメッセージから1単位が差し引かれるため、8秒ごとに5つを超えるメッセージを送信することはできません。

整数である必要があることに注意してrateください。つまり、ゼロ以外の小数部分がない場合、アルゴリズムは正しく機能しません（実際のレートは機能しませんrate/per）。たとえば、1.0に成長することはrate=0.5; per=1.0;ないため、機能しません。allowanceしかし、rate=1.0; per=2.0;正常に動作します。

于 2009-03-20T23:15:27.253 に答える
52

エンキューする関数の前に、このデコレータ @RateLimited(ratepersec) を使用してください。

基本的に、これは前回から 1/rate 秒が経過したかどうかをチェックし、経過していない場合は残りの時間待機し、そうでない場合は待機しません。これにより、レート/秒に効果的に制限されます。デコレーターは、レート制限が必要な任意の関数に適用できます。

あなたの場合、8 秒あたり最大 5 メッセージが必要な場合は、sendToQueue 関数の前に @RateLimited(0.625) を使用します。

import time

def RateLimited(maxPerSecond):
    minInterval = 1.0 / float(maxPerSecond)
    def decorate(func):
        lastTimeCalled = [0.0]
        def rateLimitedFunction(*args,**kargs):
            elapsed = time.clock() - lastTimeCalled[0]
            leftToWait = minInterval - elapsed
            if leftToWait>0:
                time.sleep(leftToWait)
            ret = func(*args,**kargs)
            lastTimeCalled[0] = time.clock()
            return ret
        return rateLimitedFunction
    return decorate

@RateLimited(2)  # 2 per second at most
def PrintNumber(num):
    print num

if __name__ == "__main__":
    print "This should print 1,2,3... at about 2 per second."
    for i in range(1,100):
        PrintNumber(i)
于 2009-03-20T19:51:44.137 に答える
30

トークン バケットの実装は非常に簡単です。

5 つのトークンを含むバケットから始めます。

5/8 秒ごと: バケットのトークンが 5 つ未満の場合は、1 つ追加します。

メッセージを送信するたびに: バケットにトークンが 1 つ以上ある場合は、トークンを 1 つ取り出してメッセージを送信します。それ以外の場合は、メッセージを待機/ドロップします。

(明らかに、実際のコードでは、実際のトークンの代わりに整数カウンターを使用し、タイムスタンプを保存することで 5/8 秒ごとのステップを最適化できます)

質問をもう一度読んで、レート制限が 8 秒ごとに完全にリセットされる場合、ここに変更があります。

タイムスタンプ から始めlast_sendます。また、同じ 5 トークン バケットから始めます。

5/8 秒ごとのルールを実行します。

メッセージを送信するたびに: まず、last_send8 秒以上前かどうかを確認します。その場合、バケットを埋めます (5 トークンに設定します)。次に、バケットにトークンがある場合は、メッセージを送信します (そうでない場合は、ドロップ/待機など)。第三に、今に設定last_sendします。

それはそのシナリオでうまくいくはずです。

私は実際に、このような戦略 (最初のアプローチ) を使用して IRC ボットを作成しました。Python ではなく Perl で作成されていますが、説明するコードを次に示します。

ここの最初の部分は、バケットへのトークンの追加を処理します。時間に基づいてトークンを追加する最適化 (最後の行から 2 行目) を確認でき、最後の行はバケットの内容を最大にクランプします (MESSAGE_BURST)。

    my $start_time = time;
    ...
    # Bucket handling
    my $bucket = $conn->{fujiko_limit_bucket};
    my $lasttx = $conn->{fujiko_limit_lasttx};
    $bucket += ($start_time-$lasttx)/MESSAGE_INTERVAL;
    ($bucket <= MESSAGE_BURST) or $bucket = MESSAGE_BURST;

$conn は、渡されるデータ構造です。これは、定期的に実行されるメソッドの内部にあります (次に行うべきことがいつになるかを計算し、その時間またはネットワーク トラフィックを取得するまでスリープします)。メソッドの次の部分は、送信を処理します。メッセージには優先度が関連付けられているため、かなり複雑です。

    # Queue handling. Start with the ultimate queue.
    my $queues = $conn->{fujiko_queues};
    foreach my $entry (@{$queues->[PRIORITY_ULTIMATE]}) {
            # Ultimate is special. We run ultimate no matter what. Even if
            # it sends the bucket negative.
            --$bucket;
            $entry->{code}(@{$entry->{args}});
    }
    $queues->[PRIORITY_ULTIMATE] = [];

これが最初のキューで、何があっても実行されます。フラッディングのために接続が切断されたとしても。サーバーの PING への応答など、非常に重要なことに使用されます。次に、残りのキュー:

    # Continue to the other queues, in order of priority.
    QRUN: for (my $pri = PRIORITY_HIGH; $pri >= PRIORITY_JUNK; --$pri) {
            my $queue = $queues->[$pri];
            while (scalar(@$queue)) {
                    if ($bucket < 1) {
                            # continue later.
                            $need_more_time = 1;
                            last QRUN;
                    } else {
                            --$bucket;
                            my $entry = shift @$queue;
                            $entry->{code}(@{$entry->{args}});
                    }
            }
    }

最後に、バケットのステータスが $conn データ構造に保存されます (実際には、このメソッドの少し後で、次の作業がどれくらい早く行われるかを最初に計算します)。

    # Save status.
    $conn->{fujiko_limit_bucket} = $bucket;
    $conn->{fujiko_limit_lasttx} = $start_time;

ご覧のとおり、実際のバケット処理コードは非常に小さく、約 4 行です。コードの残りの部分は、優先キューの処理です。ボットには優先キューがあるため、たとえば誰かがボットとチャットしていても、重要なキック/禁止の任務を遂行するのを妨げることはできません。

于 2009-03-20T19:04:30.803 に答える
12

メッセージを送信できるようになるまで処理をブロックして、さらにメッセージをキューに入れるには、antti の美しいソリューションを次のように変更することもできます。

rate = 5.0; // unit: messages
per  = 8.0; // unit: seconds
allowance = rate; // unit: messages
last_check = now(); // floating-point, e.g. usec accuracy. Unit: seconds

when (message_received):
  current = now();
  time_passed = current - last_check;
  last_check = current;
  allowance += time_passed * (rate / per);
  if (allowance > rate):
    allowance = rate; // throttle
  if (allowance < 1.0):
    time.sleep( (1-allowance) * (per/rate))
    forward_message();
    allowance = 0.0;
  else:
    forward_message();
    allowance -= 1.0;

メッセージを送信するのに十分な余裕ができるまで待つだけです。レートの 2 倍で開始しないように、許容値を 0 に初期化することもできます。

于 2011-06-20T17:39:35.310 に答える
2

最後の 5 行が送信された時刻を保持します。5 番目に新しいメッセージ (存在する場合) が過去 8 秒以上経過するまで、キューに入れられたメッセージを保持します (時間の配列として last_five を使用)。

now = time.time()
if len(last_five) == 0 or (now - last_five[-1]) >= 8.0:
    last_five.insert(0, now)
    send_message(msg)
if len(last_five) > 5:
    last_five.pop()
于 2009-03-20T19:18:10.367 に答える
1

受け入れられた回答からのコードの単なるPython実装。

import time

class Object(object):
    pass

def get_throttler(rate, per):
    scope = Object()
    scope.allowance = rate
    scope.last_check = time.time()
    def throttler(fn):
        current = time.time()
        time_passed = current - scope.last_check;
        scope.last_check = current;
        scope.allowance = scope.allowance + time_passed * (rate / per)
        if (scope.allowance > rate):
          scope.allowance = rate
        if (scope.allowance < 1):
          pass
        else:
          fn()
          scope.allowance = scope.allowance - 1
    return throttler
于 2016-10-20T09:52:31.630 に答える
0

これはどう：

long check_time = System.currentTimeMillis();
int msgs_sent_count = 0;

private boolean isRateLimited(int msgs_per_sec) {
    if (System.currentTimeMillis() - check_time > 1000) {
        check_time = System.currentTimeMillis();
        msgs_sent_count = 0;
    }

    if (msgs_sent_count > (msgs_per_sec - 1)) {
        return true;
    } else {
        msgs_sent_count++;
    }

    return false;
}
于 2009-06-01T22:58:49.223 に答える