From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: weis Received: (from weis@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id MAA19122 for caml-redist; Fri, 28 Apr 2000 12:09:33 +0200 (MET DST) Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id HAA14695 for ; Fri, 28 Apr 2000 07:23:57 +0200 (MET DST) Received: from ftpbox.mot.com (ftpbox.mot.com [129.188.136.101]) by concorde.inria.fr (8.8.7/8.8.7) with ESMTP id HAA27589 for ; Fri, 28 Apr 2000 07:23:56 +0200 (MET DST) Received: [from mothost.mot.com (mothost.mot.com [129.188.137.101]) by ftpbox.mot.com (ftpbox 2.1) with ESMTP id WAA02947; Thu, 27 Apr 2000 22:23:53 -0700 (MST)] Received: [from fraser.asc.corp.mot.com (fraser.asc.corp.mot.com [217.1.104.8]) by mothost.mot.com (MOT-mothost 2.0) with ESMTP id WAA08181; Thu, 27 Apr 2000 22:23:50 -0700 (MST)] Received: from motorola.com (jaguar [217.1.104.76]) by fraser.asc.corp.mot.com (8.8.7/8.8.7) with ESMTP id OAA08222; Fri, 28 Apr 2000 14:53:46 +0930 (CST) Sender: weis Message-ID: <390920A9.560C7512@motorola.com> Date: Fri, 28 Apr 2000 14:54:57 +0930 From: "Dennis (Gang) Chen" Organization: Motorola Australia Software Centre X-Mailer: Mozilla 4.5 [en] (X11; I; SunOS 5.5.1 sun4u) X-Accept-Language: en MIME-Version: 1.0 To: Jan Brosius CC: caml-list@inria.fr Subject: Re: simulation of doubly linked lists in OCaml? References: <002601bfb050$b47b8790$f902bed4@jannt> Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Jan Brosius wrote: > Hi, I wonder if it is possible to simulate by datatype constructors a doubly linked list > in OCaml/ I read the english version about pointers in Ocaml, interesting but it is not > cleat for me how to simulate a doubly linkedlist. Friendly Jan Brosius Here is my code for doubly linked list. type 'a tp_dlist = Nil | Cell of 'a * 'a tp_dlist ref * 'a tp_dlist ref;; let dlist_create () = ref Nil;; let rec dlist_member x rf_list = match !rf_list with Nil -> false | Cell ( y, rf_left, rf_right ) -> if y = x then true else dlist_member x rf_right;; (* insert a cell containing x to the front of the double list pointed by rf_list*) let dlist_insert x rf_list = let new_tail = !rf_list in rf_list := Cell (x, ref Nil, ref new_tail);; (* delete the first cell containing x from the double linked list pointed by rf_list *) let rec dlist_delete x rf_list = match !rf_list with Nil -> () | Cell (y, rf_left, rf_right) -> if x = y then begin rf_list := !rf_right; match !rf_right with Nil -> () | Cell (z, rf_rleft , rf_rright) -> rf_rleft := !rf_left end else dlist_delete x rf_right;; let dlist_print rf_list = let rec dlist_pr rf_lst = match !rf_lst with Nil -> print_string " ]"; print_newline () | Cell (y, rf_left, rf_right) -> print_int y; print_string "; "; dlist_pr rf_right in print_string "[ "; dlist_pr rf_list;; (* The following functiona are used to test *) (* create a double linked list containing n+1, n, ..., 1 *) let create_dlist n = let rf_inilist = ref Nil in let rec create rf_list i = if i>n then () else begin dlist_insert (i+1) rf_list; create rf_list (i+1) end in create rf_inilist 0; rf_inilist;; (* Test results: # let d1 = create_dlist 5;; val d1 : int tp_dlist ref = {contents= Cell (6, {contents=Nil}, {contents= Cell (5, {contents=Nil}, {contents= Cell (4, {contents=Nil}, {contents= Cell (3, {contents=Nil}, {contents= Cell (2, {contents=Nil}, {contents=Cell (1, {contents=Nil}, {contents=Nil})})})})})})} # dlist_print d1;; [ 6; 5; 4; 3; 2; 1; ] - : unit = () # dlist_delete 4 d1;; - : unit = () # dlist_print d1;; [ 6; 5; 3; 2; 1; ] - : unit = () # dlist_delete 7 d1;; - : unit = () # dlist_print d1;; [ 6; 5; 3; 2; 1; ] - : unit = () *) By the way, I've done some tests on list and set operations. I've not attached the codes here because not all programs are of good quality and I have not got time to carefully check if all results are reliable. Besides, attaching codes here might make the mail too big. Anyone who is interested in these codes can contact me directly. Verifying the results and improving the codes are welcome. The experimental result show that the deletion operation for functional list is quite slow in the worst case. I compile the native code: ocamlopt listTest.ml -o mlListTest Then call dchen% .time /mlListTest 100000 50000 200 2 It creates a list of size 100000 and repeat 200 times for inserting an element in the front of the list and deleting an element in the last position. The second argument 50000 is useless for this test. On my machine, it tooks 59:53 user time to finish. 59.53u 0.09s 1:32.29 64.6% For a linked list built in C, I have g++ pointer.cpp -o pointer time ./pointer 100000 50000 200 2 3.80u 0.04s 0:06.81 56.3% Mutable list in ocaml works much faster than functional list, although still somewhat slower than C code: ocamlopt mlistTest.ml -o mlistTest time ./mlistTest 100000 50000 200 2 6.62u 0.05s 0:09.56 69.7% The performance would be improved if using the implementation proposed in ocaml FAQ. To my surprise, the ocaml ordered set library is faster than STL set in all three operations that I tested: set creation, membership AND deletion. ocamlopt setTest.ml -o setTest The deletion is surprisingly fast: time ./setTest 100000 50000 200000 2 5.41u 0.06s 0:09.00 60.7% It adds the number 50000 into the balanced tree of size 100000, then deletes it. The operation repeats for 200000 times. This is even faster than STL set: g++ stlSetTest.cpp -o stlSetTest time ./stlSetTest 100000 50000 200000 2 8.83u 0.02s 0:14.14 62.5% The ocaml set is functional and each deletion needs to rebuid a subtree. Although this subtree might be significantly smaller than the whole tree, but such a good performance is still amazing. Here is the code to test the deletion: let rec deletion_test ele cnt set = if cnt > 0 then deletion_test ele (cnt-1) (IntSet.remove ele (IntSet.add ele set)) else ();; Cheers. -- Dennis Gang CHEN Senior Software Engineer Motorola Australia Software Centre, Electronic Design Automation 2 Second Avenue, Mawson Lakes, SA 5095, Australia phone: +61 8 8203 3560, mailto: Dennis.G.Chen@motorola.com