Version française
Home     About     Download     Resources     Contact us    
Browse thread
[Caml-list] Should be INSIDE STANDARD-LIB: Hashtbl.keys
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: -- (:)
From: Brian Hurt <bhurt@s...>
Subject: Re: [Caml-list] Should be INSIDE STANDARD-LIB: Hashtbl.keys
On Fri, 23 Apr 2004, Xavier Leroy wrote:

> > I think a good addition to the Hashtbl-module
> > would be a function, that gives back a list of keys
> > that are in the hash.
> 
> With your specification (no repetitions in the list), that function
> would run in quadratic time, which is a sure sign that lists aren't
> the right data structure here.  (More generally speaking, "lists
> without repetitions" is almost always the wrong data structure.)

No, I think creating such a list would take O(n log n) time.

OK, we're starting with a hash table.  That means we have a set of 
buckets, each bucket is a set of key/data pairs.  Assume the same key can 
be inserted multiple times (can it?)- in this case, all duplicate keys 
should be in the same bucket.  So, for each bucket, I sort all entries in 
the bucket by key (worst case I only have one bucket and sorting is O(n 
log n)).  Once sorted, I go throught and eliminate duplicates, which is 
now an O(n) algorithm:

let uniq lst =
   let rec loop accum = function
       | [] -> List.rev accum
       | x :: [] -> List.rev (x :: accum)
       | x :: y :: t ->
           if (x = y) then
               loop accum (x :: t)
           else
               loop (x :: accum) (y :: t)
    in
    loop [] lst
;;

(You can do it more efficiently that this, but this gets the idea across)
Viola- uniqueness in subquadratic time.  And in practice, approaching 
linear time- hashtables with lots of elements in a single bucket are 
computationally expensive, so you're likely to be sorting a whole bunch of 
short (1 and 2 element) lists.

-- 
"Usenet is like a herd of performing elephants with diarrhea -- massive,
difficult to redirect, awe-inspiring, entertaining, and a source of
mind-boggling amounts of excrement when you least expect it."
                                - Gene Spafford 
Brian

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners