Partition int 180. Out of memory

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
4 messages Options
Reply | Threaded
Open this post in threaded view
|

Partition int 180. Out of memory

Kees Bleijenberg

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) ++ "]"


_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Partition int 180. Out of memory

Erik Rantapaa-2


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-Partitions-Integer.html#line-308

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


_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Partition int 180. Out of memory

Will Yager
In reply to this post by Kees Bleijenberg
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 <[hidden email]> wrote:


What is the most memory efficient replacement for a list?

 


_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Partition int 180. Out of memory

Kees Bleijenberg
In reply to this post by Erik Rantapaa-2
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-Partitions-Integer.html#line-308

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


_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe