Lisp Forum: Its like sudoku but for lispers.

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.

Randomize List


(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)))

Removing Duplicates

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.

Templating

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.

About these ads

One Comment on “Lisp Forum: Its like sudoku but for lispers.”

  1. Hawlegid says:

    80mg cialis effect
    [url=http://genericcialis-us.com/#gformlis.wordpress.com]buy generic cialis
    [/url] cialis online yabb
    http://genericcialis-us.com/#44210 – cialis daily dose amount


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 33 other followers