zsort: portable sorting algorithms in Common Lisp

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
6 comments
  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.)

    • 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.

      • James M. Lawrence said:

        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.

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

      • James M. Lawrence said:

        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.

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

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: