算法 – Haskell性能优化

我正在编写代码来查找第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

在我看来,检查一个数字是否是Ramanujan数的时间复杂度是O(n ^(4/3)).

在ghci中运行此代码时,即使找到第二个Ramanujan数字也需要时间.

有哪些方法可以优化此代码？

首先是对我们正在寻找的内容的一个小小的澄清. Ramanujan-Hardy数是可以用两种不同方式写成的数字,作为两个立方体的总和,即a ^ 3 b ^ 3 = c ^ 3 d ^ 3,其中a <3. b和a< c< d. 一个明显的想法是按排序顺序生成所有立方数和,然后查找相同的相邻和. 这是一个开始 – 一个函数,它使用给定的第一个多维数据集生成所有多维数据集总和：

cubes a = [ (a^3+b^3, a, b) | b <- [a+1..] ]

所有可能的多维数据集总和顺序是：

allcubes = sort $concat [ cubes 1, cubes 2, cubes 3, ... ]

但是当然这不起作用,因为concat和sort不起作用
在无限的名单上.
但是,由于立方体a是一个递增的序列,我们可以对所有的进行排序
通过合并它们将序列组合在一起：

allcubes = cubes 1 `merge` cubes 2 `merge` cubes 3 `merge` ...

在这里,我们正在利用Haskell的懒惰评估.定义
合并只是：

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

我们仍然有问题,因为我们不知道在哪里停止.我们可以解决这个问题
通过在适当的时间使多维数据集成为启动立方体(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..]]

所以现在立方体1是所有可能总和的无限系列a ^ 3 b ^ 3其中a< b按排序顺序排列. 要找到Ramanujan-Hardy数,我们只需将列表中的相邻元素组合在一起,它们具有相同的第一个组件：

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

我们感兴趣的群体是长度> 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)]