From: skaller <skaller@users.sourceforge.net>
To: Gerd Stolpmann <gerd@gerd-stolpmann.de>
Cc: Radu Grigore <radugrigore@gmail.com>,
Jon Harrop <jon@jdh30.plus.com>,
caml-list@yquem.inria.fr
Subject: Re: [Caml-list] The boon of static type checking
Date: 07 Feb 2005 01:59:42 +1100 [thread overview]
Message-ID: <1107701982.6363.252.camel@pelican.wigram> (raw)
In-Reply-To: <1107692201.5887.18.camel@localhost.localdomain>
On Sun, 2005-02-06 at 23:16, Gerd Stolpmann wrote:
> For your problem, I would guess that a hash table (in phase 1) plus
> sorting (in phase 2) is the relatively best solution (from your
> description). That avoids a lot of overhead compared to Map, especially
> memory management consumes much less time.
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.
EG, 64K word array of lists, indexed by first two
bytes of the string, then 64K sorts.
If your keys are not well distributed on the first
two bytes, use a monotonic hashing function.
--
John Skaller, mailto:skaller@users.sf.net
voice: 061-2-9660-0850,
snail: PO BOX 401 Glebe NSW 2037 Australia
Checkout the Felix programming language http://felix.sf.net
next prev parent reply other threads:[~2005-02-06 14:59 UTC|newest]
Thread overview: 169+ messages / expand[flat|nested] mbox.gz Atom feed top
2005-02-02 21:31 Estimating the size of the ocaml community Yaron Minsky
2005-02-02 21:36 ` [Caml-list] " Christopher A. Watford
2005-02-02 21:54 ` Frédéric Gava
2005-02-03 3:58 ` skaller
2005-02-03 6:35 ` Erik de Castro Lopo
2005-02-03 16:29 ` Olivier Pérès
2005-02-03 18:06 ` Thomas Fischbacher
2005-02-03 18:34 ` Frédéric Gava
2005-02-03 21:16 ` Thomas Fischbacher
2005-02-03 21:58 ` Paul Snively
2005-02-03 22:42 ` Bardur Arantsson
2005-02-03 23:29 ` Thomas Fischbacher
2005-02-03 22:33 ` josh
2005-02-03 23:22 ` Thomas Fischbacher
2005-02-03 23:39 ` Richard Jones
2005-02-04 9:04 ` Frédéric Gava
2005-02-04 9:37 ` Richard Jones
2005-02-04 10:11 ` Olivier Andrieu
2005-02-04 11:14 ` Frédéric Gava
2005-02-04 12:15 ` Richard Jones
2005-02-04 12:46 ` Marcin 'Qrczak' Kowalczyk
2005-02-04 12:51 ` Gerd Stolpmann
2005-02-04 13:43 ` Richard W. M. Jones
2005-02-04 16:01 ` Gerd Stolpmann
2005-02-04 16:52 ` Oliver Bandel
2005-02-04 17:21 ` Frédéric Gava
2005-02-04 17:55 ` Oliver Bandel
2005-02-04 16:48 ` Oliver Bandel
2005-02-04 12:15 ` Olivier Andrieu
2005-02-04 16:42 ` Oliver Bandel
2005-02-04 10:58 ` Oliver Bandel
2005-02-04 17:27 ` Damien Doligez
2005-02-04 17:59 ` Oliver Bandel
2005-02-04 1:17 ` Michael Walter
2005-02-04 10:53 ` Oliver Bandel
2005-02-04 22:01 ` Thomas Fischbacher
2005-02-05 12:27 ` Oliver Bandel
2005-02-06 0:08 ` Thomas Fischbacher
2005-02-03 23:29 ` Richard Jones
2005-02-04 2:33 ` Jon Harrop
[not found] ` <877e9a170502031856175260c8@mail.gmail.com>
2005-02-04 2:56 ` Michael Walter
2005-02-04 10:26 ` [Caml-list] The boon of static type checking Jon Harrop
2005-02-04 17:02 ` Damien Doligez
2005-02-04 18:00 ` Jon Harrop
2005-02-04 20:38 ` Christophe TROESTLER
2005-02-04 21:42 ` Jon Harrop
2005-02-04 22:11 ` Christophe TROESTLER
2005-02-05 0:58 ` Jon Harrop
2005-02-05 1:52 ` Shivkumar Chandrasekaran
2005-02-07 18:47 ` Damien Doligez
2005-02-05 5:24 ` Jacques Garrigue
2005-02-04 21:52 ` Thomas Fischbacher
2005-02-04 22:27 ` Christophe TROESTLER
2005-02-05 10:00 ` Remi Vanicat
2005-02-06 11:18 ` Christophe TROESTLER
2005-02-04 22:55 ` Thomas Fischbacher
2005-02-06 0:02 ` Thomas Fischbacher
2005-02-06 0:56 ` Erik de Castro Lopo
2005-02-06 10:03 ` Thomas Fischbacher
2005-02-06 1:34 ` Richard Jones
2005-02-06 2:30 ` Erik de Castro Lopo
2005-02-06 9:54 ` Marcin 'Qrczak' Kowalczyk
2005-02-06 10:05 ` Thomas Fischbacher
2005-02-05 21:48 ` Michael Walter
2005-02-06 10:22 ` Radu Grigore
2005-02-06 12:16 ` Gerd Stolpmann
2005-02-06 14:59 ` skaller [this message]
2005-02-06 22:30 ` Radu Grigore
2005-02-07 3:15 ` Erik de Castro Lopo
2005-02-06 17:28 ` Jon
2005-02-06 22:26 ` Radu Grigore
2005-02-07 2:51 ` skaller
2005-02-07 1:54 ` skaller
2005-02-07 5:34 ` Brian Hurt
2005-02-07 6:16 ` Michael Walter
2005-02-07 14:58 ` Igor Pechtchanski
2005-02-12 15:22 ` Brian Hurt
2005-02-12 16:11 ` Thomas Fischbacher
2005-02-12 18:47 ` Brian Hurt
2005-02-12 21:58 ` Thomas Fischbacher
2005-02-12 17:06 ` skaller
2005-02-12 22:57 ` Michael Walter
2005-02-13 1:12 ` Thomas Fischbacher
2005-02-13 1:51 ` Tony Edgin
2005-02-13 2:12 ` Thomas Fischbacher
2005-02-13 10:26 ` Daniel Heck
2005-02-13 18:28 ` Thomas Fischbacher
2005-02-13 20:52 ` Michael Walter
2005-02-13 21:42 ` Thomas Fischbacher
2005-02-13 22:51 ` Michael Walter
2005-02-13 23:59 ` Thomas Fischbacher
2005-02-14 0:11 ` Michael Walter
2005-02-14 0:42 ` Thomas Fischbacher
2005-02-14 1:11 ` Michael Walter
2005-02-14 1:46 ` Michael Vanier
2005-02-14 1:57 ` Michael Walter
2005-02-14 14:19 ` Stefan Monnier
2005-02-14 14:36 ` [Caml-list] " Thomas Fischbacher
2005-02-14 1:19 ` [Caml-list] " Michael Walter
2005-02-14 17:29 ` Martin Berger
2005-02-14 18:44 ` skaller
2005-02-14 19:17 ` Thomas Fischbacher
2005-02-14 2:22 ` skaller
2005-02-14 8:04 ` Paul Snively
2005-02-14 9:33 ` Thomas Fischbacher
2005-02-14 9:39 ` Thomas Fischbacher
2005-02-14 2:10 ` skaller
2005-02-13 2:27 ` Brian Hurt
2005-02-13 2:34 ` Michael Walter
2005-02-07 10:57 ` Ville-Pertti Keinonen
2005-02-07 16:58 ` skaller
2005-02-07 17:24 ` Ville-Pertti Keinonen
2005-02-07 17:56 ` Paul Snively
2005-02-07 17:59 ` skaller
2005-02-07 17:30 ` skaller
2005-02-07 13:07 ` Marcin 'Qrczak' Kowalczyk
2005-02-12 15:42 ` Brian Hurt
2005-02-07 17:42 ` Ken Rose
2005-02-07 2:23 ` skaller
2005-02-04 9:29 ` [Caml-list] Estimating the size of the ocaml community Thomas Fischbacher
2005-02-04 10:26 ` Andreas Rossberg
2005-02-04 17:54 ` Thomas Fischbacher
2005-02-04 15:43 ` Oliver Bandel
2005-02-04 19:54 ` Christophe TROESTLER
2005-02-04 20:20 ` Karl Zilles
2005-02-04 22:07 ` Thomas Fischbacher
2005-02-04 9:41 ` Richard Jones
2005-02-04 10:03 ` Thomas Fischbacher
2005-02-04 16:00 ` Oliver Bandel
2005-02-04 17:32 ` sejourne_kevin
2005-02-04 18:46 ` Oliver Bandel
2005-02-05 1:49 ` skaller
2005-02-04 8:55 ` Ville-Pertti Keinonen
2005-02-04 9:36 ` Thomas Fischbacher
2005-02-04 10:30 ` Oliver Bandel
2005-02-04 22:02 ` Thomas Fischbacher
2005-02-05 13:14 ` Oliver Bandel
2005-02-05 16:37 ` Why can't types and exceptions be nested (was: Re: [Caml-list] Estimating the size of the ocaml community) Richard Jones
2005-02-05 17:04 ` Basile STARYNKEVITCH
2005-02-05 19:26 ` Oliver Bandel
2005-02-06 2:56 ` skaller
2005-02-04 21:55 ` [Caml-list] Estimating the size of the ocaml community Basile STARYNKEVITCH
2005-02-03 19:04 ` ronniec95
2005-02-03 20:06 ` skaller
2005-02-03 20:50 ` chris.danx
2005-02-03 21:14 ` Jon Harrop
2005-02-03 21:34 ` chris.danx
2005-02-03 22:07 ` Bardur Arantsson
2005-02-03 21:47 ` Nicolas Cannasse
2005-02-04 3:52 ` skaller
2005-02-04 16:12 ` Oliver Bandel
2005-02-05 2:04 ` skaller
2005-02-03 20:35 ` chris.danx
2005-02-03 8:36 ` sejourne_kevin
2005-02-03 8:39 ` Matthieu Brucher
2005-02-03 16:23 ` Olivier Pérès
2005-02-03 10:10 ` Stefano Zacchiroli
2005-02-03 16:44 ` Vincenzo Ciancia
2005-02-02 22:10 ` [Caml-list] " Kenneth Knowles
2005-02-02 22:40 ` Michael Jeffrey Tucker
2005-02-02 22:52 ` Richard Jones
2005-02-02 23:42 ` Nicolas Cannasse
2005-02-03 6:53 ` Evan Martin
2005-02-03 6:57 ` Eric Stokes
2005-02-03 20:53 ` chris.danx
2005-02-03 23:29 ` Sylvain LE GALL
2005-02-03 23:38 ` sejourne_kevin
2005-02-07 8:49 ` Sven Luther
2005-02-07 9:23 ` Johann Spies
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=1107701982.6363.252.camel@pelican.wigram \
--to=skaller@users.sourceforge.net \
--cc=caml-list@yquem.inria.fr \
--cc=gerd@gerd-stolpmann.de \
--cc=jon@jdh30.plus.com \
--cc=radugrigore@gmail.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).