algorithm - Haskell 性能优化

我正在编写代码来查找第 n 个拉马努金-哈代数。拉马努金-哈代数定义为n = a^3 + b^3 = c^3 + d^3表示 n 可以表示为两个立方体的和。我在haskell中编写了以下代码:-- my own implementation for cube root. Expected time complexity is O(n^(1/3))cube_root n = chelper 1 n where chelper i n = if i*i*i > n then (i-1) else chelper (i+1) n-- It checks if the given number can be expressed as a^3 + b^3 = c^3 + d^3 (is Ramanujan-Hardy number?)is_ram n = length [a| a<-[1..crn], b<-[(a+1)..crn], c<-[(a+1)..crn], d<-[(c+1)..crn], a*a*a + b*b*b == n && c*c*c + d*d*d == n] /= 0 where crn = cube_root n-- It finds nth Ramanujan number by iterating from 1 till the nth number is found. In recursion, if x is Ramanujan number, decrement n. else increment x. If x is 0, preceding number was desired Ramanujan number.ram n = give_ram 1 n where give_ram x 0 = (x-1) give_ram x n = if is_ram x then give_ram (x+1) (n-1) else give_ram (x+1) n在我看来，检查一个数是否为拉马努金数的时间复杂度为 O(n^(4/3))。在 ghci 中运行此代码时，即使找到第二个拉马努金数也需要时间。优化此代码的可能方法是什么？ 最佳答案 首先是对我们正在寻找的内容的小说明。拉马努金-哈代数是一个可以用两种不同方式写成两个立方体之和的数，即 a^3+b^3 = c^3 + d^3，其中 a 一个明显的想法是按排序顺序生成所有立方和，然后查找相同的相邻和。这是一个开始 - 一个函数，它用给定的第一个立方体生成所有的立方体总和:cubes a = [ (a^3+b^3, a, b) | b <- [a+1..] ]所有可能的立方和按顺序只是:allcubes = sort $ concat [ cubes 1, cubes 2, cubes 3, ... ]但当然这不会起作用，因为 concat 和 sort 不起作用在无限列表中。然而，由于 cubes a 是一个递增序列，我们可以对所有通过合并序列将它们组合在一起:allcubes = cubes 1 `merge` cubes 2 `merge` cubes 3 `merge` ...这里我们利用了 Haskell 的惰性求值。定义merge 只是: merge [] bs = bs merge as [] = as merge as@(a:at) bs@(b:bt) = case compare a b of LT -> a : merge at bs EQ -> a : b : merge at bt GT -> b : merge as bt我们仍然有问题，因为我们不知道从哪里停下来。我们可以解决那个通过让 cubes a 在适当的时间启动 cubes (a+1)，即cubes a = ...an initial part... ++ (...the rest... `merge` cubes (a+1) )定义是使用 span 完成的: cubes a = first ++ (rest `merge` cubes (a+1)) where s = (a+1)^3 + (a+2)^3 (first, rest) = span (\(x,_,_) -> x < s) [ (a^3+b^3,a,b) | b <- [a+1..]]所以现在 cubes 1 是所有可能和 a^3 + b^3 的无限级数，其中 a 为了找到 Ramanujan-Hardy 数，我们只需将列表中具有相同第一分量的相邻元素组合在一起: sameSum (x,a,b) (y,c,d) = x == y rjgroups = groupBy sameSum $ cubes 1我们感兴趣的组是那些长度 > 1 的组: rjnumbers = filter (\g -> length g > 1) rjgroups前 10 个解决方案是:ghci> take 10 rjnumbers[(1729,1,12),(1729,9,10)][(4104,2,16),(4104,9,15)][(13832,2,24),(13832,18,20)][(20683,10,27),(20683,19,24)][(32832,4,32),(32832,18,30)][(39312,2,34),(39312,15,33)][(40033,9,34),(40033,16,33)][(46683,3,36),(46683,27,30)][(64232,17,39),(64232,26,36)][(65728,12,40),(65728,31,33)]关于algorithm - Haskell 性能优化，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/32246236/