rightTrianglesOriginal = [ (a,b,c) | c <- [1..10], b <- [1..10], a <- [1..10], a^2 + b^2 == c^2, a+b+c == 24]
場合によります。この場合、述語の順序を変更しても実質的な変更はないため、違いがあったとしてもごくわずかです。a^2 + b^2 == c^2は よりもチェックに少しコストがかかりa + b + c == 24、両方のテストで多くの値が除外されるため、2 つのテストを交換することでわずかなスピードアップが期待できます。
rightTrianglesSwapped = [ (a,b,c) | c <- [1..10], b <- [1..10], a <- [1..10], a+b+c == 24, a^2 + b^2 == c^2]
しかし、計算全体が非常に小さいため、確実に測定することは非常に困難です。一般に、テストとジェネレーターを並べ替えると大きな違いが得られます。特に、テストとジェネレーターをインターリーブしてデッドエンドを短縮すると、大きな影響が生じる可能性があります。ここで、とジェネレーターb < cの間にテストをショートカットに追加できます。もちろん、ジェネレーターをに変更すると、さらに効率的になります。bab <- [1 .. c-1]
- 述語 (他の述語によって暗示される) を追加すると、パフォーマンスに影響しますか? (例:
a > b, c > a, c > b?)?
はい。ただし、述語の評価に異常にコストがかかる場合を除き、通常はほとんどありません。上記では、述語が成り立つ場合、暗黙の 3 番目の述語を不必要に評価することになります。ここで、述語は標準の数値型に対して計算するのが安価であり、あまり頻繁に評価されないため (ほとんどの候補トリプルは早期に失敗します)、その影響はほとんど測定できません。しかし、これは追加の作業です。コンパイラはそれを削除するほど賢くありません。そのため、追加の時間がかかります。
a > b述語 (1)と (2)に基づいてタプルのリストを作成し、c > aさらに a^2 + b^2 = c^2 を適用すると、全体のパフォーマンスが向上しますか?
場合によります。述語をショートカットできる場所に置くと、パフォーマンスが向上します。これらの述語では、ジェネレーターの並べ替えが必要になります ( のa前bに取得するため、 をショートカットできますc > a)。比較は よりも計算コストが少し低いa^2 + b^2 == c^2ため、テストの全体数が増加しても (後者の条件では前者よりも多くのトリプルが除外されます)、最初に安価なテストを実行することでパフォーマンスを向上させることができます (ただし、最も識別力の高いテストを実行します)。最初にテストすることもより良い戦略になる可能性があります。たとえそれらがより高価であっても、コストと電力の関係によって異なります）。
- または などのパラメーターの位置を変更すると、パフォーマンスに影響があります
(a,b,c)か(c, b, a)?
基本的に、それは測定可能な影響を与えることはできません。
- このような大量の順列と組み合わせが必要な場合、実際のアプリケーションで推奨される戦略は何ですか?パフォーマンスなどを向上させるために、次の使用のために事前に計算された回答を(可能な限り)保存する必要がありますか?
場合によります。計算が複雑で結果が小さい場合は、結果を保存して再利用することをお勧めします。計算が安価で結果が大きい場合は、再計算することをお勧めします。この場合、ピタゴラス数の数は少なく、計算はそれほど安価ではないため、再利用のために保存することはおそらく有益です。
rightTriangles10 = [ (a,b,c) | c <- [1..10], b <- [1..10], a <- [1..10], a^2 + b^2 == c^2, a > b , c > a]
ほぼ瞬時に結果が得られます。
rightTriangles100 = [ (a,b,c) | c <- [1..100], b <- [1..100], a <- [1..100], a^2 + b^2 == c^2, a > b , c > a]
数分で結果が得られます。
rightTriangles1000 = [ (a,b,c) | c <- [1..1000], b <- [1..1000], a <- [1..1000], a^2 + b^2 == c^2, a > b , c > a]
まあ、チェックするトリプルの数は制限内で 3 乗なので、制限を 10 倍にすると、チェックするトリプルの数が 1000 倍になります。実行時間の係数はほぼ同じです。メモリ要件が大きいため、わずかに大きくなります。したがって、最適化されたコードはもちろん、コンパイルされていないコードでも、
ghci> [ (a,b,c) | c <- [1..100], b <- [1..100], a <- [1..100], a^2 + b^2 == c^2, a > b , c > a]
[(4,3,5),(8,6,10),(12,5,13),(12,9,15),(15,8,17),(16,12,20),(24,7,25),(20,15,25),(24,10,26)
,(21,20,29),(24,18,30),(30,16,34),(28,21,35),(35,12,37),(36,15,39),(32,24,40),(40,9,41)
,(36,27,45),(48,14,50),(40,30,50),(45,24,51),(48,20,52),(45,28,53),(44,33,55),(42,40,58)
,(48,36,60),(60,11,61),(63,16,65),(60,25,65),(56,33,65),(52,39,65),(60,32,68),(56,42,70)
,(55,48,73),(70,24,74),(72,21,75),(60,45,75),(72,30,78),(64,48,80),(80,18,82),(84,13,85)
,(77,36,85),(75,40,85),(68,51,85),(63,60,87),(80,39,89),(72,54,90),(84,35,91),(76,57,95)
,(72,65,97),(96,28,100),(80,60,100)]
(2.64 secs, 2012018624 bytes)
制限 1000 の予想時間は約 45 分です。データにいくつかの制約を使用すると、はるかに高速に実行できます。
ghci> length [(a,b,c) | c <- [2 .. 1000], b <- [1 .. c-1], a <- [c-b+1 .. b], a*a + b*b == c*c]
881
(87.28 secs, 26144152480 bytes)