查找对于内存来说太大的列表大小？
Finding the size of a list that's too big for memory?
这里是全新的 Haskell 程序员。刚刚完成 "Learn you a Haskell"... 我对具有某些特定属性的集合有多大感兴趣。我有一些小参数值的工作代码，但我想知道如何处理更大的结构。我知道 Haskell 可以做到 "infinite data structures"，但我只是不知道如何从我所在的地方到达那里并向您学习 Haskell / Google 没有得到我在这。
这是我的 eSet 的工作代码，给定 "small" 个参数 r 和 t
import Control.Monad
import System.Environment
import System.Exit
myPred :: [Int] -> Bool
myPred a = myPred' [] a
where
myPred' [] [] = False
myPred' [] [0] = True
myPred' _ [] = True
myPred' acc (0:aTail) = myPred' acc aTail
myPred' acc (a:aTail)
| a `elem` acc = False
| otherwise = myPred' (a:acc) aTail
superSet :: Int -> Int -> [[Int]]
superSet r t = replicateM r [0..t]
eSet :: Int -> Int -> [[Int]]
eSet r t = filter myPred $ superSet r t
main :: IO ()
main = do
args <- getArgs
case args of
[rArg, tArg] ->
print $ length $ eSet (read rArg) (read tArg)
[rArg, tArg, "set"] ->
print $ eSet (read rArg) (read tArg)
_ ->
die "Usage: eSet r r set <set optional for printing set itself otherwise just print the size
当compiled/run我得到
$ ghc eSet.hs -rtsopts
[1 of 1] Compiling Main ( eSet.hs, eSet.o )
Linking eSet ...
$ # Here's is a tiny eSet to illustrate. It is the set of lists of r integers from zero to t with no repeated nonzero list entries
$ ./eSet 4 2 set
[[0,0,0,0],[0,0,0,1],[0,0,0,2],[0,0,1,0],[0,0,1,2],[0,0,2,0],[0,0,2,1],[0,1,0,0],[0,1,0,2],[0,1,2,0],[0,2,0,0],[0,2,0,1],[0,2,1,0],[1,0,0,0],[1,0,0,2],[1,0,2,0],[1,2,0,0],[2,0,0,0],[2,0,0,1],[2,0,1,0],[2,1,0,0]]
$ ./eSet 8 4 +RTS -sstderr
3393
174,406,136 bytes allocated in the heap
29,061,152 bytes copied during GC
4,382,568 bytes maximum residency (7 sample(s))
148,664 bytes maximum slop
14 MB total memory in use (0 MB lost due to fragmentation)
Tot time (elapsed) Avg pause Max pause
Gen 0 328 colls, 0 par 0.047s 0.047s 0.0001s 0.0009s
Gen 1 7 colls, 0 par 0.055s 0.055s 0.0079s 0.0147s
INIT time 0.000s ( 0.000s elapsed)
MUT time 0.298s ( 0.301s elapsed)
GC time 0.102s ( 0.102s elapsed)
EXIT time 0.001s ( 0.001s elapsed)
Total time 0.406s ( 0.405s elapsed)
%GC time 25.1% (25.2% elapsed)
Alloc rate 585,308,888 bytes per MUT second
Productivity 74.8% of total user, 75.0% of total elapsed
$ ./eSet 10 5 +RTS -sstderr
63591
27,478,010,744 bytes allocated in the heap
4,638,903,384 bytes copied during GC
532,163,096 bytes maximum residency (15 sample(s))
16,500,072 bytes maximum slop
1556 MB total memory in use (0 MB lost due to fragmentation)
Tot time (elapsed) Avg pause Max pause
Gen 0 52656 colls, 0 par 6.865s 6.864s 0.0001s 0.0055s
Gen 1 15 colls, 0 par 8.853s 8.997s 0.5998s 1.8617s
INIT time 0.000s ( 0.000s elapsed)
MUT time 52.652s ( 52.796s elapsed)
GC time 15.717s ( 15.861s elapsed)
EXIT time 0.193s ( 0.211s elapsed)
Total time 68.564s ( 68.868s elapsed)
%GC time 22.9% (23.0% elapsed)
Alloc rate 521,883,277 bytes per MUT second
Productivity 77.1% of total user, 76.7% of total elapsed
我发现我的内存使用率非常高，并且有很多垃圾收集。当 运行 eSet 12 6 我得到一个分段错误。
我觉得 filter myPred $ superSet r t 使我无法一次懒惰地将子集作为一个部分，这样我就可以处理更大（但有限）的集合，但我不知道如何更改为另一个可以做到这一点的方法。我认为这是我问题的根源。
此外，由于这是我的第一个 Haskell 程序，非常感谢关于风格的要点以及如何实现 "pythonic" 的 Haskell 模拟！
我怀疑这里的罪魁祸首是 replicateM，它有 this implementation:
replicateM cnt0 f =
loop cnt0
where
loop cnt
| cnt <= 0 = pure []
| otherwise = liftA2 (:) f (loop (cnt - 1))
问题行是liftA2 (:) f (loop (cnt - 1))；可能 loop (cnt - 1) 在对 (:) 的所有调用中共享，部分应用于 f 的元素，因此 loop (cnt - 1) 必须保存在内存中。不幸的是 loop (cnt - 1) 是一个很长的列表...
说服 GHC 不 分享一些东西可能有点麻烦。 superSet 的以下重新定义为我提供了一个很好的平坦内存使用；当然，对于适合内存的示例，它可能会慢一些。关键思想是让未经训练的眼睛（即 GHC）看起来像递归单子动作取决于之前做出的选择，即使它不是。
superSet :: Int -> Int -> [[Int]]
superSet r t = go r 0 where
go 0 ignored = if ignored == 0 then [[]] else [[]]
go r ignored = do
x <- [0..t]
xs <- go (r-1) (ignored+x)
return (x:xs)
如果您不介意避免优化，更自然的定义也适用：
superSet 0 t = [[]]
superSet r t = do
x <- [0..t]
xs <- superSet (r-1) t
return (x:xs)
...但是 -O2 GHC 太聪明了，注意到它可以共享递归调用。
在重新阅读 LYaH 的部分内容并考虑@daniel-wagners 的回答后，monadically composing 听起来值得再试一次。新代码的总内存是平坦的，并且可以在有和没有 -O2 优化的情况下工作。
来源：
import Control.Monad
import System.Environment
import System.Exit
allowed :: [Int] -> Bool
allowed a = allowed' [] a
where
allowed' [ ] [ ] = False
allowed' [ ] [0] = True
allowed' _ [ ] = True
allowed' acc (0:aTail) = allowed' acc aTail
allowed' acc (a:aTail)
| a `elem` acc = False
| otherwise = allowed' (a:acc) aTail
branch :: Int -> [Int] -> [[Int]]
branch t x = filter allowed [n:x | n <- [0..t]]
eSet :: Int -> Int -> [[Int]]
eSet r t = return [] >>= foldr (<=<) return (replicate r (branch t))
main :: IO ()
main = do
args <- getArgs
case args of
[rArg, tArg] ->
print $ length $ eSet (read rArg) (read tArg)
[rArg, tArg, "set"] ->
print $ eSet (read rArg) (read tArg)
_ -> die "Usage: eSet r r set <set optional>"
具有 monadic 函数组合的版本测试速度更快并且没有内存问题...
$ ./eSetMonad 10 5 +RTS -sstderr
63591
289,726,000 bytes allocated in the heap
997,968 bytes copied during GC
63,360 bytes maximum residency (2 sample(s))
24,704 bytes maximum slop
2 MB total memory in use (0 MB lost due to fragmentation)
Tot time (elapsed) Avg pause Max pause
Gen 0 553 colls, 0 par 0.008s 0.008s 0.0000s 0.0002s
Gen 1 2 colls, 0 par 0.000s 0.000s 0.0002s 0.0003s
INIT time 0.000s ( 0.000s elapsed)
MUT time 0.426s ( 0.429s elapsed)
GC time 0.009s ( 0.009s elapsed)
EXIT time 0.000s ( 0.000s elapsed)
Total time 0.439s ( 0.438s elapsed)
%GC time 2.0% (2.0% elapsed)
Alloc rate 680,079,893 bytes per MUT second
Productivity 98.0% of total user, 98.3% of total elapsed
一种完全替代的方法是只做一点组合分析。这是 eSet r t 所做的过程，尽我所能：
- 从一组大小为
t 的集合中最多选择 r 个元素而不进行替换。
- 通过交错标记值将序列填充到
r 的长度。
因此，让我们只计算执行每个步骤的方法，而不是实际执行它们。我们将引入一个新参数 s，它是步骤 (1) 生成的序列的长度（因此我们知道它有 s <= r 和 s <= t）。从一组大小为t的集合中不放回地绘制元素时，有多少个大小为s的序列？那么，第一个元素有 t 个选择，第二个元素有 t-1 个选择，第三个元素有 t-2 个选择，...
-- sequencesWithoutReplacement is a very long name!
seqWORepSize :: Integer -> Integer -> Integer
seqWORepSize s t = product [t-s+1 .. t]
然后我们要将序列填充到 r 的长度。我们将从我们的序列中选择 r 长序列中的 s 个位置，其余的将是哨兵。有多少种方法可以做到这一点？这是一个著名的组合运算符 choose.
choose :: Integer -> Integer -> Integer
choose r s = product [r-s+1 .. r] `div` product [2 .. s]
产生给定长度的填充序列的方法数就是这两个数的乘积，因为"what values to insert"和"where to insert values"的选择可以完全独立
paddedSeqSize :: Integer -> Integer -> Integer -> Integer
paddedSeqSize r s t = seqWORepSize s t * (r `choose` s)
现在我们差不多完成了。只需遍历所有可能的序列长度并添加 paddedSeqSize.
eSetSize :: Integer -> Integer -> Integer
eSetSize r t = sum $ map (\s -> paddedSeqSize r s t) [0..r]
我们可以在ghci中试试：
> :set +s
> map length $ [eSet 1 1, eSet 4 4, eSet 6 4, eSet 4 6]
[2,209,1045,1045]
(0.13 secs, 26,924,264 bytes)
> [eSetSize 1 1, eSetSize 4 4, eSetSize 6 4, eSetSize 4 6]
[2,209,1045,1045]
(0.01 secs, 120,272 bytes)
这种方式明显更快并且对内存更友好。事实上，我们可以查询并获得关于 eSet 的答案，我们永远无法逐个计算其大小，例如
> length . show $ eSetSize 1000 1000
2594
(0.26 secs, 909,746,448 bytes)
祝你好运，一次数到 10^2594。 =P
编辑
这个想法也可以适用于自己生成填充序列，而不是仅仅计算有多少。首先，我发现自己反复定义了一个方便的实用程序，用于挑选列表中的各个元素并报告剩余部分：
zippers :: [a] -> [([a], a, [a])]
zippers = go [] where
go ls [] = []
go ls (h:rs) = (ls, h, rs) : go (h:ls) rs
现在，无需替换的序列可以通过重复从剩余的元素中选择一个元素来完成。
seqWORep :: Int -> [a] -> [[a]]
seqWORep 0 _ = [[]]
seqWORep n xs = do
(ls, y, rs) <- zippers xs
ys <- seqWORep (n-1) (ls++rs)
return (y:ys)
一旦我们有了一个序列，我们就可以通过生成标记值的所有交错来将其填充到所需的大小，如下所示：
interleavings :: Int -> a -> [a] -> [[a]]
interleavings 0 _ xs = [xs]
interleavings n z [] = [replicate n z]
interleavings n z xs@(x:xt) = map (z:) (interleavings (n-1) z xs)
++ map (x:) (interleavings n z xt)
最后，顶层函数只委托给 seqWORep 和 interleavings。
eSet :: Int -> Int -> [[Int]]
eSet r t = do
s <- [0..r]
xs <- seqWORep s [1..t]
interleavings (r-s) 0 xs
在我的测试中，这个修改后的 eSet 在有和没有优化的情况下都有很好的平坦内存使用；不会生成任何需要稍后 filtered 的虚假元素，因此比您的原始提案更快；与依赖于欺骗 GHC 的答案相比，在我看来这是一个很自然的定义。一个不错的属性集合！
这里是全新的 Haskell 程序员。刚刚完成 "Learn you a Haskell"... 我对具有某些特定属性的集合有多大感兴趣。我有一些小参数值的工作代码，但我想知道如何处理更大的结构。我知道 Haskell 可以做到 "infinite data structures"，但我只是不知道如何从我所在的地方到达那里并向您学习 Haskell / Google 没有得到我在这。
这是我的 eSet 的工作代码，给定 "small" 个参数 r 和 t
import Control.Monad
import System.Environment
import System.Exit
myPred :: [Int] -> Bool
myPred a = myPred' [] a
where
myPred' [] [] = False
myPred' [] [0] = True
myPred' _ [] = True
myPred' acc (0:aTail) = myPred' acc aTail
myPred' acc (a:aTail)
| a `elem` acc = False
| otherwise = myPred' (a:acc) aTail
superSet :: Int -> Int -> [[Int]]
superSet r t = replicateM r [0..t]
eSet :: Int -> Int -> [[Int]]
eSet r t = filter myPred $ superSet r t
main :: IO ()
main = do
args <- getArgs
case args of
[rArg, tArg] ->
print $ length $ eSet (read rArg) (read tArg)
[rArg, tArg, "set"] ->
print $ eSet (read rArg) (read tArg)
_ ->
die "Usage: eSet r r set <set optional for printing set itself otherwise just print the size
当compiled/run我得到
$ ghc eSet.hs -rtsopts
[1 of 1] Compiling Main ( eSet.hs, eSet.o )
Linking eSet ...
$ # Here's is a tiny eSet to illustrate. It is the set of lists of r integers from zero to t with no repeated nonzero list entries
$ ./eSet 4 2 set
[[0,0,0,0],[0,0,0,1],[0,0,0,2],[0,0,1,0],[0,0,1,2],[0,0,2,0],[0,0,2,1],[0,1,0,0],[0,1,0,2],[0,1,2,0],[0,2,0,0],[0,2,0,1],[0,2,1,0],[1,0,0,0],[1,0,0,2],[1,0,2,0],[1,2,0,0],[2,0,0,0],[2,0,0,1],[2,0,1,0],[2,1,0,0]]
$ ./eSet 8 4 +RTS -sstderr
3393
174,406,136 bytes allocated in the heap
29,061,152 bytes copied during GC
4,382,568 bytes maximum residency (7 sample(s))
148,664 bytes maximum slop
14 MB total memory in use (0 MB lost due to fragmentation)
Tot time (elapsed) Avg pause Max pause
Gen 0 328 colls, 0 par 0.047s 0.047s 0.0001s 0.0009s
Gen 1 7 colls, 0 par 0.055s 0.055s 0.0079s 0.0147s
INIT time 0.000s ( 0.000s elapsed)
MUT time 0.298s ( 0.301s elapsed)
GC time 0.102s ( 0.102s elapsed)
EXIT time 0.001s ( 0.001s elapsed)
Total time 0.406s ( 0.405s elapsed)
%GC time 25.1% (25.2% elapsed)
Alloc rate 585,308,888 bytes per MUT second
Productivity 74.8% of total user, 75.0% of total elapsed
$ ./eSet 10 5 +RTS -sstderr
63591
27,478,010,744 bytes allocated in the heap
4,638,903,384 bytes copied during GC
532,163,096 bytes maximum residency (15 sample(s))
16,500,072 bytes maximum slop
1556 MB total memory in use (0 MB lost due to fragmentation)
Tot time (elapsed) Avg pause Max pause
Gen 0 52656 colls, 0 par 6.865s 6.864s 0.0001s 0.0055s
Gen 1 15 colls, 0 par 8.853s 8.997s 0.5998s 1.8617s
INIT time 0.000s ( 0.000s elapsed)
MUT time 52.652s ( 52.796s elapsed)
GC time 15.717s ( 15.861s elapsed)
EXIT time 0.193s ( 0.211s elapsed)
Total time 68.564s ( 68.868s elapsed)
%GC time 22.9% (23.0% elapsed)
Alloc rate 521,883,277 bytes per MUT second
Productivity 77.1% of total user, 76.7% of total elapsed
我发现我的内存使用率非常高，并且有很多垃圾收集。当 运行 eSet 12 6 我得到一个分段错误。
我觉得 filter myPred $ superSet r t 使我无法一次懒惰地将子集作为一个部分，这样我就可以处理更大（但有限）的集合，但我不知道如何更改为另一个可以做到这一点的方法。我认为这是我问题的根源。
此外，由于这是我的第一个 Haskell 程序，非常感谢关于风格的要点以及如何实现 "pythonic" 的 Haskell 模拟！
我怀疑这里的罪魁祸首是 replicateM，它有 this implementation:
replicateM cnt0 f =
loop cnt0
where
loop cnt
| cnt <= 0 = pure []
| otherwise = liftA2 (:) f (loop (cnt - 1))
问题行是liftA2 (:) f (loop (cnt - 1))；可能 loop (cnt - 1) 在对 (:) 的所有调用中共享，部分应用于 f 的元素，因此 loop (cnt - 1) 必须保存在内存中。不幸的是 loop (cnt - 1) 是一个很长的列表...
说服 GHC 不 分享一些东西可能有点麻烦。 superSet 的以下重新定义为我提供了一个很好的平坦内存使用；当然，对于适合内存的示例，它可能会慢一些。关键思想是让未经训练的眼睛（即 GHC）看起来像递归单子动作取决于之前做出的选择，即使它不是。
superSet :: Int -> Int -> [[Int]]
superSet r t = go r 0 where
go 0 ignored = if ignored == 0 then [[]] else [[]]
go r ignored = do
x <- [0..t]
xs <- go (r-1) (ignored+x)
return (x:xs)
如果您不介意避免优化，更自然的定义也适用：
superSet 0 t = [[]]
superSet r t = do
x <- [0..t]
xs <- superSet (r-1) t
return (x:xs)
...但是 -O2 GHC 太聪明了，注意到它可以共享递归调用。
在重新阅读 LYaH 的部分内容并考虑@daniel-wagners 的回答后，monadically composing 听起来值得再试一次。新代码的总内存是平坦的，并且可以在有和没有 -O2 优化的情况下工作。
来源：
import Control.Monad
import System.Environment
import System.Exit
allowed :: [Int] -> Bool
allowed a = allowed' [] a
where
allowed' [ ] [ ] = False
allowed' [ ] [0] = True
allowed' _ [ ] = True
allowed' acc (0:aTail) = allowed' acc aTail
allowed' acc (a:aTail)
| a `elem` acc = False
| otherwise = allowed' (a:acc) aTail
branch :: Int -> [Int] -> [[Int]]
branch t x = filter allowed [n:x | n <- [0..t]]
eSet :: Int -> Int -> [[Int]]
eSet r t = return [] >>= foldr (<=<) return (replicate r (branch t))
main :: IO ()
main = do
args <- getArgs
case args of
[rArg, tArg] ->
print $ length $ eSet (read rArg) (read tArg)
[rArg, tArg, "set"] ->
print $ eSet (read rArg) (read tArg)
_ -> die "Usage: eSet r r set <set optional>"
具有 monadic 函数组合的版本测试速度更快并且没有内存问题...
$ ./eSetMonad 10 5 +RTS -sstderr
63591
289,726,000 bytes allocated in the heap
997,968 bytes copied during GC
63,360 bytes maximum residency (2 sample(s))
24,704 bytes maximum slop
2 MB total memory in use (0 MB lost due to fragmentation)
Tot time (elapsed) Avg pause Max pause
Gen 0 553 colls, 0 par 0.008s 0.008s 0.0000s 0.0002s
Gen 1 2 colls, 0 par 0.000s 0.000s 0.0002s 0.0003s
INIT time 0.000s ( 0.000s elapsed)
MUT time 0.426s ( 0.429s elapsed)
GC time 0.009s ( 0.009s elapsed)
EXIT time 0.000s ( 0.000s elapsed)
Total time 0.439s ( 0.438s elapsed)
%GC time 2.0% (2.0% elapsed)
Alloc rate 680,079,893 bytes per MUT second
Productivity 98.0% of total user, 98.3% of total elapsed
一种完全替代的方法是只做一点组合分析。这是 eSet r t 所做的过程，尽我所能：
- 从一组大小为
t的集合中最多选择r个元素而不进行替换。 - 通过交错标记值将序列填充到
r的长度。
因此，让我们只计算执行每个步骤的方法，而不是实际执行它们。我们将引入一个新参数 s，它是步骤 (1) 生成的序列的长度（因此我们知道它有 s <= r 和 s <= t）。从一组大小为t的集合中不放回地绘制元素时，有多少个大小为s的序列？那么，第一个元素有 t 个选择，第二个元素有 t-1 个选择，第三个元素有 t-2 个选择，...
-- sequencesWithoutReplacement is a very long name!
seqWORepSize :: Integer -> Integer -> Integer
seqWORepSize s t = product [t-s+1 .. t]
然后我们要将序列填充到 r 的长度。我们将从我们的序列中选择 r 长序列中的 s 个位置，其余的将是哨兵。有多少种方法可以做到这一点？这是一个著名的组合运算符 choose.
choose :: Integer -> Integer -> Integer
choose r s = product [r-s+1 .. r] `div` product [2 .. s]
产生给定长度的填充序列的方法数就是这两个数的乘积，因为"what values to insert"和"where to insert values"的选择可以完全独立
paddedSeqSize :: Integer -> Integer -> Integer -> Integer
paddedSeqSize r s t = seqWORepSize s t * (r `choose` s)
现在我们差不多完成了。只需遍历所有可能的序列长度并添加 paddedSeqSize.
eSetSize :: Integer -> Integer -> Integer
eSetSize r t = sum $ map (\s -> paddedSeqSize r s t) [0..r]
我们可以在ghci中试试：
> :set +s
> map length $ [eSet 1 1, eSet 4 4, eSet 6 4, eSet 4 6]
[2,209,1045,1045]
(0.13 secs, 26,924,264 bytes)
> [eSetSize 1 1, eSetSize 4 4, eSetSize 6 4, eSetSize 4 6]
[2,209,1045,1045]
(0.01 secs, 120,272 bytes)
这种方式明显更快并且对内存更友好。事实上，我们可以查询并获得关于 eSet 的答案，我们永远无法逐个计算其大小，例如
> length . show $ eSetSize 1000 1000
2594
(0.26 secs, 909,746,448 bytes)
祝你好运，一次数到 10^2594。 =P
编辑
这个想法也可以适用于自己生成填充序列，而不是仅仅计算有多少。首先，我发现自己反复定义了一个方便的实用程序，用于挑选列表中的各个元素并报告剩余部分：
zippers :: [a] -> [([a], a, [a])]
zippers = go [] where
go ls [] = []
go ls (h:rs) = (ls, h, rs) : go (h:ls) rs
现在，无需替换的序列可以通过重复从剩余的元素中选择一个元素来完成。
seqWORep :: Int -> [a] -> [[a]]
seqWORep 0 _ = [[]]
seqWORep n xs = do
(ls, y, rs) <- zippers xs
ys <- seqWORep (n-1) (ls++rs)
return (y:ys)
一旦我们有了一个序列，我们就可以通过生成标记值的所有交错来将其填充到所需的大小，如下所示：
interleavings :: Int -> a -> [a] -> [[a]]
interleavings 0 _ xs = [xs]
interleavings n z [] = [replicate n z]
interleavings n z xs@(x:xt) = map (z:) (interleavings (n-1) z xs)
++ map (x:) (interleavings n z xt)
最后，顶层函数只委托给 seqWORep 和 interleavings。
eSet :: Int -> Int -> [[Int]]
eSet r t = do
s <- [0..r]
xs <- seqWORep s [1..t]
interleavings (r-s) 0 xs
在我的测试中，这个修改后的 eSet 在有和没有优化的情况下都有很好的平坦内存使用；不会生成任何需要稍后 filtered 的虚假元素，因此比您的原始提案更快；与依赖于欺骗 GHC 的答案相比，在我看来这是一个很自然的定义。一个不错的属性集合！