왜 primes에 대한 stdlib 구현이 느린가?

나는 eratosthenes의 체를 루비로 코딩하기로 결정했다. 내가 도서관 기능이 있다는 것을 알았 기 때문에 오직 재미로만. 또한 나는 그것이 빠를 것이라고 생각했다. 하지만 적어도 내 루비 1.9.3에서는 내 넷북에서 몇 시간 더 빠르다. 왜 이렇게이다.왜 primes에 대한 stdlib 구현이 느린가?

라이브러리 구현 : 루비

require 'prime' 
primes = Prime.each(1_000_000).to_a 
print primes.size 
puts

내 :

sieve = Array.new(1_000_000, true) 
sieve[0..1] = [false, false] 
for number in 2...Math.sqrt(sieve.size) 
    if sieve[number] 
    for multiple in (number ** 2...sieve.size).step(number) 
     sieve[multiple] = false 
    end 
    end 
end 

primes = [] 
for number in 2...1_000_000 
    if sieve[number] 
    primes << number 
    end 
end 
print primes.size 
puts

라이브러리는 매우 느립니다.

출처

2015-02-04 Anonymous

2.2로 업그레이드하는 시간이 좀 필요하다고 생각합니다. –

http://stackoverflow.com/questions/17892313/sieve-of-eratosthenes-with- 휠 분해. – LutzL

prime 라이브러리 Prime.each(1_000_000).to_a은 1_000_000 아래의 모든 소수를 생성합니다.

귀하의 방법은 실제로 1_000_000의 제곱근 이하의 소수 만 생성합니다. 즉 1000입니다.

출처

2015-02-04 07:11:43

네, 그걸 잡아줘서 고마워요. 나는 그것을 새롭게했다. 하지만 여전히 동일한 문제 –

a) 내 컴퓨터에서 라이브러리는 평균 0.270 초에 0.230 초로 구현됩니다. 편집 : MRI 2.2.0, 아니 1.9.3 실행.

b) 더 중요한 것은 MRI의 라이브러리 구현이 in Ruby이고 C가 아니라는 것입니다. Ruby 라이브러리의 모든 기능이 원시 코드로 작성되는 것은 아닙니다.

출처

2015-02-04 07:26:52 Amadan

사용중인 루비 버전은 무엇입니까? –

왜 primes에 대한 stdlib 구현이 느린가?

답변

관련 문제