[B! lisp][cpp] nfunatoのブックマーク

nfunato id:nfunato

lispとcppに関するnfunatoのブックマーク (2)

簡潔データ構造超入門II 〜ちょっとだけ実用的な簡潔ビットベクトル〜 - EchizenBlog-Zwei
簡潔データ構造(Succinct Data Structure)の魅力を紹介する本シリーズ。前回の記事では疎ベクトルを簡潔データ構造を使って効率的に実装する方法を紹介した。前回の実装ではビットベクトルのサイズの上限が256だった。今回はこれを拡張して任意の大きさを扱える簡潔ビットベクトルの実装例を紹介する。また前回はrank()を定数時間で実現する方法を紹介した。今回はこれを使ってselect()を二分探索(O(logN))で実装する。以上の2つの改善によってビットベクトルのサイズに制限がなくrank()/select()の双方を備えた、実用性のある簡潔ビットベクトルが実現できる。前回の記事：簡潔データ構造超入門〜つくって学ぶ簡潔ビットベクトル〜 - EchizenBlog-Zwei サイズに制限のないビットベクトルは前回実装した簡潔ビットベクトルのsbvクラスを用いて実装する
nfunato 2011/08/23
data structure

c++

lisp

cpp
リンク
C++とcommon lispの実行速度比較(素数判定) - sileのブログ
今日たまたま見つけた『(Sather を試そう) 1. Sather vs C++: 実行速度の比較』*1というページに触発され、lisp(sbcl-1.0.28)でも同様の比較を行ってみた。 C++のソースコードは、上記ページのものと同様だが、g++のオプションには'-O3'を渡している。実行結果は以下の通り。 > time ./prime_cpp 10000000 > /dev/null real 0m1.032s user 0m0.992s sys 0m0.004s 対するlispのコード。 ※ 変数名などは、自分の好みに合わせて変えているが、アルゴリズム的にはC++のものと同様(のはず)。 ;;;; 宣言などのため、C++のソースより長くなってしまっている (declaim (optimize (debug 0) (safety 0) (speed 3) (compilation
nfunato 2011/02/15
lisp

cpp

c++

prime_number
リンク
1