Interesting problem for me

[DrDave]

I put the different algorithms head to head on a 60000 word list. Some are an order of magnitude slower than another. It might matter some day... :)

And you're just leaving us hanging??

[xytroxon]

There's an interesting aspect of this thread that hasn't so far been mentioned: performance.

Yes. odd? and even? need to be implimented in C for best performance.



Try these changes to odd? and even? using "bitwise and" &.

Code Select Expand


;corrected 12/12/2008
(define (odd? num) (= (& num 1) 1))
(define (even? num) (= (& num 1) 0))
(dolist (x f) (if (odd? $idx) (setf (f $idx) (upper-case $it))))
(dolist (x f) (if (even? $idx) (setf (f $idx) (upper-case $it))))

And then try putting them "inline":

Code Select Expand


(dolist (x f) (if (= (& $idx 1) 1) (setf (f $idx) (upper-case $it)))) ; odd
(dolist (x f) (if (= (& $idx 1) 0) (setf (f $idx) (upper-case $it)))) ; even

-- xytroxon

[DrDave]

Good point of view @cormullion.

I want to write another possibility only using function call. Example (pseudo-code):

Code Select Expand

MY_FUNC(string_list, final_list):
get_first_string:
   is it odd?
      YES->convert to uppercase and add it to final list.
      NO -> add it to final list as is.
call MY_FUNC(remaining_strings, final_list)

I hope my concept is clear.

I see you want to recursively call your function and have it walk the list until out of strings. But how does 'dolist' handle it? Does it make recursive calls to itself or just traverses the list? (Personally, I think recursion is over rated. It certainly has some very good places where it gives simple, readable code compared to a non-recursive solution. But I don't see that it is a major tool in my toolbox.)

[DrDave]

There's an interesting aspect of this thread that hasn't so far been mentioned: performance.

-- xytroxon

Rather than go through all that code, I made a similar comparison of the time it takes to evaluate the predicate form versus the inline form for determining if a number is odd. I get a ratio of about 53:30 (inline faster).

[DrDave]

And while we're talking optimization now, in my version I built the second list on-the-fly by pushing each string to the end of a second list. Would it be faster to start off by copying the entire first list and then pushing only the changed string to its proper location (according to $idx) because it makes only half as many pushes?



Does pushing to an index location require traversing the list from the start? And if pushed to either the first or last position, would those always be "instantly" located?

[ale870]

I made some tests for recursive functions. But it seems some "instruments" are missing to "emulate" Erlang functioning.

So I think recursive way is better for newLisp.



@Curmullion can you give us the results you obtained about performance?

[Lutz]

And if pushed to either the first or last position, would those always be "instantly" located?

Yes, the first location is accessed instantly and access to the last location is optimized with no need to traverse the list. This is true not only for 'push' and 'pop' but also other indexed access with 0 or -1 and via the functions 'first' and 'last'.



Lists in newLISP are forward-single-linked lists, but a pointer to the last element is stored in the header/envelope of the list and updated whenever possible.

[xytroxon]

Correction, swap the 1 and 0 for odd and even like this. (Lunchtime programmer error. ;)

Code Select Expand


(define (odd? num) (= (& num 1) 1))
(define (even? num) (= (& num 1) 0))


Another "case" to consider is to use case inline:

Code Select Expand


(println "case 1 odd")
(setq f '("a" "b" "c" "d" "e" "f" "g") )
(dolist (x f) (case (& $idx 1)(1 (setf (f $idx) (upper-case $it)))))
(println f)
(println "case 0 even")
(setq f '("a" "b" "c" "d" "e" "f" "g") )
(dolist (x f) (case (& $idx 1)(0 (setf (f $idx) (upper-case $it)))))
(println f)
(exit)


Much faster!



-- xytroxon, now going to dinner. Without a computer...

[Kazimir Majorinc]

One "functional" contribution to the discussion.

Code Select Expand

(set 'other-one (lambda (x y z)
                        (cond ((= x y) z)
                              ((= x z) y))))

(set 'alt-case-starting-with
     (lambda(L first-case)
            (if (empty? L) (list)
                           (cons (first-case (first L))
                                 (alt-case-starting-with (rest L)
                                                         (other-one first-case
                                                                    lower-case
                                                                    upper-case))))))


(println (alt-case-starting-with '("str1" "str2" "str3" "str4") upper-case))
(exit)


[ale870]

Good exercise @Kazimir!

Your approach hightlight a potential "problem" in newLisp (maybe it could be completed with a specific function): newLisp does not apply "tail recursive" method. This is one of the biggest problems of imperative languages, and this is one of the reasons because recursive functions are not so much used.

I think, if newLisp could contain a function like (tail-recursive (...) ) we could extend the real power of newLisp language. In fact it contains many functions that could be used in such cases, like first, rest, last, cons, etc...

Now recursive algorithms are not used since they could cause serious problems to the stack area.

@Lutz, I think you need to evaluate this function implementation (tail-recursive). In fact I don't think you could implement at compile-level (but I'm still a newbie in functional programming so I do not know all the concepts in detail).

[cormullion]

Well, I wasn't originally going to post this, but I'm off sick today ... if you forgive me mangling your code, guys, just to make it fit my approach, and don't for a moment think that this is rigourous or scrupulously fair...

Code Select Expand


(set 'source-list .... your list of strings goes here...

(define (method1 lst)
    (map (fn (x) (setf (lst x) (upper-case (lst x))))  
         (sequence 0 (- (length lst) 1) 2))
    lst)
         
(define (method2 lst)
  (map (fn (x y) (if (= (/ x 2) (div x 2)) y (upper-case y)))
    (sequence 0 (- (length lst) 1))
    lst))

(define (odd? num) (= "1" (last (bits num))))
(define (odd? num) (= (& num 1) 1))

(define (method3 lst)
  (map (fn (x) (if (odd? $idx) (upper-case x) x)) lst))

(define (method4 lst)
  (dolist (x lst) (if (odd? $idx) (setf (lst $idx) (upper-case $it))))
  lst)

(define (method5 lst)
  (flat (replace '(+) (explode lst 2 true) (list (upper-case (first $it)) (last $it)) match)))

(define (method6 lst)
  (apply append (map (fn (l) (list (upper-case (first l)) (last l))) (explode lst 2 true))))

(set 'other-one (lambda (x y z)
                        (cond ((= x y) z)
                              ((= x z) y))))

(define (method7 lst (first-case upper-case))
    (if (empty? lst) (list)
        (cons (first-case (first lst))
            (method7 (rest lst)
                 (other-one first-case
                  lower-case
                  upper-case)))))

(define (method8 lst)
  (dolist (x lst) (case (& $idx 1) (0 (setf (lst $idx) (upper-case $it)))))
  lst)

(define (method9 lst)
  (dolist (this-string lst)
    (if (odd? $idx)
        (push (upper-case this-string) newList -1)
        (push this-string newList -1)))
  newList)

(push (list (time (method1 source-list)) "method1") results)
(push (list (time (method2 source-list)) "method2") results)
(push (list (time (method3 source-list)) "method3") results)
(push (list (time (method4 source-list)) "method4") results)
(push (list (time (method5 source-list)) "method5") results)
(push (list (time (method6 source-list)) "method6") results)
(push (list (time (method7 source-list)) "method7") results)
(push (list (time (method8 source-list)) "method8") results)
(push (list (time (method9 source-list)) "method9") results)

(map println (sort results))


These don't give exactly the same answer (odd/even) but I was only looking to make a quick comparison - not proper testing methodology... :)



Note that method7 requires a larger stack for longer lists.

[Lutz]

The topic of tail-recursion came up in this thread and has come up earlier. Here my thoughts about it:



As somebody else said already in this thread: "recursion is overrated"



It may be interesting from a theoretical point of view to reduce iteration to tail-recursive function calls, but from a practical point of view I don't see much sense in it. First of all, its inefficient, it took the Scheme designers a long time to implement continuations with more or less acceptable but not stellar performance.



Don't get me wrong I am all for recursion where an algorithm is elegantly expressed this way, and newLISP supports recursion. But often I see that people in traditional Lisp texts try to force recursion on naturally linear, iterative problems. Remember that only the tail-recursive part in an recursive algorithm can be optimized. But why optimize something into iteration if it was expressed more naturally iterative in the first place?



Generations of programmers have been taught by their CS professors that recursion is the holy grail of algorithm design. I think its just not true, its an important part among other important techniques, nothing else. I agree, that it has a special place in functional programming theory, but it is not special in a practical, applications oriented, multi-paradigm scripting Lisp.



Use recursion where appropriate, i.e. processing and generating tree like structures, but where the problem is linear don't force it into a recursive perspective to satisfy some theoretical purity of solving all control patterns in computer programming with recursive function calls.



newLISP has a wide selection of iterator functions to make iteration comfortable: 'dotimes, dolist, for, while, until, do-while, do-until'; more than most other scripting languages.



Most recursive algorithm will suffice with the default stack depth of 2028 in newLISP. You can bump it up to whatever number you need using the -s command line switch. Most recursive programs running into stack problems are better solved using an iterative algorithm. Again remember: only the tail-recursive part can be optimized (translated into iteration) anyway.



To  make a long story short: there will never be tail-recursion optimization in newLISP ;-)

[ale870]

Ok Lutz, I didn't want to oblige you to implement tail-recursion!

As you said, recursion is a way to apply an algorithm (so it has advantages and weakness as any other algorithm).

I proposed to insert a such function so the users will have another important instrument in their toolbox.

In other languages recursion is a must (for example to by-pass the problem related to immutable variables), but newLisp, as many other languages, offer "rewritable" variables, so recursion becomes simply another tool.



Finally, I simply think that...

If I have a tool I can decide if use it or not (flexibility); if I haven't a tool I cannot decide anything...



Thank you.

[Lutz]

Finally, I simply think that...

If I have a tool I can decide if use it or not (flexibility); if I haven't a tool I cannot decide anything...

I totally agree on that point and newLISP prides itself to often offer different styles and solutions to the same problem, which is all the fun we are having in this thread. A big part of the joy of programming is to express your own style.



Unfortunately there is no way to implement tail-recursion optimization or some helper function like 'recur' with little code and no impact on performance, the way newLISP's VM is architectured.

[DrDave]

After some minor tweaking, I ran the code that Cormullion was nice enough to post. I used a source list of length 81920. Initally, I ran the versions one at a time and discoverd that method7 never completed, even after 40 minutes. So, when I ran the whole group, it was omitted.



I implemented only this version of odd?

Code Select Expand

(define (odd? num) (= (& num 1) 1))

newLISP 10.0.0 WIN32 (Windows XP pro)



Here are typical results, time in milliseconds

(468 "method9")

(515 "method3")

(546 "method2")

(609 "method5")

(781 "method6")

(25781 "method8")

(29234 "method4")

(103562 "method1")

( never completes "method7")



I was actually surprised to see that method9 turned in the best performance.

Also note that the results clearly fall into three groups: {9, 3, 2, 5, 6}; {8, 4}; {1}. And I suppose we could add a fourth gorup {7} also out there by itself.