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).


>> 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

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

Anyway, for sorting the dispatch table, I have:

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

(de mmLt (L R)
   (use (LH RH)
         (NIL (or L R))
         (setq LH (pop 'L) RH (pop 'R))
         (T (and (not LH) RH) NIL)
          (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:

      (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,

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

Reply via email to