Re: [Caml-list] Preferred Way to Split a List

[Christophe Raffalli <christophe.raffalli@univ-savoie.fr>]

[-- Attachment #1: Type: text/plain, Size: 3859 bytes --]

David Allsopp a écrit :
> Christophe Raffalli wrote:
>> let split l n =
>>   let rec aux acc l n =
>>      if n = 0 then List.rev acc, l
>>      else match l with
>>         [] -> List.rev acc, []
>>      | hd::l -> aux (hd::acc) l (n-1)
>>   in aux [] l n
> 
> let split l n =
>   let acc = List.tlempty ()
>   in
>     let rec aux l n =
>        if n = 0 then (List.tlresult acc, l)
>        else match l with
>               []    -> (List.tlresult acc, [])
>             | hd::l -> List.tlcons hd acc; aux l (n-1)
>     in
>       aux l n
> 
> 

My point in my second last post was that in practice, for OCaml, the
second code is not much faster than the first ...

All this forced me to redo the testing : the details are bellow, but
list_split with rev wins for small list, the dirty thing with set_field
wins for big lists and the transition is between length 10000 and 100000.
Overall the difference is small.

Remark: the result might differ a lot for map if the mapped function does allocate memory ...
then there should almost no difference ...

So I would advice not to use Obj.set_field in this case ...

(* module for lists that can be constructed by both end *)
module Tlist = struct
  type 'a tlist = 'a list * 'a list

  (* a fake value for the tail of a list *)
  let rec dummy_tlist = Obj.magic 0::dummy_tlist

  let empty = [], []

  let tailcons tl a =
    match tl with
      [], [] -> let tl = a :: dummy_tlist in (tl, tl)
    | (_::_ as s), (_::dl as e) when dl == dummy_tlist ->
	let e' = a::dummy_tlist in
	Obj.set_field (Obj.repr e) 1 (Obj.repr e');
	s, e'
    | _ -> raise (Invalid_argument "Tlist.tail_cons")

  let cons a tl =
    match tl with
      [], [] -> let tl = a :: dummy_tlist in (tl, tl)
    | (_::_ as s), (_::dl as e) when dl ==  dummy_tlist ->
	a::s, e
    | _ -> raise (Invalid_argument "Tlist.cons")

  (* this must be the final call to transform a 'a tlist into a list *)
  let append tl l =
    match tl with
      [], [] -> l
    | (_::_ as s), (_::dl as e) when dl == dummy_tlist ->
	Obj.set_field (Obj.repr e) 1 (Obj.repr l);
	s
    | _ -> raise (Invalid_argument "Tlist.append")
end

(* the two versions of split *)
let split_with_rev l n =
   let rec aux acc l n =
      if n = 0 then List.rev acc, l
      else match l with
         [] -> List.rev acc, []
      | hd::l -> aux (hd::acc) l (n-1)
   in aux [] l n

let split_with_tlist l n =
  let rec aux acc l n =
    if n = 0 then (Tlist.append acc [], l)
    else match l with
      [] -> Tlist.append acc [], []
    | hd::l -> aux (Tlist.tailcons acc hd) l (n-1)
  in
  aux Tlist.empty l n

(* code for testing *)
let rec build_list n =
  let rec aux acc n =
    if n = 0 then acc else aux (n::acc) (n-1)
  in
  aux [] n

let test_tlist n p =
  for i = 1 to n do
    ignore (split_with_tlist (build_list (2*p)) p)
  done

let test_rev n p =
  for i = 1 to n do
    ignore (split_with_rev (build_list (2*p)) p)
  done

let _ = test_tlist 10 1000000

(*
result:

  test_tlist 10000000 10 : 3.1s
  test_rev 10000000 10 : 2.6s

  test_tlist 100000 1000 : 8.8s
  test_rev 100000 1000 : 6.9s

  test_tlist 100 100000 : 5.9s
  test_rev 100 100000 : 7.4s

  test_tlist 10 1000000 : 6.2s
  test_rev 10 1000000 : 7.9s
*)

-- 
Christophe Raffalli
Universite de Savoie
Batiment Le Chablais, bureau 21
73376 Le Bourget-du-Lac Cedex

tel: (33) 4 79 75 81 03
fax: (33) 4 79 75 87 42
mail: Christophe.Raffalli@univ-savoie.fr
www: http://www.lama.univ-savoie.fr/~RAFFALLI
---------------------------------------------
IMPORTANT: this mail is signed using PGP/MIME
At least Enigmail/Mozilla, mutt or evolution
can check this signature. The public key is
stored on www.keyserver.net
---------------------------------------------


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 252 bytes --]