所以我试图在 Haskell 中生成出租车号码列表。出租车号码是可以用两种不同方式写成两个不同立方体之和的数字 - 最小的是
1729 = 1^3 + 12^3 = 9^3 + 10^3
.
现在,我只是担心生成“组成”出租车号码的四个数字,例如(1,12,9,10),并被告知使用列表理解(我不太熟悉)。该函数将生成所有 4 元组,其中最大数最多为 n:
taxi n = [(a,b,c,d) | a <- [1..n], b <- [1..n], c <- [1..n], d <- [1..n], a^3 + b^3 == c^3 + d^3, a < b, a < c, c < d]
但是,由于以下几个原因,这很麻烦:
- a、b、c、d 的域都是相同的,但我不知道如何简化此代码,所以
[1..n]
只写一次。 - 我想要一个无限列表,没有上限,这样我就可以让程序尽可能长时间地运行,并在需要时终止它。显然,如果我只是设置
a <- [1..]
等等,那么程序将永远不会最终评估任何东西。 - 程序非常慢:只是
taxi 50
需要 19 秒。
任何速度优化都很好,但如果不是的话,我使用的简单方法就足够了。
最佳答案
您的限制意味着 a < c < d < b
。所以让b
跑到最外面,让其他跑在适当的较低范围内:
taxi n = [ (a,b,c,d) | b <- [1..n],
d <- [1..b-1],
c <- [1..d-1],
a <- [1..c-1],
a^3 + b^3 == c^3 + d^3 ]
要达到无限,只需使用 b <- [1..]
.
进一步的重大改进是从其他三个变量中计算四个变量之一:
taxi = [ (a,b,c,d) | b <- [1..],
c <- [1..b-1],
a <- [1..c-1],
let d3 = a^3 + b^3 - c^3,
let d = round(fromIntegral(d3)**(1/3)),
c < d,
d^3 == d3 ]
<小时/>
基准测试 taxi 50
在 GHCi 中 :set +s
就像你做的那样:
Yours: (16.49 secs, 17,672,510,704 bytes)
My first: (0.65 secs, 658,537,184 bytes)
My second: (0.09 secs, 66,229,376 bytes) (modified to use b <- [1..n] again)
Daniel's first: (1.94 secs, 2,016,810,312 bytes)
Daniel's second: (2.87 secs, 2,434,309,440 bytes)
关于haskell - 整理 Haskell 中的列表理解,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/47983444/