Cau*_*ity 8 haskell list reduction on-the-fly
假设我有一个f接受一些输入并产生数字的函数.在该函数内f,根据输入创建列表,然后减少(例如使用foldl' g)以产生最终输出数.因为毕竟要减少中间列表,是否可以应用reduce函数g 而不表示中间列表.这里的目标是限制用于存储(或表达,如果'存储'不太准确的单词)列表的存储器.
为了说明这个,这个函数foldPairProduct占用O(N1 * N2)了中间列表的空间(由于表达和惰性评估,消耗的空间可能更复杂,但我认为它是成比例的或更糟).以下N1, N2是两个输入列表的大小.
foldPairProduct :: (Num a, Ord a) => (a -> a -> a) -> [a] -> [a] -> a
foldPairProduct f xs ys = foldl1 f [ x*y | x <- xs, y <- ys]
逻辑的另一种实现是foldPairProduct',它占用O(2 * 2)空间.
foldPairProduct' :: Num a => (Maybe a -> Maybe a -> Maybe a) -> [a] -> [a] -> Maybe a
foldPairProduct' _ _ [] = Nothing
foldPairProduct' _ [] _ = Nothing
foldPairProduct' f (x:xs) (y:ys) =
foldl1 f [Just $ x*y, foldPairProduct' f [x] ys, foldPairProduct' f xs [y],
foldPairProduct' f xs ys]
除了它接受多个列表作为输入之外,foldCrossProduct其实现类似的情况更加恶化foldPairProduct.对于中间列表O(N1 * N2 * ...* Nk),它的空间复杂性(仍然是命令式语言的意义)是,k其长度是[[a]].
foldCrossProduct :: Num a => (a -> a -> a) -> [[a]] -> a
foldCrossProduct f xss = foldl1 f (crossProduct xss)
crossProduct :: Num a => [[a]] -> [a]
crossProduct [] = []
crossProduct (xs:[]) = xs
crossProduct (xs:xss) = [x * y | x <- xs, y <- crossProduct xss]
如果我们遵循实现的想法foldPairProduct',那么空间复杂性将会k^2更加节省空间.我的问题是:
我foldPairProduct'为一对列表实现了.但是,似乎为任意数量的列表实现它并不简单.
我并不是要将Haskell与命令式语言进行比较,但是是否存在使用常量空间的实现(或者在另一个词中,不表示上述长度的中间列表)？也许莫纳德会帮助我,但我很新.
编译器真的有它的魔力吗？也就是说,它注意到列表是中间的并且要减少,并且确实找到了一种空间有效地评估它的方法.毕竟,这就是我认为惰性评估和编译器优化的设计目标.
欢迎任何评论.谢谢.
更新1
性能测试确认了对"空间复杂度"的分析,foldPairProduct并foldCrossProduct根据输入大小的变化N1, N2, N3,以及观察GC复制的字节数.
性能测试证明了foldPairProduct'令人惊讶地显示N1 * N2甚至更糟的空间使用的分析.这可能是由于递归调用被低效评估.结果如下(ghc设置与Yuras相同).
更新2
我从评论和答案中学到了更新了一些进一步的实验.因为foldPairProduct,使用的总内存与Daniel Fischer所解释的空间复杂度一致.
对于遵循丹尼尔的建议,交换了foldCrossProduct,虽然丹尼尔的复杂度分析道理给我,结果不显示的线性内存使用情况.x <- xs和y <- crossproduct ys,它确实实现了线性空间复杂性.
对于foldCrossProduct (max) [[1..100],[1..n], [1..1000]]n = 100,1000,10000,100000,使用的存储器是2,2,3,14MB.
foldPairProduct [1..n] [1..10000]
n = 100
120,883,320 bytes allocated in the heap
56,867,728 bytes copied during GC
428,384 bytes maximum residency (50 sample(s))
98,664 bytes maximum slop
3 MB total memory in use (0 MB lost due to fragmentation)
n = 1000
1,200,999,280 bytes allocated in the heap
569,837,360 bytes copied during GC
428,384 bytes maximum residency (500 sample(s))
99,744 bytes maximum slop
3 MB total memory in use (0 MB lost due to fragmentation)
n = 10000
12,002,152,040 bytes allocated in the heap
5,699,468,024 bytes copied during GC
428,384 bytes maximum residency (5000 sample(s))
99,928 bytes maximum slop
3 MB total memory in use (0 MB lost due to fragmentation)
n = 100000
120,013,672,800 bytes allocated in the heap
56,997,625,608 bytes copied during GC
428,384 bytes maximum residency (50000 sample(s))
99,984 bytes maximum slop
3 MB total memory in use (0 MB lost due to fragmentation)
foldPairProduct [1..10000] [1..n]
n = 100
121,438,536 bytes allocated in the heap
55,920 bytes copied during GC
32,408 bytes maximum residency (1 sample(s))
19,856 bytes maximum slop
1 MB total memory in use (0 MB lost due to fragmentation)
n = 1000
1,201,511,296 bytes allocated in the heap
491,864 bytes copied during GC
68,392 bytes maximum residency (1 sample(s))
20,696 bytes maximum slop
1 MB total memory in use (0 MB lost due to fragmentation)
n = 10000
12,002,232,056 bytes allocated in the heap
5,712,004,584 bytes copied during GC
428,408 bytes maximum residency (5000 sample(s))
98,688 bytes maximum slop
3 MB total memory in use (0 MB lost due to fragmentation)
n = 100000
120,009,432,816 bytes allocated in the heap
81,694,557,064 bytes copied during GC
4,028,408 bytes maximum residency (10002 sample(s))
769,720 bytes maximum slop
14 MB total memory in use (0 MB lost due to fragmentation)
foldPairProduct [1..n] [1..n]
n = 100
1,284,024 bytes allocated in the heap
15,440 bytes copied during GC
32,336 bytes maximum residency (1 sample(s))
19,920 bytes maximum slop
1 MB total memory in use (0 MB lost due to fragmentation)
n = 1000
120,207,224 bytes allocated in the heap
114,848 bytes copied during GC
68,336 bytes maximum residency (1 sample(s))
24,832 bytes maximum slop
1 MB total memory in use (0 MB lost due to fragmentation)
n = 10000
12,001,432,024 bytes allocated in the heap
5,708,472,592 bytes copied during GC
428,336 bytes maximum residency (5000 sample(s))
99,960 bytes maximum slop
3 MB total memory in use (0 MB lost due to fragmentation)
n = 100000
1,200,013,672,824 bytes allocated in the heap
816,574,713,664 bytes copied during GC
4,028,336 bytes maximum residency (100002 sample(s))
770,264 bytes maximum slop
14 MB total memory in use (0 MB lost due to fragmentation)
foldCrossProduct(max)[[1..n],[1..100],[1..1000]]
n = 100
105,131,320 bytes allocated in the heap
38,697,432 bytes copied during GC
427,832 bytes maximum residency (34 sample(s))
209,312 bytes maximum slop
3 MB total memory in use (0 MB lost due to fragmentation)
n = 1000
1,041,254,480 bytes allocated in the heap
374,148,224 bytes copied during GC
427,832 bytes maximum residency (334 sample(s))
211,936 bytes maximum slop
3 MB total memory in use (0 MB lost due to fragmentation)
n = 10000
10,402,479,240 bytes allocated in the heap
3,728,429,728 bytes copied during GC
427,832 bytes maximum residency (3334 sample(s))
215,936 bytes maximum slop
3 MB total memory in use (0 MB lost due to fragmentation)
foldCrossProduct(max)[[1..100],[1..n],[1..1000]]
n = 100
105,131,344 bytes allocated in the heap
38,686,648 bytes copied during GC
431,408 bytes maximum residency (34 sample(s))
205,456 bytes maximum slop
3 MB total memory in use (0 MB lost due to fragmentation)
n = 1000
1,050,614,504 bytes allocated in the heap
412,084,688 bytes copied during GC
4,031,456 bytes maximum residency (53 sample(s))
1,403,976 bytes maximum slop
15 MB total memory in use (0 MB lost due to fragmentation)
n = 10000
quit after over 1362 MB total memory in use (0 MB lost due to fragmentation)
foldPairProduct'[1..n] [1..n]
n = 100
4,351,176 bytes allocated in the heap
59,432 bytes copied during GC
74,296 bytes maximum residency (1 sample(s))
21,320 bytes maximum slop
1 MB total memory in use (0 MB lost due to fragmentation)
n = 1000
527,009,960 bytes allocated in the heap
45,827,176 bytes copied during GC
211,680 bytes maximum residency (1 sample(s))
25,760 bytes maximum slop
2 MB total memory in use (0 MB lost due to fragmentation)
foldPairProduct :: (Num a, Ord a) => (a -> a -> a) -> [a] -> [a] -> a
foldPairProduct f xs ys = foldl1 f [ x*y | x <- xs, y <- ys]
可以成为一个记忆力好的公民。第二个参数ys被重复使用，因此在计算过程中必须完全位于内存中，但中间列表是在消耗时延迟生成的，因此仅贡献恒定量的内存，从而给出整体O(length ys)空间复杂度。当然，必须有length xs * length ys列表单元格生成和消耗，因此总体分配是O(length xs * length ys)[假设每个a值使用有界空间]。通过提供更大的分配区域，可以大大减少 GC 期间复制的字节数（以及 GC 所需的时间），其中+RTS -A1M，该数字从
3,717,333,376 bytes copied during GC
默认设置为
20,445,728 bytes copied during GC
GC time 4.88s以及从到GC time 0.07s的时间xs == ys = [1 .. 10000] :: [Int]和f = (+)。
但这取决于严格性分析器的工作 - 如果它所使用的类型是例如并且Int在编译期间已知，并且已知组合函数是严格的，那么它就可以很好地工作。如果代码不是专门的，或者如果组合函数不知道是严格的，则折叠将产生很大的O(length xs * length ys)尺寸。通过使用更严格的foldl1'.
foldPairProduct' :: Num a => (Maybe a -> Maybe a -> Maybe a) -> [a] -> [a] -> Maybe a
foldPairProduct' _ _ [] = Nothing
foldPairProduct' _ [] _ = Nothing
foldPairProduct' f (x:xs) (y:ys) =
foldl1 f [Just $ x*y, foldPairProduct' f [x] ys, foldPairProduct' f xs [y],
foldPairProduct' f xs ys]
直接遇到了严格性不足的问题，Just编译器无法将构造函数包装的值设置为严格的，因为整体结果可能不需要它，因此折叠通常会在-O(length xs * length ys)下产生大小thunkJust当然，对于某些人来说f，比如const，它会表现得很好。如果使用所有值，为了使其成为良好的记忆公民，您必须使用足够严格的组合函数，同时强制结果中的f值（如果它是 a ）；使用也有帮助。这样，它就可以具有空间复杂度（列表和被多次使用，因此被重用）。JustJustfoldl1'O(length ys + length xs)xsys
foldCrossProduct :: Num a => (a -> a -> a) -> [[a]] -> a
foldCrossProduct f xss = foldl1 f (crossProduct xss)
crossProduct :: Num a => [[a]] -> [a]
crossProduct [] = []
crossProduct (xs:[]) = xs
crossProduct (xs:xss) = [x * y | x <- xs, y <- crossProduct xss]
尽管 GHC 几乎没有执行 CSE（公共子表达式消除），但列表crossProduct xss将（可能）在不同的 s 之间共享x，从而产生O(N2*...*Nk)空间复杂度。如果列表中元素的顺序不重要，则重新排序为
crossProduct (xs:xss) = [x * y | y <- crossProduct xss, x <- xs]
有帮助。然后crossProduct xss不需要立即存储在内存中，因此可以增量地生成和消耗，只xs需要记住它，因为它被多次使用。对于递归调用，必须共享剩余列表中的第一个，因此这会产生整体O(N1+...+Nk-1)空间复杂度。