Hello fellow Lispers,
The challenge of creating an algorithm for sorting 5 items with the
minimum number of comparisons came up for me recently. Sorting 5
items can be done with only 7 comparisons. I started writing a sorter
by hand and realized that it is actually quite a bit of code. About
240 lines for sorting only 5 items! The reason is there are 120 ways
to order 5 items and a perfectly balanced comparison tree would be
nested 7 levels deep, hence the 7 comparisons.
So I got to thinking I could write a macro to generate this code for
me. Then I thought I could do one better and make a general macro for
creating optimal sorters for N numbers of items. Now this is not very
practical for large values of N because the code size grows relative
to N!.
The code I wrote to generate the sorters is 85 lines of code. Just by
generating a 5 item sorter this macro has paid for itself threefold!
CL-USER> (make-sort-n 5 '<=)
SORT-5
CL-USER> (sort-5 (list 382 12 89 -234 44))
(-234 12 44 89 382)
This is the macro code:
http://paste.lisp.org/display/75398
This is a generated optimal 3 item sorter:
http://paste.lisp.org/display/75399
This is a generated optimal 5 item sorter:
http://paste.lisp.org/display/75400
Comments are appreciated. Also, I am wondering if anyone has any real-
world examples where macros have been used to generate large amounts
of code for optimization or that would otherwise be tedious to write.
Thanks!
Anthony
On Feb 13, 12:29 am, Anthony <·················@gmail.com> wrote:
> This is a generated optimal 5 item sorter:
>
> http://paste.lisp.org/display/75400
although your compiler can probably optimize it out, since this is the
output of a macro that you are providing a function to, there is no
need for the FUNCALL. you are FUNCALLing the quoted function, just
have the macro write the function right into the output, eg. (<= N1
N2)
> Comments are appreciated.
just out of curiosity, have you benchmarked your code against a few
different lisps' provided SORT function? I'm curious how different
they actually are in practice. although, one difference is yours
creates a new list and SORT modifies the original. (I guess if that
is a requirement, you could benchmark against (SORT (COPY-LIST ...)))
Also, I don't know how SORT is typically implemented but your
DESTRUCTURING-BIND call will result in a traversal of the list and
some assignments/binding so that might cost you something, which may
vary depending on implementation.
Kevin
On Feb 13, 12:34 am, K Livingston <······················@gmail.com>
wrote:
> On Feb 13, 12:29 am, Anthony <·················@gmail.com> wrote:
>
> > This is a generated optimal 5 item sorter:
>
> >http://paste.lisp.org/display/75400
>
> although your compiler can probably optimize it out, since this is the
> output of a macro that you are providing a function to, there is no
> need for the FUNCALL. you are FUNCALLing the quoted function, just
> have the macro write the function right into the output, eg. (<= N1
> N2)
>
> > Comments are appreciated.
>
> just out of curiosity, have you benchmarked your code against a few
> different lisps' provided SORT function? I'm curious how different
> they actually are in practice. although, one difference is yours
> creates a new list and SORT modifies the original. (I guess if that
> is a requirement, you could benchmark against (SORT (COPY-LIST ...)))
> Also, I don't know how SORT is typically implemented but your
> DESTRUCTURING-BIND call will result in a traversal of the list and
> some assignments/binding so that might cost you something, which may
> vary depending on implementation.
I have not benchmarked it. The main purpose of writing it was for a
learning exercise, and not really to compete with the built in sorts.
As Pascal pointed out, the built-in sort is probably doing something
like this anyway. There are also some obvious improvements I think I
can make first. As you mentioned, the sort is not in-place. I could
modify this to work against sequences and not lists and use ELT as an
accessor. That will also get rid of the DESTRUCTURING-BIND. Instead
of creating a new sequence at the end I can do the minimum number of
swaps to put the list in order. This will require a bit more work
than just doing the minimum comparisons, but I will probably do it
because it will keep me up at night until I do!
Anthony
From: Pascal J. Bourguignon
Subject: Re: Creating optimized sorters for N items
Date:
Message-ID: <87skmiadjs.fsf@galatea.local>
Anthony <·················@gmail.com> writes:
> The code I wrote to generate the sorters is 85 lines of code. Just by
> generating a 5 item sorter this macro has paid for itself threefold!
> [...]
> Comments are appreciated. Also, I am wondering if anyone has any real-
> world examples where macros have been used to generate large amounts
> of code for optimization or that would otherwise be tedious to write.
I'd bet your lisp implementation sources contain such a macro to
optimize the base case of their quick-sort implementation. It this
real-world enough?
--
__Pascal Bourguignon__
From: Stanisław Halik
Subject: Re: Creating optimized sorters for N items
Date:
Message-ID: <gn3jqj$2atv$1@opal.icpnet.pl>
thus spoke Anthony <·················@gmail.com>:
> The challenge of creating an algorithm for sorting 5 items with the
> minimum number of comparisons came up for me recently. Sorting 5
> items can be done with only 7 comparisons. [...]
If comparison is expensive, how about using the decorate-sort-undecorate
idiom instead of writing one's own sort?
http://en.wikipedia.org/wiki/Schwartzian_transform
From: Stanisław Halik
Subject: Re: Creating optimized sorters for N items
Date:
Message-ID: <gn3k0r$2atv$2@opal.icpnet.pl>
thus spoke Stanisław Halik <·······@test123.ltd.pl>:
> thus spoke Anthony <·················@gmail.com>:
>> The challenge of creating an algorithm for sorting 5 items with the
>> minimum number of comparisons came up for me recently. Sorting 5
>> items can be done with only 7 comparisons. [...]
> If comparison is expensive, how about using the decorate-sort-undecorate
> idiom instead of writing one's own sort?
> http://en.wikipedia.org/wiki/Schwartzian_transform
Oh, and one more thing.
Since the sorter needs to account for every possible permutation of the
sorted output, it certainly doesn't scale for 10 or more elements.
Optimizing the case where N is very small and the optimization doesn't
scale for more elts seems like a waste of time.
On Thu, 12 Feb 2009 22:29:49 -0800, Anthony wrote:
> This is a generated optimal 5 item sorter:
>
> http://paste.lisp.org/display/75400
>
> Comments are appreciated. Also, I am wondering if anyone has any real-
> world examples where macros have been used to generate large amounts of
> code for optimization or that would otherwise be tedious to write.
Nice. Take a look at Let Over Lambda by Doug Hoyte, it has examples
of using macros for optimization. Incidentally, it also discusses
sorting with the smallest number of comparisons. It is a great book,
well worth reading for advanced lispers.
HTH,
Tamas
On Feb 13, 4:23 am, Tamas K Papp <······@gmail.com> wrote:
> On Thu, 12 Feb 2009 22:29:49 -0800, Anthony wrote:
> > This is a generated optimal 5 item sorter:
>
> >http://paste.lisp.org/display/75400
>
> > Comments are appreciated. Also, I am wondering if anyone has any real-
> > world examples where macros have been used to generate large amounts of
> > code for optimization or that would otherwise be tedious to write.
>
> Nice. Take a look at Let Over Lambda by Doug Hoyte, it has examples
> of using macros for optimization. Incidentally, it also discusses
> sorting with the smallest number of comparisons. It is a great book,
> well worth reading for advanced lispers.
>
> HTH,
>
> Tamas
This looks like a really good book, exactly the kind of thing I was
looking for. I ordered a copy, thanks for the recommendation!
From: Alexander Lehmann
Subject: Re: Creating optimized sorters for N items
Date:
Message-ID: <gn4ann$dii$1@online.de>
Anthony wrote:
> http://paste.lisp.org/display/75398
Nice ;-)
Don't mean to be nitpicking, but maybe using
"for b in (permutations (remove a seq)"
instead of
"for b in (permutations (remove a (copy-seq seq)))"
would cons up a little less ;-) AFAIK remove is non-destructive.
-- Alexander
From: Tobias C. Rittweiler
Subject: Re: Creating optimized sorters for N items
Date:
Message-ID: <87eiy2ql1l.fsf@freebits.de>
Alexander Lehmann <········@in.tum.de> writes:
> Don't mean to be nitpicking, but maybe using
> "for b in (permutations (remove a seq)"
> instead of
> "for b in (permutations (remove a (copy-seq seq)))"
> would cons up a little less ;-) AFAIK remove is non-destructive.
But careful! REMOVE is allowed to share structure with its argument. It
does not matter in this case because PERMUTATIONS is not destructive,
but
(SORT (REMOVE MUMBLE LIST) ...)
is a common pitfall.
-T.
From: Alexander Lehmann
Subject: Re: Creating optimized sorters for N items
Date:
Message-ID: <gn4v1m$v51$1@online.de>
Tobias C. Rittweiler wrote:
> But careful! REMOVE is allowed to share structure with its argument. It
> does not matter in this case because PERMUTATIONS is not destructive,
> but
>
> (SORT (REMOVE MUMBLE LIST) ...)
>
> is a common pitfall.
Oh, thanks! I wasn't aware of that!
On 2009-02-13, Alexander Lehmann <········@in.tum.de> wrote:
> Tobias C. Rittweiler wrote:
>> But careful! REMOVE is allowed to share structure with its argument. It
>> does not matter in this case because PERMUTATIONS is not destructive,
>> but
>>
>> (SORT (REMOVE MUMBLE LIST) ...)
>>
>> is a common pitfall.
>
> Oh, thanks! I wasn't aware of that!
Note that LIST, APPEND, CONS and many other functions all reuse structure from
their arguments. This is a complete red herring.
From: Alexander Lehmann
Subject: Re: Creating optimized sorters for N items
Date:
Message-ID: <gn5pqa$jin$1@online.de>
Kaz Kylheku wrote:
> On 2009-02-13, Alexander Lehmann <········@in.tum.de> wrote:
>> Tobias C. Rittweiler wrote:
>>> But careful! REMOVE is allowed to share structure with its argument. It
>>> does not matter in this case because PERMUTATIONS is not destructive,
>>> but
>>>
>>> (SORT (REMOVE MUMBLE LIST) ...)
>>>
>>> is a common pitfall.
>> Oh, thanks! I wasn't aware of that!
>
> Note that LIST, APPEND, CONS and many other functions all reuse structure from
> their arguments. This is a complete red herring.
Yes, I knew about these. It was only REMOVE that surprised me in this case.
Luckily, it turns out that in the cases where I've used REMOVE in the first
place there were no risks in sharing structure.
Well, thanks anyway!
On 2009-02-14, Alexander Lehmann <········@in.tum.de> wrote:
> Kaz Kylheku wrote:
>> On 2009-02-13, Alexander Lehmann <········@in.tum.de> wrote:
>>> Tobias C. Rittweiler wrote:
>>>> But careful! REMOVE is allowed to share structure with its argument. It
>>>> does not matter in this case because PERMUTATIONS is not destructive,
>>>> but
>>>>
>>>> (SORT (REMOVE MUMBLE LIST) ...)
>>>>
>>>> is a common pitfall.
>>> Oh, thanks! I wasn't aware of that!
>>
>> Note that LIST, APPEND, CONS and many other functions all reuse structure from
>> their arguments. This is a complete red herring.
>
> Yes, I knew about these. It was only REMOVE that surprised me in this case.
They are no different from remove.
For instance (cdr list) is the same thing as removing the first element
of the list. The ``new'' list shares its entire structure with the old.
> Luckily, it turns out that in the cases where I've used REMOVE in the first
> place there were no risks in sharing structure.
The risks are not in structure sharing, but in destructive manipulation,
but I think I'm repeating myself.
From: Tobias C. Rittweiler
Subject: Re: Creating optimized sorters for N items
Date:
Message-ID: <87ljs9owly.fsf@freebits.de>
Kaz Kylheku <········@gmail.com> writes:
> Note that LIST, APPEND, CONS and many other functions all reuse structure from
> their arguments. This is a complete red herring.
ITYM LIST*.
-T.
On 2009-02-13, Tobias C. Rittweiler <···@freebits.de.invalid> wrote:
> Alexander Lehmann <········@in.tum.de> writes:
>
>> Don't mean to be nitpicking, but maybe using
>> "for b in (permutations (remove a seq)"
>> instead of
>> "for b in (permutations (remove a (copy-seq seq)))"
>> would cons up a little less ;-) AFAIK remove is non-destructive.
>
> But careful! REMOVE is allowed to share structure with its argument. It
> does not matter in this case because PERMUTATIONS is not destructive,
> but
>
> (SORT (REMOVE MUMBLE LIST) ...)
>
> is a common pitfall.
That is not right. The pitfall is purely in SORT, not in REMOVE.
(sort any-list ...)
REMOVE shares structure, but it's non-destructive. The sharing is a red
herring, since it's a common behavior of many functions, and helps to improve
the efficiency of applicative programming without sacrificing correctness.
There are two pitfalls with SORT. One is failing to capture the return value,
and the other is that the input structure is shared in ways that the code
fails to account for.
You may be thinking of DELETE, which is simiar to REMOVE, but allowed to mutate
its argument, and has pitfalls similar to SORT.
From: Tobias C. Rittweiler
Subject: Re: Creating optimized sorters for N items
Date:
Message-ID: <87prhlowmu.fsf@freebits.de>
Kaz Kylheku <········@gmail.com> writes:
> You may be thinking of DELETE, which is simiar to REMOVE, but allowed to mutate
> its argument, and has pitfalls similar to SORT.
No, I was thinking of REMOVE.
-T.