5

(疑似コード) のような命令のループがあります。

for i = 1 to 1000000
    // Process the ith input
    doSomething(input[i])
end

これは完了するまでに長い時間がかかります。ある種の進行状況と、さらに重要な残り時間の見積もりをユーザーに出力して、親指をいじってそこに座っているか、コーヒーを飲みに行くか、散歩に行くか、1週間の休暇に行くかを決定できるようにしたいと思いますアルゴリズムがその数字を処理している間、ヨーロッパへ。

問題を単純化するために、反復回数が多いと想定できます (たとえば、100 を超えると、すべてのパーセンタイルで進行状況を出力できます)。

一般的なアルゴリズムは、最後の反復にかかった時間を単純に測定し、それを残りの反復回数で乗算して出力として与えることです。これは、各反復で実行にかかる時間が大きく異なる場合、うまくいきません。

もう 1 つの方法は、最初の反復から経過した時間を完了した反復の数で割り、それを残りの反復で乗算することです。反復の期間が均等に分散されていない場合、これはうまくいきません。たとえば、最初のいくつかの入力が「難しく」、入力配列の最後に向かって簡単になる場合、アルゴリズムは、ほぼ終了するまで残り時間を過大評価します (その時点で、わずかに過大評価します)。

では、各反復にかかる時間が非単純な恣意的な関数 (各反復の完了までの時間を単純に分析的に導出して実装することは非現実的) である場合、どのようにして残り時間をより適切に見積もることができますか? ?

私が想像できる 2 つのアイデアは実りある研究手段かもしれませんが、現時点では自分自身を完全に探求することはできません。

  • 過去の各反復を完了するまでの時間に残りの反復を掛けた指数平均。
  • 各反復を完了するのに使用される時間を追跡し、関数を適合させて外挿します。

計算量の多いソリューション (フィッティング方程式など) が問題ない理由:

まず、この議論が価値のある真に大規模なタスクの場合、実行時間は数時間または数日で測定される場合があります。最近の複雑な数学演算は数ミリ秒かかるため、追加の負担は大きくありません.上記の例では、明らかに、doSomething数学を行うコストを小さくするほど時間がかかります.最初の場所。

次に、たとえば反復をパーセンタイルにビン化することができます。次に、「反復完了対所要時間」のデータセットを操作する代わりに、推定器は最大 100 個のデータ ポイントを持つ「完了率対所要時間」のデータセットを操作します。これにより、さらに複雑になります。タスクが完了するまでに 1 日以上かかるとします。各パーセンテージが完了するまで残り時間を 1 回だけ見積もるということは、推定関数の 100 回の評価を意味します。すでに 1 日を費やしている場合、残り時間を見積もるために 1 分半余分に費やすことは大したことではありませんが、それでも方程式をフィッティングするための 1 秒のウィンドウがすでに与えられています。最新のシステムで。そのため、私は計算集約型のソリューションを歓迎します。

tl;dr:非常に時間のかかるタスクに対して、正確な残り時間推定関数をオーバーエンジニアリングする方法。

4

3 に答える 3

2

一貫して適切な予測を取得したい場合は、2 番目の方法 (適合と外挿) が最適である可能性がありますが、フィッティング関数がインデックスの関数としての処理時間の真の依存性に合理的に一致するという前提に限られます。たとえば、f(n) が O(n^2) アルゴリズムの場合、

for i = 1 to N
  f(i)

解くのに約 k*N^3 時間がかかります。そのため、合計時間に 3 次を当てはめると、かなり良い近似が得られるはずですが、2 次または指数関数を当てはめると、単純な完成率の近似よりも悪くなる可能性があります。同様に、f が O(2^n) の場合、多項式の当てはめは残り時間を大幅に過小評価します。これはすべて、N が十分に大きく、真の O(n^2) 動作が支配的であることを前提としています。

したがって、適切に選択されたフィッティング関数は残り時間を正確に予測できるはずですが、一般的な予測関数は役に立たない可能性があります。

于 2012-08-20T04:20:11.933 に答える
0

私は以前にこのようなことをしたことがあります。かなり正確な時間の見積もりを作成するために私が見つけた最も簡単な方法は、次のとおりです（これもpコードで）：

initTime = getTime()
for i = 0 to maxIter
    doSomething()
    remainTime = convertToHoursMinutes(((getTime - initTime)/i)*maxIter)
next

このようにして、反復ごとの「平均」時間を短縮し、30 ～ 50 回の反復の後、ユーザーは残り時間について良い考えを持つことができます (最終的に、中心極限定理が働きます)。

于 2012-08-20T01:07:53.060 に答える