生成形如2^m*3^n*5^l的数字，有哪些好用的Haskell概念？

Question

我正试图生成形如2^m*3^n*5^l的数字，其中m、n和l是自然数（包括0）。

该序列如下：1、2、3、4、5、6、8、9、10、12、15、16、18、20、24、25、27、30、32、......

我正在测试获取第一百万个数字。我使用列表推导和排序进行实现，但是它太慢了。我想要一个更快的解决方案。我已经花了几天时间尝试做这件事，但无济于事。

我不需要完整的解决方案。我只想知道Haskell概念在完成此任务时是必要的。

- Ian Hsl

---

所以，你能否只编写一个函数，将m、n和l作为参数输入并返回数字，还是需要更复杂的东西？你是否尝试高效地生成符合该形式的所有数字序列，并希望它们按递增顺序排列？ - David Grayson

是的，我正在使用无限列表以递增顺序生成数字。 - Ian Hsl

请参见：无限生成汉明序列的最新技术。 - David Lukas

请参考以下链接 https://dev59.com/QLPma4cB1Zd3GeqPmTDl#55808095，该网页提供了有关SICP流和Hamming数的程序说明。 - Will Ness

Answer 1

这里有一种方法，不需要任何Haskell概念，只需要一些数学和计算机科学知识。

获取一个提供优先队列的库。

初始化一个仅包含数字1的优先队列。

无限循环以下步骤：从队列中提取最小值。将该值放入输出列表中。将该数字乘以2、3和5后作为三个单独的条目插入到队列中。确保队列插入函数合并重复项，因为由于乘法的可交换性，会有很多重复项。

如果你有一个最大值，你可以使用它来修剪对队列的插入作为一个次要的优化。或者，你可以利用实际的Haskell属性，使用惰性返回一个无限的列表。

- Carl

---

这是我想到的第一件事，应该可以工作。优先队列的大小似乎会像O(N^3)那样增长，其中N是要生成的元素数量。队列的内存最终将无法适应CPU缓存并进入RAM。因此，我怀疑它在实践中比使用O(1)内存的其他解决方案慢。 - David Grayson

嗯，我的 O(N^3) 的想法可能是错误的，但它仍然会变得非常大。 - David Grayson

是的，这种方法更适合那些具有不太可接近模式的事物。 - Carl

关于队列的大小 - 它将保存在返回值和该数字的5倍之间。这是O(n)队列条目作为开销。仍然比其他方法要差得多，但并不可怕。 - Carl

剩余队列的大小似乎随着生成的N个数字而增长为~N^(2/3)。将数字乘以5是指其数量级——完全不同的东西。这意味着最好情况下需要N log N时间。Dijkstra算法及其等效算法的时间是线性的，因为它不会过度生成，其内部队列指向后方并且具有恒定的3个元素大小。 - Will Ness

我想我曾经向自己证明过N^(2/3)的说法，尽管现在我不记得了。（这可能会成为数学交换/溢出上的好问题？）但经验证据强烈支持它。 - Will Ness

Answer 2

首先，编写一个类型为Int -> Bool的函数，确定给定整数是否在您定义的序列中。它将尽可能多地将数字除以2（不创建分数），然后尽可能多地将其除以3，最后尽可能多地将其除以5。在所有这些操作之后，如果数字大于1，则无法表示为二、三和五的乘积，因此函数将返回false。否则，该数字在您的序列中，因此函数返回true。

然后，取大于0的整数的无限序列，并使用上述函数过滤掉不在序列中的所有数字。

- David Grayson

---

该列表的第10000个数字是288555831593533440，因此您需要等待一段时间才能通过筛选到达它。 - j.p.

Answer 3

通过在删除最小元素x时插入较少的元素，可以改进Carl的方法：如2<3<4<5<6，您只需

• 如果x为偶数但不能被4整除，则附加3*x/2
• 如果x可被3整除，则附加4*x/3
• 如果x可被4整除，则附加5*x/4
• 如果x可被5整除，则附加6*x/5

代码如下：

g2 x | mod x 4 == 0 = [5*div x 4]
     | even x       = [3*div x 2]
     | otherwise    = []
g3 x | mod x 3 == 0 = [4*div x 3]
     | otherwise    = []
g5 x | mod x 5 == 0 = [6*div x 5]
     | otherwise    = []
g x = concatMap ($ x) [g2, g3, g5]

如果你从优先队列中删除最小元素x，那么你必须将g x的元素插入到优先队列中。在我的笔记本电脑上，即使我使用列表而不是更好的优先队列，当列表增长到略多于10000个元素时，我也可以在大约8分钟后得到第一百万个元素。

- j.p.

---

我刚刚看到David Lukas在评论中链接了更好的答案。 - j.p.