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 AAA01105; Fri, 8 Aug 2003 00:19:49 +0200 (MET DST) X-Authentication-Warning: pauillac.inria.fr: majordomo set sender to owner-caml-list@pauillac.inria.fr using -f Received: from nez-perce.inria.fr (nez-perce.inria.fr [192.93.2.78]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id AAA03013 for ; Fri, 8 Aug 2003 00:19:48 +0200 (MET DST) Received: from mail2.tpgi.com.au (mail.tpgi.com.au [203.12.160.58]) by nez-perce.inria.fr (8.11.1/8.11.1) with ESMTP id h77MJkT07597 for ; Fri, 8 Aug 2003 00:19:47 +0200 (MET DST) Received: from ozemail.com.au (203-213-127-88-syd-ts20-2600.tpgi.com.au [203.213.127.88]) (authenticated bits=0) by mail2.tpgi.com.au (8.12.9/8.12.9) with ESMTP id h77MJaKk023867; Fri, 8 Aug 2003 08:19:37 +1000 Message-ID: <3F32D078.7060705@ozemail.com.au> Date: Fri, 08 Aug 2003 08:19:36 +1000 From: John Max Skaller User-Agent: Mozilla/5.0 (X11; U; Linux i686; en-US; rv:0.9.2.1) Gecko/20010901 X-Accept-Language: en-us MIME-Version: 1.0 To: Matt Gushee CC: caml-list@pauillac.inria.fr Subject: Re: [Caml-list] Multi-keyed lookup table? References: <20030807194135.GB21983@swordfish> Content-Type: text/plain; charset=us-ascii; format=flowed Content-Transfer-Encoding: 7bit X-Kaspersky-Antivirus: Passed X-Loop: caml-list@inria.fr X-Spam: no; 0.00; ozemail:01 caml-list:01 gushee:01 all--:01 font:99 caching:01 optimise:01 font-family:99 helvetica:99 model:01 toxteth:01 glebe:01 2037,:01 9660:01 0850:01 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk 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