マージソート(3): 高階関数呼び出し最適化 - sileのブログ
マージソート(1)の改良版。 ソートのような高階関数では、引数で渡した比較関数の間接呼び出しのコストも実行速度にそれなりの影響を与えるので、それを(マクロをほとんど使わずに)できるだけ低く抑えるための試み。 比較関数最適化 まず、比較関数自体の実行コストを下げるために、汎用的な数値比較関数ではなく、より特殊化されたものを使用するようにする。 ;; fixnum用の比較関数 (define-symbol-macro fixnum< (lambda (x y) (declare (fixnum x y)) (< x y))) ;;; fixnum< を使用した場合の処理時間 ;;; ;;; 大量データのソート速度 ;;; 100万要素のリストが対象 (sb-sys:without-gcing (let* ((data (loop REPEAT 1000000 COLLECT (random 1
マージソート(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
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
