头部反转与尾部反转的空间复杂度对比

Question

在许多系统中，head.reverse 需要与列表大小成比例的空间，而 last 则只需要常量空间。是否有系统可以执行这样的转换? 对于 reverse.take n.reverse 也是如此吗?

编辑: 我想扩展我的问题: 我不追求具体的转换，我只是想达到任何优化的目的。

- false

---

@WillNess：的确，我假设列表没有其他消费者。看起来没有令人满意的方法可以解决这个空间泄漏问题。 - false

为什么，如果没有其他消费者，那就不会有泄漏了。 (?) - Will Ness

@WillNess：在计算过程中，空间需求为O（n），而使用last则为O（1）。 - false

也许我误解了你的意思（你指的是哪个计算？）；但即使计算 takeLast k xs 应该占用 O(1) 的空间（当然要打开优化 -O2）。它 的结果的使用者将决定下一部分的大小需求。例如，last (takeLast 5 xs) 总体上占用 O(1) 的空间。（再次说明，如果这是关于 xs 的程序中唯一的语句，即没有其他消费者持有其中的某些其他部分）。-- 澄清：takeLast 5 xs 不是一个计算；它是一个定义。只有 main 描述了整个计算。 - Will Ness

让我们在聊天中继续这个讨论：http://chat.stackoverflow.com/rooms/41055/discussion-between-will-ness-and-false - Will Ness

Answer 1

您可以将reverse . take n . reverse转换为将列表视为特别晦涩的惰性自然数：空列表为零，而conses为succ。对于以列表形式编码的惰性自然数，减法是drop:

type LazyNat a = [a]

lengthLazy :: [a] -> LazyNat a
lengthLazy = id

dropLazy :: LazyNat a -> [b] -> [b]
dropLazy [] xs = xs
dropLazy (_:n) (_:xs) = dropLazy n xs
dropLazy _ _ = []

-- like Prelude.subtract, this is flip (-)
subtractLazy :: Int -> LazyNat a -> LazyNat a
subtractLazy = drop

现在我们可以轻松地实现“获取最后n个元素”的函数：

takeLast n xs = dropLazy (subtractLazy n (lengthLazy xs)) xs

...你会很高兴知道，在任何给定时间只需要在内存中保存n个cons。特别地，takeLast 1（或者对于任何字面量N的takeLast N）可以在常量内存中运行。你可以通过比较在ghci中运行takeLast 5 [1..]和(reverse . take 5 . reverse) [1..]时发生的情况来验证这一点。

当然，我尝试在上面使用非常具有启示性的名称，但在实际实现中，您可能会内联所有上述无聊内容：

takeLast n xs = go xs (drop n xs) where
    go lastn  []    = lastn
    go (_:xs) (_:n) = go xs n
    go _      _     = []

- Daniel Wagner

Answer 2

如果我们比较 drop 和 last

>>> last [1..10^5]
100000
(0.01 secs, 10496736 bytes)
>>> last [1..10^6]
1000000
(0.05 secs, 81968856 bytes)
>>> last [1..10^7]
10000000
(0.32 secs, 802137928 bytes)


>>> drop (10^5-1) [1..10^5]
[100000]
(0.01 secs, 10483312 bytes)
>>> drop (10^6-1) [1..10^6]
[1000000]
(0.05 secs, 82525384 bytes)
>>> drop (10^7-1) [1..10^7]
[10000000]
(0.32 secs, 802142096 bytes)

我们在时间和空间上获得了类似的性能，我必须承认我有点作弊，因为这里我们不需要计算列表的长度。无论如何，我相信在空间上这不应该是一个问题。然后你的reverse . take n . reverse可以使用drop和length表达。

---

作为附注，我已经尝试了其他解决方法，结果很糟糕。

takeLastN = foldl' (.) id . flip replicate tail 

lastN = foldl' (.) last . flip replicate init

- zurgl

---

计算长度将有效地需要与长度成比例的空间，因为列表只能通过drop使用。对吧？ - false

当计算列表的长度时，不需要进行反转操作，只需累加结果（加一），因此在整个过程中只需要一个“插槽”内存，与反转相反，反转操作会随着遍历列表而不断增加内存量，我们构建了一个与原列表长度相同的新列表。 - zurgl

无论如何，如果您更普遍地谈论“系统”，我在某个地方读到过，对于列表数据类型的特殊编码，我们可以通过构造包含列表长度，然后当您请求列表长度时，答案以恒定的时间和空间返回。列表携带这些额外的信息。但我想这取决于依赖类型，我不确定我们是否可以在Haskell中这样做。 - zurgl

дҪҶжҳҜеҲ—иЎЁд»Һ[1..10^7]жү©еұ•еҲ°O(10^7)зҡ„жҹҗдёӘдёңиҘҝгҖӮ - false

我同意，这就是为什么我说“在太空中不应该是一个问题”，但是在时间上，肯定会有额外的开销 :/ - zurgl

我已经踩了。reverse 不好的原因是它会一次性将整个列表强制装入内存，而你的提议运行 length 然后再运行 drop 也会做同样的事情。 - Daniel Wagner

Answer 3

您可以为此编写一个简单的重定向规则。

http://www.haskell.org/haskellwiki/Playing_by_the_rules

融合规则也可能捕捉到它，这取决于反向编码的方式。

- Don Stewart

---

你建议声明 head.reverse = last。对吗？ - false