SHARE
TWEET

Untitled

a guest Feb 23rd, 2019 128 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. I want to exhaustively generate sidon sets, but my haskell code seems slow. Are there any improvements I could make to run this faster?
  2.  
  3.  
  4.  
  5. Previous Attempts: presorting sequences and choosing the head, using Data.Set, using a count variable instead of using size (all these attempts were slower)
  6.  
  7.  $ ghc -O2 sidon.hs
  8.  $ time ./sidon
  9. [5,10,12,18,21,22]
  10.  
  11. real    0m3.880s
  12. user    0m3.836s
  13. sys     0m0.041s
  14.  
  15.  
  16. import           Data.IntSet (IntSet, empty, insert, notMember, size)
  17. import           Data.List   (sortOn, subsequences)
  18.  
  19. isCollision' :: [Int] -> IntSet -> IntSet
  20. isCollision' currL set = case currL of
  21.   []     -> set
  22.   (x:xs) -> if notMember x set
  23.                then isCollision' xs (insert x set)
  24.                else set
  25.  
  26. isCollision :: [Int] -> Bool
  27. isCollision xs = length xs /= size (isCollision' xs empty)
  28.  
  29. isSidon :: [Int] -> Bool
  30. isSidon xs = not $ isCollision [ x+y | x <- xs, y <-xs, x <= y]
  31.  
  32. sidon :: Int -> [[Int]]
  33. sidon x = filter isSidon (subsequences [1..x])
  34.  
  35. maxSidon :: Int -> [Int]
  36. maxSidon sz = snd $ maximum $ [(length x, x) | x <- sidon sz]
  37.  
  38. main = putStrLn $ show $ maxSidon 22
  39. Thank you :)
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top