Version française
Home     About     Download     Resources     Contact us    

This site is updated infrequently. For up-to-date information, please visit the new OCaml website at

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: 2008-02-20 (16:02)
From: Christopher L Conway <cconway@c...>
Subject: Re: [Caml-list] Re: large hash tables

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]).