Version française
Home     About     Download     Resources     Contact us    

This site is updated infrequently. For up-to-date information, please visit the new OCaml website at

Browse thread
[Caml-list] Multi-keyed lookup table?
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: -- (:)
From: John Max Skaller <skaller@o...>
Subject: Re: [Caml-list] Multi-keyed lookup table?
Matt Gushee wrote:

> Hello, all--
> I am trying to decide on a data structure that allows efficient lookup
> of fonts according to various font properties. I am thinking that the
> data structures describing fonts will be something like this:
> So, does anyone have an idea what sort of data structure would work
> best?
> TIA for your suggestions.

Since you have 'arbitrary' keying, the ideal data structure
is clearly a relational database :-)

I personally suggest the brain dead equivalent, assuming
you have a *finite* set of fonts available: an array of
all the fonts in random order, and just use a linear search.

It's likely for a small number of fonts (<1000) that this
is faster than any other method due to caching issues:
arrays outperform ALL other data structures for small
number of entries.

You  might optimise this in two ways: cache some results,
on the basis the same request is made many times in one
program. [possibly making the cache persistent]

And you might be able to index the most commonly
used keys, such as font-family...much like you'd do in
a database.

You might gain some advantage in the comparisons
for equality using the == operator (physical equality)
provided you can ensure equal values have the same
physical representation (eg:

	let helvetica = "Helvetica"

	[.. helvetica .. ]
	[.. helvetica .. ]

which would mean you'd have to match the incoming request against the
available font-families:

	let bff = match ff with | "Helvetica" -> helvetica ..

so you can do the comparisons like

	if bff == font.(i).ff ......

This is an address comparison, and is faster than a string

There's a good chance the comparisons will dominate,
rather than the time taken to read each entry from
the database. That means an index would give you an
order of magnitude speed improvement .. in theory ..
but its hard to know which keys to index. I think I'd
be building a model with no indexes, encapsulating
it so that you can add indexes transparently later.
Then profile/performance test to see where the bottlenecks
are... I suspect it is client dependent (some clients will
key by font-family, other may choose font class ...)

John Max Skaller,
snail:10/1 Toxteth Rd, Glebe, NSW 2037, Australia.

To unsubscribe, mail Archives:
Bug reports: FAQ:
Beginner's list: