Jorge Tavares

"It is sometimes an appropriate response to reality to go insane." — Philip K. Dick

zsort: portable sorting algorithms in Common Lisp

with 6 comments

zsort is a library that I started working on as a simple hobby project. More or less around the same time I decided to check which algorithms the different Common Lisp implementations use. It is now part of Quicklisp so it can be easily used (thanks Zack!).

The main goal of zsort is to be a collection of portable sorting algorithms. If they can be fast, even better. Common lisp provides the sort and stable-sort functions but these can have different algorithms implemented according to each implementation, which can make an application unportable if you rely on a specific type of sorting. Also, the standard functions might not be the best for a certain situation and as such you might need a specialized sort. Even if for most situations the standard functions are more than enough, the zsort library could be a useful complement.

Right now the implemented algorithms are: insertion sort, quicksort, randomized quicksort, merge sort, heapsort and counting sort. The plan is to add more algorithms, for example, bucket sort and timsort. However, the main thing on the todo list is adding the possibility of external sorting (to handle large amounts of data) and parallel versions of some sorting algorithms. I am considering using lparallel for this but I am still undecided.

There is still a lot of work to be done, but I think the library as it is can already be a little useful. And of course, all kind of suggestions and improvements are welcome!

About these ads

Written by Jorge Tavares

April 22, 2012 at 20:15

6 Responses

Subscribe to comments with RSS.

  1. FYI the next release of lparallel will add support for fine-grained parallelism, which may simplify some algorithms.

    (defun fib (n)
    (declare (optimize (speed 3)))
    (if (< n 2)
    n
    (let ((a (fib (- n 1))) (b (fib (- n 2))))
    (+ a b))))

    (defpar pfib (n)
    (declare (optimize (speed 3)))
    (if (< n 2)
    n
    (plet ((a (pfib (- n 1))) (b (pfib (- n 2))))
    (+ a b))))

    On my two-core machine (pfib 35) is 2x faster than (fib 35). `defpar' does not do any code-walking; it uses a macrolet and an alternate scheduler.

    If `pfib' had been defined using `defun' instead of a `defpar', the `plet' would cause massive slowdown due to task overhead.

    (I am not settled on the name `defpar' because it's too close to `defparameter', however I lack something better.)

    James M. Lawrence

    April 23, 2012 at 10:26

    • Hi James,

      Thanks for your update. From your example it really looks quite easy to code certain algorithms. I will definitely take a closer look at lparalell. It is a very nice piece of work!

      Regarding the name, what about “pdefun” ? It would be more coherent with other names, like pmap, preduce, plet, etc.

      Jorge Tavares

      April 23, 2012 at 14:53

      • Yes, the original name was `pdefun’ for the reasons you mention. However I found the expectation of seeing the `def’ prefix for toplevel definitions too great.

        But `defpar’ isn’t a winner either. `defpfun’ might have worked if it wasn’t so awkward.

        James M. Lawrence

        April 23, 2012 at 22:14

      • Oh, I see! What about `defparallel’? IMHO, it’s nicer than `defpar’ and it’s not that longer.

        Jorge Tavares

        April 24, 2012 at 12:14

      • The disadvantage of `defparallel’ is that it is notoriously easy to fumble typing `parallel’, as you did in your first comment. I also wanted to keep the length short in order to preserve indentation when switching to/from `defun’.

        But I don’t have strong opinions on it; pdefun, defpar, defparallel seem about equally good and equally bad.

        James M. Lawrence

        April 26, 2012 at 2:02

      • Yes, you’re right. Anyway, I look forward for the new release!

        Jorge Tavares

        April 26, 2012 at 8:42


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.

%d bloggers like this: