优化速度代码

Question

这是一个素数筛子,但不是Eratosthenes的筛子.

我觉得它编写得很糟糕,因为我是编程和Ruby的新手.这只是我用Ruby编写的第二个程序,但我想尽可能优化它.问题是我没有完全理解我需要改变什么以使其更快,除了我知道程序路径/数据结构不理想 - 我只是没有一个概念可以工作到MAKE他们理想

一个理想的答案不一定会说"将X改为Y",但如果它指向了这种信息的良好资源方向,或者我可以从中获得有关效率的信息的方法,那将会更有帮助.程序的不同部分.

count = 0
x = 0
$results = Array.new []
inpt = []

class PrimeFun

  def initialize(x, y)

    array1 = (x..y).to_a
    array1.each do |n|

      if PrimeFun.primelogic(n%60, n) == 1
        array1.delete_if { |p| p % n == 0}
        $results << n
      elsif n == 2 || n == 3 || n == 5
        $results << n

      end
    end
  end


  def self.primelogic(r, n)

    @prime = case r
      when 1, 13, 17, 29, 37, 41, 49, 53
        formulaone(n)
      when 7, 19, 31, 43
        formulatwo(n)
      when 11, 23, 47, 59
        formulathree(n)
      else -1

    end  
  end


  def self.formulaone(n)
   @x = 1
   @y = -1

   until 4*(@x**2) >= n
      @y = -@y if Math.sqrt(n-(4*(@x**2))).floor - Math.sqrt(n-(4*(@x**2))) == 0  
     @x += 1

   end
   @y
  end

  def self.formulatwo(n)
    @x = 1
    @y = -1

    until 3*(@x**2) >= n
      @y = -@y if Math.sqrt(n-(3*(@x**2))).floor - Math.sqrt(n-(3*(@x**2))) == 0
      @x += 1

    end
    @y
  end

  def self.formulathree(n)
    @x = 1
    @y = -1

    until 3*(@x**2) >= n
      @y = -@y if Math.sqrt(((@x**2)+n)/3).floor - Math.sqrt(((@x**2)+n)/3) == 0 && @x > @y
      @x += 1

    end
   @y
  end

end


x = STDIN.gets.to_i

while count < x
  inpt << STDIN.gets.chomp
  count += 1
end

inpt.each do |n|
  a = n.split(" ").map { |a| a.to_i }
  PrimeFun.new(a[0], a[1])
  $results << ""
end

puts $results

Answer 1

您应该熟悉Ruby标准库中包含的Benchmark模块,以测量您的方法(不同版本)的运行时间.我没有通过Benchmark自己运行以下代码建议,它们只是一些关于如何提高代码速度和可读性的快速想法 - 随意对它们进行基准测试并报告结果!:-)

分析代码以找到瓶颈也是一个好主意 - 没有必要花费数小时优化代码的部分内容,而这些部分对总运行时间的影响不大.查看ruby-prof gem是一个很好的工具来帮助你解决这个问题.

现在快速浏览一下您的代码和一些改进建议.

如果不考虑您使用的实际算法,您的第一个业务应该是消除代码重复多次重复计算相同值的倾向.

此外,您似乎正在使用实例变量(@x,@ y等),其中局部变量可以很好地完成工作.更不用说你使用的类方法只能在同一个类的实例方法中调用.您应该将它们转换为实例方法.(这些不是真正的优化提示,而是关于如何改进Ruby代码的建议.)

以此方法为例:

def self.formulaone(n)
  @x = 1
  @y = -1
  until 4*(@x**2) >= n
    @y = -@y if Math.sqrt(n-(4*(@x**2))).floor - Math.sqrt(n-(4*(@x**2))) == 0  
    @x += 1
  end
  @y
end

在循环中,你正在计算表达式4*(@x**2) 3倍.一个就足够了,所以将结果存储在临时局部变量fsq中.您还在循环内计算两次相同数字的平方根.再次,将值存储在临时变量根中,并使用它.

def formulaone_b(n)
  x = 1
  y = -1
  until (fsq = 4*(x**2)) >= n
    root = Math.sqrt(n - fsq)
    y = -y if root.floor - root == 0
    x += 1
  end
  y
end

这应该是一个好的开始.

可能不是优化,但你可以通过事先计算x的范围来使代码更清晰,然后使用每个代码迭代它:

def formulaone_c(n)
  y = -1
  (1..Math.sqrt(n / 4)).each do |x|
    root = Math.sqrt(n - 4*(x**2))
    y = -y if root.floor == root # See below
  end
  y
end

在上面的代码中,我也用root.floor - root == 0更简单但等价的比较替换了比较root.floor == root,删除了一个不必要的减法.

还有一个想法:不是计算n - 4*(x**2)每次迭代,而是通过注意x * 8 + 4每个步骤都会减少这个值来获得一点点速度,所以使用辅助变量d来更新前一个表达式的值,如下所示:

def formulaone_d(n)
  y = -1
  d = n - 4 # Value of n - 4*(x**2) when x = 1
  (1..Math.sqrt(n / 4)).each do |x|
    root = Math.sqrt(d)
    y = -y if root.floor == root
    d -= x * 8 + 4 # Value of n - 4*(x**2) after x increases
  end
  y
end