Ruby算法求优化：spoj PRIME1

0 0

Ruby算法求优化：spoj PRIME150

原问题见 https://www.spoj.pl/problems/PRIME1/
打印m到n内所有质数，每行一个

要求：用Ruby写，对于m=999900000, n=1000000000，比下面这个程序快一倍就行了

$stdin=DATA
require 'benchmark'
elapsed = Benchmark.measure do

# Begin of program--------------------

#使用双筛法：先用普通筛法产生sqrt(n)以内的质数表，然后按质数表筛m, n内的整数
(t = gets.to_i).times do |c|
  m,n = gets.split(' ').map{|e|e.to_i}

  #ps：sqrt(n)以内质数表
  pmax = Math.sqrt(n).to_i 
  ps = []
  3.step pmax, 2 do |i|
    ps << i
  end

  #一筛
  imax = Math.sqrt(pmax).to_i + 1
  3.step imax, 2 do |i|
    ps.delete_if do |e|
      e % i == 0 && e != i
    end
  end

  #准备数组：填入m到n内的一堆奇数
  if m <= 2
    puts 2
    m = 3
  end
  m += 1 if m%2 == 0
  res = []
  m.step n, 2 do |e|
    res << e
  end

  #二筛
  if m <= pmax  #m比较小时，ps可能包含m，所以加一个!=
    for p in ps
      res.delete_if do |e| 
        e % p == 0 && e != p
      end
    end
  else #m比较大时，不用判断 e!=p，稍微减少负担。
    align = 16
    while (sz = ps.size) % align > 0
      ps[sz] = ps[sz-1]
    end
    #重头戏在下面，这个瓶颈能解决，世界就和谐了！
    #这里使用切片大小为16的each_slice，比each快约50%
    #数组方括号方法极其缓慢！写成这样实在是不得已
    ps.each_slice align do |p1,p2,p3,p4,p5,p6,p7,p8,p9,p10,p11,p12,p13,p14,p15,p16|
      #reject!直接调用 rb_arr_reject_bang() 进行迭代
      res.reject! do |e|
        e % p1 == 0 or
        e % p2 == 0 or
        e % p3 == 0 or
        e % p4 == 0 or
        e % p5 == 0 or
        e % p6 == 0 or
        e % p7 == 0 or
        e % p8 == 0 or
        e % p9 == 0 or
        e % p10 == 0 or
        e % p11 == 0 or
        e % p12 == 0 or
        e % p13 == 0 or
        e % p14 == 0 or
        e % p15 == 0 or
        e % p16 == 0
      end
    end
  end

  #输出结果
  puts res
  puts "\n" if not c==t-1
end

# End of program ----------------

end
puts elapsed #看看多长时间能跑完

#__END__后是输入数据，第一行表示输入的数据的组数，后面每行格式为：m n
__END__
2
999900000 1000000000
1 10

难点在于：Ruby很慢，同样的算法在C里面零点几秒就能完成了。
ruby的mathn库完全就是业余人士作品，Prime类比单筛法还要慢……

我还尝试过费马小定理的“逆定理”（但是还要剔除伪素数）等方法，
但是Ruby产生新对象代价极其高昂，a^n mod n这种运算也很杀性能。

各位有闲人士，帮个忙吧~
问题补充：

fivestarwy 写道

试试素数测试

Rabin-Miller方法也要调用模幂运算，分解开来就会多次创建对象
问题补充：

引用

你可以用c++写成dll,然后ruby调用！

人家是online judge，服务器运行，连调用File都不允许……
问题补充：

引用

你能不能把你写的算法和那几种方法来对比一下时间，给我们看看！

这可是50分题耶

数据结构