|
[OCAML] Minimun element in a list |
FMC
Member #4,431
March 2004
|
I've recently started studying this language for a university course; after many years of C\C++ coding i'm having a hard time getting used to this new way of doing things. Currently i'm trying to figure out a way to extract the smallest element from a list of integers, but have no idea where to start. [FMC Studios] - [Caries Field] - [Ctris] - [Pman] - [Chess for allegroites] |
nonnus29
Member #2,606
August 2002
|
Think about what the recursive function in C/C++ would be: int least(int* mylist) { if(!mylist) return 0; int a = mylist[0]; //this will segfault, but it's just for demonstration purposes. You get the idea. int b = least(mylist++); if(a < b) return a; else return b; } Then do it in Ocaml: let rec least mylist = function | [] -> 0 | a :: tail -> let b = least(tail) in if(a < b) a else b I have no idea if that will compile or not. Edit; Sorry, that doesn't work because for positive integers it will always return zero, oops. |
kazzmir
Member #1,786
December 2001
|
Here are two ways, one using direct recursion and another that uses fold_left.
The first one doesn't use tail-recursion so it wastes stack space. fold_left will use tail-recursion so its a little better. |
Don Freeman
Member #5,110
October 2004
|
I don't know if this helps: std::vector<int> numList; // Insert numbers into numList unsigned int min, max; min = max = 0; for ( unsigned int num = 0; num <= numList.size(); num++ ) { if ( numList[num] < min ) min = numList[num]; if ( numList[num] > max ) max = numList[num]; } // Now min is the lowest number // and max is the greatest number
Also, why is the code highlighter retared? Shouldn't the > be red as well???? It is in the for (...) loop, but not for std::vector<int>:o -- |
OnlineCop
Member #7,919
October 2006
|
FMC: Your question can be answered in two ways, depending on what you want. FMC said: Currently i'm trying to figure out a way to extract the smallest element from a list of integers. If you are given an unsorted list (this is assumed), you are either looking to sort this list, and then return the first element of the sorted list (which would be the smallest element). Or, you assume that the "smallest" number in an unsorted list is a VERY large number (the biggest that you can use, like 0xFFFFFFFF). Then for each integer in the array, you test to see if the next number is smaller than that big number. If it is, you set the smallest number to THAT number, and go to the next element. The reason you start with the LARGEST number you can find, is that if you start with 0, but the smallest number in the array is actually 5 or something LARGER than 0, you'll get invalid results. However, if you start with 999, and the smallest is 5, 5 < 999, and therefore, you smallest number will correctly be "5". EDIT: Don Freeman said: for ( unsigned int num = 0; num <= numList.size(); num++ ) Oh, and you NEVER want to do this (test numList.size() within the for..loop expression). If numList never changes, you're going to be re-calling size() for no reason, making this VERY slow. Move it out of the loop to speed it up The only time you WOULD do this is if the size of numList changes within this for..loop. int numListSize = numList.size(); for ( unsigned int num = 0; num <= numListSize; num++ )
|
Peter Wang
Member #23
April 2000
|
The way to think about any recursive problem is to consider the base case, and the recursive case. 1. What is the minimum element of an empty list? Answer: doesn't apply. Throw an exception or let the compiler throw one for you. 2. What is the minimum element of a single element list? Trivial. This is the base case. 3. What is the minimum element of a list with the first element H and the rest of the list T? Answer: the smaller of H and minimum(T). This is the recursive case. Then you just translate that directly to code. [This gives you the direct recursion solution. The "accumulator recursion" solution is analogous to what you'd write in C, and is probably more efficient. The thinking is not much different.] Pretty soon it becomes second nature.
|
Edgar Reynaldo
Major Reynaldo
May 2007
|
Quote: Or, you assume that the "smallest" number in an unsorted list is a VERY large number (the biggest that you can use, like 0xFFFFFFFF). Then for each integer in the array, you test to see if the next number is smaller than that big number. If it is, you set the smallest number to THAT number, and go to the next element. Just assign the starting value the value of the first element. There's no need to assign it to the largest possible number. Besides, I don't think he needed help with the logic of finding/sorting a list of numbers, just how to do it in OCAML. My Website! | EAGLE GUI Library Demos | My Deviant Art Gallery | Spiraloid Preview | A4 FontMaker | Skyline! (Missile Defense) Eagle and Allegro 5 binaries | Older Allegro 4 and 5 binaries | Allegro 5 compile guide |
Jonatan Hedborg
Member #4,886
July 2004
|
Quote: Oh, and you NEVER want to do this (test numList.size() within the for..loop expression). If numList never changes, you're going to be re-calling size() for no reason, making this VERY slow. Move it out of the loop to speed it up The only time you WOULD do this is if the size of numList changes within this for..loop. That will never be a bottleneck, don't be so dramatic The number of elements in an STL container is most probably (and absolutely in the case of a vector) stored. It probably looks something like: int size() { return size; } I have nothing to add on the actual topic. Sorry
|
Edgar Reynaldo
Major Reynaldo
May 2007
|
He is right about it though, it calls size() on every iteration. No need to call it repeatedly if it doesn't change. My Website! | EAGLE GUI Library Demos | My Deviant Art Gallery | Spiraloid Preview | A4 FontMaker | Skyline! (Missile Defense) Eagle and Allegro 5 binaries | Older Allegro 4 and 5 binaries | Allegro 5 compile guide |
SiegeLord
Member #7,827
October 2006
|
Not necessarily. The size() function is defined in a header, and thus is liable to be inlined. I don't think there is any performance difference. I take my size out first, but only for readability's sake. "For in much wisdom is much grief: and he that increases knowledge increases sorrow."-Ecclesiastes 1:18 |
Jonatan Hedborg
Member #4,886
July 2004
|
But during the entire life of an application, that optimization would probably not save more time than it took to write that extra line of code And besides, if you alter your app so that it needs to change the size inside the loop, you have to remember that you did that. Sure, it's not a big deal, but I like to keep it simple whenever possible. Also, I'm a fan of clean, nice (and still fast enough) one-liners. Which is also why I try to stay away from horrible languages like C/C++ EDIT: Anyway, I don't want to start a flame war. I just reacted to the wording "NEVER want to do this" and "VERY slow" which is just silly.
|
FMC
Member #4,431
March 2004
|
kazzmir: thanks! Peter: thanks for the insight. nonnus29: nearly there, thanks. The others: thanks but i had problems with the (recursive) implementation in OCaml, not the C way. P.S. Yay for smileys [FMC Studios] - [Caries Field] - [Ctris] - [Pman] - [Chess for allegroites] |
|