Version française
Home     About     Download     Resources     Contact us    
Browse thread
Re: large hash tables
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: -- (:)
From: Christopher L Conway <cconway@c...>
Subject: Re: [Caml-list] Re: large hash tables
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