Listというgemを書きました。
といってもインターフェースがArrayとの完全互換を目標にしているのでまだ未完成です。
なんせメソッドが多い。。。
でも待ちきれないので公開しちゃいます。
拡張ライブラリで書いているのですが、MRIの1.9.3、2.0.0、2.1.0に対応しています。
一部機能でArrayに比べ192倍の性能を秘めています。
ListとはLinkedListとも呼ばれる基本的なデータ構造の一種で「最終的な長さはわからないけどどんどん追加できる配列」がほしいときに、主にCでよく使われます。
http://ja.wikipedia.org/wiki/%E9%80%A3%E7%B5%90%E3%83%AA%E3%82%B9%E3%83%88
今回は単純な片方リストを実装しています。 また、片方向循環リストも実験的に実装しています。
Arrayがあればいいじゃん？
はいそうです。でも違います。
Rubyは大クラス主義をとっているためJavaやC#のようにごちゃごちゃと同じことをするclassはありません。スタックや行列など配列っぽいものはすべてArrayで表現しています。
しかしGemなら色々模索してもいいじゃない！という独自理論によってArrayと全く同じ動作をするけどアルゴリズムが違うものを作ってみました。MRI命なのでMRIでの利用しか考えてません。
アルゴリズムが違えばそれぞれのメソッドの実現方法が違います。よってArrayより早いメソッド、遅いメソッドができました。
RubyでのArrayの説明
配列を実現しようと思ったらListのような方法もありますが、Rubyの場合はいわゆる普通の配列を使っています。各データを等間隔に連続で並べて「各データサイズ×番号」を計算するだけで欲しいデータを一瞬でひけるようにしているのが特徴です。電車の横並びの座席のイメージです。Rubyではデータを全てlongと同じサイズの「VALUE」で統一しているのでどのclassでも同じデータサイズとして配列に収めることができます。
Rubyではこの配列をラップしていて、配列の「先頭の位置」と「長さ」と「メモリを確保している分の長さ」を持ちます。「メモリを確保している分の長さ」を持っている理由はある程度大きめにメモリをとっておいて、一般的にコストの高いメモリの再取得(realloc)の回数を減らすためです。この戦略ならばちょっと配列を追加するだけならメモリを確保せず済みます。
配列の特徴は「参照」の早さです。その代わり苦手なのは配列の途中にデータを追加・削除です。この場合、後ろのデータを全部少しずつ隣の席にずらさなければなりません。
Listの説明
Listはデータを「自分自身のデータ」と「次のデータ」を持つデータ構造でラップします。 次のアドレスを再帰的に見ていけば次々に連続した値が参照できるという仕組みです。
利点はメモリの確保場所がバラバラでもいいこと。欠点はそれ故に参照が先頭から順番にループを回して調べなければならないことです。
利点はつまり、「列の真ん中辺りにデータを追加」をした時に他のデータをどっこらしょと大移動させなくても「次のデータ」を書き換えるだけでデータを列に追加できます。延長コードのイメージです。
今回はこの「自分自身のデータ」と「次のデータ」を持つデータ構造を更に、「最初の位置」と「最後の位置」と「長さ」を持つデータ構造でラップしています。
「最後の位置」も「長さ」も純粋な片方リストには必要ないのですが、処理の効率化のために追加しています。
予想
Arrayは参照など基本的な動作は早そうです。unshiftで差がでそう。insert、delete_atではかなりListが速いんじゃないかなと考えられます。
比べてみた
四の五の言ったので数値で比較しましょう。同じ100000個のデータ列で同じ操作を実行させ100000回繰り返すBenchmarkをとりました。
比べたメソッドは、new、[ ]、push、unshift、pop、shift、insert、delete_atです。
https://github.com/ksss/list/blob/master/spec/benc ...
上から見ると、まず100000回も繰り返すループ(times)を作るのにかかる時間を測っています。 移行の計測にはだいたいこれぐらいの余計な時間が追加されていると考えられます。
new: この時点でListの方が遅いです。処理的にはほぼ何もしていないのでこれはもうRArray v.s. RDataの性能の差ですかね。100000回繰り返した時のArray/List比は約0.7倍です。以下この計算で処理速度を比較します。
[]: 100000個目のデータを参照させています。こちらはやはり毎回100000回ループが走るのでListが圧倒的に遅く、性能比は0.001倍と1000倍遅くなっています。
push: Arrayは溢れそうになったらある程度多めにメモリを確保する戦略から追加に弱いという弱点を克服しています。対するListは毎回mallocが発生するため、結果的にArrayより遅くなっていますが、およそ0.7倍の比しかありません。
unshift: これはArrayで不得意かと思いきや、Rubyではある程度大きいデータになると共有をうまく使って工夫し高速しているようです。性能比は0.6倍です。
pop: Arrayはメモリはそのままにしておいて、ただ自身の長さを短くするだけなので非常に高速です。対するListは最後のデータを取り出すには最後の一個手前のデータの「次のアドレス」を書き換えなければならない、つまり長さ分の処理回数が必要になり非常に低速です。これは自身の長さを利用して工夫すれば改善の余地があるかもしれませんが、循環リストにできる仕様と相談になりそうです。比はなんと0.0013倍です。
shift: 先頭データを消すのでList有利かとおもいきや、データの共有や先頭アドレスを隣にずらすという方法で非常に高速に処理しています。オブジェクトの開放用のアドレスはどうしているのか気になります。。。差は0.5倍と食らいついてはいますが、Listは律儀に毎回freeが入るのでその分遅くなっているようです。
insert: いよいよ特徴的な効果が出ています。Arrayはこれまで様々な工夫で高速化を図っていましたが、途中にデータを入れられるとさすがに以降全てのデータをずらさなければならないので低速な結果になっています。Listでは挿入する前後のデータに対しては少しの操作で済むので期待通り高速です。差は192倍です。(当社比)
delete_at: こちらもinsertと同じことが起こっているためListが非常に高速です。差は75倍です。
結果
結果としては1000倍遅い時もあれば192倍速い時もある。と、期待通りの差別化が図れているようです。
利用方法
正直思いつきからの実装だったので考えていなかったのですが。特徴を考えるとデータを追加するとソートした順番の位置に挿入するSortedListを作るのに向いているかなと予想しています。 まだやりたいことが沢山あるので先の話になりそうですが、これはRubyで書こうかな。
類似ライブラリ
気にしていません！
