I want to partition the integer n=180 with terms >=5 I.e. n=15 => [[5,5,5],[8,7],[9,6],[10,5],[15]] The function part does this. memopart does it with memoization a lot faster. mempart works fine on my machine until n=120. For n=130 I get 'out of memory'. For other reasons I work on Win64 with ghc32. To save memory I replaced Int with Word8. I also replaced [Word8] with B.ByteString (memopartB). But no luck. I still get 'out of memory' for n=130. I run the program with: part +RTS -M4294967295 (429... is according to ghc the max memory I can use) Any ideas how to solve this? What is the most memory efficient replacement for a list? module Main ( main,part,memopart ) where import Data.Int import System.Time import qualified Data.ByteString.Lazy as B import Data.Word import Data.List (intercalate) part :: Int -> [[Int]] part 0 = [[]] part n = [x:y | x <- [5..n], y <- part (n-x), [x] >= take 1 y] partB :: Word8 -> [B.ByteString] partB 0 = [B.empty] partB n = [B.cons x y | x <- [5..n], y <- partB (n-x), B.singleton x >= y] memopart a = memo !! a where memo = [[]] : [[x:y | x <- [5..n], y <- memo !! (n-x), [x] >= take 1 y] | n <- [5..]] memopartB :: Int -> [B.ByteString] memopartB a = memo !! a where memo :: [[B.ByteString]] memo = [B.empty] : [[B.cons x y | x <- [5 :: Word8 .. n :: Word8], y <- memo !! minusWord8 n x, B.singleton x >= y] | n <- [5 :: Word8 ..]] minusWord8 :: Word8 -> Word8 -> Int minusWord8 c d = (fromIntegral c :: Int) - (fromIntegral d:: Int) main = do startTime <- getClockTime -- print $ length $ memopart 50 putStrLn $ showPartBRes $ memopartB 120 stopTime <- getClockTime putStrLn ("Time: " ++ timeDiffToString (diffClockTimes stopTime startTime)) showPartBRes :: [B.ByteString] -> String showPartBRes res = intercalate ", " $ map showB res where showB :: B.ByteString -> String showB arr = '[' : intercalate "," (B.foldr (\w acc -> show w : acc) [] arr) ++ "]"
On Wednesday, November 18, 2015 at 3:25:12 AM UTC-6, Kees Bleijenberg wrote:
I want to partition the integer n=180 with terms >=5
I.e. n=15 => [[5,5,5],[8,7],[9,6],[10,5],[15]]
For an alternate way to produce partitions, have a look at how the combinat package does it: https://hackage.haskell.org/package/combinat-0.2.8.1/docs/src/Math-Combinat-... In particular, in this part: _partitions' (!h ,!w) d = [ i:xs | i <- [1..min d h] , xs <- _partitions' (i,w-1) (d-i) ] if you change `i <- [1..min d h]` to ` i <- [5..min d h]` it appears you will get the partitions which have size at least 5. After you make the change, call the function like this: _partitions' (180,180) 180
Hi Erik, Complicated stuff. Your proposal worked. It took (on my compter )341 secs to compute the 612.743.290 partitions. Thanks! Kees ----------------------- On Wednesday, November 18, 2015 at 3:25:12 AM UTC-6, Kees Bleijenberg wrote: I want to partition the integer n=180 with terms >=5 I.e. n=15 => [[5,5,5],[8,7],[9,6],[10,5],[15]] For an alternate way to produce partitions, have a look at how the combinat package does it: https://hackage.haskell.org/package/combinat-0.2.8.1/docs/src/Math-Combinat-... In particular, in this part: _partitions' (!h ,!w) d = [ i:xs | i <- [1..min d h] , xs <- _partitions' (i,w-1) (d-i) ] if you change `i <- [1..min d h]` to ` i <- [5..min d h]` it appears you will get the partitions which have size at least 5. After you make the change, call the function like this: _partitions' (180,180) 180
Data.Vector.Unboxed and Data.Vector.Storable. Sometimes you have to be clever with memoization on these data structures, because every element in the vector is strict in the whole vector. There are some functions to help with this (like constructN). --Will On Wed, Nov 18, 2015 at 3:25 AM, Kees Bleijenberg < K.Bleijenberg@lijbrandt.nl> wrote:
What is the most memory efficient replacement for a list?
participants (3)
-
Erik Rantapaa -
Kees Bleijenberg -
William Yager