[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: [Gcl-devel] Efficiency of sort
From: |
Camm Maguire |
Subject: |
Re: [Gcl-devel] Efficiency of sort |
Date: |
08 Oct 2003 17:02:44 -0400 |
User-agent: |
Gnus/5.09 (Gnus v5.9.0) Emacs/21.2 |
I've looked at it and agree. I'll commit this into CVS HEAD shortly.
thanks!
"Stavros Macrakis" <address@hidden> writes:
> The list sort function in gcl 2.5.0 calls the predicate approximately
> twice as many times as necessary. This is because it checks both a<b
> and b<a at every choice point, presumably because it wants to exclude
> the a=b case (for stability?). But (a) sort does not guarantee
> stability; (b) I don't think the test is even necessary for stability.
> (Am I wrong?)
>
> This matters because sort is often called with expensive predicates.
>
> The solution is simple: in list-merge-sort, comment out the clauses:
>
> ((funcall predicate key-left key-right) (return l))
> and
> ((funcall predicate key-left key-right) (go left))
>
>
>
> _______________________________________________
> Gcl-devel mailing list
> address@hidden
> http://mail.gnu.org/mailman/listinfo/gcl-devel
>
>
>
--
Camm Maguire address@hidden
==========================================================================
"The earth is but one country, and mankind its citizens." -- Baha'u'llah