From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Delivered-To: caml-list@yquem.inria.fr Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by yquem.inria.fr (Postfix) with ESMTP id 6B01CBC88 for ; Mon, 7 Feb 2005 04:15:40 +0100 (CET) Received: from smtp.syd.swiftdsl.com.au (smtp.syd.swiftdsl.com.au [218.214.224.138]) by concorde.inria.fr (8.13.0/8.13.0) with SMTP id j173FbTK027516 for ; Mon, 7 Feb 2005 04:15:39 +0100 Received: (qmail 24128 invoked from network); 7 Feb 2005 03:15:43 -0000 Received: from unknown (HELO coltrane.mega-nerd.net) (218.214.64.136) by smtp.syd.swiftdsl.com.au with SMTP; 7 Feb 2005 03:15:43 -0000 Received: from coltrane (coltrane [192.168.1.101]) by coltrane.mega-nerd.net (Postfix) with SMTP id D9F9F7ADD for ; Mon, 7 Feb 2005 14:15:31 +1100 (EST) Date: Mon, 7 Feb 2005 14:15:31 +1100 From: Erik de Castro Lopo To: caml-list@yquem.inria.fr Subject: Re: [Caml-list] The boon of static type checking Message-Id: <20050207141531.60c639ee.erikd@mega-nerd.com> In-Reply-To: <7f8e92aa05020614301a11ca97@mail.gmail.com> References: <891bd33905020213315a2ebb18@mail.gmail.com> <877e9a170502031856175260c8@mail.gmail.com> <877e9a17050203185674680413@mail.gmail.com> <200502041026.56107.jon@jdh30.plus.com> <7f8e92aa0502060222383aac60@mail.gmail.com> <1107692201.5887.18.camel@localhost.localdomain> <1107701982.6363.252.camel@pelican.wigram> <7f8e92aa05020614301a11ca97@mail.gmail.com> Organization: Erik Conspiracy Secret Labs X-Mailer: Sylpheed version 1.0.0 (GTK+ 1.2.10; i386-pc-linux-gnu) Mime-Version: 1.0 Content-Type: text/plain; charset=US-ASCII Content-Transfer-Encoding: 7bit X-Miltered: at concorde with ID 4206DD59.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Spam: no; 0.00; caml-list:01 wrote:01 sourceforge:01 wrote:01 indexing:01 trie:98 trie:98 nospam:98 strings:01 strings:01 simpler:01 checking:01 tree:02 languages:03 string:03 X-Spam-Checker-Version: SpamAssassin 3.0.2 (2004-11-16) on yquem.inria.fr X-Spam-Status: No, score=0.1 required=5.0 tests=FORGED_RCVD_HELO autolearn=disabled version=3.0.2 X-Spam-Level: On Mon, 7 Feb 2005 00:30:12 +0200 Radu Grigore wrote: > On Sun, 06 Feb 2005 06:59:52 -0800 (PST), skaller > wrote: > > If you know something of the distribution of your keys, > > which are strings, you can also make this much faster > > by indexing using some suitable monotonic function > > on the string prefix, and only sorting equivalent > > strings. > > This is a nice idea that crossed my mind. If a simpler (to code) > solution won't work I'll definitely try it. Sounds a little like a simplified version of a TRIE: http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Tree/Trie/ Erik -- +-----------------------------------------------------------+ Erik de Castro Lopo nospam@mega-nerd.com (Yes it's valid) +-----------------------------------------------------------+ "The one thing that reading these five books has hammered home is how much C++ has turned into 3 languages stuck in a bag fighting to get out. Low C++, High C++, and Generic C++."