0

レート制限する API を使用しているため、URL に頻繁にアクセスすると、要求を待機して再試行する必要があります。議論のために、特定のレート制限のしきい値が何であるかがわからない(知っていたとしても、アプリにハードコードしたくない)としましょう。

API 呼び出しを行って、それが成功するのを確認するか、レート制限されているという応答を受け取ってすぐに再試行し、API を正常に完了するまでのすべての試行の合計時間を記録できます。電話。

レート制限に達した後、API 呼び出しを再試行する前に待機する必要がある最小時間を予測するには、どのアルゴリズムが適していますか?

4

1 に答える 1

0

片側二分探索のようなものを使用してください。

The Algorithm Design Manual の 134 ページを参照してください。

ここで、一連の 0 とそれに続く無制限の一連の 1 で構成される配列Aがあり、それらの間の遷移の正確なポイントを特定したいとします。配列内の要素数にバインドされたnがある場合、配列の二分探索は⌈lg n ⌉テストで遷移点を提供します。そのような境界がない場合、最初の境界が見つかるまで、より大きな間隔 (A[1]、A[2]、A[4]、A[8]、A[16]、...) で繰り返しテストできます。非ゼロ値。これで、ターゲットを含むウィンドウができ、二分探索を続行できます。この片側二分探索は、最大2 ⌈lg(p)⌉を使用して遷移点pを見つけます。 配列が実際にどれだけ大きいかに関係なく、比較します。片側二分探索は、おそらく現在の位置の近くにあるキーを探しているときに最も役立ちます。

于 2013-06-10T10:48:47.783 に答える