2010-10-25

挿入ソート

アルゴリズム

こう言うわかりきっている基礎的なところを復習し固めるのが、無職時代にすることですな。

とりあえず、簡単に言うとやね、

整列済み区間と非整列済み区間を区別する
最初は整列済み区間の数は０
非整列済み区間から一つ取り出し整列済み区間へ挿入
挿入の際に先客がいれば、先客と比較して先客より小さければ先客の位置に挿入、先客は一つ後ろにずれる
先客と比較して先客より大きければ、先客の後ろにつける、このとき別の先客がいれば比較を行い、4または5と同じ事をする
非整列済み区間がなくなるまで3〜5を繰り返す

カッコ内が整列区間だとすると

[]|3|4|1|5|2|
[|3|]|4|1|5|2|
[|3|4|]|1|5|2|
[|1|3|4|]|5|2|
[|1|3|4|5|]|2|
[|1|2|3|4|5|]

てな順番でソートされる。簡単でしょ？
整列済み区間は整列済みなので、挿入する奴は左側から順に比較して、自分より大きな数が見つかった時点でその手前に挿入してやりゃいい。

以下に擬似コードを書いたよ…もはや何言語だかわかりゃあしねぇ



for j=1 to Array.length

	--keyは挿入する対象

	key=Array[j]

	i=j-1

	while i>0 and Array[i]>key

		Array[i+1]=Array[i]--ずらす

		i=i-1

	Array[i+1]=key--挿入

アルゴリズムは簡単だけど、速くない。ただし、ある特定の場合には最強になる。
それは、最初からほぼソート済みに近い状態であれば、特に何もすることなく、ずらす必要もないため、高速になる。

また、配列でなく、リスト構造を使用していれば、ずらす必要がないため高速にはなる。

2010-10-25

作業用音楽の一つ

息抜記事

勉強したり、絵を描いたり、プログラミングしたりする際の作業用音楽
http://nicosound.anyap.info/sound/sm63193

なにこれかっちょいい

2010-10-19

DXTに関するメモ

データフォーマット

DirectXSDKのヘルプ見ながら…僕の理解をまとめてみました。

カラーについて

カラーの部分についてはDXT1,DXT3,DXT5のそれぞれに差はない。それぞれの生成するプログラム上は
差があるかもしれないが画像フォーマットとしては同じものだ。

カラー部分はDXT1,DXT3,DXT5ともに、例えばオールブラックの場合

00 00 00 00 00 00 00 00

オールホワイトの場合

FF FF FF FF 00 00 00 00

となります。え？オールホワイトの場合は

FF FF FF FF FF FF FF FF

じゃないのかって？違うんだなぁ…これが。
説明すると、最初のFF FF FF FFの32bitは二つの16bitにわけられる
で、FF FFで何を表現するのかというとRGB(565)を表現する。それぞれの色を32bitで表現するわけだ。
所謂ハイカラーで、十分な表現能力を持っている。Gだけ6なのは、人間がGの色に敏感だからだ。
あと、 DXT1でアルファありの場合はこのGを5ビットにして1ビットをアルファに割り当てている。厳密に言うと同じっちゅうわけじゃない。

このため、DXT1をαありで使用すると画質が若干落ちることだけは頭に置いておいた方がいい。

で、ここで疑問が、では「αなしのDXT1」と「αありのDXT1」は、どこでどのように区別しているのか？フラグなんか見当たらないぞ？
マニュアルにはIf the first color is greater than the second, it implies that only opaque texels are defined.って書いてる。
要は、代表２色の大きさの比較で、αかそうでないかを決めているようだ。ちなみにコードは↓

if (color_0 > color_1)
{
// Four-color block: derive the other two colors.
// 00 = color_0, 01 = color_1, 10 = color_2, 11 = color_3
// These 2-bit codes correspond to the 2-bit fields
// stored in the 64-bit block.
color_2 = (2 * color_0 + color_1 + 1) / 3;
color_3 = (color_0 + 2 * color_1 + 1) / 3;
}
else
{
// Three-color block: derive the other color.
// 00 = color_0, 01 = color_1, 10 = color_2,
// 11 = transparent.
// These 2-bit codes correspond to the 2-bit fields
// stored in the 64-bit block.
color_2 = (color_0 + color_1) / 2;
color_3 = transparent;
}

で、その代表２色はマイクロソフトのドキュメントではcolor_0,color_1と表現されている。
これを足したり割ったりして補間する。

00 ? color_0
01 ? color_1
10 ? 2/3 * color_0 + 1/3 * color_1
11 ? 1/3 * color_0 + 2/3 * color_1

で、残りの32bitは16ピクセルのためのルックアップテーブル(LUT)というわけだ
1ピクセルあたり2ビット使用する…よくこれであれだけの表現力があるもんだ。感心する。
アルファについて

ここからはDXT3,DXT5の話になる。
DXT1にはなかった前半64bitの話だ。
DXT3

意外と簡単である。1ピクセルごとに4bitのアルファ値を割り当てて16ピクセル分。そんだけ。4bitだから
表現能力は低く、アルファグラデとかされると、マッハバンド出まくりである。が、通常２Dゲームではドット絵なんで
急激にアルファ値が変わるものと思っていい。なんで、大抵はこちらの方が適している。
例えば、全透明だと

┌-----アルファ部分-----┐
00 00 00 00 00 00 00 00 FF FF FF FF 00 00 00 00

ね？簡単でしょ？
DXT5

これが一番やっかいである。ハッキリ言って説明したくない。頭使って説明した揚句に間違ってたら、目も当てられん…
たとえば、上のDXT3のをDXT5にコンバートすると、こうなる

代表	┌-----LUT------┐

FF 00 49 92 24 49 92 24 FF FF FF FF 00 00 00 00

なんじゃこりゃ…で、簡単に言うと、先頭2バイトが代表アルファで、それぞれ1バイトずつが
8bitアルファを表現している。残りの６バイト＝48ビットがルックアップテーブルだ。
つまり1ピクセルあたり3ビット。これでルックアップテーブルインデクスを表現している。
3ビットなので、8種の表現能力があるわけだ。このおかげでグラデーションなんかも比較的きれーに表現できる。

マイクロソフトドキュメントでは代表アルファはalpha_0,alpha_1と表現されている。
例によって例のごとく、足したり割ったりして補間するが、ややこしいのはalpha_0とalpha_1の大きさによって
補間の仕方が変わっちゃうということ…なんでこういうことするのよ。その辺の詳しい事情は知らない。

(なんでこういうことするのかという疑問の私なりの解釈…
αの分布が代表点αの線形補間のみでうまいこといけるならば、前者の方法でよいが
そうでないこともある…か？αの分布が微妙(0-255の8分割では表現できない)でかつ、極所値(完全透明と完全不透明)が必要
てな分布の場合に後者が採用されるとかそういう話ではないだろうか…資料を見つけ切れてないため、完全に予想。お許しください！！)

alpha_0の方が大きい場合

010 ? (6*alpha_0 + 1*alpha_1)/7
011 ? (5*alpha_0 + 2*alpha_1)/7
100 ? (4*alpha_0 + 3*alpha_1)/7
101 ? (3*alpha_0 + 4*alpha_1)/7
110 ? (2*alpha_0 + 5*alpha_1)/7
111 ? (1*alpha_0 + 6*alpha_1)/7

そうじゃないとき

010 ? (4*alpha_0 + 1*alpha_1)/5
011 ? (3*alpha_0 + 2*alpha_1)/5
100 ? (2*alpha_0 + 3*alpha_1)/5
101 ? (1*alpha_0 + 4*alpha_1)/5
110 ? 0
111 ? 255

で、結局49 92 24 49 92 24ってなんなのよっていうと…2進法表現すると

0100 1001 1001 0010 0010 0100 0100 1001 1001 0010 0010 0100

こうなるわけで…あれー？予想では

0010 0100 1001 0010 0100 1001 0010 0100 1001 0010 0100 1001

ってなる予定だったんだけどな…エンディアンか？わけわからん…えーとマニュアルには
0 Alpha_0
1 Alpha_1
2 [0][2] (2 MSBs), [0][1], [0][0]
3 [1][1] (1 MSB), [1][0], [0][3], [0][2] (1 LSB)
4 [1][3], [1][2], [1][1] (2 LSBs)
5 [2][2] (2 MSBs), [2][1], [2][0]
6 [3][1] (1 MSB), [3][0], [2][3], [2][2] (1 LSB)
7 [3][3], [3][2], [3][1] (2 LSBs)

って書いてる
MSBはMost Significant Bitだから…ちょっと分けると

0100 1001 2バイト目
1001 0010 3バイト目
0010 0100 4バイト目
0100 1001 5バイト目
1001 0010 6バイト目
0010 0100 7バイト目

で、2バイト目には01,00,(02の上位2ビット)が含まれているわけだから

[0,2] [0,0] [0,1]
01 001 001

[1,1] [1,0] [0,3] [0,2]
1 001 001 0

[1,3] [1,2] [1,1]
001 001 00

[2,2] [2,1] [2,0]
01 001 001

[3,1] [3,0] [2,3] [2,2]
1 001 001 0

[3,3] [3,2] [3,1]
001 001 00

で、一応全てが001を指して、全て完全透明になる…と、あーくそややこしい！！
あとまー、分岐があったり乗算除算があったりと…復号時にけっこう処理食うんじゃねーのかな…

まぁ、ネタ元はDirectXSDKであってWikipediaではないです。Wikipediaは若干説明が違います。

また、日本語の資料もありますが、この辺の翻訳は若干おかしいというか…それこそ信用ならないので、英語版を見ることをお勧めします。

2010-08-25

Builderパターン

デザインパターン

Builderパターン

さて、GOF本を読むと、

複合オブジェクトについて、その制作過程を表現形式に依存しないものにすることにより、同じ制作過程で異なる表現形式のオブジェクトを生成できるようにする。

と、ある。複合オブジェクトってなに？

とりあえずGOF本はまだ難しいので「Java言語で学ぶデザインパターン入門」を読んでみたが、
あー？これ、Template Methodパターンと何が違うのん？なるほど、わからん。

本を読む分には、DirectorとBuilder,TextBuilder,HTMLBuilderの関係を強調しているけど
そうじゃないでしょ。その関係はTemplate MethodのキモであってBuilderのキモじゃないでしょ！

じゃあBuilderのキモってなんなのさってのがJava言語デザパタ本では不明確なので、もう一度GOF本を読んでみる。
多分この複合オブジェクトというのがキモではないかと、俺のカンは言っている。

…GOF本にケチをつけるのは畏れ多いけど、ショボプログラマの自覚を持ちつつもP105,P106の図
にケチをつけたくなりました。

P105のクラス図にBuilderからそれぞれ派生したクラスのメソッドに
GetASCIIText(),GetTeXText(),GetTextWidget()があります。派生クラスにそれぞれ
定義されているのです。いや…これ、僕的にはどう考えてもTextConverterにGetText()メソッドを追加すべきでしょ…
と思うんですが、不遜な考えでしょうか？

読み間違えているのかな、とより抽象的なP106の図を見てみる

うーん。やっぱりConcreateBuilderクラスにGetResult()メソッドがあって、Builderインターフェイスにはない。

…いや、やっぱりこれはBuilderインターフェイスに持ってくるべきでしょう！！

僕は本を鵜呑みにするのはあまり意味がないと思うのだ。確かに独善的に読むのは良くないが、
経典や聖書じゃないんだから…数学の本も暗記したところで意味ないでしょ？
後から恥をかいたっていいのだ！！俺は声を大にして言う「GetResult()メソッドはBuilderに純粋仮想関数として定義すべき」だと！！

さて、自己主張は置いておいて、「適用可能性」を見てみよう。

多くの構成要素からなるオブジェクトを生成するアルゴリズムを、構成要素自体やそれらがどのように組み合わされるのかということから独立にしておきたい場合
オブジェクトの作成プロセスが、オブジェクトに対する多様な表現を認めるようにしておかなければならない場合

とある。とあるので、GetResult()はインターフェイスにあるべきだと思うのです。

結論
結局のところ、Builderパターンは、それの実装によらず、クライアント側が呼び出すメソッドを組み合わせて最終的に「何か」を生成するパターンですね。
なので、「何か」をクライアントに渡すメソッドはBuilder側に必要である(この場合はGetResult)

要点：

メソッドを組み合わせる責任はクライアントが負う
Builder側は組み合わせ通りになんかしら生成する。(その生成したものをクライアントに渡されることもある)
複数のBuilderがある場合にはTemplate Methodパターンも使用される

さてこれも使いどころはあるのか…と。まぁ、頭に入れておけばなんらかのヒントになるかな…。

正直あまり面白いパターンじゃないなぁ…。

2010-08-25

木の回転

アルゴリズム

一次元領域探索の解説を呼んでいるうちに分かってない概念が多すぎて愕然とした。

結局

Kd-Tree→一次元領域探索→平衡二分探索木→赤黒木→木の回転

にまで遡ることになった。どんだけプログラマとしてモノを知らんねん…

木の回転

　　R
　　∧
　 P　C
　∧
A　B

これを右回転すると

　　P
　　∧
　 A　R
　　　∧
　　B　C

となる。当然これを左回転すると元に戻る。

イメージ的には、木はそれぞれリングに棒が一つないしは二つくっついていて、それらが

ダラーんとぶら下がっているイメージだ。当然上から下までの長さは短い方が探索が速い。

で、回転のイメージは、右回転時は左下のリングを持って重力に任せるといい。

だが、そうだとすると回転の際にBの位置が変わっている。

これは、回転のルールとして

要素の順序を崩さずに構造を変更する

というルールがあるためだ。二分木である以上は特定の順序付けルールで並んでいるため、その順序が変われば意味がなくなるからだ。

左の木：（（A,P,B),Q,C)⇔右の木：（A,P,(B,Q,C))

というわけである。右回転疑似コードを書くと…

Pivot = Root.LChild
Root.LChild = Pivot.RChild
Pivot.RChild = Root
Root = Pivot

ついでに左回転

Pivot = Root.RChild
Root.RChild = Pivot.LChild
Pivot.LChild = Root
Root = Pivot

となる。

2010-05-02

音響(感性的な)

音響

迫力因子：周波数が低く、音圧レベルが高いほど、迫力が増す。

金属性因子：周波数が高く音圧レベルが高いほど鋭い音色になる。

美的因子：周波数関数が山形カーブを描き、1kmHz付近でもっともきれいな音色になる。

2010-05-02

音響メモ(聴覚心理)

音響

音のエネルギー自体と、実際に感じる音の大きさとはそのまま対応しない。
感覚的な音の大きさの単位として、デシベルが定義されている。とりあえず音のエネルギーの対数に感覚的音量は対応しているっぽいので、

L=10log(B/A)
logの底は10

としている。上のAは基準量、Bが測りたい量。なので、無次元の値になっている。

ちなみにWikipediaから表を引用してみた。
1倍 0.00dB 0.00dB
2倍 6.02dB 3.01dB
3倍 9.54dB 4.77dB
4倍 12.04dB 6.02dB
5倍 13.98dB 6.99dB
8倍 18.06dB 9.03dB
10倍 20.00dB 10.00dB
16倍 24.08dB 12.04dB
50倍 33.98dB 16.99dB
100倍 40.00dB 20.00dB
255倍 48.13dB 24.07dB
500倍 53.98dB 26.99dB
1000倍 60.00dB 30.00dB
5000倍 73.98dB 36.99dB
10000倍 80.00dB 40.00dB
65535倍 96.33dB 48.16dB

また、話は変わるが、順行性マスキング、逆行性マスキングというのがあるらしい。これは、前の音が後ろの音を打ち消したり、その逆が起こったりするものらしい。打ち消す側の音のほうが非常に強いときに発生するようだ。

音の高さには2種類あって、音色的高さと音楽的高さがあるんだって。
音の高さはオクターブの螺旋階段を上るように上昇してゆく。

螺旋階段の基本となる円に、ドレミファソラシド(もちろん＃も中に入っている)を配置した状態を思い浮かべると、円が音楽的高さ、そこで描かれる高さが音色的高さとなっている。

これを利用したものが無限音階。

http://www.youtube.com/watch?v=kC1J8894vu0