Entry

興味に勝る動機なしの話

2009年03月03日

前回 C の話で盛り上がっていた同僚は,休日にいろいろ実験していたらしく,連結リストにランダムアクセスする際のスピードを向上させようとゴニョゴニョやっていたそうです。同僚といっても,あたしよりもかなり若い20代前半の人なんですけれど,ともかく暇さえあればいろいろ作ってる。仕事しろよ。

一般的に,連結リスト構造でランダムアクセスするのはご法度で,当の実験でも「90万件くらい登録したけど40万件目くらいから目に見えて遅くなった」と話していました。そりゃそうだ。ただ,挿入や削除の速さを考えると,リストの利点は捨てがたいそうで,折衷案はないかとごにょごにょ。

この人は,ともかくいろいろ試す人なもんで,毎度のことながら感心してしまうんですけれど,改善したデータ構造では,100件くらいずつをひとつの単位にしたインデックスの構造体を上位に作って,間接的にアクセスすることにしたんだそうな。インデックスは二分木で作ってみたとか言ってたっけな。おそらく,これなら,配列のインデックスアクセスには(まだかなり)劣るけれども,ある程度の速さは期待できそうです。挿入・削除が面倒になるので(インデックスも更新するから),全般的にオーバーヘッドを均すだけなのかもしれませんけど。

で,こゆ話,どこかで聞いたなと思っていたところ,大規模疎行列のインデックスアクセスのアルゴリズムに,そゆ話があるのを思い出しました。

ここでは,「チャンク」と呼ばれるデータ構造の単位を上位に作って,値があるチャンクかを判断することで大規模疎行列演算の効率化を図っています。基本的な構造がリスト構造だったので,当の彼に紹介したところ,嬉々として読んでいました。興味に勝る動機なしといったところか。つか,仕事してほしい。

なんだか,彼を見ていると,自分がよりいっそう老け込んだ気がしてしまいます。そういや白髪増えたな。

Trackback
Trackback URL:
Ads
About
Search This Site
Ads
Categories
Recent Entries
Log Archive
Syndicate This Site
Info.
クリエイティブ・コモンズ・ライセンス
Movable Type 3.36
Valid XHTML 1.1!
Valid CSS!
ブログタイムズ

© 2003-2012 AIAN