# Re: sort

```Hi Alex,

> It seems that you underestimate the consequences and power of the
> built-in ordering principle.```
```
Probably, I haven't got used to it yet;-)

> I believe that when you are able to define a binary 'less-than'
> function to be passed to your sort routine, you should always also
> be able to define a unary weighting function.

As the list being sorted is finite, it must be possible to come up
with a unary weighting function.  The question is whether the unary
function is always "better" then the binary predicate?

> A typical example would be sorting a list of customers by city, name and
> customer number, in that order. A binary comparison for 'sort2' would
> look like
>
>    (sort2
>       (collect ... '+CuSu ...)
>       '((CuSu1 CuSu2)
>          (cond
>             ((<> (; CuSu1 ort) (; CuSu2 ort))
>                (> (; CuSu2 ort) (; CuSu1 ort)) )
>             ((<> (; CuSu1 nm) (; CuSu2 nm))
>                (> (; CuSu2 nm) (; CuSu1 nm)) )
>             (T
>                (> (; CuSu2 nr) (; CuSu1 nr)) ) ) ) )
>
> This binary function is rather complicated (and thus slow), and it might
> be called nearly O(N^2) times.
>
>
> Now consider the PicoLisp solution
>
>    (by '((This) (cons (: ort) (: nm) (: nr)))
>       sort
>       (collect ... '+CuSu ...) )
>
> This unary function is quite short and fast, and it is called only O(N).

Cute:-)

>> I imagine other problems where the built-in 'sort' function is not
>> "good enough", e.g. sorting strings by application specific rules like
>> http://www.davekoelle.com/alphanum.html
>
> Well, that's an easy one ;-)
>
>    (by
>       '((Str)
>          (let Res NIL
>             (for C (chop Str)
>                (nond
>                   ((format C) (push 'Res C))
>                   ((num? (car Res)) (push 'Res @))
>                   (NIL (set Res (+ (format C) (* 10 @)))) ) )
>             (flip Res) ) )
>       sort
>       My-List-Of-Alnum-Strings )
>
> This weighting function simply builds a list of characters and numbers,
> and then relies on the built-in comparisons.
>
> Compare that to the solutions in Java (84 lines), C# (128 lines), C++
> (78 lines) or Python (34 lines) in the above link!

Very nice:-)

> Can you show an example where you can provide a binary comparison
> function, but not a unary weighting function?

If the list is finite, it should be always possible to have both I
think.

I updated http://logand.com/picoWiki/multimethods which I didn't
manage to do last time as the internet in the internet cafe went
down:-(

Anyway, for sorting the dispatch table, I have:

(de subclass? (X Y)
(if (pair Y)
(loop
(NIL Y T)
(NIL (subclass? X (pop 'Y))) )
(let Q (if (pair X) X (val X)) # dfs
(use H
(loop
(NIL Q)
(setq H (pop 'Q))
(T (= H Y) T)
(for HH (val H)
(push 'Q HH) ) ) ) ) ) )

(de mmLt (L R)
(use (LH RH)
(loop
(NIL (or L R))
(setq LH (pop 'L) RH (pop 'R))
(T (and (not LH) RH) NIL)
(T
(when LH
(or (not RH) (and (<> LH RH) (subclass? LH RH))) )
T ) ) ) )

(de mmSort (L)
(order L '((L R) (mmLt (car L) (car R)))) )

where 'mmLt' is my binary less-than predicate.

The dispatch table looks something like:

(list
(cons '((+Asteroid) (+Asteroid)) '((X Y) (prinl "aa")))
(cons '((+Asteroid) (+Spaceship)) '((X Y) (prinl "as")))
(cons '((+Spaceship) (+Asteroid)) '((X Y) (prinl "sa")))
(cons '((+Spaceship) (+Spaceship)) '((X Y) (prinl "ss")))
(cons '((+Asteroid) NIL) '((X Y) (prinl "a?")))
(cons '((+Spaceship) NIL) '((X Y) (prinl "s?")))
(cons '(NIL (+Asteroid)) '((X Y) (prinl "?a")))
(cons '(NIL (+Spaceship)) '((X Y) (prinl "?s")))
(cons '(NIL (+Spaceship)) '((X Y) (prinl "?s")))
(cons '(NIL NIL) '((X Y) (prinl "??"))) )

The 'mmLt' predicate behaves as follows:

(let S '(NIL ((+Asteroid) (+Asteroid)) ((+Asteroid) (+Asteroid))
T ((+Asteroid) (+Asteroid)) ((+Asteroid) NIL)
T ((+Asteroid) (+Asteroid)) (NIL (+Asteroid))
T ((+Asteroid) (+Asteroid)) (NIL NIL)
NIL ((+Asteroid) NIL) ((+Asteroid) (+Asteroid))
NIL ((+Asteroid) NIL) ((+Asteroid) NIL)
T ((+Asteroid) NIL) (NIL (+Asteroid))
T ((+Asteroid) NIL) (NIL NIL)
NIL (NIL (+Asteroid)) ((+Asteroid) (+Asteroid))
NIL (NIL (+Asteroid)) ((+Asteroid) NIL)
NIL (NIL (+Asteroid)) (NIL (+Asteroid))
T (NIL (+Asteroid)) (NIL NIL)
NIL (NIL NIL) ((+Asteroid) (+Asteroid))
NIL (NIL NIL) ((+Asteroid) NIL)
NIL (NIL NIL) (NIL (+Asteroid))
NIL (NIL NIL) (NIL NIL))
(while S
(let (R (pop 'S) X (pop 'S) Y (pop 'S))
(unless (= R (mmLt X Y))
(println 'failed R X Y) ) ) ) )

I admit I cannot see a way of defining a unary weighting function
easily.  Maybe this is the challenge, "switching" from binary to unary
function, in this case?

>> I have attached 'sort2' function which "extends" the existing 'sort'
>> You can see the difference running:
>
> Yes, but what when you compare the execution speed?
>
>    : (let L (make (do 100000 (link (rand)))) (bench (sort2 L '((L R) (> L
> R))) T))
>    0.607 sec
>    -> T
>
> (the 'T' at the end is to suppress the output of that long list)
>
>
> The old 'sort'
>
>    :  (let L (make (do 100000 (link (rand)))) (bench (sort L) T))
>    0.251 sec
>    -> T
>
> takes less than half the time, so this is the overhead of 'apply'ing
> the function.

Yes, but this is a trivial example.

I would be curious to compare the running times for the multimethod
example, if there is a reasonably "simple" unary function, it should
be significantly faster provided there are many multimethods;-) (Even
though the speed does not matter in this case, as sorting takes place
during load time/method definition, not application.)

Thank you,

Tomas
--
UNSUBSCRIBE: mailto:picol...@software-lab.de?subject=unsubscribe
```