Haskell性能优化

Question

我正在编写代码以查找第n个Ramanujan-Hardy编号。 Ramanujan-Hardy数字定义为

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中运行此代码时，甚至需要花费时间才能找到第二个Ramanujan编号。

什么是可能的方法来优化此代码？

Answer 1

首先澄清我们要找的东西。 Ramanujan-Hardy数是可以以两个不同的方式写成两个立方体的总和的数字，即a^3 + b^3 = c^3 + d^3，其中a为< b和< c为< d。

一个明显的想法是按排序顺序生成所有立方体和，然后查找相同的相邻和。

这里是一个开始 - 它生成所有与给定的第一个立方体魔方和的功能：

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是无穷级数的所有可能的和一个^ 3 + B^3，其中一个< b在排序顺序。

要查找的Ramanujan-哈迪号码，我们相邻只是组列表的元件一起具有相同第一组件：

sameSum (x,a,b) (y,c,d) = x == y 
rjgroups = groupBy sameSum $ cubes 1 

的基团，我们感兴趣的是那些长度为> 1：

rjnumbers = filter (\g -> length g > 1) rjgroups 

THRE第一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)] 

Answer 2

您的is_ram函数通过尝试a，b，c，d的所有值直到cuberoot，然后循环遍历所有n来检查Ramanujan数。

另一种方法是简单地将a和b的值循环到某个极限，并将每个选项的索引a^3 + b^3增加1。

然后可以通过遍历此数组中的非零值并返回数组内容大于等于2（意味着至少有2种计算该结果的方法）的位置来找到Ramanujan数字。

我相信这是O（n ^（2/3））相比，你的方法是O（n.n ^（4/3））。