リストの逆転

common lisp algorithm speed C++

最近は少し忙しいので、気分転換を兼ねて簡単な関数を実装する。

リストの破壊的なリバース。


以下、ソース。
参照: nlet

(defun list-reverse! (lst)
  (nlet self ((lst lst) head)
    (if (endp lst)
        head
      (self #1=(cdr lst) (progn (setf #1# head) lst)))))

最適化宣言は、(sbclでは)つけてもつけなくても速度が全く変わらなかったので割愛。
再帰ではなく、繰り返しを使った実装も試してみたが、こちらも有意と云えるほどの差異はなかったので、簡潔な再帰版を採用。
※ ただし、末尾再帰最適化を行わない処理系では、両者で大きな差が出ると思うので、ポータビリティ(?)の高い関数にしたいなら再帰ではなく繰り返しを使った方が良さそう。

C++と比較

lispはリスト処理が得意(?)なので、「リストリバース関数ならC++よりも速いかも」という期待を込めて比較してみる。

C++のソース。

// g++ -O3 -oreverse reverse.cc

#include <stdio.h>
#include <stdlib.h>
#include <sys/time.h>

// 計時用
inline double gettime(){
  timeval tv;
  gettimeofday(&tv,NULL);
  return static_cast<double>(tv.tv_sec)+static_cast<double>(tv.tv_usec)/1000000.0;
}

// リンクリスト用の構造体
struct List {
  List(int v) :val(v), next(NULL){}
  int   val;
  List* next;
};

// 要素数がn個のリンクリストを作成
List* make_list(int n) {
  List* beg = new List(0);
  List* cur = beg;
  for(int i=1; i < n; i++){
    cur->next = new List(i);
    cur = cur->next;
  }
  return beg;
}

// リストリバース
// C++ではループで実装した方が自然なので、再帰は使わない
List* list_reverse(List* list) {
  List* head=NULL;
  
  while(list){
    List* tmp = list->next;
    list->next = head;
    head=list;
    list=tmp;
  }

  return head;
}

// main
// argv[1] = リストの要素数
int main(int argc, char** argv) {
  List* lst = make_list(atoi(argv[1]));
  
  double beg_t = gettime();  // 計時開始
  lst = list_reverse(lst);
  double end_t = gettime();  // 計時終了

  printf("%f\n",end_t-beg_t);
  return 0;
}

三千万要素のリストに対して上の二つの関数を適用してみたところ、処理時間はlisp版が0.268秒、C++版は0.217秒だった。
C++版の方が1.25倍程度速い。


もっと複雑な操作ならともかく、逆転のような簡単なものの場合、やっぱりC++の方が高速なようだ。
少し残念。
蛇足だが、同じリストに対してlist-reverse!関数を続けて適用した場合*1、二回め以降の処理時間は0.110秒程度となり、C++よりも速くなった。キャッシュの関係だと思うが、原因は不明。

繰り返し版

再帰ではないリバース関数の実装も一応載せておく。

;; 上のC++での実装のcommon lisp翻訳版
(defun list-reverse! (list)
  (let ((head '()))
    (loop WHILE list DO
      (let ((tmp (cdr list)))
        (setf (cdr list) head
              head  list
              list tmp)))
    head))

;; SBCL-1.0.28での実装
(defun list-nreverse (list)
  (do ((1st (cdr list) (if (endp 1st) 1st (cdr 1st)))
       (2nd list 1st)
       (3rd '() 2nd))
      ((atom 2nd) 3rd)
    (rplacd 2nd 3rd)))

*1: (dotimes (i 2) (time (progn (setf *lst* (list-reverse! *lst*) ) ) ) ) )