haskell - 获取列表中间元素的最有效方法是什么？

Question

我想得到一个列表，但最后一个和第一个元素。最有效的方法是什么？

middle = init . tail

或者：

middle = tail . init

在删除 n-first 元素和 n-last 元素的情况下？

Answer 1

无论哪种方式都没有关系（很多）。请注意，这tail是 O(1)，init而是 O(n)。如果您选择第tail一个，则init必须检查 (n-1) 个构造函数，总共检查了 n 个构造函数。

如果取第init一个，则init检查 n 个构造函数并tail检查 1，总共检查 n+1 个构造函数。

因此，这样做的效率会稍微高一点init . tail，但效率不会高到你应该担心的程度。

这同样适用于从列表的前端和末尾删除前 k 个元素，但它可能会产生更大的不同。如果您首先删除初始元素，那么在删除最终元素时不必检查它们，并且您可以节省一些时间，所以您应该这样做

dropLast k . drop k

它检查 n 个构造函数，而不是

drop k . dropLast k

它检查 n+k 构造函数。

Answer 2

两者实际上是相同的。您正试图在错误的位置进行优化。如果您的代码确实需要进行这种优化，那么您可能不需要列表，请使用 Data.Sequence 或 Data.Vector 之类的东西。