无限生成汉明序列的最新技术水平

Question

(这很令人兴奋!)我知道,主题是众所周知的.最先进的(在Haskell以及其他语言中)有效生成汉明数字的无限增加序列,没有重复和没有遗漏,长期以来一直是如此(AFAIK - 并且它等同于原始Edsger Dijkstra的代码)太):

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

我问的问题是,你能找到让它在任何重要方面更有效的方法吗？它仍然是最先进的技术还是实际上可以通过两次更快的速度和更好的经验增长启动来改善这一点？

如果您的答案是肯定的,请显示代码,并与上述相比,讨论其速度和经验增长顺序(它的运行速度约为~ n^1.05 .. n^1.10前几十万个数字).此外,如果它存在,这个有效的算法是否可以扩展到生成一系列具有任何给定素数的平滑数？

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和h的3-5列表需要在内存中.由于3-5列表更稀疏,并且k平滑数的密度减小,因此这两个列表部分需要比完整列表的较大部分少得多的存储器.

两种算法的一些时间产生k^th汉明数,每个目标的经验复杂性相对于前一个,排除和包括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时间差别不大.

⁽¹⁾嗯,它看起来不变,我认为这两种变体具有相同的计算复杂性,但我还没有拿出铅笔和纸来证明它,我也不打算这样做.

Answer 2

所以基本上,现在Daniel Fischer给出了他的回答,我可以说我最近遇到了这个问题,我认为这是一个令人兴奋的发展,因为经典代码自Dijkstra以来已经知道了很久.

Daniel在经典版本中正确地确定了必须删除的重复生成的冗余.

原始发现(AFAIK)的归功于Rosettacode.org的撰稿人Ledrug,截至2012-08-26.当然还有 Daniel Fischer的独立发现(2012-09-18).

稍微重写,该代码是:

import Data.Function (fix)

hamm = 1 : foldr (\n s -> fix (merge s . (n:) . map (n*))) [] [2,3,5]

与通常的合并实现,

merge a@(x:xs) b@(y:ys) | x < y     = x : merge xs b
                        | otherwise = y : merge a ys
merge [] b = b
merge a [] = a

与经典版相比,它提供了大约2.0倍 - 2.5倍的加速比.