「オンラインアルゴリズム」の版間の差分
Love love show(会話 | 投稿記録) |
m Bot作業依頼#Cite webの和書引数追加 |
||
| (5人の利用者による、間の6版が非表示) | |||
| 1行目: | 1行目: | ||
'''オンラインアルゴリズム'''（{{lang-en-short|Online algorithm}}）は、入力全体を最初からアクセス可能にしなくても、先頭から順に処理していける[[アルゴリズム]]を指す。これに対して、'''オフラインアルゴリズム'''（{{lang-en-short|Offline algorithm}}）は、問題を解くのに最初からデータ全体へのアクセスが必要なアルゴリズムを指す。例えば、[[挿入ソート]]はオンラインアルゴリズムで、[[選択ソート]]はオフラインアルゴリズムである。 |
'''オンラインアルゴリズム'''（{{lang-en-short|Online algorithm}}）は、入力全体を最初からアクセス可能にしなくても、先頭から順に処理していける[[アルゴリズム]]を指す。これに対して、'''オフラインアルゴリズム'''（{{lang-en-short|Offline algorithm}}）は、問題を解くのに最初からデータ全体へのアクセスが必要な[[バッチ処理]]型アルゴリズムを指す。例えば、[[挿入ソート]]はオンラインアルゴリズムで、[[選択ソート]]はオフラインアルゴリズムである。 |
||
また、[[時系列]]データを |
また、[[時系列]]データをリアルタイムに処理して未来を予測するようなアルゴリズムを特に「オンラインアルゴリズム」と呼ぶ場合もあり、その場合単に入力を蓄積せずに逐次的に処理するアルゴリズムを「ストリームアルゴリズム」と呼ぶ。 |
||
例として、有限な連結[[グラフ理論|グラフ]]における[[最短経路問題]]を考えてみよう。ひとつのノードが入力され、そこから次の連結されたノードが辿れるようなデータ形式の場合、単純かつ完全な探索をしないと問題が解けないのは明らかである。そこで、オンラインアルゴリズムの性能と理想的なオフラインアルゴリズムの性能（全てのデータが最初からわかっている状態）とを比較する Competitive Analysis という手法が新たに生まれた。 |
例として、有限な連結[[グラフ理論|グラフ]]における[[最短経路問題]]を考えてみよう。ひとつのノードが入力され、そこから次の連結されたノードが辿れるようなデータ形式の場合、単純かつ完全な探索をしないと問題が解けないのは明らかである。そこで、オンラインアルゴリズムの性能と理想的なオフラインアルゴリズムの性能（全てのデータが最初からわかっている状態）とを比較する Competitive Analysis という手法が新たに生まれた。 |
||
オンラインアルゴリズムは、データをあらかじめすべて用意したり、読みだしたりする必要がなく、少量のデータを逐次読み込んで処理を行うことが可能である。そのため、すべてのデータを保持しておくのが難しいような大規模データ（[[ビッグデータ]]）を扱う状況や、時々刻々とデータが与えられる状況においてよく用いられる<ref>{{ |
オンラインアルゴリズムは、データをあらかじめすべて用意したり、読みだしたりする必要がなく、少量のデータを逐次読み込んで処理を行うことが可能である。そのため、すべてのデータを保持しておくのが難しいような大規模データ（[[ビッグデータ]]）を扱う状況や、時々刻々とデータが与えられる状況においてよく用いられる<ref>{{Cite web|和書|title=オンラインアルゴリズムで平均値の逐次計算 |url=http://qiita.com/awakia/items/f58e90b3b2562d787aa5|accessdate=2014-10-05}}</ref>。また未来のデータに依拠せず、その時点までに得られたデータだけに依拠し、かつ逐次型で処理を行う特徴がある。 |
||
==オンラインアルゴリズムの例== |
|||
* [[粒子フィルタ]](Particle filter) |
* [[粒子フィルタ]] (Particle filter) |
||
* [[データ圧縮]]アルゴリズムの多くはストリームアルゴリズムである。[[LZSS]]、[[LZ77]] |
* [[データ圧縮]]アルゴリズムの多くはストリームアルゴリズムである。[[Lempel–Ziv–Storer–Szymanski|LZSS]]、[[LZ77]] |
||
==脚注== |
|||
{{reflist}} |
|||
==関連項目== |
==関連項目== |
||
2023年10月12日 (木) 03:51時点における最新版
オンラインアルゴリズム（英: Online algorithm）は、入力全体を最初からアクセス可能にしなくても、先頭から順に処理していけるアルゴリズムを指す。これに対して、オフラインアルゴリズム（英: Offline algorithm）は、問題を解くのに最初からデータ全体へのアクセスが必要なバッチ処理型アルゴリズムを指す。例えば、挿入ソートはオンラインアルゴリズムで、選択ソートはオフラインアルゴリズムである。
また、時系列データをリアルタイムに処理して未来を予測するようなアルゴリズムを特に「オンラインアルゴリズム」と呼ぶ場合もあり、その場合単に入力を蓄積せずに逐次的に処理するアルゴリズムを「ストリームアルゴリズム」と呼ぶ。
例として、有限な連結グラフにおける最短経路問題を考えてみよう。ひとつのノードが入力され、そこから次の連結されたノードが辿れるようなデータ形式の場合、単純かつ完全な探索をしないと問題が解けないのは明らかである。そこで、オンラインアルゴリズムの性能と理想的なオフラインアルゴリズムの性能（全てのデータが最初からわかっている状態）とを比較する Competitive Analysis という手法が新たに生まれた。
オンラインアルゴリズムは、データをあらかじめすべて用意したり、読みだしたりする必要がなく、少量のデータを逐次読み込んで処理を行うことが可能である。そのため、すべてのデータを保持しておくのが難しいような大規模データ（ビッグデータ）を扱う状況や、時々刻々とデータが与えられる状況においてよく用いられる[1]。また未来のデータに依拠せず、その時点までに得られたデータだけに依拠し、かつ逐次型で処理を行う特徴がある。
オンラインアルゴリズムの例
[編集]脚注
[編集]- ^ “オンラインアルゴリズムで平均値の逐次計算”. 2014年10月5日閲覧。
関連項目
[編集]参考文献
[編集]- Borodin, A.; El-Yaniv, R. (1998年). Online Computation and Competitive Analysis. Cambridge University Press. ISBN 0-521-56392-5
外部リンク
[編集] | この項目は、コンピュータに関連した書きかけの項目です。この項目を加筆・訂正などしてくださる協力者を求めています（PJ:コンピュータ/P:コンピュータ）。 |