以前 Emscripten の性能を調べたときは、すずき氏のプログラムを何も考えずに流用したが、ちょっと自分で書いてみたくなった。 やはり最初は再帰を用いるのが簡単だが、ビット演算になおすのを考えていたら、再帰を使わないシンプルなプログラムが書けた。
print(hoge(13));
function hoge(n)
{
var i,j,k,z,y=0,s=0,a=new Int32Array(n);
a[0]=1<<(n-1);
do{
i=j=k=a[y];for(z=y;z-->0;)if(a[z]&(i|(j<<=1)|(k>>=1)))break;
if(z<0){if(y+1==n)s++;else a[++y]=1<<n;}
do if(a[y]>>=1)break;while(y-->0);
}while(y>=0);
return s;
}
hoge 関数がそれで、引数は N の値で、解の数を返す。 最初の print は SpiderMonkey でのテスト用。 単純にすべて数え上げるので、時間はかかる。 再帰はしないし、メモリーを使うのは N 個の要素を持つ配列といくつかの変数なので、メモリー消費量は極めて少ない。
試しに置いてみて駒が取られないかどうかをいちいちチェックするやり方だが、ポイントは、解においてはすべての行 (または列) にひとつずつ駒が置かれることになるので、端から順に埋めていけばよいということ。 それまでに置かれた他の駒に取られないかどうかを埋める時に探索するならば、探索はそれまでに埋めた範囲についてのみ行えばよく、また、端から順ということは、ひとつの行 (または列) に複数を置く可能性がないので、同じ行 (または列) の探索もする必要がなくなり、その結果、8 方向に移動可能な駒であるが、3 方向のみの探索で済む。 ビット演算にしたことで端っこを気にする必要がなくなり (盤面をはみ出した位置にはそもそもビットを立てないことと、32 ビットを超えると 0 になることを利用)、より簡単になった。
これを GPU の力を借りてなんていうくだらないことを少し考えていたんだけど、並列処理ってやっぱり難しいね。
結局 TV アニメ「タッチ」の DVD を買っちゃった。 新品。 しかしフランスからの輸入版。 安さに釣られた。 映像が NTSC ではなく PAL らしいのだが、パソコンでの視聴は可能。PSX に入れたらなぜかディスクを認識しないが、前に GT4 も認識しなかったりしたドライブなので、PAL なら正しい挙動なのか、単にドライブがいかれているのかよくわからない。 ヘッドクリーニングはしてみたんだけど。 リージョンコードは日本とフランスは同じなので特に悩む必要はない。
最初入れたらフランス語音声しかなくて焦った。 日本語は別のディスクになってた。 つまりこれ全部でディスク何枚あるんだ? 画質がちょっと悪いというか、色が変な気がする。 画面の上下に本来見えるべきではなさそうな段差のついた部分が見える。 日本語音声でも「フランス語」と出る。 オプションでフランス語字幕を出すことができるが、第 26 話を再生したらなぜか強制的にフランス語字幕が出てきて笑った。
気づいた人は気づいたと思うけど、実は今朝気づいたんだけど、ビット演算じゃなくすればメモリー使用量はさらに減らすことができて、すなわち、Int32Array を Uint8Array にでもして、1<<n を n+1 にでもすればいいんだけど、おもしろいことに、遅くなる。a[z] の条件比較が 3 回の compare になること、それが毎回配列 a の要素を参照していることが関係あるのかないのか、よくわからないがおもしろい現象である。 っていうか JavaScript インタープリターの最適化も相当なもので、for ループを変な ;z-->0; とするより ,z--;z>=0;z-- のほうが速かったりして。
C に書き直して試すとやっぱ速いんだが、y+1==n に unlikely つけたら逆効果なのは興味深かった。likely のほうが微妙に速いとか、あれ、そうなの? みたいな感じ。 あとやっぱり無駄な break; より一発 goto のほうがよい。
藤野。4 回乗ってベストは 38.877 秒。
テレビでやってた映画。 見たやつかとおもったら違った。 いい感じのノリで見ていたのだが、勘違いにより最後の 6 分を録画しそこねたため、最後のほんの少しを見損ねた。 はぁー、前にも似たようなことやったなー。
この前書いたのは性能を完全に無視した極めて単純な形。 上から下に埋めると見るとして、上向きの 3 方向について駒が置かれているかをいちいち判断しながら進める方式。 なんとなく遅そうである。
これをひっくり返し、上から下に埋めるのはいいとして、下向きの 3 方向について駒が置けないよと印をつけながら進める方式が考えられる。 最適化の余地はこっちのほうがあるのではないかと考える。 そんなふうに考えて書いてみたのがこれ。
function hoge(n)
{
var i,j,k,w,x,z,y=0,s=0,a=new Int32Array(n),b=new Int32Array(n*n);
a[0]=1<<(n-1);
w=(1<<n)-1;
do{
i=a[y];
x=b[y*n+y];
if(!(x&i)){
if(y+1==n)s++;
else{
j=k=i;
for(z=y+1;z<n;z++)
if(((b[z*n+y+1]=b[z*n+y]|i|(j<<=1)|(k>>=1))&w)==w)
break;
if(z==n){
y++;
a[y]=1<<n;
}
}
}else if((x&(i-1))==i-1)a[y]=0;
do if(a[y]>>=1)break;while(y-->0);
}while(y>=0);
return s;
}
とりあえず、どこにも置けなくなったら下には進めないという処理と、これから調べようとしている部分がすべて置けないとわかったら上に戻る処理を入れてある。 これだけでも確かに速い。 これをいろいろ考えてチューニング。 ビットシフトを反対にする。 下から順にチェックするなら、簡単な演算により、ビットを見つけることができるから、1 ビットずつ順に見ていく必要がなくなる。 それをうまく活用していくと、a 配列もいらなくなり、ずいぶん高速化できた。 最後に、鏡像を利用した最適化も適用し、一応こんなもんかなぁ。
function hoge(n)
{
var i,j,k,v,w,x,z,y=0,s=[],b=new Int32Array(n<<5);
n&=31;
w=(1<<n)-1;
for(i=n>>1;i<n;i++)s[i]=0;
v=n>>1;
i=1<<v;
x=i-1;
do{
do{
if(!(x&i)){
x|=i;
if(y+1==n)s[v]++;
else{
j=k=i;
for(z=y+1;z<n;z++)
if(((b[(z<<5)+y+1]=b[(z<<5)+y]|i|(j<<=1)|(k>>=1))&w)
==w)
break;
if(z==n){
b[(y<<5)+y]=x;
y++;
x=b[(y<<5)+y];
i=(x^(x+1))&(x+1);
continue;
}
}
}
i=(x^(x+1))&(x+1);
}while(i&w);
while(y-->0){
x=b[(y<<5)+y];
i=(x^(x+1))&(x+1);
if(i&w)break;
}
if(y==0)v++;
}while(y>=0);
j=0;
for(i=(n+1)>>1;i<n;i++)j+=s[i];
j*=2;
if(n&1)j+=s[n>>1];
return j;
}
今になってやっと、すずき氏のプログラムを理解した。 ビットの 0・1 の用途が逆なのと、左下・下・右下の 3 方向のビットマスクを別々に持ち続けることで、毎回下までのマスクを作るループを回さなくてよいというのが特徴。 ふむふむ。 なるほどよくできてる。
それを理解できたところできのうのプログラムを改良する。
function hoge(n)
{
var i,v,w,x,y=0,s=[0,0],b=new Int32Array(n);
var c=new Int32Array(n),d=new Int32Array(n),e=new Int32Array(n);
for(w=(1<<n)-1,e[0]=(1<<(n>>1))-1,v=n&1;y>=0;y--){
for(x=e[y];(i=(x^(x+1))&(x+1))&w;){
x|=i;
if(y+1==n){s[v]++;continue;}
e[y]=x;
x=(b[y+1]=b[y]|i)|(c[y+1]=(c[y]|i)<<1)|(d[y+1]=(d[y]|i)>>1);
y++;
}
if(y==1)v=0;
}
return s[0]*2+s[1];
}
結局かなりシンプルな二重ループに仕上がったみたい。 本当にシンプルかというとアレだけど、再帰を使っていない部分でのトリッキーさはある。 単に書き方がトリッキーなだけかも。
こういう風になってくると、SIMD とか何とかでベクトル演算で何個か並列に処理をこなすというのもできそうな気がしてくる。 処理が単純なだけに、メモリーのアクセス性能の影響とかあまり出なさそうだから (全部キャッシュされそう)、純粋に演算性能の差が見られるかもね。
朝しっかり出遅れて原付で出たら雨だった。 小雨くらいだったとは思うが雨だった。 新しいヘルメットは雨の中でも快適であった。 ヘルメットの軽さも実感がわいてきたというか、頭を振ったときの首まわりへの負担が小さくなっている気がする。
オドメーターが 8,000km になった。 もうすぐなりそうだというのに気づいていたので、ちょうどいいタイミングで住宅街の細い道に入って写真撮影。
今年は去年までとは別の展示会で、横浜より近くなったのはいいけど朝イチで行くのはやっぱり楽ではない。 意外だったのは職場の最寄り駅で降りる人がかなり多くて、これはもしかして某大企業に 8:45 頃までに出社する人達だろうかと。
乗換駅までの乗車券を入れる→乗換先の駅に入場するために IC 乗車券をタッチする、というのがうまくいった。 以前失敗したことがあったので、通勤ラッシュの中やるのはちょっと緊張した。 失敗したときは単なる読み取りエラーだったのかなぁ。
今日は午後というか後半担当。 なんか知ってる方が何名もいらっしゃった。 そんな日だった。
夕方が去年までの展示会より遅い。 帰りの列車が通勤ラッシュっぽい感じで、各駅停車を選んでいったらいつもの仕事帰りぐらいの時間になってた。 山手線ってやつはやっぱりこむんだなっていう。
乗換先の乗車券を入れる→乗換駅までの運賃を精算し出場するために IC 乗車券をタッチする、というのもうまくいった。 これはあんまりやったことない、いや、完全に初めてかも知れない。 だって乗換先の乗車券を持ってるってのがね、普通はないパターン。
以前 Twitter で見かけた写真に発駅と着駅が同一の JR 東日本の片道乗車券があった。 調べてみるとよく一周乗車券とよばれていたりするものらしく、窓口できちんと経路を指定すれば買えるものらしい。
例によって 101km 以上の区間で条件がそろうなら途中下車が可能。 発着が大都市近郊区間であっても、区間外に出る経路を選べば途中下車可能だが、東京近郊区間は大変広く、東北本線の黒磯駅、常磐線のいわき駅、中央本線の塩尻駅、東海道本線の熱海駅などが含まれており、東京近郊で一周 & 途中下車しようと思うとかなり遠くまで行く必要があるようである。 他に特定都区市内とやらでなんか小難しい決まりがあるようだが、東京都区内の駅の改札を通ることがなければ気にする必要はなさそう。
でもそんなわけなので、大都市近郊区間の格安大回り乗車と比べるとなかなか挑戦しづらい感じである。 あと都心なら都区内パスというのもあって、一日乗車券的なもので都区内フリーエリアのどこでも乗り降りできる。
朝から。 おとといよりはやかったせいか電車混雑。 途中駅で人は減ったけど、先のほうで人転落か何かあったらしくて遅延が増える。 最後はめんどくさくなってお金に物を言わせて必殺技を...
うちあげ終わって 21 時、らくらくコースを選択して快速電車の始発をめざすと 22 時前、なぜかとてもすいていたので乗車し、金曜日のこの時間帯ってこんなにすいてるのかなと不思議に思いつつ順調に着駅に向かっていたところ、某駅で車掌室のほうから不穏なピーピー音が聞こえ、車掌が無線機のようなもので何か連絡を受けているのが見えた。 ひとつ先の駅で人転落のため安全確認を行うとかいって一時運転見合わせ。 それにおよそ 8 分を要し、おまけにその先のんびりになってしまって遅延が増えた。 各駅停車も同じくらい見合わせていたけど、こういうときは各駅停車に行ってしまうほうが (終点が近かったので) いいようだ。
「第 17 回渋谷・鹿児島おはら祭」 の日らしいのだが、展示会ですっかり疲れてしまったので、今年は見に行く気力さえ残ってない感じがする。 足腰が痛い。
原付のエンジンオイル交換。 くさい。
抜いたオイルは見た感じ 500ml くらいしかないような気がする。 そもそも前回交換したとききちんと 600ml 入れたかと言われると自信はない。
例によって少し静かになることを期待、というか、なったかな、近所をまわった程度ではよくわからん。 振動の多い単気筒エンジンだからこそ、振動が小さくなるのは人にも車体にもメリットがある。 もとのエンジンオイルは、距離的にはあと 3 倍程度は使えたはずだが、まぁいい。 この原付、実際に 8,000km になってみると、買った時点で 10,000km を超えていた可能性が否定できない気がしはじめていて、でもエンジンに関しては、定期的にエンジンオイル交換と量チェックさえしておけば大丈夫といわれるスーパーカブのエンジンなので、そこだけ気をつけるようにしようと。
例の WebGL の本を適当に一通り読んだ。 新鮮だったのは 4 章で、最初のほうのサンプルがやたらシンプルで複雑な 3D 図形が書けそうにはとても思えなかったところ、そんな疑問は解決した。
特に OpenGL や Direct3D などに難しそうな印象を持っていたのは、15 年以上前に少し手を出してみた 3D グラフィックス関連のプログラムの難しさからだったのかも知れない。 とある本に載っていた立方体を描く BASIC プログラム。 本には小難しい座標変換の方法が説明されていて、とにかく実行するとそれらしき立方体が表示できて、角度をくるくると変えると立方体が回って、それはそれでいい感じだったのだが、面を塗りつぶそうとするととたんにやっかいになった、というのは、LINE ステートメントと PAINT ステートメントを駆使して塗りつぶすまではよかったものの、隠れていてほしい部分が表に出てきてしまうという問題があった。 見えない部分を描かない方法的なものも説明はあったのだが理解できなかったし、簡単にできる方法があるのではないかと考えたがわからなかった。 その後 3DMark などいろんなかっこいい 3D コンピューターグラフィックスのデモやゲームを見てきて、ハードウェアは 3D の世界のデータと視点等を入力すればきれいに描画してくれるのかというような、そんな気がしていたが、OpenGL の基本的なサンプルなどは三角形が出るだけで、その間の溝が埋まらないような感じがしていたんだと思う。
WebGL に関して、新鮮だったというのは、座標についてで、例えば BASIC では左上隅が (0,0)、右下隅が (639,199) というような座標がデフォルトでは使われていて、はみ出した部分は見えないというものだったが、実は WebGL もそれに関してはたいした差はなくて、見える範囲の X, Y 座標は -1〜1 の浮動小数点を常に使っている。 なんとこの範囲を変えることはできないっぽくて、頂点シェーダーから座標を渡すときにこれに合わせて計算して調整するようである。 奥行きがあるじゃないかと考えるものだが、奥行きは見える範囲が -1〜0 なだけで、平面となる画面上の X, Y 座標には影響を与えない。 奥行きは、深度バッファーによるチェックを有効にしていれば、もっとも手前のものが残されるというだけで、有効にしていなければ、最後に描いたものが手前に表示される。 もし、奥のものが小さく見えるというのを表現したければ、頂点の位置の計算にそういう計算を含めるらしい。 その計算式はおそらく BASIC でやっていたこととたいして変わらない。 というふうに見ていくと、WebGL や OpenGL というのは、3D に向いているのは間違いないが、基本的な部分は 2D でできているとも言える。 あと、GPU は、塗りつぶされた面の各ピクセルについて、深度バッファーを利用して見えない部分を隠す処理ができるので、以前 BASIC で難しかった話については、簡単に解決する。
フラグメントというのがピクセルみたいなものだと、しかしそれは 3D の世界で行われるものだと思っていたが、前述のとおり奥行きは画面上の X, Y 座標に影響を与えないのだから、おそらく、X, Y 座標を用いて多角形を描く場合の、各ピクセルに相当する部分をフラグメントとしているというか、Z 座標も計算はされることになるがそれは varying 変数を求めるのと同じ意味ではないか。
161 円/l。 燃費計算 17.7km/l。 燃費表示 18.6km/l。
きのうまでに得た知識を使って、適当にアナログ時計を作ってみた。
適当なので context lost とか処理してないし、ソースコードもサンプルを改造した感じでかっこよくないんだけど、とにかく、以下のようなことをやった。
まぁたいしたプログラムではないけど、特にシェーダーに関して、実際に自分で書いてみることで、float 型と int 型を直接比較しようとするとエラーになるとか、mat4() の書き方とか、int() とか、C と似ているところ、違うところを体験できて、これはこれで勉強にはなった。
念のため原付の下を覗いてみたらエンジンオイルがしたたり落ちようとしている & 落ちた跡が。 あわてて六角棒レンチを引っ張り出し増し締め。 明らかに回った。 適当に締めてこんなもんかと思っていたのがゆるかったようだ。 気づいてよかった。
HTML5 の JavaScript でアニメーションしましょうというときに、setTimeout の代わりに使いましょうとされているのが window.requestAnimationFrame()。 これは描画ができるタイミングでコールバックがよばれますということで、通常はフレームレートでの呼び出しが行われるが、負荷が高くフレームレートでの描画ができないときには、フレームレートよりも低い頻度で呼び出されたり、描画の必要がないとき (別のタブがアクティブになっているときなど) にはそもそも呼び出されないようにされたりといった気配り仕様になっているものである。
ということなのだが、世間一般にはフレームレート = 60 フレーム/秒、というのが一般的であり、setTimeout で 1/60 秒を指定する代わりなどとも説明されている。 果たしてそうなのか、ということで、テストプログラムを作った。
タイトルにレートと時刻情報を表示する。 時刻情報は引数に渡されてくるミリ秒単位の数値を分・秒に変換したものである。 タイトルというところがみそで、タブを切り替えるなどして様子を観察することができる。
そんなわけで、ブラウン管ディスプレイなど、リフレッシュレートが 60Hz より高い環境においても、問題なく使えそうなことが判明した。
株主優待目当てで所有している株式のうち 3 種類がイオングループなのであった。 株主総会の招集通知の冊子のデザインがそっくり。
それぞれ別々の優待内容になっているところがおもしろい。 今回の統合のニュースがそのとおりに実現されるとすると、マックスバリュ関東はイオンの優待のままなのか、カスミでも優待が使えるようになったりするのか。 ワーナーマイカルがイオンシネマになったのは、ワーナーマイカルをよく使っていたこともあって知っていたし、この前は優待を使ってジュースが飲めた。
来週のイオンの株主総会、場所は幕張メッセらしい。 その近くには、超巨大な「イオンモール幕張新都心」がある。 どれだけ広いのか一度行ってみようと思っているのだが、よくそんな巨大なのをたてて利益が出せるよなぁと。
Powered by Tomsoft Diary System 1.7.4
Hideki EIRAKU