Hi Tomas,
> I am implementing multi-methods in picolisp, see
> http://logand.com/picoWiki/multimethods
Great! That's nice!
> some consing when 'by' is used. It also assumes "absolute"
> ordering of list elements as understood by compare().
It seems that you underestimate the consequences and power of the
built-in ordering principle.
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.
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).
In addition, 'sort' does not require the overhead of 'apply'ing (i.e.
interpreting) the passed-in lisp function.
> do the pre-processing and compute *absolute* ordering values the way
> my 'order' function does, but that is not that great.
I think that this is generally not a problem. The key lies in the fact
that PicoLisp has a well-defined precedence law for comparing numbers,
symbols and (recursively) lists. So it should always be possible to
define a unary weighting function.
> where these absolute values are not available for the problem at hand
> and then I need to pre-compute them. And computing this absolute
> ordering cannot be implemented "efficiently".
Can you show an example where you can provide a binary comparison
function, but not a unary weighting function?
> 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!
> > True, as the list is iterated proportional to the square of the length.
> > Why do you think this is necessary?
>
> Not sure what do you mean? Why it has to be O(N^2)? Because only a
> sort function can possibly know how to use a lessThan predicate less
> than O(N^2) times as this depends on the sorting strategy I think.
Yes, what I meant was that your 'order' function used two nested 'for'
loops over the list
...
(for X Lst
(let S 0
(for Y Lst
(when (apply Lt NIL X Y)
...
so that it is iterated O(N^2) times. Not very critical.
> A good sorting algorithm should minimize the total number of
> comparisons. Ideally two elements would be compared once at most. If
Exactly. But usually the cost of retrieving and calculating the values
to be compared is much higher than the actual comparison (see the
customer and alpahnum examples above). So the PicoLisp solution of
calculating these values only once is much more efficient.
> 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.
Cheers,
- Alex
--
UNSUBSCRIBE: mailto:picol...@software-lab.de?subject=unsubscribe
