From mboxrd@z Thu Jan  1 00:00:00 1970
Received: (from majordomo@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id BAA27520; Tue, 6 Nov 2001 01:34:20 +0100 (MET)
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 BAA27695 for <caml-list@pauillac.inria.fr>; Tue, 6 Nov 2001 01:34:19 +0100 (MET)
Received: from mail.mimuw.edu.pl (paf87.warszawa.sdi.tpnet.pl [217.96.225.87])
	by concorde.inria.fr (8.11.1/8.10.0) with ESMTP id fA60YHH29314
	for <caml-list@inria.fr>; Tue, 6 Nov 2001 01:34:18 +0100 (MET)
Received: (from news@localhost)
	by mail.mimuw.edu.pl (PLD/8.9.3) id BAA30644
	for caml-list@inria.fr; Tue, 6 Nov 2001 01:35:51 +0100
X-Authentication-Warning: qrnik.zagroda: news set sender to  Marcin 'Qrczak' Kowalczyk <qrczak@knm.org.pl> using -f
From: "Marcin 'Qrczak' Kowalczyk" <qrczak@knm.org.pl>
Subject: Re: [Caml-list] Specialized dictionaries
Date: Tue, 6 Nov 2001 00:35:47 +0000 (UTC)
Organization: Klub Nieszkodliwych =?iso-8859-2?Q?Manjak=F3w?=
Message-ID: <slrn9uec33.tip.qrczak@qrnik.zagroda>
References: <slrn9ucp5i.4an.qrczak@qrnik.zagroda> <15334.27347.973997.129488@pc803> <9s6j7c$i6r$1@qrnik.zagroda> <slrn9udm04.i70.qrczak@qrnik.zagroda> <9s6m53$k16$1@qrnik.zagroda>
X-Trace: qrnik.zagroda 1005006947 30298 192.168.0.1 (6 Nov 2001 00:35:47 GMT)
X-Complaints-To: abuse@localhost
NNTP-Posting-Date: Tue, 6 Nov 2001 00:35:47 +0000 (UTC)
User-Agent: slrn/0.9.7.2 (Linux)
To: caml-list@inria.fr
Sender: owner-caml-list@pauillac.inria.fr
Precedence: bulk

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