2006年04月

入力の要素数 n が与えられたとき，n 個の要素をループなしでソートするプログラムは簡単にかける（挿入ソートとか）．特に，n! 個の出力命令と二要素の大小比較を条件文に持つ if-else のみでかける．では，この条件下で O(n log(n)) のソートはかけるだろうか？　マージソートなら書ける気がするけど面倒なので放ってく．

2^n で割ったあまりを求めるには 2^n -1 との AND をとる方が一般には速い．んで，コンパイラもそこらへんがわかっているので AND 演算に置き換えてくれるのだが…　以下の二つのプログラム

int main(int argc, char *argv[])
{
    int k = 0;
    for(int i = 0; i < 100000000; i++){
        k = k % 4;
    }
    return k;
}

と

int main(int argc, char *argv[])
{
    int k = 0;
    for(int i = 0; i < 100000000; i++){
        k = k % 4U;
    }
    return k;
}

では後者のほうが３倍くらい速くなる（倍率は環境によるかもしれないけど）．両者のアセンブリコードを比べると

	xorl	%edx, %edx
	movl	$99999999, %ecx
	jmp	L6
	.p2align 4,,7
L5:
	andl	$-4, %eax
	subl	%eax, %edx
	decl	%ecx
	movl	%edx, %eax
	js	L10
L6:
	testl	%edx, %edx
	movl	%edx, %eax
	jns	L5
	leal	3(%edx), %eax
	andl	$-4, %eax
	subl	%eax, %edx
	decl	%ecx
	movl	%edx, %eax
	jns	L6
L10:
	leave
	ret

と

	xorl	%ecx, %ecx
	movl	$99999999, %edx
	.p2align 4,,15
L5:
	movl	%ecx, %eax
	andl	$3, %eax
	decl	%edx
	movl	%eax, %ecx
	jns	L5
	leave
	ret

のようになっており(gcc3.4.4)，後者のほうが分岐が無いし速いのは当たり前．とりあえず問題点は「符号付の剰余は負数のときにめんどくさい」という点にある．その面倒な処理が分岐を必要として遅くなってしまうと．

ということで，負数なんて知らんという場合には明示的に符号なしであることを指定しておくべし．

よくわからないけど Raw Input 使うのに必要そうなので必要なことだけ調べてみたり．とりあえず Top-Level Collections Opened by Windows for System Use やら Hardware IDs for HID Devices やらにより，RowInputDeviceの登録に必要な情報がとりあえず判明．

Device Type 	Usage Page 	Usage ID
Mouse           0x01             0x02
Keyboard        0x01             0x06

しかし，これらを RAWINPUTDEVICE 構造体に入れて RegisterRawInputDevices してもパラメータが違うとエラーが返ってる…　なぞだ．とりあえず http://www.usb.org/developers/hidpage/ とか http://www.usb.org/developers/docs/ とかを眺めようか？

をしようと思ったら Row Input の API を叩けば良いらしい．これ使って入力がどのキーボードからきたかに応じてレイアウトを切り替えればキーボードごとにレイアウトを変えて使えそうだが…　できるかどうかよくわからん．