2

这是一个素数筛，但不是埃拉托色尼筛。

我觉得它写得不好，因为我对编程和 Ruby 不熟悉。这只是我用 Ruby 编写的第二个程序，但我想尽可能地优化它。问题是我对我需要改变什么以使其更快，除了我知道程序路径/数据结构并不理想之外没有一个明确的理解——我只是没有一个可以用来制作的概念他们理想

一个理想的答案不一定会说“将 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
4

2 回答 2

5

您应该熟悉 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) 三次。一个就足够了，因此将结果存储在临时局部变量fsq中。您还在循环内两次计算相同数字的平方根。同样，将值存储在临时变量root中，并使用它。

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 的范围来使代码更简洁，然后使用each对其进行迭代：

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
于 2012-05-08T19:00:28.607 回答
3

正确性

首先，您的代码不正确：

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

是否@y小于@x是无关紧要的，它总是正确的，因为@y = ±1和何时@x = 1，@y = -1 < 1。

您感兴趣的是表示的数量

n = 3*a^2 - b^2

用整数a > b > 0。现在a^2 = (n + b^2)/3，，所以你想要

(n + b^2)/3 > b^2
n + b^2 > 3*b^2
n > 2*b^2

而不是n > 3*b^2（b在这里代表@x）。例如，

143 = 11* 13 = 3*7^2 - 2^2 = 3*8^2 - 7^2

但是 3*7^2 = 147 > 143，所以@x = 7不会被考虑，所以 143 将被视为素formulathree数

179 = 3*9^2 - 8^2

不会被认为是素数，尽管它是，因为3*8^2 = 192 > 179.

n当您输出每个考虑进行initialize调试时，另一个问题变得明显。

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

  if PrimeFun.primelogic(n%60, n) == 1
    array1.delete_if { |p| p % n == 0}

array1.each或多或少

for(index = 0; index < array1.length; ++i)

但是当您删除 的倍数时n，您也会删除n自身，因此直接在移动到索引之后的元素n具有，并且被跳过。您可以通过仅删除n大于的倍数来解决此问题n：

array1.delete_if { |p| p > n && p % n == 0 }

表现

最大的性能问题是算法。如果您调用initialize(2,n)，对于每个素数，您将遍历数组并通过试除法删除倍数。每个素数除以每个较小的素数（2、3 和 5 除外），以查看是否应将其从数组中删除。那就是臭名昭著的特纳“筛子”，其复杂度为 O((n/log n)^2)，几乎是二次的。由于您甚至不会从数组中删除 2,3 和 5 的倍数，除非这些倍数具有更大的素因数，因此复杂性可能会稍微差一些。

在您选择更好的算法之前，微优化根本不值得付出努力。

下一个问题是使用 确定素数formulaX。如果您还从数组中删除了 2、3 和 5 的倍数，则甚至不需要进行测试，每个考虑的数字都是每个试除法的已知素数。由于您不这样做，因此检查候选者是否可被 2、3 或 5 整除会比primelogic.

primelogic使用同样用于 Atkin 筛的逻辑来确定素数，但它单独测试每个数字，因此测试每个数字n是 O(√n)。计算平方根比除法复杂得多，因此比试除法的素数测试需要更长的时间。

于 2012-05-08T22:20:24.487 回答