[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))
and
((funcall predicate key-left key-right) (go left))
- [Gcl-devel] Efficiency of sort,
Stavros Macrakis <=