You can subscribe to this list here.
2003 
_{Jan}

_{Feb}
(81) 
_{Mar}
(97) 
_{Apr}
(88) 
_{May}
(80) 
_{Jun}
(170) 
_{Jul}
(9) 
_{Aug}

_{Sep}
(18) 
_{Oct}
(58) 
_{Nov}
(19) 
_{Dec}
(7) 

2004 
_{Jan}
(22) 
_{Feb}
(9) 
_{Mar}
(28) 
_{Apr}
(164) 
_{May}
(186) 
_{Jun}
(101) 
_{Jul}
(143) 
_{Aug}
(387) 
_{Sep}
(69) 
_{Oct}
(14) 
_{Nov}
(8) 
_{Dec}
(99) 
2005 
_{Jan}
(10) 
_{Feb}
(34) 
_{Mar}
(24) 
_{Apr}
(7) 
_{May}
(41) 
_{Jun}
(20) 
_{Jul}
(3) 
_{Aug}
(23) 
_{Sep}
(2) 
_{Oct}
(26) 
_{Nov}
(41) 
_{Dec}
(7) 
2006 
_{Jan}
(6) 
_{Feb}
(3) 
_{Mar}
(11) 
_{Apr}

_{May}

_{Jun}
(5) 
_{Jul}
(8) 
_{Aug}
(20) 
_{Sep}

_{Oct}
(6) 
_{Nov}
(5) 
_{Dec}

2007 
_{Jan}

_{Feb}
(1) 
_{Mar}

_{Apr}
(3) 
_{May}
(2) 
_{Jun}

_{Jul}

_{Aug}
(1) 
_{Sep}
(7) 
_{Oct}
(6) 
_{Nov}
(19) 
_{Dec}
(11) 
2008 
_{Jan}

_{Feb}
(7) 
_{Mar}
(9) 
_{Apr}
(21) 
_{May}
(42) 
_{Jun}
(27) 
_{Jul}
(28) 
_{Aug}
(26) 
_{Sep}
(16) 
_{Oct}
(32) 
_{Nov}
(49) 
_{Dec}
(65) 
2009 
_{Jan}
(35) 
_{Feb}
(20) 
_{Mar}
(36) 
_{Apr}
(42) 
_{May}
(111) 
_{Jun}
(99) 
_{Jul}
(70) 
_{Aug}
(25) 
_{Sep}
(15) 
_{Oct}
(29) 
_{Nov}
(3) 
_{Dec}
(18) 
2010 
_{Jan}
(10) 
_{Feb}
(4) 
_{Mar}
(57) 
_{Apr}
(63) 
_{May}
(71) 
_{Jun}
(64) 
_{Jul}
(30) 
_{Aug}
(49) 
_{Sep}
(11) 
_{Oct}
(4) 
_{Nov}
(2) 
_{Dec}
(3) 
2011 
_{Jan}
(1) 
_{Feb}
(1) 
_{Mar}

_{Apr}

_{May}

_{Jun}
(1) 
_{Jul}
(1) 
_{Aug}
(2) 
_{Sep}

_{Oct}

_{Nov}

_{Dec}
(1) 
2012 
_{Jan}

_{Feb}

_{Mar}

_{Apr}

_{May}

_{Jun}

_{Jul}

_{Aug}
(1) 
_{Sep}

_{Oct}

_{Nov}

_{Dec}

2013 
_{Jan}

_{Feb}
(1) 
_{Mar}

_{Apr}

_{May}

_{Jun}

_{Jul}

_{Aug}

_{Sep}

_{Oct}

_{Nov}

_{Dec}

2014 
_{Jan}

_{Feb}

_{Mar}

_{Apr}

_{May}

_{Jun}
(2) 
_{Jul}

_{Aug}

_{Sep}

_{Oct}

_{Nov}

_{Dec}

S  M  T  W  T  F  S 







1

2

3
(8) 
4
(3) 
5
(1) 
6

7

8

9

10
(1) 
11

12

13

14

15

16

17

18

19

20

21
(1) 
22
(3) 
23
(1) 
24

25
(8) 
26

27

28

29

30

31






From: Brian Hurt <bhurt@sp...>  20051022 20:12:49

On Fri, 21 Oct 2005, sejourne_kevin wrote: > Hello evrybody. > > Thanks for that lib I use evryday. > > But, I notice that ExtList.unique is in O(n^2) this is a problem for me, > I often use list over 100000 elements(and some time over million). > So I wrote a replacement function that is faster O(n+n*log(n)). > It use about 5X the space of the parameter list. On my computer (512 Mo) > the limit before the stak overflow is just over a million. I think this is actually a sign that you don't want to be using lists at all, but sets and/or maps. Brian 
From: sejourne_kevin <sejourne_kevin@ya...>  20051022 16:50:55

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 
From: Amit Dubey <amit.dubey@gm...>  20051022 16:09:32

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: let unique ?(last=3Dfalse) ?(cmp=3DNone) l =3D match cmp with  None > (* old unique *)  Some c > let cmp_node x y =3D c (fst x) (fst y) in let cmp_idx x y =3D Pervasives.compare (snd x) (snd y) in (* Sorted order, with an index for the original ordering *) let l' =3D stable_sort cmp_node (mapi (fun i x > (x,i)) l) in let rec remove_dup accu =3D function  [] > accu  x::xs > match accu with  [] > remove_dup [x] xs  (y::ys) as yl > if (cmp_node x y) =3D 0 then if last then remove_dup (x::ys) xs else remove_dup yl xs else remove_dup (x::yl) xs in (* Remove duplicates, restore original order, and remove the original index. *) map fst (stable_sort cmp_idx (remove_dup [] l')) Amit On 10/21/05, sejourne_kevin <sejourne_kevin@...> wrote: > > Hello evrybody. > > Thanks for that lib I use evryday. > > But, I notice that ExtList.unique is in O(n^2) this is a problem for me, > I often use list over 100000 elements(and some time over million). > So I wrote a replacement function that is faster O(n+n*log(n)). > It use about 5X the space of the parameter list. On my computer (512 Mo) > the limit before the stak overflow is just over a million. > > > let delete_double_unsort ?(last=3Dfalse) ?(cmp=3DPervasives.compare) l = =3D > let lg =3D List.length l in > let tcn =3D Array.make lg (List.hd l,0) in > let rec add_num n =3D function > [] > () >  h :: t > tcn.(n) < (h,n) ; (add_num (succ n) t) > in > let () =3D add_num 0 l in > let compare x y =3D cmp (fst x) (fst y) in > let tcn' =3D Array.copy tcn in > let () =3D Array.stable_sort compare tcn in > let plg =3D lg 1 in > let rec get_dbl ac n =3D > if n =3D=3D plg then ac > else > let n' =3D n+1 in > let h1 =3D tcn.(n) in > let h2 =3D tcn.(n') in > if (cmp (fst h1) (fst h2)) =3D=3D 0 > then get_dbl ((snd (if last then h1 else h2))::ac) n' > else get_dbl ac n' > in > let dbl =3D get_dbl [] 0 in > let sdbl =3D List.sort Pervasives.compare dbl in > let rec delete n =3D function > [] > > let ac =3D ref [] in > for i =3D n to lg 1 do > ac :=3D (fst tcn'.(i)) :: !ac > done; > List.rev !ac >  na::ta when na =3D=3D (snd tcn'.(n)) > delete (n+1) ta >  l > (fst tcn'.(n)) :: (delete (n+1) l) > in delete 0 sdbl > ;; > > As you can see this function support a additionnal option that let you > select if you want delete the first or the last occurence of a term. > For the "equivalence" with ExtList.unique set "~last:true". > > > for 100000 elements : > Extlib.list.unique : 165.850 seconds > this function : 0.380 seconds > for 1000000 elements : > Extlib.list.unique : stop by error after 2 hours... > this function : 9.600 seconds > > > > Even if you don't want to include it in the ExtLib I would be glade if > someone know how to improve it. > > > > Here few test code: > (* > let bench n p =3D > Random.self_init (); > let rec new_list n =3D > if n =3D=3D 0 then [] else (Random.int <http://Random.int>; 100000)::(new_= list > (pred n)) > in > let a_bench n =3D > let l =3D new_list n in Gc.compact(); > (*let t1 =3D Sys.time() in ignore (delete_double_unsort_list l);*) > (*let t1 =3D Sys.time() in ignore (delete_double l);*) > let t1 =3D Sys.time() in ignore ();(*(ExtLib.List.unique l);*) > let t2 =3D Sys.time() in Gc.compact (); > (*let t3 =3D Sys.time() in ignore (ExtLib.List.unique l);*) > let t3 =3D Sys.time() in ignore (delete_double_unsort l); > let t4 =3D Sys.time() in > (t2.t1,t4.t3) > in > let rec make_bench r n p =3D > if p =3D=3D 0 then r else make_bench ((a_bench n)::r) n (pred p) > in > let somme r =3D > let a,b =3D List.split r in > List.fold_left (+.) 0. a, List.fold_left (+.) 0. b > in > let t1,t2 =3D somme (make_bench [] n p) in > Printf.printf "\n[%.3f] [%.3f]\n" t1 t2 > ;; > bench (int_of_string Sys.argv.(1)) (int_of_string Sys.argv.(2)) > *) > (* > let verif n =3D > Random.self_init(); > let rec new_list n =3D > if n =3D=3D 0 then [] else ( Random.int <http://Random.int>; 10)::(new_lis= t > (pred n)) > in > let test l =3D > let p l =3D List.iter (Printf.printf "%d ") l in > (* p l ;print_newline (); *) > let l1 =3D delete_double_unsort_list ~last:true l > and l2 =3D delete_double_unsort ~last:true l > and l3 =3D ExtLib.List.unique l > in > (* p l1;print_newline (); > p l2;print_newline (); > p l3;print_newline (); *) > (l1 =3D l2 && l1 =3D l3) > in > while (test (new_list n)) do (); done > ;; > verif (int_of_string Sys.argv.(1));; > *) > > > > > > > > _________________________________________________________________________= __ > Appel audio GRATUIT partout dans le monde avec le nouveau Yahoo! Messenge= r > > T=E9l=E9chargez cette version sur http://fr.messenger.yahoo.com > > > >  > This SF.Net email is sponsored by: > Power Architecture Resource Center: Free content, downloads, discussions, > and more. http://solutions.newsforge.com/ibmarch.tmpl > _______________________________________________ > ocamllibdevel mailing list > ocamllibdevel@... > https://lists.sourceforge.net/lists/listinfo/ocamllibdevel > 