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 XAA06569; Fri, 8 Aug 2003 23:30:48 +0200 (MET DST) X-Authentication-Warning: pauillac.inria.fr: majordomo set sender to owner-caml-list@pauillac.inria.fr using -f 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 XAA31887 for ; Fri, 8 Aug 2003 23:30:46 +0200 (MET DST) Received: from mz1.forethought.net (mzpi3.forethought.net [216.241.36.12]) by concorde.inria.fr (8.11.1/8.11.1) with ESMTP id h78LUjf19487 for ; Fri, 8 Aug 2003 23:30:45 +0200 (MET DST) Received: from [216.241.35.41] (helo=swordfish) by mz1.forethought.net with esmtp (Exim 4.14) id 19lEou-0000qs-6N for caml-list@pauillac.inria.fr; Fri, 08 Aug 2003 15:30:44 -0600 Received: from matt by swordfish with local (Exim 3.35 #1 (Debian)) id 19lEos-0005tY-00 for ; Fri, 08 Aug 2003 15:30:42 -0600 Date: Fri, 8 Aug 2003 15:30:37 -0600 From: Matt Gushee To: caml-list@pauillac.inria.fr Subject: Re: [Caml-list] Multi-keyed lookup table? Message-ID: <20030808213037.GA21525@swordfish> Reply-To: Matt Gushee Mail-Followup-To: caml-list@pauillac.inria.fr References: <3F32D078.7060705@ozemail.com.au> <20030807194135.GB21983@swordfish> <38641.141.155.88.179.1060292970.squirrel@minsky-primus.homeip.net> <3F32D210.6060302@ozemail.com.au> <20030807194135.GB21983@swordfish> <38641.141.155.88.179.1060292970.squirrel@minsky-primus.homeip.net> <20030807194135.GB21983@swordfish> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <3F32D078.7060705@ozemail.com.au> <3F32D210.6060302@ozemail.com.au> <38641.141.155.88.179.1060292970.squirrel@minsky-primus.homeip.net> User-Agent: Mutt/1.3.27i X-Loop: caml-list@inria.fr X-Spam: no; 0.00; gushee:01 caml-list:01 font:99 fallback:01 preferable:01 0400,:01 yaron:01 minsky:01 simplistic:01 hashtable:01 hash:01 illustrating:01 runtime:01 caching:01 postgres:01 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk Thanks for the very informative answers. Even if I end up not exactly following any of your suggestions, this thread has given me some very good information about data structures in general. On Thu, Aug 07, 2003 at 03:16:49PM -0500, Brian Hurt wrote: > > In the general case, this is hard. In this specific case, you might > consider just hard coding your levels. So you'd end up with a data > structure like: > > All font > / | \ > / | \ > medium bold light <-- pick the weight > / | \ > [ ..... ] Interesting idea, and not one that I had considered at all. It seems quite efficient, too. On the other hand, it looks like the fixed search path would make it rather hard to implement fallback rules in case an exact match isn't found. It seems to me that that's fairly important for fonts: there are many situations where it is preferable to produce some output with some fonts not quite right rather than producing nothing. Maybe it should be up to the application to handle that. But then if my library only implements an exact-match-or-nothing approach, you could easily end up an application that has to handle a whole lot of Not_found exceptions. I'd rather create a library that can do a closest-match kind of thing. On Thu, Aug 07, 2003 at 05:49:30PM -0400, Yaron Minsky wrote: > This might be too simplistic, but how about creating a union type the > includes all of the different things you might want to index on, and then > use that as the key to a hashtable. The efficiency of that would hinge on > the efficiency of the hash function, I would think. I would expect it to > be simple to implement and pretty quick. You mean something like: type font_spec = (font_family * font_weight * font_style * font_width * encoding) ? I thought of doing something like that, but then how would you handle something like: (_, Bold, Italic, _, _) (* Not intended to represent real code, just illustrating the concept *) ? I was actually thinking of doing a little bitmask voodoo, e.g. let candidates = List.filter (fun key font -> (key land pattern) == pattern) all_fonts (BTW, why isn't there an Array.filter function?) On Fri, Aug 08, 2003 at 08:19:36AM +1000, John Max Skaller wrote: > > Since you have 'arbitrary' keying, the ideal data structure > is clearly a relational database :-) Now why didn't I think of that? I may actually follow that semi-suggestion. Or rather, having thought through my idea a little more, it becomes clear that having a good runtime data structure is only part of the problem. A persistence mechanism is also important, and if we use, say, an RDBMS or DBM, it probably doesn't make much sense to layer an OCaml data structure on top of that. Or does it? Does caching have much value when the data being cached is a bunch of short strings? Anyway, I think what I'm going to do is--since what I have in mind is a pretty simple utility that does one thing--to whip together a library with several backends--Dbm, Postgres, etc.--and see how they work out. Again, thanks for the ideas. -- Matt Gushee When a nation follows the Way, Englewood, Colorado, USA Horses bear manure through mgushee@havenrock.com its fields; http://www.havenrock.com/ When a nation ignores the Way, Horses bear soldiers through its streets. --Lao Tzu (Peter Merel, trans.) ------------------- To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/ Beginner's list: http://groups.yahoo.com/group/ocaml_beginners