haskell - 无限生成汉明序列的最新技术

Question

(这太令人兴奋了!)我知道，这个主题是众所周知的。高效生成汉明数无界递增序列、无重复、无遗漏的最先进技术(在 Haskell 以及其他语言中)长期以来一直如下(AFAIK - 顺便说一句，它相当于 original Edsger Dijkstra's solution ，也):

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<sup>1.05…1.10</sup> )产生了数千个数字)。另外，如果存在的话，这种有效的算法是否可以扩展到生成具有任何给定素数集的平滑数字序列？

(澄清:我不是在询问更快的 direct generation of an nth Hamming number ，而是生成序列中的所有前 n 数字。)

Answer 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 之间的部分，以及 h/3 和 之间的部分3-5-list 的 h 需要位于内存中。由于 3-5 列表更加稀疏，并且 k 平滑数的密度降低，因此这两个列表部分需要的内存比完整列表的较大部分少得多。

两种算法生成第 k 个汉明数的一些时间，以及每个目标相对于前一个目标的经验复杂度，不包括和包括 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 时间相差不大。

⁽¹⁾ 嗯，它看起来是恒定的，我认为两种变体具有相同的计算复杂度，但我还没有拿出铅笔和纸来证明这一点，我也不打算这样做。