Re: [Ocaml-lib-devel] Extlib.list.unique

[sejourne_kevin <sej...@ya...>]

Amit Dubey a écrit :
> In principle, I like the idea. I don't know if I like the implementation,
> though. It seems a bit too complex, and the variable names are difficult to
> decipher (e.g. "ac" means "accu/accumulator", but it isn't clear what tcn
> means; if you want to use short names, might as well use "x", "y", etc.)
> Maybe this is going too far, but could you overload the O(n^2)
> implementation with the faster one, for cases where you don't have an
> ordering over elements? i.e. something like this:
When ordering isn't need I use this one :
let delete_double ?(cmp=Pervasives.compare) l =
  let rec delete accu = function
      [] -> accu
    | [x] -> x :: accu
    | x::y::reste->
	delete (if (cmp x y) == 0 then accu else x::accu) (y::reste)
  in delete [] (List.sort cmp l)
;;
Witch


William Neumann proposed another implementation (with ordering)
without the problem of the array:


let uniq ?(last=false) ?(cmp=Pervasives.compare) l =
  let map = if last then List.rev_map else (fun f l -> List.rev
(List.rev_map f l)) in
  let cnt = let c = ref 0 in fun () -> incr c; !c in
  let rec drop_extras acc = function
    | h1::h2::t ->
        if fst h1 = fst h2
	then drop_extras acc (h1::t)
        else drop_extras (h1::acc) (h2::t)
    | [h] -> h::acc
    | [] -> acc
  in
    List.rev_map fst
      (* Reverse the list created by mapping fst over... *)
      (List.sort (fun (_,a) (_,b) -> b - a)
	 (* The list of pairs made by sorting in descending order by  the
second (int) element... *)
	 (drop_extras
            (* The list created by dropping all the duplicates from... *)
            []
            (* The list made by (stable) sorting by the first element... *)
            (List.sort (fun (a,_) (b,_) -> cmp a b)
               (* The list made by pairing each element with its
position  in the original list
		  (and possibly reversing the result if last = true) *)
               (map (fun x -> x,cnt ()) l))))
;;


I also have the same version of the function I post but without list :

let delete_double_unsort_list ?(last=false) ?(cmp=Pervasives.compare) l =
  let rec add_num ac n = function
      [] -> List.rev ac | h :: t -> add_num ((h,n)::ac) (succ n) t
  in
  let compare x y = cmp (fst x) (fst y) in
  let nl = add_num [] 0 l in
  let snl = List.sort compare nl in
  let rec get_dbl ac = function
      [] | [_] -> ac
    | (h1,nh1) :: (((h2,nh2) :: _) as l) ->
	if (cmp h1 h2) == 0
	then get_dbl ((if last then nh1 else nh2)::ac) l
	else get_dbl ac l
  in
  let dbl = get_dbl [] snl in
  let sdbl = List.stable_sort Pervasives.compare dbl in

  let rec delete ac a b = match a , b with
      _ , [] -> List.rev ((List.rev_map fst a) @ ac)
    | (_,na)::ta,nb::tb when na == nb -> delete ac ta tb
    | (e,_)::ta,gb -> delete (e::ac) ta gb
    | [],_ -> assert false
  in  delete [] nl sdbl
;;



It seems that William Neumann's version is the fastest on G4 / G5. On
the computers which I have at my arrangement (p4 1.6GZ) and (Barton 2500
+) I observed that it is my version the fastest.
As proposed by William I will write a "array version" with all functions
tails recursives that switch on list when max_array_size is reached.



	

	
		
___________________________________________________________________________ 
Appel audio GRATUIT partout dans le monde avec le nouveau Yahoo! Messenger 
Téléchargez cette version sur http://fr.messenger.yahoo.com