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
