Name: Anonymous 2009-08-30 15:07
Which do you prefer?
Fibonacci Butt Sort
or
Directed Acyclic Butt Sort
Fibonacci Butt Sort
or
Directed Acyclic Butt Sort
(asdf:oos 'asdf:load-op '#:split-sequence)
(defun wrap-tag (string tag)
(if (null tag)
""
(format nil "[~a]~a[/~a]" tag string tag)))
(defun wrap-tags (string &rest tags)
(labels ((rec (string tags)
(if tags
(rec (wrap-tag string (car tags)) (cdr tags))
string)))
(rec string (reverse tags))))
(defun split-string (s)
(loop for c across s collect c))
(defun bbsort (s &optional acyclic)
(let ((seqs (if acyclic
(mapcan #'(lambda (x) (list x #\Space)) (split-sequence:split-sequence #\Space s))
(split-string s)))
parity)
(wrap-tags
(apply #'concatenate 'string
(mapcar #'(lambda (x)
(if (member x '(#\ "" " ") :test #'equal)
" "
(progn
(setf parity (not parity))
(wrap-tag x (if parity "o" "u")))))
seqs)) "i" "b")))SETF once (could have easily avoided that, but at the cost of some slight performance loss). import Data.List; import Control.Monad.State;
tag t str = "[" ++ t ++ "]" ++ str ++ "[/" ++ t ++ "]"
[b,i,o,u] = tag `map` words "b i o u"
dabs = b . i . unwords . zipWith id (cycle [o,u]) . words
fbs = b . i . concat . flip evalState (cycle [o,u]) . mapM f where
f ' ' = return " "
f c = (liftM . concatMap) ($ [c]) (State $ splitAt 1)
(defun split-string (s)
(map 'vector #'identity s))PROGN and SETF could also be removed by adding a (cycle t nil) (cycle can be found on /prog/, it was posted a few days ago) and rewriting the code around that MAP a bit. The point still stands that LOOP will usually be more efficient than the equivalent MAP in this case, of course this is implementation dependent.
(defun split-string (s)
(map 'list #'identity s))MAP version:
CL-USER> (time-test 1000000 (split-string2 "ABC"))
Evaluation took:
0.094 seconds of real time
0.093750 seconds of total run time (0.093750 user, 0.000000 system)
100.00% CPU
238,621,410 processor cycles
24,001,080 bytes consedLOOP version:
CL-USER> (time-test 1000000 (split-string "ABC"))
Evaluation took:
0.062 seconds of real time
0.062500 seconds of total run time (0.062500 user, 0.000000 system)
[ Run times consist of 0.016 seconds GC time, and 0.047 seconds non-GC time. ]
100.00% CPU
180,198,549 processor cycles
31,999,776 bytes consedLOOP version conses more, but is faster, while MAP version conses less, but is slower by a bit. Implementation used was SBCL. [oode]TIME-TEST[/code] is just a macro which executes a form a given number of times (1 million times in that example).
(coerce output-type-spec obj) and not (coerce obj output-type-spec).
COERCE is actually slower for some reason:
CL-USER> (time-test 1000000 (coerce "ABC" 'list))
Evaluation took:
0.375 seconds of real time
0.375000 seconds of total run time (0.375000 user, 0.000000 system)
[ Run times consist of 0.015 seconds GC time, and 0.360 seconds non-GC time. ]
100.00% CPU
904,049,172 processor cycles
31,999,520 bytes consed