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引数は (null ではない) list の長さの範囲内にあることがわかっているため、1..n関数でエラーが発生することはありません。n(x:xs)

しかし、ここではパフォーマンスが低下しました。私の最初の推測は、リストを別の構造に変更する必要があるということです。しかし、さまざまな構造の選択とコードのテストを開始する前に (これには多くの時間がかかります)、ここで第三者の意見を求めたいと思いました。また、私はそれを最善の方法で行っていないと確信しています。どんなポインタでも大歓迎です！

aタイプが のインスタンスでない場合があることに注意してくださいEq。

解決

Data.SequenceモジュールSequenceの s を使用するコードを適応させました。結果は次のとおりです。

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 に答える