(这很令人兴奋!)我知道，这个主题是众所周知的。长期以来，一直有效地(无重复，无遗漏)有效地生成海明数字无界递增序列的最新技术(用Haskell以及其他语言)(AFAIK-顺便说一句，它也等效于original Edsger Dijkstra's code):
hamm :: [Integer]
hamm = 1 : map (2*) hamm `union` map (3*) hamm `union` map (5*) hamm
where
union a@(x:xs) b@(y:ys) = case compare x y of
LT -> x : union xs b
EQ -> x : union xs ys
GT -> y : union a ys
我要问的问题是，您能找到在任何重要方面使其更有效的方法吗？它仍然是最新技术吗？实际上是否有可能对其进行改进，使其运行两次更快，并使用更好的empirical orders of growth进行引导？
如果您的回答是肯定的，请显示代码并与上面的内容进行比较，讨论其速度和增长的经验顺序(对于前几十万个数字，其运行速度约为
~ n^1.05 .. n^1.10)。另外，如果存在，是否可以将此有效算法扩展为生成具有任何给定素数集的平滑数序列？ 最佳答案
如果恒定因子(1)加速非常重要，那么我可以提供一个效率更高的版本:
hamm :: [Integer]
hamm = mrg1 hamm3 (map (2*) hamm)
where
hamm5 = iterate (5*) 1
hamm3 = mrg1 hamm5 (map (3*) hamm3)
merge a@(x:xs) b@(y:ys)
| x < y = x : merge xs b
| otherwise = y : merge a ys
mrg1 (x:xs) ys = x : merge xs ys
您可以轻松地将其推广为给定素数集的平滑数字:
hamm :: [Integer] -> [Integer]
hamm [] = [1]
hamm [p] = iterate (p*) 1
hamm ps = foldl' next (iterate (q*) 1) qs
where
(q:qs) = sortBy (flip compare) ps
next prev m = let res = mrg1 prev (map (m*) res) in res
merge a@(x:xs) b@(y:ys)
| x < y = x : merge xs b
| otherwise = y : merge a ys
mrg1 (x:xs) ys = x : merge xs ys
它更有效，因为该算法不会产生任何重复并且使用更少的内存。在您的版本中，当产生靠近
h的汉明码时，h/5和h之间的列表部分必须在内存中。在我的版本中，仅完整列表的h/2和h之间的部分以及3-5-list的h/3和h之间的部分需要存储在内存中。由于3-5-list较稀疏，且k平滑数的密度降低，因此与整个列表的较大部分相比，这两个列表部分所需的内存要少得多。这两种算法产生
k th Hamming数的一些时间安排，每个目标相对于前一个目标的经验复杂度，不包括和包括GC时间: k Yours (MUT/GC) Mine (MUT/GC)
10^5 0.03/0.01 0.01/0.01 -- too short to say much, really
2*10^5 0.07/0.02 0.02/0.01
5*10^5 0.17/0.06 0.968 1.024 0.06/0.04 1.199 1.314
10^6 0.36/0.13 1.082 1.091 0.11/0.10 0.874 1.070
2*10^6 0.77/0.27 1.097 1.086 0.21/0.21 0.933 1.000
5*10^6 1.96/0.71 1.020 1.029 0.55/0.59 1.051 1.090
10^7 4.05/1.45 1.047 1.043 1.14/1.25 1.052 1.068
2*10^7 8.73/2.99 1.108 1.091 2.31/2.65 1.019 1.053
5*10^7 21.53/7.83 0.985 1.002 6.01/7.05 1.044 1.057
10^8 45.83/16.79 1.090 1.093 12.42/15.26 1.047 1.084
如您所见，MUT时间之间的因数约为3.5，但是GC时间相差无几。
(1)好吧，它看起来是不变的，而且我认为两个变体都具有相同的计算复杂性，但是我没有掏出笔和纸来证明这一点，也没有打算这样做。