クリックすると拡大します。
Blog
前のページ
｜
次のページ
2006/07/09のBlog
[ 03:55 ]
[ アルゴリズム ]
VC8のstl::mapと自作Mapの比較です。データ数は1M個です。
Mapの特徴は親ポインタを持たないことで使用メモリが少ないことです。
乱数の挿入です。
Map 1668ms
stl::map 2518ms
上記で挿入したデータを同じ乱数系列で削除です。
Map 1758ms
stl::map 3284ms
昇順で挿入です。
Map 1215ms
stl::map 2027ms
上記で挿入したデータを昇順で削除です。
Map 316ms
stl::map 1551ms
降順で挿入です。
Map 1228ms
stl::map 2370ms
上記で挿入したデータを降順で削除です。
Map 333ms
stl::map 2779ms
乱数の挿入、削除をします。
Map 3018ms
stl::map 4681ms
色をポインタの最上位ビットに持たせるかメンバ変数で持たせるかで評価してみましたがまったくといってよいほど同じ速度だったのでポインタに色を持たせる方法で評価しました。
メモリ管理を自前でやると不公平なのでstl::mapのallocatorに同じ仕組みのを使うか自作Mapのメモリ管理にnew,deleteを使うと同等ど土俵で評価できます。
以下は自作Mapのメモリ管理にnew,deleteを使った場合の速度評価です。
stl::mapと自作Mapの比較です。データ数は1M個です。
①乱数の挿入です。
Map 2066ms
stl::map 2612ms
②上記で挿入したデータを同じ乱数系列で削除です。
Map 2205ms
stl::map 3276ms
③昇順で挿入です。
Map 2494ms
stl::map 2231ms
④上記で挿入したデータを昇順で削除です。
Map 1418ms
stl::map 1535ms
⑤降順で挿入です。
Map 2506ms
stl::map 2256ms
⑥上記で挿入したデータを降順で削除です。
Map 1308ms
stl::map 2564ms
⑦乱数の挿入、削除をします。
Map 3523ms
stl::map 4635ms
考察してみる。不等号は"速い>遅い"で表現します。
③⑤はMap<stl::map。挿入は確実に成功するので親ポインタの有無やその他の実装の差が出ている。 ④⑥は④map><⑥Map,④std::map>⑥std::map。違いに心当たりがあるとすれば削除する葉が２つ子を持っていたときMapは右部分木の最小キーの葉で置換するがstd::mapは左部分木の最大キーの葉で置換するということ。
⑦はMap>std::map
①⑦の挿入はキーの重複があり。挿入処理の失敗がありえます。探索処理の比率が大きくなります。
②⑤の挿入はキーの重複がなく、必ず挿入処理が成功します。①⑦に比べ探索処理の比率が小さいです。
このことからMapは探索が高速でstd::mapは挿入が高速であるといえます。
Mapを高速がさせるために親ポインタの有無による速度差であれば改善できませんが、そうでなければ同等の速度まで改善できる可能性があります。
Mapの特徴は親ポインタを持たないことで使用メモリが少ないことです。
乱数の挿入です。
Map 1668ms
stl::map 2518ms
上記で挿入したデータを同じ乱数系列で削除です。
Map 1758ms
stl::map 3284ms
昇順で挿入です。
Map 1215ms
stl::map 2027ms
上記で挿入したデータを昇順で削除です。
Map 316ms
stl::map 1551ms
降順で挿入です。
Map 1228ms
stl::map 2370ms
上記で挿入したデータを降順で削除です。
Map 333ms
stl::map 2779ms
乱数の挿入、削除をします。
Map 3018ms
stl::map 4681ms
色をポインタの最上位ビットに持たせるかメンバ変数で持たせるかで評価してみましたがまったくといってよいほど同じ速度だったのでポインタに色を持たせる方法で評価しました。
メモリ管理を自前でやると不公平なのでstl::mapのallocatorに同じ仕組みのを使うか自作Mapのメモリ管理にnew,deleteを使うと同等ど土俵で評価できます。
以下は自作Mapのメモリ管理にnew,deleteを使った場合の速度評価です。
stl::mapと自作Mapの比較です。データ数は1M個です。
①乱数の挿入です。
Map 2066ms
stl::map 2612ms
②上記で挿入したデータを同じ乱数系列で削除です。
Map 2205ms
stl::map 3276ms
③昇順で挿入です。
Map 2494ms
stl::map 2231ms
④上記で挿入したデータを昇順で削除です。
Map 1418ms
stl::map 1535ms
⑤降順で挿入です。
Map 2506ms
stl::map 2256ms
⑥上記で挿入したデータを降順で削除です。
Map 1308ms
stl::map 2564ms
⑦乱数の挿入、削除をします。
Map 3523ms
stl::map 4635ms
考察してみる。不等号は"速い>遅い"で表現します。
③⑤はMap<stl::map。挿入は確実に成功するので親ポインタの有無やその他の実装の差が出ている。 ④⑥は④map><⑥Map,④std::map>⑥std::map。違いに心当たりがあるとすれば削除する葉が２つ子を持っていたときMapは右部分木の最小キーの葉で置換するがstd::mapは左部分木の最大キーの葉で置換するということ。
⑦はMap>std::map
①⑦の挿入はキーの重複があり。挿入処理の失敗がありえます。探索処理の比率が大きくなります。
②⑤の挿入はキーの重複がなく、必ず挿入処理が成功します。①⑦に比べ探索処理の比率が小さいです。
このことからMapは探索が高速でstd::mapは挿入が高速であるといえます。
Mapを高速がさせるために親ポインタの有無による速度差であれば改善できませんが、そうでなければ同等の速度まで改善できる可能性があります。
2006/07/02のBlog
[ 04:25 ]
[ ソフトウェア ]
.NETライブラリは大規模で非常に便利で上手く整理されている優れたライブラリである。安全の為にManagedコードになっており。至れり尽くせりだ。しかしながらManagedコードはメモリ管理を任せる代わりに大幅にパフォーマンスを犠牲にしている。
そこでほとんど.NET Frameworkと同等の機能を備えたunmanagedなライブラリがないものだろうか？なければ自作か。出来たならば実はすごく高く売れるんじゃないのだろうか？
http://ja.wikipedia.org/wiki/.NET_Framework によると.NET Frameworkの特徴は、
1,Common Type System (CTS、共通型システム)
2,Common Language Specification (CLS、共通言語仕様)
3,ガベージコレクタを持つCommon Language Runtime (CLR、共通言語ランタイム) 4,MSILと呼ばれる中間言語
5,メタデータ
6,属性
7,コードアクセスセキュリティ
8,アプリケーションドメイン
9,Windows、Web アプリケーション向けクラスライブラリ
10,アセンブリベース Side-by-Side バージョン管理
unmanagedコードで近いもの実装するならC++が候補に挙がる。
1.○typedefで簡単に実装可能。
2.×C++以外に出来るか？
3.×スマートポインタぐらいは出来るが。そもそも速度低下の原因はガベージコレクタだからないほうがいい。
4.×ネイティブだからない。
5.×Refrectionによる型情報の参照。便利な機能だが型情報を埋め込む方法がない。
6.×言語仕様により制限される。
7.△public,protected,privateのみ。
8.×
9.○理論上は
10.×
目的は便利なライブラリを安全性を犠牲にして高速に実行したい、ということなので十分だろう。これらは妄想だ。
そこでほとんど.NET Frameworkと同等の機能を備えたunmanagedなライブラリがないものだろうか？なければ自作か。出来たならば実はすごく高く売れるんじゃないのだろうか？
http://ja.wikipedia.org/wiki/.NET_Framework によると.NET Frameworkの特徴は、
1,Common Type System (CTS、共通型システム)
2,Common Language Specification (CLS、共通言語仕様)
3,ガベージコレクタを持つCommon Language Runtime (CLR、共通言語ランタイム) 4,MSILと呼ばれる中間言語
5,メタデータ
6,属性
7,コードアクセスセキュリティ
8,アプリケーションドメイン
9,Windows、Web アプリケーション向けクラスライブラリ
10,アセンブリベース Side-by-Side バージョン管理
unmanagedコードで近いもの実装するならC++が候補に挙がる。
1.○typedefで簡単に実装可能。
2.×C++以外に出来るか？
3.×スマートポインタぐらいは出来るが。そもそも速度低下の原因はガベージコレクタだからないほうがいい。
4.×ネイティブだからない。
5.×Refrectionによる型情報の参照。便利な機能だが型情報を埋め込む方法がない。
6.×言語仕様により制限される。
7.△public,protected,privateのみ。
8.×
9.○理論上は
10.×
目的は便利なライブラリを安全性を犠牲にして高速に実行したい、ということなので十分だろう。これらは妄想だ。
2006/06/29のBlog
[ 01:27 ]
[ アルゴリズム ]
メモリ管理を最適化してインチキするのではなく、ちゃんと標準のnew,delete演算子で同等の土俵で戦った。
自作mapは6000ms、stl::mapは10000ms。勝った。
要素は親ポインタを持たないということで容量面でも勝った。
実装もシンプル。もしやstlを超えるライブラリ集作れるんじゃね？
自作mapは6000ms、stl::mapは10000ms。勝った。
要素は親ポインタを持たないということで容量面でも勝った。
実装もシンプル。もしやstlを超えるライブラリ集作れるんじゃね？
2006/06/27のBlog
[ 12:14 ]
[ アルゴリズム ]
あるアルゴリズムの実装を学ぶのに他のソースコードから学ぶというのは有用である。
が、他のコードを見るというのはエネルギーがいるものである。
自分の場合、自分で一生懸命実装して、うまく行かない、パフォーマンスに満足しないと感じてから他のソースコードを見るとすっきりと理解できる事が多い。
それは悩みながらアルゴリズムを実装しようとする事でかなり深いところまで動作を理解しているからこそである。それでstl::map::insertの実装が理解できた。まだ見ていないがeraseも同様に理解できよう。
過去に挑戦して諦めた事でも今やれば出来た、という経験は誰しもが持っているだろう。挑戦して諦めるという事は一生諦めるとは限らない。
北斗七星の脇に輝く星が見れないときはまだ挑戦するときではないということだ。ならば馬ごと死ぬがいい！
std::mapの話に戻るがある一定のデータを挿入するのに標準allocator(標準new,delete演算子)を使ったstl::mapは440ms、自作の赤黒木は予め確保した固定長のメモリから要素メモリを確保しているにもかかわらず3200msで圧倒的にstl::mapの勝ちである。
それでstl::mapのソースコードを見ようと思ったのだ。
実装はstl::mapのまま、allocatorを実装すればよいのだが良く分からん！さらに扱うデータ構造に最適化するとなるとstl::mapでは限界がある。
例えば1つのデータにキーが二つ以上ありそれぞれのキーをmapにもたせる等。
stlの欠点といえばそういった僅かな事だけだと思っていたがもう１つ初心者泣かせのコンパイルエラーである。templateを多用しているためコンパイルエラーの原因が一体何なのか慣れないと想像出来ない。大抵は必要なメソッド、演算子の定義がなされていないという事なのだがエラー行がstlのソース内なので戸惑ってしまう。
.NETのライブラリでもstlライクなライブラリは無く、従来の「分かり易い」ライブラリになっており、stlはオブジェクト指向と並んで現実に使いこなすのは至難の業かも知れぬ。
が、他のコードを見るというのはエネルギーがいるものである。
自分の場合、自分で一生懸命実装して、うまく行かない、パフォーマンスに満足しないと感じてから他のソースコードを見るとすっきりと理解できる事が多い。
それは悩みながらアルゴリズムを実装しようとする事でかなり深いところまで動作を理解しているからこそである。それでstl::map::insertの実装が理解できた。まだ見ていないがeraseも同様に理解できよう。
過去に挑戦して諦めた事でも今やれば出来た、という経験は誰しもが持っているだろう。挑戦して諦めるという事は一生諦めるとは限らない。
北斗七星の脇に輝く星が見れないときはまだ挑戦するときではないということだ。ならば馬ごと死ぬがいい！
std::mapの話に戻るがある一定のデータを挿入するのに標準allocator(標準new,delete演算子)を使ったstl::mapは440ms、自作の赤黒木は予め確保した固定長のメモリから要素メモリを確保しているにもかかわらず3200msで圧倒的にstl::mapの勝ちである。
それでstl::mapのソースコードを見ようと思ったのだ。
実装はstl::mapのまま、allocatorを実装すればよいのだが良く分からん！さらに扱うデータ構造に最適化するとなるとstl::mapでは限界がある。
例えば1つのデータにキーが二つ以上ありそれぞれのキーをmapにもたせる等。
stlの欠点といえばそういった僅かな事だけだと思っていたがもう１つ初心者泣かせのコンパイルエラーである。templateを多用しているためコンパイルエラーの原因が一体何なのか慣れないと想像出来ない。大抵は必要なメソッド、演算子の定義がなされていないという事なのだがエラー行がstlのソース内なので戸惑ってしまう。
.NETのライブラリでもstlライクなライブラリは無く、従来の「分かり易い」ライブラリになっており、stlはオブジェクト指向と並んで現実に使いこなすのは至難の業かも知れぬ。
2006/06/23のBlog
[ 12:29 ]
[ アルゴリズム ]
バイナリーツリー(2分探索木)は記憶容量も少なくシンプルで高速であるがソート済みのデータに弱いという弱点がある。
赤黒木はstl::mapの実装に良く使われており1ビットの情報(実際には1バイト)で探索深さをLog2(N)*2以内に抑える事が出来る優れたデータ構造である。
バイナリーツリーも要素の追加場所を乱数で確率的に決定する「ランダマイズドアルゴリズム」とする事でLog2(N)*Tに抑える事を期待できる。この場合単純なバイナリーツリーよりは複雑だが赤黒木よりはシンプルなアルゴリズムになり、余分な記憶領域も要らないことから高速に実行出来るかもしれない。
クイックソートのピボットを乱数で決めると定数Tは概ね1.38程度になるらしいのでランダマイズドバイナリーツリーも同程度であろう。
赤黒木はstl::mapの実装に良く使われており1ビットの情報(実際には1バイト)で探索深さをLog2(N)*2以内に抑える事が出来る優れたデータ構造である。
バイナリーツリーも要素の追加場所を乱数で確率的に決定する「ランダマイズドアルゴリズム」とする事でLog2(N)*Tに抑える事を期待できる。この場合単純なバイナリーツリーよりは複雑だが赤黒木よりはシンプルなアルゴリズムになり、余分な記憶領域も要らないことから高速に実行出来るかもしれない。
クイックソートのピボットを乱数で決めると定数Tは概ね1.38程度になるらしいのでランダマイズドバイナリーツリーも同程度であろう。
2006/06/03のBlog
[ 07:37 ]
[ アルゴリズム ]
以前幅優先探索で正規化した完全な置換表を作る方法を模索したがやっぱり時間がかかりすぎる。原因の一つにαβの枝刈りがされないことだ。
といって深さ優先で置換表を作るとハッシュは衝突が多いし、平衡木はポインタの領域が必要だし、配列のソート全データが集まらないと出来ないためサイズがでかくなり過ぎる。
しかし妥協案を考えた。まず普通にハッシュ置換表を作る。一定量を超えたら配列に直してソートしてディスクに保存。単純だが最も現実的だと思う。
といって深さ優先で置換表を作るとハッシュは衝突が多いし、平衡木はポインタの領域が必要だし、配列のソート全データが集まらないと出来ないためサイズがでかくなり過ぎる。
しかし妥協案を考えた。まず普通にハッシュ置換表を作る。一定量を超えたら配列に直してソートしてディスクに保存。単純だが最も現実的だと思う。
2006/05/30のBlog
[ 22:56 ]
[ ゲーム ]
;)
なんとスト2ダッシュのキャラ限定版"ストリートファイター3"も
;)
;)
;)
近距離、遠距離によって技が変わり、強中弱の技が全てではないにしろ出るようになってる。すばらしい。
2006/05/29のBlog
[ 01:03 ]
[ ゲーム ]
;)
ファミコンの生産が中止されても有志によりソフト制作されている。まずはストゼロ2。
キャラ選択。すげー多い。
;)
VS画面。
;)
リュウVSナッシュ。
ファミコンはまだまだ現役だな。
ファミコンはまだまだ現役だな。
[ 00:04 ]
[ ハードウェア ]
本当にSCSIって信頼性あるのかな？
なんか手段と目的を履き違えているように思える。
SCSIだからではなくって、SCSIブランドは信頼性をイメージさせるのでディスクの冗長性を高めたり高性能なパーツを使ったりしているって言うのが現実ではないのかな。
何しろ大量生産すればコスト安くなるのでわざわざ異なるインターフェースを採用する理由が見つからない。
プラッタやヘッドを作って良い品質、悪い品質のものはいくつか出てくるだろう。そのときに低容量、高容量、低速、高速にランク付けすればいいのに。
なんか手段と目的を履き違えているように思える。
SCSIだからではなくって、SCSIブランドは信頼性をイメージさせるのでディスクの冗長性を高めたり高性能なパーツを使ったりしているって言うのが現実ではないのかな。
何しろ大量生産すればコスト安くなるのでわざわざ異なるインターフェースを採用する理由が見つからない。
プラッタやヘッドを作って良い品質、悪い品質のものはいくつか出てくるだろう。そのときに低容量、高容量、低速、高速にランク付けすればいいのに。
2006/05/25のBlog
[ 03:24 ]
[ ソフトウェア ]
DirectX10は次期WindowsのVistaがリリースされた後にリリースされるそうだ。そしてVista以降のWindowsのみサポートされるとこのとだ。
OSが起動時にデバイスを初期化管理するためリソースのロストはプログラマが管理する必要はないとのこと。
DirectXの重要な変更点はGPUのシェーダプログラミングがより汎用的になり制限が減る事にある。
以前RPGの2Dマップを表示するのに四角ポリゴンは三角ポリゴンを２つ繋げて実現しタイル上に並べる事で表現していたが1つの頂点のみを格納し他の5頂点は計算により生成することが出来ればビデオメモリと帯域の相当な節約になろう。
GPU内でマルチスレッドも可能になるのでCPUは画面のアニメーションや処理のファンクションをGPUに指示するだけのプログラミングモデルが出来るだろう。
OSが起動時にデバイスを初期化管理するためリソースのロストはプログラマが管理する必要はないとのこと。
DirectXの重要な変更点はGPUのシェーダプログラミングがより汎用的になり制限が減る事にある。
以前RPGの2Dマップを表示するのに四角ポリゴンは三角ポリゴンを２つ繋げて実現しタイル上に並べる事で表現していたが1つの頂点のみを格納し他の5頂点は計算により生成することが出来ればビデオメモリと帯域の相当な節約になろう。
GPU内でマルチスレッドも可能になるのでCPUは画面のアニメーションや処理のファンクションをGPUに指示するだけのプログラミングモデルが出来るだろう。
2006/05/22のBlog
[ 14:47 ]
[ データベース ]
色々調べたらAND条件で2つのオペランドで使われる複数列が一つのインデックスに含まれていればインデックス探索される。よく考えれば当たり前であった。
F1>3 AND F2<=4という条件があればF1,F2を一つのインデックスとして扱えばよい。
F1>3 AND F2<=4という条件があればF1,F2を一つのインデックスとして扱えばよい。
[ 01:28 ]
[ ゲーム ]
; Minelvaton Saga
#1 0038-03-0F423F GD
#1 003B-03-0F423F EX
#1 07ED-01-63 KEMURIDAMA
#1 07F2-01-63 KEY
#1 07F0-01-63 INORI
#1 07F1-01-63 KAZE
#1 07EE-01-63 GANYAKU
#1 07F3-01-63 KUKO
#1 07EC-01-63 BOA
#1 07EA-01-63 ADAN
#1 00D1-01-00 ITEM1
#1 00F0-01-06 ITEM2
#1 00F1-01-06 ITEM3
#1 00F2-01-08 ITEM4
#1 00F3-01-09 ITEM5
#1 01DB-01-37 ITEM6
#1 01DC-01-41 ITEM7
#1 01DD-01-33 ITEM8
#1 01DE-01-A5 ITEM9
#1 035E-01-00 ITEM10
#1 06B4-01-5C ITEM11
#1 07D6-01-01 ITEM12
ミネルバトンサーガで敵にあっても終了する
「たから」を全て手に入れた状態
経験値、お金最大
これを.chtファイルとして保存する。
virtual NESで内側からえぐり込むように実行すべし。
#1 0038-03-0F423F GD
#1 003B-03-0F423F EX
#1 07ED-01-63 KEMURIDAMA
#1 07F2-01-63 KEY
#1 07F0-01-63 INORI
#1 07F1-01-63 KAZE
#1 07EE-01-63 GANYAKU
#1 07F3-01-63 KUKO
#1 07EC-01-63 BOA
#1 07EA-01-63 ADAN
#1 00D1-01-00 ITEM1
#1 00F0-01-06 ITEM2
#1 00F1-01-06 ITEM3
#1 00F2-01-08 ITEM4
#1 00F3-01-09 ITEM5
#1 01DB-01-37 ITEM6
#1 01DC-01-41 ITEM7
#1 01DD-01-33 ITEM8
#1 01DE-01-A5 ITEM9
#1 035E-01-00 ITEM10
#1 06B4-01-5C ITEM11
#1 07D6-01-01 ITEM12
ミネルバトンサーガで敵にあっても終了する
「たから」を全て手に入れた状態
経験値、お金最大
これを.chtファイルとして保存する。
virtual NESで内側からえぐり込むように実行すべし。
2006/05/21のBlog
[ 23:46 ]
[ データベース ]
DBの実装を考えていると、単にインデックスを設定して条件式にその列を含ませれば全てのインデックスを活用して高速化されるのか疑問になってきた。
FIELD1 INT INDEX1
FIELD2 INT INDEX2
というスキーマのテーブルTがあったとする。
SELECT * FROM T
WHERE FIELD1>=3
これはDBMSではINDEX1インデックスから数字の3のインデックスを取り出し、その位置からINDEX1の最後のインデックスが指定するレコードまでスキャンする。これは問題ない。
SELECT * FROM T
WHERE FIELD1>=3 AND FIELD2<=1
これは考えてみるとINDEX1,INDEX2のいずれかのインデックスしか使われない気がする。なぜならFIELD1>=3,FIELD2<=1でINDEX1,INDEX2のそれぞれのインデックスは取得できるがレコードをスキャンするインデックスはどちらからしか指定できない(としか思えん)。
革命的な実装方はないのか？
FIELD1 INT INDEX1
FIELD2 INT INDEX2
というスキーマのテーブルTがあったとする。
SELECT * FROM T
WHERE FIELD1>=3
これはDBMSではINDEX1インデックスから数字の3のインデックスを取り出し、その位置からINDEX1の最後のインデックスが指定するレコードまでスキャンする。これは問題ない。
SELECT * FROM T
WHERE FIELD1>=3 AND FIELD2<=1
これは考えてみるとINDEX1,INDEX2のいずれかのインデックスしか使われない気がする。なぜならFIELD1>=3,FIELD2<=1でINDEX1,INDEX2のそれぞれのインデックスは取得できるがレコードをスキャンするインデックスはどちらからしか指定できない(としか思えん)。
革命的な実装方はないのか？
2006/05/20のBlog
[ 06:34 ]
[ アルゴリズム ]
プログラミングしていると複雑な構造体を使うことが多くなる。それらをディスクに読み書きや独自のメモリマネージャを実装するとなるとアライメントが問題になる。
アライメントっていうのは色々なサイズの変数を宣言するとそれらはメモリ上の特定の位置に配置される。1バイトの空き間もなく配置されるのが最も無駄が無いが処理が遅くなる。
楽譜で言うと「タイ」のようにシンコペーションした位置に変数を配置すると2回アクセスが必要になり遅くなるのだ。
変数のサイズは大体1,2,4,8バイトである。それぞれ8,4,2,1分音符の長さ＝容量を必要とすると考えていただきたい。
音符で言うと8,4,2,1分音符で並べるとタイが発生しまくるが1,2,4,8分音符なら綺麗に書ける。
音符の組み合わせによっては休符＝パディングを挟むことで高速にアクセスするようにする。
それでもIA32プロセッサはアライメントを跨いでも若干の速度低下ですむが、他のRISCプロセッサは例外を発生させOSがトラップしてメモリアクセスさせるために大幅にパフォーマンスを犠牲にしてしまう。
この問題はこれからもずっと続いてしまうのか…？
アライメントっていうのは色々なサイズの変数を宣言するとそれらはメモリ上の特定の位置に配置される。1バイトの空き間もなく配置されるのが最も無駄が無いが処理が遅くなる。
楽譜で言うと「タイ」のようにシンコペーションした位置に変数を配置すると2回アクセスが必要になり遅くなるのだ。
変数のサイズは大体1,2,4,8バイトである。それぞれ8,4,2,1分音符の長さ＝容量を必要とすると考えていただきたい。
音符で言うと8,4,2,1分音符で並べるとタイが発生しまくるが1,2,4,8分音符なら綺麗に書ける。
音符の組み合わせによっては休符＝パディングを挟むことで高速にアクセスするようにする。
それでもIA32プロセッサはアライメントを跨いでも若干の速度低下ですむが、他のRISCプロセッサは例外を発生させOSがトラップしてメモリアクセスさせるために大幅にパフォーマンスを犠牲にしてしまう。
この問題はこれからもずっと続いてしまうのか…？
2006/05/15のBlog
[ 05:42 ]
[ アルゴリズム ]
オンメモリDBではB-Treeではなくよりメモリに最適化したT-Treeというデータ構造を採用しているらしい。
これって赤黒木よりいいのか？そんなデータ構造想像つかんなー。
最近並列アルゴリズムについて考えている。
より粒度の粗いタスクにスレッドを割り当てればロックのコストが少なく住むが、早く処理が終わってしまうスレッドも出てくるので平均的にタスクを割り当てるのは難しい。
ちょっと考えた粗い粒度の並列処理の典型的な手続きは、
スレッド1,スレッド2,スレッド3...
とCPUの数だけスレッドを割り当てる。
その後これらの命令を呼び出したスレッド=プライマリスレッドは子スレッドがすべて終了するまでスリープ状態にする(APIがあったと思う)。
続きの処理を書く。つまり並列処理は子スレッドに任せ、直列処理はプライマリスレッドに任せるということだ。
将来的にこういうのは言語レベルでサポートされるようになるんだろうな。
AMDの見解では現状のアプリケーションを進歩させるだけではマルチコアの恩恵は受けれるもののせいぜい8CPUぐらいであると見ている。
それに対しIntelはレイトレーシング、AIなどの分野では複数スレッドに分解したとき極めて高い独立性を得ることができるため数十のマルチコアでも効果を出すことができるらしい。
現在のアプリケーションを並列化する技術は必要ではあるが性能向上にあまり期待しないほうがよさそうだ。
それよりはIntelが求める分野の研究をしたほうが有意義ではないかと思う。
数十のマルチコアとなるとやはりCellプロセッサのようなローカルメモリを持つアーキテクチャーがベターなのか？
キャッシュのコヒーレンシを考慮くすることなく、各プロセッサが明示的にキャッシュにアクセスできるということはハードウェアによって制御されていたキャッシュをプログラマーが指定することになる。スケジューラをCPUからコンパイラに任せたVLIWやEPICみたいなものか。
命令セットはよくわからんが00000000～00FFFFFFをローカルメモリにマッピングして、それ以外は実メモリというのが命令セットを肥大化させずに済みそう。
これって赤黒木よりいいのか？そんなデータ構造想像つかんなー。
最近並列アルゴリズムについて考えている。
より粒度の粗いタスクにスレッドを割り当てればロックのコストが少なく住むが、早く処理が終わってしまうスレッドも出てくるので平均的にタスクを割り当てるのは難しい。
ちょっと考えた粗い粒度の並列処理の典型的な手続きは、
スレッド1,スレッド2,スレッド3...
とCPUの数だけスレッドを割り当てる。
その後これらの命令を呼び出したスレッド=プライマリスレッドは子スレッドがすべて終了するまでスリープ状態にする(APIがあったと思う)。
続きの処理を書く。つまり並列処理は子スレッドに任せ、直列処理はプライマリスレッドに任せるということだ。
将来的にこういうのは言語レベルでサポートされるようになるんだろうな。
AMDの見解では現状のアプリケーションを進歩させるだけではマルチコアの恩恵は受けれるもののせいぜい8CPUぐらいであると見ている。
それに対しIntelはレイトレーシング、AIなどの分野では複数スレッドに分解したとき極めて高い独立性を得ることができるため数十のマルチコアでも効果を出すことができるらしい。
現在のアプリケーションを並列化する技術は必要ではあるが性能向上にあまり期待しないほうがよさそうだ。
それよりはIntelが求める分野の研究をしたほうが有意義ではないかと思う。
数十のマルチコアとなるとやはりCellプロセッサのようなローカルメモリを持つアーキテクチャーがベターなのか？
キャッシュのコヒーレンシを考慮くすることなく、各プロセッサが明示的にキャッシュにアクセスできるということはハードウェアによって制御されていたキャッシュをプログラマーが指定することになる。スケジューラをCPUからコンパイラに任せたVLIWやEPICみたいなものか。
命令セットはよくわからんが00000000～00FFFFFFをローカルメモリにマッピングして、それ以外は実メモリというのが命令セットを肥大化させずに済みそう。
2006/05/12のBlog
[ 06:55 ]
[ アルゴリズム ]
http://webpages.ull.es/users/jriera/Docencia/AVL/AVL%20tree%20applet.htm
ここにAVL、赤黒木、SPLの追加削除を視覚化したJavaアプレットがある。
これは凄い！脳内でアルゴリズムをシナプスに理解させることができよう。
メモリ管理方法によってコンテナの速度は大幅に変わる。アロケータの実装を具体的に説明しているサイトはないものか？
B木ってディスクのセクタを考慮することで速度を最適化できるらしいが、メモリ上でもキャッシュのサイズを考慮することで速度を上げれないか？
ここにAVL、赤黒木、SPLの追加削除を視覚化したJavaアプレットがある。
これは凄い！脳内でアルゴリズムをシナプスに理解させることができよう。
メモリ管理方法によってコンテナの速度は大幅に変わる。アロケータの実装を具体的に説明しているサイトはないものか？
B木ってディスクのセクタを考慮することで速度を最適化できるらしいが、メモリ上でもキャッシュのサイズを考慮することで速度を上げれないか？
2006/05/11のBlog
[ 10:43 ]
[ マンガ、アニメ ]
聖闘士星矢が恋しくてネットを見てたらアニメ版聖闘士星矢のサイトを発見。見ていると思い出す思い出す。
青銅2軍の面子でリーダー格は邪武であるがウルフ那智を知っているだろうか？
彼は原作では一輝に幻魔拳を食らい悲惨な負け方をしたが、アニメバージョンの彼は非常にカッコイイ聖衣装着シーンを持っている。
彼の栄光
「カモーン ウルフクロース！！」
ピカァァァァッ！！！
「アームアンドニーッ！」
「ショルダーッ！レッグアンドチェストッ！」
シャキィィンッ！シャキィィンッ！シャキィィンッ!！
「アンドマスクッ！パーフェクトッ！！」
バァァァァァンッ！！！！
空を裂くマッハの拳！リングに駆ける青き狼！！
その名は狼星座の聖闘士、那智！！
以前見たとき「な、なんてカッコイイんだ」と子供心に思った。
これを日常生活に応用させたい。
首相が車を呼ぶときに、
「カモーン プレジデント！！」
ブロロロローッ！！！
「11時アンド首相官邸前ッ！」
「目的地ッ！皇居ッ！」
カチャッ！ピッ！グオオオオッ!！
「アンド伊勢ッ！パーフェクトッ！！」
ラジャアアアッ！！！！(運転手)
空を裂く高速の車！道路を駆ける黒きセダン！！
その名は日産のセレブ御用達、プレジデント！！
青銅2軍の面子でリーダー格は邪武であるがウルフ那智を知っているだろうか？
彼は原作では一輝に幻魔拳を食らい悲惨な負け方をしたが、アニメバージョンの彼は非常にカッコイイ聖衣装着シーンを持っている。
彼の栄光
「カモーン ウルフクロース！！」
ピカァァァァッ！！！
「アームアンドニーッ！」
「ショルダーッ！レッグアンドチェストッ！」
シャキィィンッ！シャキィィンッ！シャキィィンッ!！
「アンドマスクッ！パーフェクトッ！！」
バァァァァァンッ！！！！
空を裂くマッハの拳！リングに駆ける青き狼！！
その名は狼星座の聖闘士、那智！！
以前見たとき「な、なんてカッコイイんだ」と子供心に思った。
これを日常生活に応用させたい。
首相が車を呼ぶときに、
「カモーン プレジデント！！」
ブロロロローッ！！！
「11時アンド首相官邸前ッ！」
「目的地ッ！皇居ッ！」
カチャッ！ピッ！グオオオオッ!！
「アンド伊勢ッ！パーフェクトッ！！」
ラジャアアアッ！！！！(運転手)
空を裂く高速の車！道路を駆ける黒きセダン！！
その名は日産のセレブ御用達、プレジデント！！
2006/05/10のBlog
[ 22:46 ]
[ 妄想 ]
コンピュータに自動送信させたいんだけど、規約違反ってどんなのがあるのかな？
ほとんど監視してないサイト
携帯のサイトがPCで見れるサイト
登録がPCのフリーメールアドレスでOK
ちゃんとキャッシュバックが支払われる
こういったサイトの情報が沢山欲しいな。
ほとんど監視してないサイト
携帯のサイトがPCで見れるサイト
登録がPCのフリーメールアドレスでOK
ちゃんとキャッシュバックが支払われる
こういったサイトの情報が沢山欲しいな。
2006/05/04のBlog
[ 05:19 ]
[ アルゴリズム ]
現在赤黒木(2色木)が最も性能がよいらしい。
スキップリスト(skip list)はメモリが余分にいる。が、この乱数でリンク位置を決定する方法を参考に二分探索木の計算量をN*Log2(N)に近づける方法を考えた。
ソートされた①②③④⑤⑥⑦というデータをバランス木で表現すると、
○○○④○○○
○②○○○⑥○
①○③○⑤○⑦
になる。二分探索木では
①
○②
○○③
○○○④
○○○○⑤
○○○○○⑥
○○○○○○⑦
これは要素を追加する時は必ず葉につけるからだ。
葉に付けるか枝につけるかを乱数で決定すれば、
①
これに②を追加する。乱数により葉に付けることに決定。
①○
○②
これに③を追加する。乱数により②と置き換えることに決定。
①○○
○○③
○②○
これに④を追加する。乱数により①と置き換えることに決定。
○○○○④
①○○○○
○○③○○
○②○○○
これに⑤を追加する。乱数により④の葉に追加決定。
○○○○④○○○○
①○○○○○○○⑤
○○③○○○○○○
○②○○○○○○○
これに⑥を追加する。乱数により⑤の葉に追加決定。
○○○○④○○○○○○
①○○○○○○○⑤○○
○○③○○○○○○○⑥
○②○○○○○○○○○
これに⑦を追加する。乱数により⑤と置き換えることに決定。
○○○○④○○○○○○
①○○○○○○○⑦○○
○○③○○○⑤○○○⑥
○②○○○○○○○○○
どのように確率を決定するかを考える。
ノードのレベルが1～あるとする。
レベル1に追加される確率は1/N。
レベル2に追加される確率は2/N。
レベル3に追加される確率は4/N。
...
追加する位置に既にデータがあった場合は既存データを葉に付ける。
この方法は単純でオーバヘッドが少なく、少々バランスが悪くても良い性能が発揮できそうな気がする。
データを削除する時はどうすればよいだろうか？
うーん、いやまて追加、削除は通常の二分探索木として乱数から「回転する確率」によって回転させるアイデアはどうだろうか？
スキップリスト(skip list)はメモリが余分にいる。が、この乱数でリンク位置を決定する方法を参考に二分探索木の計算量をN*Log2(N)に近づける方法を考えた。
ソートされた①②③④⑤⑥⑦というデータをバランス木で表現すると、
○○○④○○○
○②○○○⑥○
①○③○⑤○⑦
になる。二分探索木では
①
○②
○○③
○○○④
○○○○⑤
○○○○○⑥
○○○○○○⑦
これは要素を追加する時は必ず葉につけるからだ。
葉に付けるか枝につけるかを乱数で決定すれば、
①
これに②を追加する。乱数により葉に付けることに決定。
①○
○②
これに③を追加する。乱数により②と置き換えることに決定。
①○○
○○③
○②○
これに④を追加する。乱数により①と置き換えることに決定。
○○○○④
①○○○○
○○③○○
○②○○○
これに⑤を追加する。乱数により④の葉に追加決定。
○○○○④○○○○
①○○○○○○○⑤
○○③○○○○○○
○②○○○○○○○
これに⑥を追加する。乱数により⑤の葉に追加決定。
○○○○④○○○○○○
①○○○○○○○⑤○○
○○③○○○○○○○⑥
○②○○○○○○○○○
これに⑦を追加する。乱数により⑤と置き換えることに決定。
○○○○④○○○○○○
①○○○○○○○⑦○○
○○③○○○⑤○○○⑥
○②○○○○○○○○○
どのように確率を決定するかを考える。
ノードのレベルが1～あるとする。
レベル1に追加される確率は1/N。
レベル2に追加される確率は2/N。
レベル3に追加される確率は4/N。
...
追加する位置に既にデータがあった場合は既存データを葉に付ける。
この方法は単純でオーバヘッドが少なく、少々バランスが悪くても良い性能が発揮できそうな気がする。
データを削除する時はどうすればよいだろうか？
うーん、いやまて追加、削除は通常の二分探索木として乱数から「回転する確率」によって回転させるアイデアはどうだろうか？
2006/05/03のBlog
[ 22:22 ]
[ アルゴリズム ]
固定長の要素を動的に拡張縮小するためのアルゴリズムを以前考えた。
単方向リストで全空き要素を繋ぐ。
メモリを要求されると単方向リストの先頭要素を返す。
メモリが返却されると単方向リストの先頭要素に返す。
シンプルだ。これに対して可変長の要素を動的に拡張縮小するためのアルゴリズムを考えた。
可変長の要素の長さ毎にメモリ管理するための配列を用意する。あと割り当てようの大きなメモリを用意する。
(1)2バイト要求されたら0を割り当てる。
(2)4バイト要求されたら2を割り当てる。
(3)1バイト要求されたら3を割り当てる。
(4)4バイト要求されたら4を割り当てる。(2)をポイントする。
(4)2バイト要求されたら6を割り当てる。(1)をポイントする。
ということで各サイズの要素ごとに単方向リストが構築される。
こうして追加、削除していくとメモリの断片化が発生する。
これをデフラグするためには次の要素を指し示していた変数に要素のバイト数を代入する。
そして同じサイズの要素を直線的に並べる。
例、デフラグ前
ABACBAACBBC
例、デフラグ後
AAAABBBBCCC
こうした後、サイズを代入していた変数に次の要素を指せば完了である。
単方向リストで全空き要素を繋ぐ。
メモリを要求されると単方向リストの先頭要素を返す。
メモリが返却されると単方向リストの先頭要素に返す。
シンプルだ。これに対して可変長の要素を動的に拡張縮小するためのアルゴリズムを考えた。
可変長の要素の長さ毎にメモリ管理するための配列を用意する。あと割り当てようの大きなメモリを用意する。
(1)2バイト要求されたら0を割り当てる。
(2)4バイト要求されたら2を割り当てる。
(3)1バイト要求されたら3を割り当てる。
(4)4バイト要求されたら4を割り当てる。(2)をポイントする。
(4)2バイト要求されたら6を割り当てる。(1)をポイントする。
ということで各サイズの要素ごとに単方向リストが構築される。
こうして追加、削除していくとメモリの断片化が発生する。
これをデフラグするためには次の要素を指し示していた変数に要素のバイト数を代入する。
そして同じサイズの要素を直線的に並べる。
例、デフラグ前
ABACBAACBBC
例、デフラグ後
AAAABBBBCCC
こうした後、サイズを代入していた変数に次の要素を指せば完了である。
2006/04/30のBlog
[ 09:49 ]
[ データベース ]
ライセンス料が高い理由は今まで複数のサーバで構築されていたものをより少ないサーバで実現できるかららしい。
オンメモリデータベース自体の信頼性の低さは、少ないハードウェアを利用することによる信頼性の高さでペイ出来るのかもしれない。
オンメモリデータベース自体の信頼性の低さは、少ないハードウェアを利用することによる信頼性の高さでペイ出来るのかもしれない。
2006/04/29のBlog
[ 06:01 ]
[ アルゴリズム ]
基本的に配列で実現する。
メモリ管理は自前で行う。
GCによるメモリ配置の移動のように1つ以上のテーブルを移動することが考えられる。出来るだけ移動量を減らし、移動頻度も減らしたい。メモリ管理アルゴリズムやパラメータはベンチマークから決定するのが良いと思う。
直線(シーケンシャル)プログラムにすれば排他処理なくなり高速化される。しかしマルチプロセッサの効果は発揮できなくなる。
直線処理でもある程度並列化は可能だ。
1.TCP/IPからコマンド受付、デコード、コンパイル等。
2.実際の処理。ソート、マージ、テーブルとレコードの再配置。インデックスの再構築等。これはメモリを直線的にアクセスするため、メモリの帯域がボトルネックとなると思われる。
3.結果セットをTCP/IPから返す。結果セットは各セッション毎に必要になると思われる。が、圧縮して転送すればセッション毎にメモリを用意しなくて済むかも。
4CPUが有効に働けば御の字だ。
なんかオンメモリデータベースは1ライセンスウン千万円だったりするので美味しいかも。
メモリ管理は自前で行う。
GCによるメモリ配置の移動のように1つ以上のテーブルを移動することが考えられる。出来るだけ移動量を減らし、移動頻度も減らしたい。メモリ管理アルゴリズムやパラメータはベンチマークから決定するのが良いと思う。
直線(シーケンシャル)プログラムにすれば排他処理なくなり高速化される。しかしマルチプロセッサの効果は発揮できなくなる。
直線処理でもある程度並列化は可能だ。
1.TCP/IPからコマンド受付、デコード、コンパイル等。
2.実際の処理。ソート、マージ、テーブルとレコードの再配置。インデックスの再構築等。これはメモリを直線的にアクセスするため、メモリの帯域がボトルネックとなると思われる。
3.結果セットをTCP/IPから返す。結果セットは各セッション毎に必要になると思われる。が、圧縮して転送すればセッション毎にメモリを用意しなくて済むかも。
4CPUが有効に働けば御の字だ。
なんかオンメモリデータベースは1ライセンスウン千万円だったりするので美味しいかも。
2006/04/28のBlog
[ 06:46 ]
[ 勉強 ]
「文法なんかやっても会話できん」
などとのたまう輩がいる。で貴様は会話は勿論文法も正しく出来るのか？
また実際に英語が堪能な者も同じようなことを言うことがいう。彼らは既に基礎を身に着けているからこそいえる、強者の理論だ。
確かにカナダに来る前に勉強してたかといえば結果の出る勉強はしていない。結果の出ない勉強はした。
色んな技術を習得するのに伝統的で保守的な手法がある。何も知らない人ならばそれを選択するのがベターであろう。
ちょっと知ったからといって自称進歩的文化人を名乗ってうまくいけばいいのだが。
などとのたまう輩がいる。で貴様は会話は勿論文法も正しく出来るのか？
また実際に英語が堪能な者も同じようなことを言うことがいう。彼らは既に基礎を身に着けているからこそいえる、強者の理論だ。
確かにカナダに来る前に勉強してたかといえば結果の出る勉強はしていない。結果の出ない勉強はした。
色んな技術を習得するのに伝統的で保守的な手法がある。何も知らない人ならばそれを選択するのがベターであろう。
ちょっと知ったからといって自称進歩的文化人を名乗ってうまくいけばいいのだが。
2006/04/26のBlog
[ 14:28 ]
[ アルゴリズム ]
前回多次元インデックスで<,>,<=,>=,BETWEEN演算子を使えるようにするような記述をしたが、正確にはBETWEEN,=,<>演算子のみだ。
なぜなら(0,1,4)と(3,2,6)のどちらが大きいかはわからないからだ。
だが(0,1,4)と(3,2,6)の範囲の座標は条件に指定できる。
もうひとつBETWEENに指定する座標を含むか、含まない
なぜなら(0,1,4)と(3,2,6)のどちらが大きいかはわからないからだ。
だが(0,1,4)と(3,2,6)の範囲の座標は条件に指定できる。
もうひとつBETWEENに指定する座標を含むか、含まない