[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[Chicken-users] three-way comparison functions in Chicken
From: |
Sven . Hartrumpf |
Subject: |
[Chicken-users] three-way comparison functions in Chicken |
Date: |
Thu, 17 Jul 2003 14:46:48 +0200 (CEST) |
Hi.
There are many algorithms whose good performance values rely on efficient
three-way comparison functions (e.g. sorting with removing duplicates).
For characters and numbers, the Scheme-only versions are fast enough, I guess:
(define char-compare3 (lambda (a b)
(- (char->integer a) (char->integer b))))
(define number-compare3 (lambda (a b)
(- a b)))
But for strings - I think - I would need support from the Scheme system
because the 1st implementation is very slow and the 2nd is still not optimal:
; 1st implementation
(define string-compare3 (lambda (a b)
(let ((a-length (string-length a))
(b-length (string-length b)))
(or (string-compare32 a b 0 (min a-length b-length))
(- a-length b-length)))
))
(define string-compare32 (lambda (a b pos l)
(if (= pos l)
#f
(let ((result (- (char->integer (string-ref a pos)) (char->integer
(string-ref b pos)))))
(if (zero? result)
(string-compare32 a b (+ pos 1) l)
result)))))
; 2nd implementation
(define string-compare3 (lambda (a b)
(if (string<? a b)
-1
(if (string=? a b)
0
1))
))
Would it make sense to have a new Chicken function, like string-compare3 ?
(Maybe not much more than a call to memcmp is needed.)
Background: I am trying to provide some more feedback for the sorting SRFI-32
(http://srfi.schemers.org/srfi-32/ ), including some experimental data.
(Especially in the area of two-way comparison functions vs. three-way
comparison functions.)
Greetings
Sven
[Prev in Thread] |
Current Thread |
[Next in Thread] |
- [Chicken-users] three-way comparison functions in Chicken,
Sven . Hartrumpf <=