Re: simulation of doubly linked lists in OCaml?

From: Dennis (Gang) Chen (Dennis.G.Chen@motorola.com)
Date: Fri Apr 28 2000 - 07:24:57 MET DST

  • Next message: Coscoy, Yann: "RE: hashtables for mutable records"

    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
    



    This archive was generated by hypermail 2b29 : Fri Apr 28 2000 - 12:12:51 MET DST