在索引处打破列表

Question

我今天有一个表现问题.

我正在编写一个(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参数是已知的范围内1..n,其中n是(不能为null)列表的长度(x:xs),因此函数从未产生误差.

但是,我在这里表现不佳.我的第一个猜测是我应该更改另一个结构的列表.但是,在开始选择不同的结构和测试代码(这将花费我很多时间)之前,我想在这里询问第三人的意见.另外,我很确定我没有以最好的方式做到这一点.欢迎任何指示!

请注意,该类型a可能不是一个实例Eq.

解

我Sequence从Data.Sequence模块调整了我的代码tu use .结果如下:

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

但是,我仍然接受进一步的改进建议!

Answer 1

是的,这是低效的.您可以通过使用splitAt(在递归位期间将数字解除容器)来做得更好,通过使用具有高效拆分的数据结构(例如指尖)更好,并且最好通过按摩上下文以避免需要此操作.如果您发布更多上下文,可能会提供更有针对性的建议.