Re: [Caml-list] Specialized dictionaries

["Marcin 'Qrczak' Kowalczyk" <qrczak@knm.org.pl>]

Mon, 5 Nov 2001 19:24:06 +0100, Nicolas George <nicolas.george@ens.fr> pisze:

>>				    So updates are rare, dictionaries are
>> small and they contain small integers, but lookups are very frequent.
> 
> What about using a simple array for that?

I tested how fast is 'a option array, allocated big enough for the
test and with bounds checking disabled. Surprisingly it's only 5%
faster than the Patricia tree, measuring the whole program which does
many lookups but also other things like computing Fibonacci numbers.

The difference would be obviously larger if actual dictionaries had
more entries (the ones I used happened to have 10, 2 and 3), but now
I feel that this part is optimized enough.

Here is the mutable version of Ptmap I'm using:

module Typetbl =
  struct
    type 'a t = 'a Ptmap.t ref
    let create _ = ref Ptmap.empty
    let add dict k v = dict := Ptmap.add k v (!dict)
    let find dict k = Ptmap.find k (!dict)
    let mem dict k = Ptmap.mem k (!dict)
    let replace dict k v = dict := Ptmap.add k v (!dict)
    let clear dict = dict := Ptmap.empty
  end

And here is the quick & dirty array wrapper:

module Typetbl =
  struct
    type 'a t = 'a option array
    let create _ = Array.make 100 None
    let add dict k v = dict.(k) <- Some v
    let find dict k = match dict.(k) with
      | Some v -> v
      | None -> raise Not_found
    let mem dict k = match dict.(k) with
      | Some _ -> true
      | None -> false
    let replace dict k v = dict.(k) <- Some v
    let clear dict = for i = 0 to 99 do dict.(i) <- None done
  end

-- 
 __("<  Marcin Kowalczyk * qrczak@knm.org.pl http://qrczak.ids.net.pl/
 \__/
  ^^
QRCZAK

-------------------
Bug reports: http://caml.inria.fr/bin/caml-bugs  FAQ: http://caml.inria.fr/FAQ/
To unsubscribe, mail caml-list-request@inria.fr  Archives: http://caml.inria.fr