gcl-devel
[Top][All Lists]
Advanced

[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: 09 Oct 2003 23:43:56 -0400
User-agent: Gnus/5.09 (Gnus v5.9.0) Emacs/21.2

Greetings!  OK this is in cvs head now.  Please test.

take care,

"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




reply via email to

[Prev in Thread] Current Thread [Next in Thread]