[Haskell-cafe] Re: can there be (hash-table using) O(n) version of this (I think currently) n log n algo?

[Jon Harrop]

On Sunday 19 July 2009 09:26:14 Heinrich Apfelmus wrote:
> Thomas Hartman wrote:
> > The code below is, I think, n log n, a few seconds on a million + element
> > list.
> >
> > I wonder if it's possible to get this down to O(N) by using a
> > hashtable implemementation, or other better data structure.
> >
> > -- findsums locates pairs of integers in a list
> > that add up to a wanted sum.
> >
> > findsums :: [Int] -> Int -> S.Set (Int,Int)
> > findsums xs wanted = snd . foldl' f (S.empty,S.empty) $ xs
> >   where f (candidates,successes) next =
> >      if  S.member (wanted-next) candidates
> >        then (candidates, S.insert (next,wanted-next) successes)
> >        else (S.insert next candidates,successes)
>
> Remember that hash tables are actually O(key length) instead of O(1), so
> I don't think you can break the  log n  for really large lists this
> way since the key length increases as well (unless most elements are
> equal anyway).

Use a trie of hash tables with ~word-sized pieces of key.

-- 
Dr Jon Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/?e