From: "Christopher L Conway" <cconway@cs.nyu.edu>
To: caml-list@yquem.inria.fr
Subject: Re: [Caml-list] Re: large hash tables
Date: Wed, 20 Feb 2008 11:02:31 -0500 [thread overview]
Message-ID: <4a051d930802200802w6c0e9a0ayde1000f1b4584753@mail.gmail.com> (raw)
In-Reply-To: <33d2b3f70802192118p4d887212mcf76e34447c54e52@mail.gmail.com>
John,
Everybody else has answered your main concerns in great detail. I just
have a silly nitpick...
> let newList = List.rev_append [newElement] oldList in
This is what is known as a "functional anti-pattern" [1]. As you
probably know, adding an element at the head of a list is O(1),
whereas adding an element at the tail is O(n). If possible, you should
just keep these lists in reverse order (let newList = newElement ::
oldList) and call List.rev "on demand" when you pull the data out of
the table (or keep separate forward/reversed lists, populating the
forward list on demand, ala Okasaki's deques [2]).
Regards,
Chris
[1] http://trevion.blogspot.com/2006/12/little-knowledge-gets-you-long-way.html
[2] http://www.eecs.usma.edu/webs/people/okasaki/pubs.html#jfp95
next prev parent reply other threads:[~2008-02-20 16:02 UTC|newest]
Thread overview: 9+ messages / expand[flat|nested] mbox.gz Atom feed top
[not found] <fa.XXbywsQknpl7bhlesWN8vFLM58c@ifi.uio.no>
[not found] ` <55e81f00-5ef7-4946-9272-05595299e114@41g2000hsc.googlegroups.com>
2008-02-20 5:18 ` John Caml
2008-02-20 6:11 ` [Caml-list] " Francois Rouaix
2008-02-20 8:37 ` David Allsopp
2008-02-20 8:44 ` Alain Frisch
2008-02-20 13:37 ` Damien Doligez
2008-02-20 14:37 ` Oliver Bandel
2008-02-20 16:02 ` Christopher L Conway [this message]
2008-02-21 13:54 ` Damien Doligez
2008-02-21 16:40 ` Christopher L Conway
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=4a051d930802200802w6c0e9a0ayde1000f1b4584753@mail.gmail.com \
--to=cconway@cs.nyu.edu \
--cc=caml-list@yquem.inria.fr \
/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).