時間と空間のトレードオフ

ウィキペディア

時間と空間のトレードオフ

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/04/29 06:36 UTC 版)

計算機科学における時間と空間のトレードオフ（じかんとくうかんのトレードオフ、英: space-time tradeoff）または時間と記憶域のトレードオフ（じかんときおくいきのトレードオフ、英: time-memory tradeoff、タイム・メモリ・トレードオフ）とは、メモリの使用量が削減できる代わりにプログラムの速度が低下する、または逆に、計算にかかる時間を削減できる代わりにメモリの使用量が増える、という状況のことを言う。

時間と空間がトレードオフの関係にある場合、最適な選択は、CPUの速度、RAMの量、ハードディスクの容量の価格比によって大きく異なる。しばしば、時間と空間のトレードオフを利用して、問題の複雑性クラスを変えるというテクニックも使用される。

時間と空間のトレードオフの例として最も一般的なのはルックアップテーブルを利用したアルゴリズムである。テーブルの全てを最初から持つようにした実装では、処理時間は削減できるが、必要なメモリの量は増加する。また、テーブルの要素をその都度計算することもでき、これは計算時間は増加するが、必要なメモリの量を削減できる。

時間と空間のトレードオフは、データストレージにも当てはまる。データを圧縮せずに保存すると、圧縮した場合と比べ、消費する容量は多く、必要な時間は短くなる。データの圧縮によって保存に必要な領域を減らすことができるが、データ圧縮処理を行う時間が必要になる。どちらが適切かは場合によって異なる。

もう一つの例として、数式をウィキペディアで表示する方法が挙げられる。LaTeXのソースだけを保存しておき、ページを表示する度にそれをレンダリングする方法をとれば、時間はかかるが、記憶装置の使用量は少なくて済み、空間を時間でまかなうことができる。ページが保存されたときに画像をレンダリングし、それを保存しておく方法をとれば、記憶装置の使用量は多くなるが、時間は短くて済み、時間を空間でまかなうことができる。

時間と空間のトレードオフを利用して実行時間を短くしているアルゴリズムとして、離散対数の計算で利用されるベビーステップジャイアントステップアルゴリズムがある。

他の分野では、暗号システムに対する総当たり攻撃におけるレインボーテーブルの作成が、時間と空間のトレードオフにあたる。中間一致攻撃も時間と空間のトレードオフの応用である。

外部リンク

• Philippe Oechslin: Making a Faster Cryptanalytic Time-Memory Trade-Off.
• Once Upon a Time-Memory Tradeoff.
• Password Cracking and Time-Memory Trade Off - ウェイバックマシン（2009年2月8日アーカイブ分）

ウィキペディア小見出し辞書

時間と空間のトレードオフ

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/04/15 02:21 UTC 版)

「コラッツの問題」の記事における「時間と空間のトレードオフ」の解説

上記の パリティシーケンス により、コラッツ数列の計算の高速化が可能である。 （パリティシーケンス節の f 関数を使ったとして）k ステップ先にジャンプするために、まず現在の数値を2つに分割する： b（2進数表記で下位 k ビット）と、a（残りの上位ビット）。k ステップをジャンプした結果は以下になる： f k ( a   2 k + b ) = a   3 c ( b ) + d ( b ) . c (もしくは 3c)と d 配列は、k ビットの数すべてについて事前計算しておく。d(b) は b に f 関数を k 回行った数で、c(b) はその間に登場した奇数の数である。例えば k = 5 なら5ステップのジャンプが可能で、そのために下位5ビットを分割して、下記配列を使う： c ( 0 … 31 ) = { 0 , 3 , 2 , 2 , 2 , 2 , 2 , 4 , 1 , 4 , 1 , 3 , 2 , 2 , 3 , 4 , 1 , 2 , 3 , 3 , 1 , 1 , 3 , 3 , 2 , 3 , 2 , 4 , 3 , 3 , 4 , 5 } d ( 0 … 31 ) = { 0 , 2 , 1 , 1 , 2 , 2 , 2 , 20 , 1 , 26 , 1 , 10 , 4 , 4 , 13 , 40 , 2 , 5 , 17 , 17 , 2 , 2 , 20 , 20 , 8 , 22 , 8 , 71 , 26 , 26 , 80 , 242 } これは、2k 個の事前計算とストレージが要求される。これにより計算速度が k 倍高速化出来るが、時間と空間のトレードオフである。