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

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

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

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

Answer 1

首先是对我们正在寻找的内容的一个小小的澄清.Ramanujan-Hardy数是可以以两种不同方式写成的数字,作为两个立方体的总和,即a ^ 3 + b ^ 3 = c ^ 3 + d ^ 3,其中a <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也不适用于无限列表.但是,由于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 <b按排序顺序.

要找到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)]