All about テーブル化
スパースなデータのテーブル化
いまS, Tを適当な（離散的な）順序集合として、写像d:S→Tをテーブルで実現するというのはよくある話で、y=d(x)のx∈Sを添え字とする配列aに、y∈Dを代入しとけばおk
しかしこれ一本槍ではSがスパースな集合だったりするとﾋｼﾞｮｰに苦しいことになる
すわなち、aのサイズはmax{ S } - min{ S } + 1が必要だがそのうちの0.1 %ぐらいの値しか実際には取り得ない値とかだったりするとメモリのﾁｮｰ無駄づかいだる、
こういうときは、適当な全単射写像f:S→Dを用意して、ただしDは稠密となるようにして、
d = (d・f^(-1))・f ・・・(1)
と分解し（ここでf^(-1)はfの逆写像）、g := d・f^(-1)に対しy=g(z)をテーブル化しておいて、dの計算にあたってはz=f(x)を都度毎回計算してzでy=g(z)のテーブルを引くようにする、
ここで注目すべきは、テーブル構成時に∀x∈Sでループを回す限り、合成写像d・f^(-1)のテーブル化は、
y=d(x)
z=f(x)
の2つを計算し、テーブル実体となる配列b[]の添え字をz、値をyとすることで、f^(-1)を陽には計算しなくて全く良い、*1
入力段におけるちょっとした追加の演算もついでにテーブル化
(1)によりめでたく最高の記憶密度とそこそこの処理速度で写像dを計算できるようになったところで、全く同じコードでもって*2、合成写像
d・r
を計算したくなったと汁、
ただしrはr:S→Sな全単射写像で、定義域と値域がどっちもSというのがポイント、
これをテーブルの差し替えだけで実現するには…
こう考える、
d・r = ( (d・r)・f^(-1) )・f ・・・(2)
(1)と(2)を比較してわかるのは、今度は( (d・r)・f^(-1) )をテーブル化すれば良いのだということ
より具体的には、
foreach (x in S) {
x' = r(x)
y = d(x')
z = f(x)
b[z] = y
}
でおk
これで(1)を計算するのと全く同じコードで*3、(2)によりめでたく最高の記憶密度とそこそこの処理速度で写像d・rを計算できるようになた、*4
このようにしてfの計算前に適用するr:S→S的かつ全単射な写像であれば、いくつあってもテーブル構成時に事前計算しとける
、
