さて、これは私が思っていたよりも簡単でした。これにより、自宅の遅いPCで0.05秒で1000回のハミングが実行されます。今日の午後の仕事と600未満のより速いPC時間はゼロ秒として出てきました。
これはハミングスからハミングスを取ります。これは、Excelで最速で実行することに基づいています。
250000以降、。で間違った番号を取得していましたInt。数値は非常に速く大きくなるため、制限Integerされているため、必ず使用する必要があります。Int
mkHamm :: [Integer] -> [Integer] -> [Integer] -> [Integer]
-> Int -> (Integer, [Int])
mkHamm ml (x:xs) (y:ys) (z:zs) n =
if n <= 1
then (last ml, map length [(x:xs), (y:ys), (z:zs)])
else mkHamm (ml++[m]) as bs cs (n-1)
where
m = minimum [x,y,z]
as = if x == m then xs ++ [m*2] else (x:xs) ++ [m*2]
bs = if y == m then ys ++ [m*3] else (y:ys) ++ [m*3]
cs = if z == m then zs ++ [m*5] else (z:zs) ++ [m*5]
テスト、
> mkHamm [1] [2] [3] [5] 5000
(50837316566580,[306,479,692]) -- (0.41 secs)
> mkHamm [1] [2] [3] [5] 10000
(288325195312500000,[488,767,1109]) -- (1.79 secs)
> logBase 2 (1.79/0.41) -- log of times ratio =
2.1262637726461726 -- empirical order of growth
> map (logBase 2) [488/306, 767/479, 1109/692] :: [Float]
[0.6733495, 0.6792009, 0.68041545] -- leftovers sizes ratios
これは、このコードの実行時の経験的な成長順序が2次式を上回っていることを意味します（~n^2.13GHCiプロンプトで測定、解釈）。
また、シーケンスの3つのぶら下がっている過剰生成されたセグメントのサイズはそれぞれ~n^0.67です~n^(2/3)。
さらに、このコードは遅延しません。結果のシーケンスの最初の要素にアクセスできるのは、最後の要素が計算された後のみです。
問題の最先端のコードは線形であり、関心のあるポイントを超えて正確に0個の要素を過剰生成し、適切に怠惰です。つまり、すぐに数値の生成を開始します。
したがって、このポスターによる以前の回答よりも大幅に改善されていますが、上位2つの回答に表示されている改善は言うまでもなく、元の回答よりも大幅に悪化しています。
2018年12月31日
最高の人だけが教育します。@Will Nessは、GoalKicker.comの「Haskellfor Professionals」で、19の章を執筆または共同執筆しています。無料の本は宝物です。
私はこのようにこれを行う関数のアイデアを持ち歩いていました。いくつかの現代語のように複雑で複雑な論理になると思ったので、私は心配していました。私は書き始めることに決めました、そしてHaskellが悪い考えさえ実現するのがいかに簡単であるかに驚いていました。
一意のリストを生成するのに問題はありませんでした。私の問題は、私が生成するリストがうまく終わらないことです。私が対角化を使用するときでさえ、それらは残差値を残し、せいぜいそれらの使用を信頼できないものにします。
これは、最後に何も残っていない、作り直された3と5のリストです。非国家化は、とにかく含まれることのない重複を排除しないように、残差値を減らすことです。
g3s5s n=[t*b|(a,b)<-[ (((d+n)-(d*2)), 5^d) | d <- [0..n]],
t <-[ 3^e | e <- [0..a+8]],
(t*b)<-(3^(n+6))+a]
ham2 n = take n $ ham2' (drop 1.sort.g3s5s $ 48) [1]
ham2' o@(f:fo) e@(h:hx) = if h == min h f
then h:ham2' o (hx ++ [h*2])
else f:ham2' fo ( e ++ [f*2])
リストは、すべてのsにそれぞれを掛けてtwos生成できますが、IDが含まれている場合は、合計でハミングになります。2^e3s5s2^0
2019年3月25日
さて、ついに。私はこれを少し前に知っていましたが、最後に過剰な値がないと実装できませんでした。問題は、デカルト積の結果である超過分を生成しない方法でした。Excelをよく使用しますが、デカルト積ワークシートから除外する値のパターンを確認できませんでした。じゃあ、エウレカ！関数は、各リードファクターのリストを生成します。各リストの値を制限する値は、最初のリストの終点です。これが行われると、すべてのハミングが過剰に生成されます。
ハミングの2つの関数。1つ目は、新しい3と5のリストで、2で倍数を作成するために使用されます。倍数はハミングです。
h35r x = h3s5s x (5^x)
h3s5s x c = [t| n<-[3^e|e<-[0..x]],
m<-[5^e|e<-[0..x]],
t<-[n*m],
t <= c ]
a2r n = sort $ a2s n (2^n)
a2s n c = [h| b<-h35r n,
a<-[2^e| e<-[0..n]],
h<-[a*b],
h <= c ]
last $ a2r 50
1125899906842624
（0.16秒、321,326,648バイト）
2 ^ 50
1125899906842624
（0.00秒、95,424バイト
これは、メモリ使用量の少ない実装で、よりクリーンで高速な代替手段です。
gnf n f = scanl (*) 1 $ replicate f n
mk35 n = (\c-> [m| t<- gnf 3 n, f<- gnf 5 n, m<- [t*f], m<= c]) (2^(n+1))
mkHams n = (\c-> sort [m| t<- mk35 n, f<- gnf 2 (n+1), m<- [t*f], m<= c]) (2^(n+1))
last $ mkHams 50
2251799813685248
（0.03秒、12,869,000バイト）
2^51
2251799813685248
2019年5月6日
さて、私は別の方法で制限しようとしましたが、常に最も単純なものに戻ります。私はメモリ使用量を最小限にすることを選択しています。これも最速のようです。
mapまた、暗黙のパラメーターで使用することを選択しました。
mergeAllまた、 fromの方がorと。Data.List.Orderedよりも高速であることがわかりました。sortsortconcat
また、サブリストが作成されるのも気に入っているので、データをはるかに簡単に分析できます。
次に、@ Will Nessが原因で、よりクリーンなコードを作成するiterate代わりに切り替えました。scanlまた、@ Will Nessのために、最後の2のリストの使用をやめ、すべての長さを決定する1つの値に切り替えました。
再帰的に定義されたリストの方が効率的だと思います。前の数値に係数を掛けたものです。
関数を2つに分割するだけでは違いがないため、3と5の倍数は次のようになります。
m35 lim = mergeAll $
map (takeWhile (<=lim).iterate (*3)) $
takeWhile (<=lim).iterate (*5) $ 1
そして、それぞれ2に3と5の積を掛けたもの
ham n = mergeAll $
map (takeWhile (<=lim).iterate (*2)) $ m35 lim
where lim= 2^n
関数を編集した後、私はそれを実行しました
last $ ham 50
1125899906842624
（0.00秒、7,029,728バイト）
それから
last $ ham 100
1267650600228229401496703205376
（0.03秒、64,395,928バイト）
おそらく使用する方が良いです10^nが、比較のためにもう一度使用しました2^n
2019年5月11日
私は無限で再帰的なリストをとても好むので、これらを無限にすることに少し夢中になりました。
私は@DanielWagnerにとても感銘を受け、インスピレーションを得ました。彼Data.Universe.Helpersは使い始めましたが+*+、+++その後、自分の無限のリストを追加しました。私はmergeAll自分のリストを機能させる必要がありましたが、その後、無限の3と5の倍数がまさにそれらが本来あるべきものであることに気づきました。それで、2を追加してmergeAllすべてをdして、それらが出てきました。以前、私は愚かなmergeAllことに無限のリストを処理しないと思っていましたが、それは最も素晴らしいことです。
Haskellでリストが無限大の場合、Haskellは必要なものだけを計算します。つまり、怠惰です。補助は、それが最初から計算するということです。
さて、Haskellは必要なものの限界まで倍数になるので、関数に限界は必要ありません。つまり、それ以上は必要ありませんtakeWhile。スピードアップは信じられないほどで、メモリも低下しました、
以下は、3GBのRAMを搭載した私の遅い自宅のPCです。
tia = mergeAll.map (iterate (*2)) $
mergeAll.map (iterate (*3)) $ iterate (*5) 1
最後の$は10000ティアを取る
288325195312500000
（0.02秒、5,861,656バイト）
6.5.2019
方法を学びましたghc -02ので、以下は50000ハミングから2.38E+30までです。そして、これは私のコードがゴミであることのさらなる証拠です。
INIT time 0.000s ( 0.000s elapsed)
MUT time 0.000s ( 0.916s elapsed)
GC time 0.047s ( 0.041s elapsed)
EXIT time 0.000s ( 0.005s elapsed)
Total time 0.047s ( 0.962s elapsed)
Alloc rate 0 bytes per MUT second
Productivity 0.0% of total user, 95.8% of total elapsed
6.13.2019
@WillNessrawks。彼は上記のクリーンでエレガントな改訂版を提供し、tiaそれはで5倍速いことが証明されましたGHCi。私がghc -O2 +RTS -s彼に反対したとき、私のものは数倍速かった。妥協が必要でした。
それで、私はR. Bird's Thinking Functionally with Haskellで遭遇した融合について読み始め、ほとんどすぐにこれを試しました。
mai n = mergeAll.map (iterate (*n))
mai 2 $ mai 3 $ iterate (*5) 1
ウィルの0.08と100Kハミングで一致しましたGHCiが、私が本当に驚いたのは（100Kハミングでも）これと特に経過時間です。100Kは最大2.9e+38です。
TASKS: 3 (1 bound, 2 peak workers (2 total), using -N1)
SPARKS: 0 (0 converted, 0 overflowed, 0 dud, 0 GC'd, 0 fizzled)
INIT time 0.000s ( 0.000s elapsed)
MUT time 0.000s ( 0.002s elapsed)
GC time 0.000s ( 0.000s elapsed)
EXIT time 0.000s ( 0.000s elapsed)
Total time 0.000s ( 0.002s elapsed)
Alloc rate 0 bytes per MUT second
Productivity 100.0% of total user, 90.2% of total elapsed