哈斯克尔性能优化 [英] Haskell Performance Optimization

问题描述

我写code找到第n个拉马努金 - 哈迪数。拉马努金 - 哈代数定义为

I am writing code to find nth Ramanujan-Hardy number. Ramanujan-Hardy number is defined as

n = a^3 + b^3 = c^3 + d^3

指n可pssed为两个立方之和EX $ P $。

means n can be expressed as sum of two cubes.

我在Haskell写了下面的code：

I wrote the following code in 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））。

In my opinion, time complexity to check if a number is Ramanujan number is O(n^(4/3)).

在运行此code在ghci中，它需要时间，甚至找到第二拉马努金人数。

On running this code in ghci, it is taking time even to find 2nd Ramanujan number.

什么是可能的方法来优化这个code？

What are possible ways to optimize this code?

推荐答案

首先一个小的澄清，我们要查找的内容的。一个拉马努金耐寒号码是其中一个可以写入两种不同的方式为两个立方之和，即^ 3 + B ^ 3 = C ^ 3 + D ^ 3，其中A＆LT; b和a＆其中; C＆LT; ð。

First a small clarification of what we're looking for. A Ramanujan-Hardy number is one which may be written two different ways as a sum of two cubes, i.e. a^3+b^3 = c^3 + d^3 where a < b and a < c < d.

这是显而易见的想法是生成所有的立方体款项的分类顺序，然后寻找邻近的款项哪都一样。

An obvious idea is to generate all of the cube-sums in sorted order and then look for adjacent sums which are the same.

下面是一个开始 - 一个函数生成所有的立方体款项与给定的第一个立方体的：

Here's a start - a function which generates all of the cube sums with a given first cube:

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

所有可能的魔方款项的顺序就是：

All of the possible cube sums in order is just:

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

不过，这当然不会，因为工作CONCAT 和排序不工作 在无限的名单。 然而，由于立方体一个是一个递增的序列，我们可以排序的所有 一起序列通过合并它们：

but of course this won't work since concat and sort don't work on infinite lists. However, since cubes a is an increasing sequence we can sort all of the sequences together by merging them:

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

在这里，我们正在采取Haskell的惰性计算的优势。定义 对合并就是：

Here we are taking advantage of Haskell's lazy evaluation. The definition of merge is just:

 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）在适当的时候，也就是

We still have a problem since we don't know where to stop. We can solve that by having cubes a initiate cubes (a+1) at the appropriate time, i.e.

cubes a = ...an initial part... ++ (...the rest... `merge` cubes (a+1) )

该定义使用范围完成的：

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

So now cubes 1 is the infinite series of all the possible sums a^3 + b^3 where a < b in sorted order.

要找到拉马努金 - 哈迪号码，名单在一起，他们同为第一部分，我们只是一群相邻的元素：

To find the Ramanujan-Hardy numbers, we just group adjacent elements of the list together which have the same first component:

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

我们感兴趣的群体是那些长度> 1

The groups we are interested in are those whose length is > 1:

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

THRE前10个解决方案是：

Thre first 10 solutions are:

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)]

这篇关于哈斯克尔性能优化的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！