4

リストを効率的に表現するにはどうすればよい[0..] \\ [t+0*p, t+1*p ..]ですか?

私は定義しました：

Prelude> let factors p t = [t+0*p, t+1*p ..]

と の違いである無限リストを効率的に表現したいのですが、fromを使用すると、[0..]中規模のリストでも大量のメモリが必要になります。factors p t\\Data.List

Prelude Data.List> [0..10000] \\ (factors 5 0)
<interactive>: out of memory

t+0*pとの間の値を次のように表すことができることを知っていますt+1*p。

Prelude> let innerList p1 p2 t = [t+p1+1, t+p1+2 .. t+p2-1]
Prelude> innerList 0 5 0
[1,2,3,4]

ただし、innerList間隔を増やして繰り返し計算と連結を行うのは、扱いにくいようです。

[0..] \\ (factors p t)計算せずにrem、またはmod要素ごとに効率的に表現できますか?

4

5 に答える 5

7

無限リスト については[0..] \\ [t,t+p..]、

yourlist t p = [0..t-1] ++ [i | m <- [0,p..], i <- [t+m+1..t+m+p-1]]

もちろん、このアプローチは、次のような他の要因を削除したい場合、まったく拡張できません。

[0..] \\ [t,t+p..] \\ [s,s+q..] \\ ...

その場合minus、Daniel Fischer's answer に記載されているように、それらを順番に削除する必要があります。ここには魔法の弾丸はありません。

しかし、上記がなるもありますunion

[0..] \\ ( [t,t+p..] `union` [s,s+q..] `union` ... )

利点は、ユニオンをツリーに配置し、アルゴリズムを改善できることです。

于 2013-08-19T19:00:54.327 に答える
3

(\\)そのためには使用できません。

(\\)                    :: (Eq a) => [a] -> [a] -> [a]
(\\)                    =  foldl (flip delete)

削除したい要素のリストは無限であり、折り畳まれるリストが無限である場合、左の折り畳みは決して終了しません。

自分で書くよりも既に書かれているものを使いたい場合は、data-ordlistパッケージのマイナスを使用できます。

パフォーマンスは十分なはずです。

さもないと、

minus :: Ord a => [a] -> [a] -> [a]
minus xxs@(x:xs) yys@(y:ys)
    | x < y     = x : minus xs yys
    | x == y    = minus xs ys
    | otherwise = minus xss ys
minus xs _      = xs
于 2013-08-19T19:01:49.870 に答える
1

昇順のリストがあるため、それらを単純に遅延マージできます。

 nums = [1..]
 nogos = factors p t
 result = merge nums (dropWhile (<head nums) nogos) where
      merge (a:as) (b:bs)
        | a < b = a : merge as (b:bs)
        | a == b = merge as bs
        | otherwise = error "should not happen"

これを一般的な方法で記述して、2 つの無限リストの差を構築する関数を作成します。ただし、それらが昇順であることのみを条件として、演習として残します。最終的に、次のことが可能になるはずです

 [1..] `infiniteDifference` primes `infiniteDifference` squares

このために、左結合演算子にします。

于 2013-08-20T08:37:42.503 に答える
1

効率が必要な場合、ソリューションでリスト内包表記を使用する必要があるのはなぜですか?

なぜこのようなものではないのですか？

 gen' n i p | i == p = gen' (n + p) 1 p
 gen' n i p = (n+i) : gen' n (i+1) p
 gen = gen' 0 1

そして、する

 gen 5
于 2013-08-19T18:47:00.280 に答える
1

remを使用して、述語でリスト内包表記を使用できます。

>>> let t = 0
>>> let p = 5
>>> take 40 $ [ x | x <- [1..], x `rem` p /= t ]
[1,2,3,4,6,7,8,9,11,12,13,14,16,17,18,19,21,22,23,24,26,27,28,29,31,32,33,34,36,37,38,39,41,42,43,44,46,47,48,49]
于 2013-08-19T18:22:52.473 に答える