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

[John Max Skaller <skaller@ozemail.com.au>]

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
comparison.

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, mailto:skaller@ozemail.com.au
snail:10/1 Toxteth Rd, Glebe, NSW 2037, Australia.
voice:61-2-9660-0850


-------------------
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