如何获取列表中最后n个元素

Question

如何获取列表中最后n个元素

listhaskell

22

为了获取一个列表 xs 的最后 n 个元素，我可以使用 reverse (take n (reverse xs))，但这并不是很好的代码（在返回任何东西之前它会将整个列表保留在内存中，并且结果与原始列表不共享）。

如何在Haskell中实现这个名为 lastR 的函数？

- Joachim Breitner

我从未尝试过Haskell，但了解OCaml并且有一行引起了我的注意：结果如何与原始列表共享？在Haskell中对象不是不可变的吗？（就像大多数函数式语言一样） - Boris Dalstein

2

@Boris 是的。但是当你执行像 drop 1 xs 这样的操作时，从列表中删除第一个元素。Haskell通常通过只更改指针以指向原始列表的第二个元素来优化此过程，而不是创建一个新的少1个元素的列表。 - Satvik

2

谢谢澄清。事实上，我可能已经累了；-) 实际上，正是因为它是不可变的，我猜你可以进行这种优化：共享地址仍然是安全的，并且保留了按值复制的语义，因为你知道对象不会改变。如果我错了，请纠正我，我已经好几年没玩这些东西了。 - Boris Dalstein

tailn n xs = drop (length xs - n) xs ---- 从列表的前面删除您不想要的内容，留下您想要的内容，即列表的剩余部分。 - fp_mora

一个好奇心：\n xs -> [x | [x] <- transpose [drop n xs, xs]]。与此同时：(\n xs -> foldr (\_ r (_:z) -> r z) id (drop n xs) xs)（与Davorak的foldl'解决方案相同）。 - Will Ness

7个回答

12

据我所知，您可以使用类似于

的东西。

lastN :: Int -> [a] -> [a]
lastN n xs = drop (length xs - n) xs

但是，任何内置列表的实现都无法比 O(列表长度-n) 更好地执行。

看起来你正在尝试使用列表来执行它不擅长高效执行的任务。使用Data.Sequence或其他允许在列表末尾高效执行操作的列表实现。

编辑：

Davorak的实现似乎是从内置列表中获得的最有效的实现。但请记住，除了单个函数的运行时间之外，还有其他复杂性，例如它是否与其他函数良好融合等。

Daniel 的解决方案使用内置函数，并且具有与 Davorak 相同的复杂度，我认为它更有可能与其他函数融合。

- Satvik

你能否评论一下Daniel的函数有什么特点使它更容易与其他函数融合？或者说有哪些提示可以让它更容易融合呢？ - Davorak

@Davorak 我不是融合方面的专家，但使用内置函数编写的函数更有可能被融合。我认为Daniel可以提供更多信息来评论这个问题。 - Satvik

谢谢，这也是我的印象，特别是使用递归运算符而不是显式递归，因为融合重写规则是基于这些运算符的。 - Davorak

我不明白为什么这不是答案，它很容易理解和实现，并且应该成为序言的一部分。 - windmaomao

融合在这里无济于事，因为列表被使用了两次。这个实现严格来说不太有效率。保持多少数据存活对于垃圾回收性能非常重要。当“Int”参数很小时，在计算期间会使列表中更多的内容保持活动状态。 - dfeuer

5

不确定它是否非常快，但它很容易：

lastR n xs = snd $ dropWhile (not . null . fst) $ zip (tails $ drop n xs) (tails xs)

- Daniel Fischer

1

这是Davorak第一个解决方案的简化版：

-- dropLength bs = drop (length bs)
dropLength :: [b] -> [a] -> [a]
dropLength [] as = as
dropLength _ [] = []
dropLength (_ : bs) (_ : as) = dropLength bs as

lastR :: Int -> [a] -> [a]
lastR n as = dropLength (drop n as) as

当n <= length as时，length (drop n as) = length as - n，因此dropLength (drop n as) as = drop (length (drop n as)) as = drop (length as - n) as，即as的最后n个元素。当n > length as时，dropLength (drop n as) as = dropLength [] as = as，这是唯一合理的答案。

如果想要使用fold，可以编写：

dropLength :: [b] -> [a] -> [a]
dropLength = foldr go id
  where
     go _b _r [] = []
     go _b r (_a : as) = r as

这不会对lastR产生任何影响，但在其他应用程序中，它可以帮助您实现一些列表融合。

- dfeuer

1

请注意，无论你做什么，都需要遍历整个列表。话虽如此，您可以通过先计算列表的长度，并且删除相应数量的元素，比使用reverse (take n (reverse xs))更好。

lastN :: Int -> [a] -> [a]
lastN n xs = let m = length xs in drop (m-n) xs

- Chris Taylor

这并不好，因为它保留内存的时间比必要的时间长。特别是，在计算超过n个元素后，它仍然保持着列表开头的位置。而双指针解决方案避免了这种情况。 - dfeuer

0

简单解决方案也不错。无论如何，算法都是O(n)。

takeLastN n = reverse . take n . reverse

时间比较：

> length $ lastN 3000000 (replicate 10000000 "H") -- Davorak's solution #1
3000000
(0.88 secs, 560,065,232 bytes)
> length $ lastN' 3000000 (replicate 10000000 "H") -- Davorak's solution #2
3000000
(1.82 secs, 840,065,096 bytes)
> length $ lastN'' 3000000 (replicate 10000000 "H") -- Chris Taylor's solution
3000000
(0.50 secs, 560,067,680 bytes)
> length $ takeLastN 3000000 (replicate 10000000 "H") -- Simple solution
3000000
(0.81 secs, 1,040,064,928 bytes)

正如Joachim Breitner在问题和评论中指出的那样，仍然存在内存问题。虽然这种解决方案的速度不比其他解决方案慢多少，但几乎需要两倍的内存。您可以在基准测试中看到这一点。

- Nolan

请注意，您会失去共享：现在您的内存中有两个（后缀的）脊柱副本，一个是原始列表的一部分，另一个是返回列表中的一个。 - Joachim Breitner

@JoachimBreitner 已经被编辑以避免提及此事。 - Nolan

1

当只有一部分列表被使用时，这也会分配整个反转列表。 - dfeuer

1

O(n) 到底是什么？正确的 take 2 $ lastN 10000000 [1..10000000] 是 _O(1)_，而你的则是 _O(n)_。这是一个很大的区别。 - Will Ness

@WillNess 在单向链表中没有办法以 O(1) 的时间复杂度到达链表末尾。你写的代码也是 O(n) 的。我提出的解决方案可能存在性能问题，但从算法复杂度的角度来看，它并不比其他方案更糟糕。 - Nolan

-1

takeLast :: Int -> [a] -> [a]
takeLast n xs 
 | n < 1 = []
 | otherwise = let s = splitAt n xs in bla (fst s) (snd s)
 where 
  bla xs [] = xs
  bla (x:xs) (y:ys) = bla (xs ++ [y]) ys

- leandromoh

在循环中出现 xs ++ [y] 的任何代码肯定不是 *O(n)*。 - Joachim Breitner

但是我不是已经遍历了这个列表一次吗？ - leandromoh

但是每一步的大小不是恒定的。 - Joachim Breitner

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Davorak · Accepted Answer

这应该具有仅迭代列表长度一次的属性。用于drop n的N和用于zipLeftover的n-1。

zipLeftover :: [a] -> [a] -> [a]
zipLeftover []     []     = []
zipLeftover xs     []     = xs
zipLeftover []     ys     = ys
zipLeftover (x:xs) (y:ys) = zipLeftover xs ys

lastN :: Int -> [a] -> [a]
lastN n xs = zipLeftover (drop n xs) xs

以下是另一种较短且更好的替代方案，正如Satvik所指出的那样，使用递归运算符比显式递归通常更好。

import Data.Foldable

takeLeftover :: [a] -> t -> [a]
takeLeftover [] _ = []
takeLeftover (x:xss) _ = xss

lastN' :: Int -> [a] -> [a]
lastN' n xs = foldl' takeLeftover xs (drop n xs)

此外，请注意Will Ness在下面的评论中提到，takeLeftover只是：

takeLeftover == const . drop 1

这使事情变得更加整洁：

lastN' :: Int -> [a] -> [a]
lastN' n xs = foldl' (const . drop 1) xs (drop n xs)
-- or
-- lastN' n xs = foldl' (const . drop 1) <*> drop n