adding lots of elements to a list

adding lots of elements to a list

[julien.michel]

An application creates as many instances of a class as they are iterations in a
while-loop. 
I would like to store these objects once they are created, at each loop, in
order to operates on them later (to sort, to filter some elements etc...)
For example I would like to add each new instance to a list of object of this
class. 

The number of created objects can grow very fast, and may raise an amount
greater than 100 000 elements. 


At the beginning, I choose to store them in a list, because we can add/delete
elements without wondering about size problem... Actually, in my application, I
can not know how many elements I will add. So It is quite difficult to use arrays.
 
On the other hand, I heard there were some problems with lists wich are very long...

Can someone advise me a better way to do what I want ? 



By the way, I have some difficulties to simply add a new element to the same
list, each time I enter in a while-loop:

let count = ref 3 ;;    (* number of iteration *)
let list = [] in

while (!count > 0)  do
  decr count;
  let list = list@[!count] in
  Printf.printf "The 1st element is  %i \n" (List.hd list) ;
done;

Printf.printf "list contains %i elements \n" (List.length list) ;;


Here is the result after running the program:
The 1st element is  2
The 1st element is  1
The 1st element is  0
list contains 0 elements

The first 3 lines show that new elements are well added to the "local" list,
inside the loop but we can not access to the list outside the while loop,
according to the last line.

I try to declare "list" as a global variable:

let count = ref 3 ;;
let list = [] ;;

while (!count > 0)  do
  decr count;
  list = [!count]@list ;
  Printf.printf "The 1st element is  %i \n" (List.hd list) ;
done;

Printf.printf "list contains %i elements \n" (List.length list) ;;


But this time I get a "Warning S: this expression (list = [!count]@list ;)
should have type unit."
and I get the following error while running the program:
Fatal error: exception Failure("hd")
It seems that no elements are added to the list, which remains empty.

I hope this trivial question won't bother too much people...


Thank you all




-- 
MICHEL Julien
Elève Ingénieur 5ème année Polytech'Orléans
filière Electronique-Signaux-Images (ESI)
spécialité Systèmes Embarqués (SE)

200 Rue Ardoux
Bat A, appt 43
45160
OLIVET

Re: [Caml-list] adding lots of elements to a list

[Jonathan Roewen]

> By the way, I have some difficulties to simply add a new element to the same
> list, each time I enter in a while-loop:
>
> let count = ref 3 ;;    (* number of iteration *)
> let list = [] in
>
> while (!count > 0)  do
>  decr count;
>  let list = list@[!count] in
>  Printf.printf "The 1st element is  %i \n" (List.hd list) ;
> done;
>
> Printf.printf "list contains %i elements \n" (List.length list) ;;

The let in the function is local, so is completely different to the
global list value. You'd want to use a ref.

let list = ref [];;

while ... do
  list := !list @ [!count];
done

(* btw, the output proves you're not adding to the global list, as the
head of the list should never change, as you're concatenating to the
end of the list *)

(* as a further aside, concatenating two lists takes time proportional
to the length of the first argument (your global list). prepending is
faster, though ends up with a reversed list, as in: list := !count ::
!list *)

> I try to declare "list" as a global variable:
>
> let count = ref 3 ;;
> let list = [] ;;
>
> while (!count > 0)  do
>  decr count;
>  list = [!count]@list ; ***
>  Printf.printf "The 1st element is  %i \n" (List.hd list) ;
> done;

*** 'list = [!count] @ list' is a boolean equation. It in fact tests
if list is structurally equivalent to [!count] @ list, and generates
the value false, which is then discarded. Since list is never
modified, it is always empty, thus List.hd will raise the exception
you have witnessed.

> But this time I get a "Warning S: this expression (list = [!count]@list ;)
> should have type unit."

Yes, this is what I meant by the boolean equation -- it's return type
is bool, not unit.

Jonathan

Re: [Caml-list] adding lots of elements to a list

[Shawn]

julien.michel@etu.univ-orleans.fr wrote:
> Can someone advise me a better way to do what I want ? 
>
>   
Lists sound like the best choice for now. If memory becomes a problem, a 
disk-based db like gdbm might be an alternative. But until you /know/ 
that the lists are a bottleneck, don't bother.

>
> By the way, I have some difficulties to simply add a new element to the same
> list, each time I enter in a while-loop:
>
> let count = ref 3 ;;    (* number of iteration *)
> let list = [] in
>
> while (!count > 0)  do
>   decr count;
>   let list = list@[!count] in
>   Printf.printf "The 1st element is  %i \n" (List.hd list) ;
> done;
>
> Printf.printf "list contains %i elements \n" (List.length list) ;;
>
>
> Here is the result after running the program:
> The 1st element is  2
> The 1st element is  1
> The 1st element is  0
> list contains 0 elements
>   

You're creating a new binding named list each time you do let list = 
..., not updating an existing one.  Outside of the while loop, the fir
st, outer one is what's visible and used. You need references:

...
let list = ref []
...
while !count > 0 do
  ...
  list := !count :: !list
  ....
done

Also, avoid appending to the list like you do if it's going to be big, 
as doing so will cause a lot of extra work for the garbage collector.


Alternatively, do away with the while, and use a recursive function, and 
eliminate the need for references at all. Something like:

let rec count_list count lst =
    let count = count - 1 in
      if count > 0 then count_list count (count :: lst) else lst

let list = count_list 3 []

Re: [Caml-list] adding lots of elements to a list

[Nils Gesbert]

On Fri,  2 Jun 2006 17:28:46 +0200
julien.michel@etu.univ-orleans.fr wrote:

> let list = list@[!count] in
>   Printf.printf "The 1st element is  %i \n" (List.hd list) ;

What you are doing with this expression is not to modify the list "list" (which you cannot do, because lists are immutable) but to define a new variable, which happens to have the same name "list", whose scope is just the printf expression. So it is not even true that new elements are well added to the local list. You may see better the meaning of this code by using a different identifier for the local variable : your code is equivalent to

let new_list = list@[!count] in Printf.printf "The 1st element is  %i \n" (List.hd new_list)

so the original list is never modified and each iteration creates a new list.

To construct a list step by step, you may either use a reference and a loop or use a recursive function, like this for instance :

let list =
  let rec add_elem list count =
    if count > 0 then add_elem (count::list) (count-1)
    else list
  in add_elem [] 3

By the way, you should construct the list by always adding elements at the head (with the :: constructor) and avoid @, because @ is a function that has to go through the whole list to reach the end, take your new element then reconstruct the whole list (the lists are constructed backwards), whereas adding an element at start is immediate.

Re: [Caml-list] adding lots of elements to a list

[Jon Harrop]

On Friday 02 June 2006 16:28, julien.michel@etu.univ-orleans.fr wrote:
> The number of created objects can grow very fast, and may raise an amount
> greater than 100 000 elements.

That's fine as long as you don't use the non-tail-recursive modules from the 
List module (e.g. map, fold_right).

> let count = ref 3 ;;    (* number of iteration *)
> let list = [] in
>
> while (!count > 0)  do
>   decr count;
>   let list = list@[!count] in
>   Printf.printf "The 1st element is  %i \n" (List.hd list) ;
> done;
>
> Printf.printf "list contains %i elements \n" (List.length list) ;;

To get the desired behaviour you must use a list ref and replace the list each 
iteration:

# let count = ref 3 ;;    (* number of iteration *)
  let list = ref [] in

  while (!count > 0)  do
    decr count;
    list := !list @ [!count];
    Printf.printf "The 1st element is  %i \n" (List.hd !list) ;
  done;

  Printf.printf "list contains %i elements \n" (List.length !list);;
The 1st element is  2
The 1st element is  2
The 1st element is  2
list contains 3 elements
- : unit = ()

OCaml's lists are designed to be consed and decapitated from the front, 
so "h :: t" is O(1) whereas "t @ [h]" is O(n^2). ***

Also, you might find functional style easier to use here:

# let rec make = function 0 -> [] | n -> n-1 :: make (n-1);;
val make : int -> int list = <fun>
# make 3;;
- : int list = [2; 1; 0]

That version isn't tail-recursive, so it'll raise Stack_overflow or even 
segfault if you give it a big "n":

# make 1000000;;
Stack overflow during evaluation (looping recursion?).

But you can write a tail-recursive version by accumulating the list in reverse 
order:

# let rec make a = function 0 -> List.rev a | n -> make (n-1::a) (n-1);;
val make : int list -> int -> int list = <fun>
# make [] 1000000;;
- : int list =
[999999; 999998; 999997; 999996; 999995; 999994; 999993; ...]

*** actually I think this is O(n^3) in native code.

-- 
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
Objective CAML for Scientists
http://www.ffconsultancy.com/products/ocaml_for_scientists