マルチキークイックソート - 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
行をバイト列として読み込む - sileのブログ
テキストファイルの各行をバイト列として読み込むマクロを定義。 SBCL等のように文字列を内部的にユニコードとして表現している処理系では、テキストファイルを読み込む際、そのファイルが不正なバイト列を含んでいると読み込みに失敗することがあるので、その対処として。 ;;;; エラーの例 ;;;; sbcl-1.0.40 ;;;; ;; 普通の行読み込みマクロを定義 (defmacro each-file-line ((line filepath) &body body) `(with-open-file (#1=#:in ,filepath) (loop FOR ,line = (read-line #1# nil nil) WHILE ,line DO (progn ,@BODY)))) ;;;; ;; 不正なバイト列を含むテキストファイルの作成 (with-open-file (out "s
FunkyMic / SourceCode usage demo
FAQTo delete a repo, swipe horizontally on top of the project in project list viewTo change the font size, pinch the pageSource Code only fetches repository that is publicly accessible from the InternetVery large projects are probably not supported, in particular, a pull request should finish within 30 seconds
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
