リストの途中に挿入

リストの途中に挿入ってどうやるのが良いのかと思って時間を測ってみました。あまり一般的な状況設定じゃないですが。破壊的でいいなら多分 set! がいちばん速いだろうと思うけど、他に良い方法があればそれを使いたいなあと思いつつ set! が速いことを確かめるための実験。

というかそもそもリストとか木の一部を更新するイディオムを全く知らないことに気づいて驚いた。

#!/usr/bin/env gosh
;; -*- coding: utf-8 mode: scheme -*-

(use gauche.time)
(use srfi-1)


(define (splitver l i)
  (receive (head tail) (split-at l 2)
    `(,@head ,i ,@tail)))

(define (split!ver l i)
  (receive (head tail) (split-at! l 2)
    `(,@head ,i ,@tail)))

(define (setver l i)
  (begin
    (set! (cddr l)
          (cons i (cddr l)))
    l))

(define (main args)
  (time
   (dotimes (t 100000)
     (splitver (list 1 2 3) 5)))
  (time
   (dotimes (t 100000)
     (split!ver (list 1 2 3) 5)))
  (time
   (dotimes (t 100000)
     (setver (list 1 2 3) 5)))
  0)

結果

;(time (dotimes (t 100000) (splitver (list 1 2 3) 5)))
; real   0.460
; user   0.390
; sys    0.020
;(time (dotimes (t 100000) (split!ver (list 1 2 3) 5)))
; real   0.358
; user   0.290
; sys    0.000
;(time (dotimes (t 100000) (setver (list 1 2 3) 5)))
; real   0.225
; user   0.180
; sys    0.010

リストを繋げるところはこれでいいのかな？オーダ的にはどうやっても前にくるリストの長さに対してO(n)だから気にしなくても良いのかもしれないけど。

結論としては、破壊的で良いなら split-at より setter があればそれを使ったほうが速いということで。