[Haskell-cafe] can there be (hash-table using) O(n) version of this
(I think currently) n log n algo?
tphyahoo at gmail.com
Fri Jul 17 18:24:21 EDT 2009
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.
Further, is there a hashtable implementation for haskell that doesn't
live in IO? Maybe in ST or something?
import qualified Data.Set as S
import Data.List (foldl')
testdata = [1,4,8,9,20,11,20,14,2,15] ++ [1..(10^6)]
wantedsum = 29
-- set data structure
-- findsums locates pairs of integers in a list that add up to a
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
else (S.insert next
-- hashtable data structure
-- result: t
-- fromList [(15,14),(16,13),(17,12),(18,11),(19,10),(20,9),(21,8),(22,7),(23,6),(24,5),(25,4),(26,3),(27,2),(28,1)]
-- probably O(n log n) complexity since using tree based Data.Set (a
few seconds on million+ element list)
t = findsums testdata wantedsum
More information about the Haskell-Cafe