[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

[Gcl-devel] Efficiency of sort

From: Stavros Macrakis
Subject: [Gcl-devel] Efficiency of sort
Date: Wed, 8 Oct 2003 15:40:26 -0400

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))
    ((funcall predicate key-left key-right) (go left))

reply via email to

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