Lisp Forum: Its like sudoku but for lispers.Posted: 2010/12/29
I thought I’d plug Lisp Forum, a forum I frequent that answers Lisp related questions; I go by the name “Warren Wilkinson”.
I go when I’m taking a break from my code. The problems posted by new lispers are often short and stand-alone, like a good puzzle. And you learn a lot too; In this post new user aaron4osu created a cypher to permutate the words in a file. His version of randomize-list was very clever.
(defun randomize-list (list) (mapcar #'car (sort (mapcar (lambda (c) (cons c (random 1.0))) list) #'> :key #'cdr)))
I’ve written randomize-list before, but mine worked by taking items from the list in random order to build up a new list:
(defun randomize-list (a) (let ((a (copy-list a)) (b nil) (n (length a))) (loop repeat n for place = (random (length a)) for item = (elt a place) do (push item b) do (setf a (delete item a :start place :count 1))) b))
Doing it aaron4osu’s way is about 3 times faster, and you can make it slightly faster by consing random fixnums and using a fixnum-only <.
(defun fixnum< (a b) (> (the fixnum a) (the fixnum b))) (defun randomize-list (list) (mapcar #'cdr (sort (mapcar (lambda (c) (cons (random #xFFFFFF) c)) list) #'fixnum< :key #'car)))
Surprisingly, it’s faster to remove duplicates after than to filter them before. Using remove-duplicates is about 20 times faster than checking them before hand (but using a hash table to test inclusion is much quicker, but still twice as slow as remove-duplicates). In SBCL, using delete-duplicates was really slow.
Replacing non-destructive routines with destructive ones (e.g. map vs map-into, remove-duplicates vs delete-duplicates, a new string vs replace) makes things slower.
In this post, I probably scared newbie indianerrostock away, when he asked for improvements to his templating program.
Given a text file that contained #SPORTNAME# in multiple places, his program replaced that with the name of a sport. The kicker was it did it several times in batch for many sport names.
His method was the obvious one: Loop through the string searching for #SPORTNAME# while making a copy of the string with #SPORTNAME# replaced.
My solution was to sort the sport names biggest to smallest and precompute where all the #SPORTNAMES# where, and then replace them in the source string (i.e. no duplicate string, no memory allocation, etc) with a sport name. Then I would repeat this replacing the previous sport name with the next one.
My super optimized no-allocation and no-searching method was 2.5 times slower. It boggles the mind.
How Fast is Sorting?
This post starts out about CLOS and ends with a discussion of sorting. SBCL sorts lists using merge sort, but vectors with heap-sort. stable-sort for both vectors and lists uses merge-sort.
Its faster to use STABLE-SORT for vectors.
Also, merge-sort works well without random access, so sorting singly linked lists is fast. There is no need to convert the list into a vector before sorting.
Why So Counter-intuitive?
Well, I think a lot of this has to do with memory allocation in Lisp. Lisp is garbage collected, most Lisps use a stop-and-copy garbage collector. This is like a constant defrag on your memory. One benefit of which is that allocation is VERY FAST — far faster than C’s malloc. In C you’d have to search a binary tree for available space , but in lisp, you just increment the memory-end pointer.
If you made a linked list a node at a time C would have you search a hundred times, while Lisp would increment a pointer 100 times. C’s linked list would be scattered in memory, while Lisp’s would be continuous.
This is why Lisp is so fast at functional programming. You create a lot of garbage, but you create it fast, and it goes away fast.