Re: [Caml-list] Multi-keyed lookup table?

[Matt Gushee <matt@gushee.net>]

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