マージソート(1) - sileのブログ
久々にマージソートを実装してみたら、結構良いものができたので載せておく。 まずはパッケージ定義とグルーバルな宣言。 ;;;; SBCL-1.0.51 (x86-64) (defpackage merge-sort (:use common-lisp) (:shadow :common-lisp sort) (:export sort)) (in-package :merge-sort) (declaim (inline halve merge-lists) (optimize (speed 3) (debug 0) (safety 0))) ユーティリティ関数とマクロ。 ;; 整数nを二分割する関数 ;; => (values n1 n2) ;; ;; nが奇数の場合は (= (1+ n1) n2) となる (defun halve (n) (declare (fixnum n)) (mu
SA-IS: SuffixArray線形構築 - sileのブログ
『Linear Suffix Array Construction by Almost Pure Induced-Sorting』*1という論文を参考にして、Induced-Sortingを用いたSuffixArrayの線形構築アルゴリズム(SA-IS)をCommon Lispで実装した。 以下、そのソースコードとメモ書き。 線形構築 汎用ソートアルゴリズムと今回実装したSA-ISアルゴリズムでのSuffixArray構築時間の簡単な比較。 百文字〜一千万文字の文字数のテキストを入力として与えて、その構築時間を計測。 百文字千文字一万文字十万文字百万文字一千万文字 汎用ソート*20.000 sec0.002 sec0.023 sec0.358 sec5.604 sec94.196 sec SA-IS0.031 sec0.120 sec0.135 sec0.335 sec2.580 sec2
B木 - sileのブログ
B木をWikipediaの記事*1を参考にしてcommon lispで実装してみた。 実装 実装コード。 コメント抜きで140行程度。 オンメモリ。最適化なし。 ※ 末尾に全部まとめた(+ コメント無し)のソースコード有り ;;;; パッケージ定義 (defpackage btree (:use :common-lisp) (:shadow :common-lisp get set remove) (:export make ; B木作成 get ; 検索および挿入(setf (get ...)) remove)) ; 削除 (in-package :btree) ;;;; 補助関数群 ;; 常にnilを返す (defun return-nil (&rest _) (declare (ignore _)) nil) ;; 常に三番目の引数を返す (defun identity3 (_1 _
マルチキークイックソート - sileのブログ
「Sorting and Searching Strings」で説明されているマルチキークイックソートの実装。 詳細はリンク先を参照。 マルチキークイックソート 文字列の配列のソートが高速に行える URL("http://...")の配列のような接頭部分の重複率が高い文字列配列の場合でも性能が低下しにくい クイックソート + 基数ソート、のような感じ？ ソート方法 基本的には通常のクイックソートと似ていて「ピボット要素*1を選んで、配列を分割する」といったことを繰り返す。 ただし、クイックソートは各段階で配列を二分割(ピボット要素よりも大きいか小さいか*2 )し、そのための比較には要素(文字列)全体を用いるのに対して、マルチキークイックソートでは、配列は三分割(ピボット要素よりも大きいか小さいか、それとも等しいか)され、そのための比較には文字列全体ではなく(各段階で)一文字のみ、が用いられ
クイックソートの内部ループ - sileのブログ
クイックソートの内部ループには(自分が知っている限りでは)二種類あるな、とふと思ったので、思い出して書いてみた。 ;;; 補助マクロ/関数 ;; whileループ (defmacro while (exp &body body) `(loop WHILE ,exp DO (locally ,@body))) ;; 配列をシャッフル (defun shuffle (ary) (loop REPEAT 2 DO (loop FOR i FROM 0 BELOW (length ary) DO (rotatef (aref ary i) (aref ary (random (length ary)))))) ary) ;;; クイックソート１ ;;; 内部ループ: ;;; - 配列の前方と後方から不正な要素を探して、見つかった場合は互いを交換する、ということを繰り返す (defun qsort1
Algorithmic Composition: A Gentle Introduction to Music Composition Using Common LISP and Common Music
Published by: Ann Arbor, MI: Michigan Publishing, University of Michigan Library, 2003. Permissions: This work is protected by copyright and may be linked to without seeking permission. Permission must be received for subsequent distribution in print or electronically. Please contact mpub-help@umich.edu for more information. For more information, read Michigan Publishing's access and usage policy.
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
