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

Question

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

middle = init . tail

或者:

middle = tail . init

如果删除前 n 个元素和后 n 个元素呢？

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 个构造函数。