テーブル参照をビット幅で分割

[どぶろく]

「遊びのレシピ」という本に書いてある以下の文章が理解できません。

テーブルデータの数を少なくするには、たとえば、テーブル範囲の最大数が65,536個の場合、
4ビット幅に分割することでテーブルに使うデータは4ビットの最大値となる16(0x1111)個だけで
済むようになります。値を変換するときは「変換したい値」をこのビット幅に分割してから
値を引き出します。得られた値は分割したときの順序に従って組み立てます。

以上の文章です。int arry[65536]; が int arry[16]; だけで済むということでしょうか？
変換したい値を4ビット幅に分割するというのは16進数にすることかな？
得られた値は分割したときの順序に従って組み立てる。というところは、まったく分かりません。

[みけCAT]

まだ読解できていませんが、とりあえず16(10進数) != 0x1111です。
0x1111 == 4369(10進数)
1111(2進数) == 15(10進数)
16(10進数) * 0x1111 == 69904(10進数)

オフトピック

そういえば、おどるかばね。さんの同人誌に
2⁷ + 2⁶ + 2⁵ + 2⁴ + 2³ + 2² + 2¹ + 2⁰ = 256
という記述があったな…。どう考えても左辺は奇数、右辺は偶数なんだよな…。

[ただの屍のようだ]

その本を読んだことはありませんが、アマゾンの評価すさまじく低いようですね。
配列を小さくしたいなら、サンプルあげます。その中からコーディングのヒントは得られるかもしれないが、
本の作者の意図にあった回答がほしければ、改善前のコードとどう改善したいかを提示しないと答えようがありません。

コード:

＊脳内イメージをそのままコードにしたもので、コンパイラ通してません
typedef int* LP_INT;
const unsigned int MAX_SIZE = 65536/16;

LP_INT table[16];
for(int i=0;i<16;i++)
	table[i] = new int[MAX_SIZE];
delete[] table;

[Poco]

懐かしいなあと思いつつ本棚を探すとあったので、私なりの解釈を説明します。
まず、この本ではテーブル参照を高速化のテクニックとして紹介しています。
要は、頻繁に使用される関数y=f(x)があったとして、呼び出しのたびにfの処理を走らせると性能に響く可能性があるから、
答えが分かっているなら予めソースコードなり初期化関数なりで、xに対するyを直ぐに引き出せるようにしましょう、というものです。

ここまでが前提。

で、テーブルに収めるときにxが取りうる種類(範囲)や、yのサイズによってはテーブルのサイズが大きくなります(xの範囲とyのサイズの積がテーブルのサイズです。)
本の例ではxが65,536個、yが4バイトで、なんと256キロバイトも使用してしまいます。大問題です。
じゃあ、どうするか？
本の例では4bit単位にxを分割するとあります。
xは16bitで表すことができるデータなので、xを4bitずつに分割するとx0,x1,x2,x3という風に分割できる筈です。
で、y0=f0(x0)、y1=f1(x1)、y2=f2(x2)、y3=f3(x3)、y=f(x)=g(y0,y1,y2,y3)、となるような関数f0,f1,f2,f3,gがあったとします。
ここでf0,f1,f2,f3にそれぞれテーブル参照のテクニックがつかえると考えてください。
y0を求めるテーブルサイズはx0が16個×データが4バイトで64バイト、y1,y2,y3も同様なので、64×4=256バイトとなります。
xをx0,x1,x2,x3に分割する前のテーブルサイズが256キロバイトに対し、大幅に必要メモリ量を削減できています。

「得られた値は分割したときの順序に従って組み立てます。」という表現は上記関数g()が該当すると思ってください。
まとめると、xという入力に対し、処理fの結果yを求めるものがあった時に、
　1．テーブルを使用してfの実行にかかる時間を1度のテーブル参照に要する時間まで短縮させる。でもメモリ使用量が大きくなるかも。
　2．メモリ使用量を削減するために、xを分解し、分解した数だけテーブルを参照し、その結果を結合する。1より遅くなるけど、fの実行より早いはず。メモリ使用量は1より少なくなるはず。
ということかと。
ただし、これはxがうまく分解できること、yをうまく結合できることが大前提です。
ここの文章は、"xやyの性質をよく考えると"メモリを節約しつつ高速化できるかもね、くらいの理解でよろしいと思います。

[どぶろく]

＞みけCATさん
16(0x1111)からしておかしいですよね。一体なんなんでしょう。

＞ただの屍のようだ さん
この本の作者はプログラマーとしては優秀かもしれませんが文書力や解説力が欠如していると思われます。
アマゾンでの評価が低いのも納得できます。
サンプルコードは頭の中に大切にしまっておきますね。

＞Pocoさん
すばらしい解説ありがとうございます。長年の疑問が解決しました。感動しております。
要素が１６個のテーブルが４つあって、４つの答えを元にして１つの答えを出すんですね。

[ソフト屋（外出中）]

外出中なのですが、ただの屍のようだ さんのコードがメモリリークしている上にｄｅｌｅｔｅがまちがっています。あとたとえ間違っていなくても意図が不明です。

[ただの屍のようだ]

そのようですね。一応＊で注意コメントもありますし、大丈夫でしょう。
まぁ脳内イメージはだいたいバグ入りですよ。それはどんなベテランにも言えることです。
優れたソフトを作るには、優れた設計、優れたエンジニア、そして優れたテストケース。どれが欠けてもダメです。

コード:

//正しい解放ループ文
for(int i=0;i<16;i++)
	delete[] table[i];

＊優れたコード技法があるのに、優れた設計が書けないとは我ながら情けないことです。
＊softyaさんがそんな自分を救える期限はあと9時間！アドバイスお待ちしております＾－＾
＊というわけで、今度こそ座学に戻りますよ。（今夜0時に）