Back to General and Gameplay Programming

Interesting Problem

General and Gameplay Programming Programming

Started by jperalta June 16, 2005 08:20 AM

4 comments, last by Wyrframe 18 years, 10 months ago

jperalta

356

Author

June 16, 2005 08:20 AM

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


let rec length_aux len = function
    [] -> len
  | a::l -> length_aux (len + 1) l

let length l = length_aux 0 l

Illco

928

June 16, 2005 09:17 AM

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

jperalta

356

Author

June 16, 2005 09:20 AM

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.

Illco

928

June 17, 2005 02:08 AM

Ok. But unfortunately I do not know the answer.

CoderGuy

130

June 17, 2005 02:19 AM

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.

Wyrframe

2,489

June 17, 2005 03:06 AM

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]

RIP GameDev.net: launched 2 unusably-broken forum engines in as many years, and now has ceased operating as a forum at all, happy to remain naught but an advertising platform with an attached social media presense, headed by a staff who by their own admission have no idea what their userbase wants or expects.Here's to the good times; shame they exist in the past.

Interesting Problem

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Interesting Problem

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Reticulating splines