algorithm - オンラインアルゴリズムとオフラインアルゴリズムの違いは何ですか？

Question

これらの用語は私のデータ構造の教科書で使用されていましたが、説明は非常に簡潔で不明確でした。計算の各段階でアルゴリズムがどれだけの知識を持っているかと関係があると思います。

（ウィキペディアのページにリンクしないでください。私はすでにそれを読んでいて、まだ説明を探しています。私が12歳であるかのような説明や例がはるかに役立つでしょう。）

Answer 1

ウィキペディア

ウィキペディアのページは非常に明確です。

コンピュータサイエンスでは、オンラインアルゴリズムは、入力全体を最初から利用できるようにすることなく、入力を1つずつ順番に処理できるアルゴリズムです。つまり、入力がアルゴリズムに供給される順序で処理できます。対照的に、オフラインアルゴリズムは最初から問題データ全体を与えられ、目前の問題を解決する答えを出力する必要があります。（たとえば、選択ソートでは、リストをソートする前にリスト全体を指定する必要がありますが、挿入ソートでは指定できません。）

上記について詳しく説明します。

オフラインアルゴリズムでは、アルゴリズムを開始する前にすべての情報が必要です。ウィキペディアの例では、ステップ1がであるため、選択ソートはオフラインFind the minimum value in the listです。これを行うには、リスト全体を利用できるようにする必要があります。そうでない場合、最小値をどのようにして知ることができますか？それはいけません。

対照的に、挿入ソートはオンラインです。これは、ソートする値について何も知る必要がなく、アルゴリズムの実行中に情報が要求されるためです。簡単に言えば、反復ごとに新しい値を取得できます。

まだはっきりしていませんか？

次の例を考えてみてください（4歳向け！）。デビッドはあなたに2つの問題を解決するように頼んでいます。

最初の問題で、彼は言います：

「私はあなたに異なる質量の2つのボールを与えるつもりです、そしてあなたはそれらをタワーから同時に落とす必要があります..ガリレオが正しいことを確認するためだけに。あなたは時計を使うことができません、私たちはただ眼球になりますそれ。"

私があなたにボールを1つだけ与えたとしたら、あなたはおそらく私を見て、あなたが何をしているのか疑問に思うでしょう。結局のところ、指示はかなり明確でした。問題の最初に両方のボールが必要です。これはオフラインアルゴリズムです。

2番目の問題について、Davidは言います

「さて、それはかなりうまくいきました、しかし今、私はあなたが先に進んで、フィールドを横切っていくつかのボールを蹴る必要があります。」

私は先に進み、あなたに最初のボールを与えます。あなたはそれを蹴ります。それから私はあなたに2番目のボールを与え、あなたはそれを蹴ります。私はあなたに3番目と4番目のボールを与えることもできます（私があなたにそれらを与えるつもりであったことさえあなたが知らなくても）。これはオンラインアルゴリズムの例です。実際のところ、あなたは一日中ボールを蹴っている可能性があります。

これが明確だったといいのですが：D

Answer 2

オンラインアルゴリズムは、入力を1つずつ処理し、アルゴリズムの開始時に実際の入力サイズを認識しません。

よく使用される例はスケジューリングです。マシンのセットがあり、未知のワークロードがあります。各マシンには特定の速度があります。できるだけ早くワークロードをクリアしたい。ただし、最初からすべての入力を把握しているわけではないため（キュー内の次の入力のみが表示されることが多い）、現在の入力に最適なマシンを見積もることしかできません。これにより、入力データを想定できないため、ワークロードの分散が最適化されない可能性があります。

一方、オフラインアルゴリズムは、完全な入力データでのみ機能します。アルゴリズムがデータの処理を開始する前に、すべてのワークロードを知る必要があります。

例：

ワークロード：
   1.単位（重量：1）
   2.単位（重量：1）
   3.単位（重量：3）
マシン：
   1.機械（1重量/時間）
   2.マシン（2ウェイト/時間）

考えられる結果（オンライン）：
   1.ユニット->2.マシン//2.マシンのワークロードは30分になりました
   2.ユニット->2.マシン//2.マシンのワークロードは1時間になりました
  また
   3.ユニット->1.マシン//1.マシンのワークロードは3時間になりました
  また
   3.ユニット->2.マシン//1.マシンのワークロードは2.5時間になりました

 ==>作業は2.5時間後に行われます

考えられる結果（オフライン）：
   1.ユニット->1.マシン//1.マシンのワークロードは1時間になりました
   2.ユニット->1.マシン//1.マシンのワークロードは2時間になりました
   3.ユニット->2.マシン//2.マシンのワークロードは1.5時間になりました

 ==>作業は2時間後に行われます

オフラインアルゴリズムでより良い結果が得られるのは、最初からより良いマシンを使用していないためです。重いユニット（ユニット3）があることはすでにわかっているので、このユニットは最速のマシンで処理する必要があります。

Answer 3

オフラインアルゴリズムは、呼び出された瞬間に入力データをすべて認識します。一方、オンラインアルゴリズムは、実行中に入力データの一部またはすべてを取得できます。

Answer 4

アルゴリズムは、実行されるデータが事前にわからない場合、オンラインであると言われます。オフラインアルゴリズムでは、すべてのデータが事前に表示される場合があります。

Answer 5

オンラインアルゴリズムは、一連の要求を受信し、各要求に応答して即時アクションを実行するアルゴリズムです。

対照的に、オフラインアルゴリズムは、すべての要求が実行された後にアクションを実行します。

リチャード・カープによるこの論文は、オンライン、オフラインのアルゴリズムに関するより多くの洞察を提供します。

Answer 6

アルゴリズムを処理する前の入力の可用性に基づいて、オフラインアルゴリズムとオンラインアルゴリズムを区別できます。

オフラインアルゴリズム：すべての入力情報はアルゴリズムで利用可能であり、アルゴリズムによって同時に処理されます。入力情報の完全なセットを使用して、アルゴリズムは入力を効率的に処理し、最適なソリューションを取得する方法を見つけます。

オンラインアルゴリズム：入力はオンザフライで行われます。つまり、すべての入力情報をアルゴリズムで同時に利用できるわけではなく、シーケンスとして、または時間の経過とともに部分的に利用できます。入力が利用可能になると、アルゴリズムは将来の入力情報を知らなくても即座に決定を下す必要があります。このプロセスでは、アルゴリズムは、全体的なパフォーマンスの最終的な品質に影響を与える一連の決定を生成します。

例：通信ネットワークでのルーティング：

さまざまなソースからのデータパケットが最も近いルーターに届きます。複数の通信リンクがルーターに接続されています。新しいデータパケットがルータに到着すると、ルータはデータパケットを送信するリンクをすぐに決定する必要があります。（すべてのリンクが宛先にルーティングされ、すべてのリンク帯域幅が同じであり、すべてのリンクが宛先への最短パスの一部であると想定します）。ここでの目的は、各リンクの負荷が分散されるように、将来のデータパケットを知らなくても、各着信データパケットをリンクの1つに割り当てることです。リンクをオーバーロードしないでください。これは負荷分散の問題です。

ここで、ルーターに実装されているスケジューラーは、将来のデータパケットについては認識していませんが、着信データパケットごとにスケジュールを決定する必要があります。対照的に、オフラインスケジューラは、すべての着信データパケットについて完全な知識を持っているため、データパケットをさまざまなリンクに効率的に割り当て、さまざまなリンク間で負荷を最適に分散できます。

Answer 7

キャッシュミスの問題：コンピュータシステムでは、キャッシュは、高速のプロセッサと低速のプライマリメモリ間の速度の不一致を回避するために使用されるメモリユニットです。キャッシュを使用する目的は、頻繁にアクセスされるページをキャッシュに保持することにより、平均アクセス時間を最小限に抑えることです。これらのページは、近い将来、プロセッサによって要求される可能性があると想定されています。一般に、ページ要求がプロセッサによって行われると、ページはプライマリまたはセカンダリメモリからフェッチされ、ページのコピーがキャッシュメモリに保存されます。キャッシュがいっぱいであるとすると、キャッシュに実装されたアルゴリズムは、将来のページ要求を知らなくても、キャッシュブロックを置き換えることを即座に決定する必要があります。問題が発生します：どのキャッシュブロックを置き換える必要がありますか？（最悪の場合、キャッシュブロックを交換し、次の瞬間に、置き換えられたキャッシュブロックに対するプロセッサ要求）。したがって、アルゴリズムは、要求シーケンス全体の事前知識がなくても、着信要求の到着時に即座に決定を下すように設計する必要があります。このタイプのアルゴリズムは、ONLINEALGORITHMとして知られています。