9

我今天有一个性能问题。

我正在制作一个（Haskell）程序，并且在进行分析时，我看到大部分时间都花在了您可以在下面找到的功能上。它的目的是获取列表的第 n 个元素并返回除了元素本身之外没有它的列表。我目前的（慢）定义如下：

breakOn :: Int -> [a] -> (a,[a])
breakOn 1 (x:xs) = (x,xs)
breakOn n (x:xs) = (y,x:ys)
 where
  (y,ys) = breakOn (n-1) xs

已知Int参数在 (never null) list 的长度范围1..n内，因此该函数永远不会出现错误。n(x:xs)

但是，我在这里的表现很差。我的第一个猜测是我应该为另一个结构更改列表。但是，在开始选择不同的结构和测试代码（这将花费我很多时间）之前，我想在这里征求第三人的意见。另外，我很确定我没有以最好的方式做到这一点。欢迎任何指点！

请注意，该类型a可能不是Eq.

解决方案

我改编了我的代码 tu useSequence来自Data.Sequence模块。结果在这里：

import qualified Data.Sequence as S

breakOn :: Int -> Seq a -> (a,Seq a)
breakOn n xs = (S.index zs 0, ys <> (S.drop 1 zs))
 where
  (ys,zs) = S.splitAt (n-1) xs

但是，我仍然接受进一步的改进建议！

4

2 回答 2

9

是的，这是低效的。您可以通过使用splitAt（在递归位期间将数字拆箱）做得更好，通过使用具有有效拆分的数据结构（例如fingertree ）做得更好，最好通过按摩上下文以避免需要此操作。如果您发布更多上下文，则可以提供更有针对性的建议。

于 2013-01-03T15:32:06.963 回答
4

Prelude 函数通常非常有效。您可以使用 重写您的函数splitAt，如下所示：

breakOn :: Int -> [a] -> (a,[a])
breakOn n xs = (z,ys++zs)
 where
  (ys,z:zs) = splitAt (n-1) xs
于 2013-01-03T15:39:21.593 回答