Jump to content
  • Advertisement
Sign in to follow this  

Interesting Problem

This topic is 4722 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I'm developing some material for a programming class that will run most likely next summer for high school students and one of the classes will focus on the following problem: Which of these three code snippets will execute fastest, and which one is preferable to use, and why? (A note for the uninitiated '!rlist' -> 'deference the reference rlist', not 'not rlist')
let wlen list =
    let rlist = ref list in
    let i = ref 0 in
    while !rlist <> [] do
          i := (!i+1);
          rlist := (List.tl !rlist);
    done;
    !i;;

let rec listLen = function
    [] -> 0
    | h::t -> 1 + (listLen t);;
The following code is copyright 1996 Institut National de Recherche en Informatique et en Automatique.
let rec length_aux len = function
    [] -> len
  | a::l -> length_aux (len + 1) l

let length l = length_aux 0 l

Share this post


Link to post
Share on other sites
Advertisement
Ok. Great. But what is the question? It still rings the homework alert bells with me, since if you'd be the teacher it would not be a problem, now would it?

Greetz,

Illco

Share this post


Link to post
Share on other sites
Heh, I know the answer, I wrote the first two functions myself and tested all three. The question is if any of y'all can figure out the correct answers to the two parts of the problem. My other argument against it being homework is that (1) I'm not taking any summer classes and (2) if I were they would most likely be directed at my major of Aviation/Air Traffic Management, not at computer science.

Share this post


Link to post
Share on other sites
Ah yes, that's Haskell if I remember. Or are you teaching Curry? Isn't the answer the second one, because it either goes to the guard or it's done. I do know that sometimes recursion can get big, but I want to say the second one. Am I wrong? I haven't done Haskell in a while.

Share this post


Link to post
Share on other sites
That's be Caml (either Objective or Light), based on that it's from INRIA. The fastest code would be the third, because it's tail-recursive (meaning the compiler automatically re-writes it as a loop instead of real recursive code), although it can be better written as follows...
let length =
let rec v n = function
| _::r -> v (n+1) r
| [] -> n
in v 0
;;


The third I already explained. (constant heap, constant stack, O(n) processing)

The first is an explicit loop, which will be bogged down slightly by the call to the library function List.tl ("tail") and the extra garbage-collection checks incurred by the repeated alterations to the list reference 'rlist'. (constant heap, constant stack, O(4n) processing)

The second is pure recursive, but not tail-recursive; every instance will have to sit on the stack until the last call completes, and then an addition and stack reshuffle gets performed for each call on the way back. (constant heap, O(n) stack, O(n) processing)

[Edited by - Wyrframe on June 17, 2005 10:06:05 PM]

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!