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 _______________________________________________ Haskell-Cafe mailing list [email protected] http://www.haskell.org/mailman/listinfo/haskell-cafe
