Почему мой код Ruby для Project Euler #10 такой медленный?

Я относительно новичок в Ruby, но с точки зрения языка он кажется достаточно простым. Я работаю над проектом Euler с Ruby, и у меня огромная проблема со скоростью в следующем:

Сумма простых чисел меньше 10 равна 2 + 3 + 5 + 7 = 17. Найдите сумму всех простых чисел меньше двух миллионов.

Мой код:

beginning_time = Time.now
(1..10000).each { |i| i }

def isPrime(num)
    factors = 0
    primecount = 1
    while primecount <= num
        if (num%primecount == 0)
            factors += 1
        end
        if (factors > 2)
            return false
        end
        primecount += 1
    end
    return true 
end

def make_sieve(num)
    sieve = Array.new(num)
    summation = 0
    for i in 1..num
            if(isPrime(i) == true)
                summation += i
                puts i
                for x in i..num
                    if x%i == 0
                    # Go through entire array and make all multiples of i False
                        sieve[x] = false
                    else
                        sieve[i] = true                     
                    end
                end
            else
                # If i is NOT prime, move to the next number. in the For Loop
                next
            end
    end
    puts summation
end

make_sieve(2000000)


end_time = Time.now
puts "Time elapsed #{(end_time - beginning_time)*1000} milliseconds"

Я думаю, что у меня есть правильное представление о сите, но я действительно понятия не имею, что происходит, что делает эту программу такой медленной. Я запускаю его с 20 000, и это занимает около 15 секунд, что кажется медленным даже до сих пор, хотя вывод выходит НАМНОГО быстрее, чем когда я ставлю 2 000 000.

Я делаю это неправильно логически или синтаксически или и то, и другое?


ruby performance primes sieve-of-eratosthenes
person nucleogenesis    schedule 09.08.2013    source источник
comment
Это гораздо более идиоматичное решение: require 'prime'; puts Prime.each(2_000_000).reduce(:+) # 142913828922   -  person Jörg W Mittag    schedule 09.08.2013

Ответы (2)


arrow_upward
2
arrow_downward

Ваш тест isPrime() очень медленный на простых числах; но тебе это даже не нужно. Ключ к решету в том, что изначально все числа помечены как простые; затем для каждого простого числа мы отмечаем все его кратные. Поэтому, когда мы добираемся до определенной записи в решете, мы уже знаем, является ли она простым числом или нет — помечено ли оно true как простое или помечено false как составное (кратное некоторому меньшему простому числу).

Нет необходимости проверять его на простоту вообще.

И чтобы найти кратные, мы просто считаем: для 5 это каждая пятая запись после нее; на 7 - каждый 7-й. Не нужно тестировать их оператором %, просто сразу установите false. Нет необходимости устанавливать какой-либо из них на true, потому что все числа были установлены на true в начале.

person Will Ness    schedule 09.08.2013
comment
Для 5 достаточно начать с 25 (= 5^2); 10, 15 и 20 уже помечены как составные. Для простого p вы можете начать отмечать композиты с p^2. - person rossum; 09.08.2013
comment
Чего я не понял, так это того, что когда 2 помечено как простое, а его составные части помечены как непростые, следующее число будет простым, а когда составные части этого числа помечены как непростые, следующее число будет простым и так далее. - person nucleogenesis; 09.08.2013
comment
@нуклеогенез точно!.. принять? (знаете, большой пустой знак V сбоку) - person Will Ness; 09.08.2013

arrow_upward
2
arrow_downward

Похоже, вы пишете код JavaScript на Ruby и упускаете те тонкости, которые делают Ruby таким элегантным. Вы должны взглянуть на что-то вроде Ruby Best Practices, которое довольно легко читать, но имеет дело с использованием идиом Ruby вместо навязывания концепций другого языка.

Как уже было сказано, весь смысл решета Эратосфена в том, что вы просто удаляете из списка все составные числа, оставляя только простые числа. Нет необходимости проверять каждый элемент на простоту.

Это решение Rubyish. Выполняется примерно за 1,5 секунды. Немного усложняется представление числа N элементом массива N-1, поэтому (i+i+1 .. num).step(i+1) эквивалентно (n * 2 .. num).step(n)

def make_sieve(num)

  sieve = Array.new(num, true)

  sieve.each_with_index do |is_prime, i|
    next if i == 0 or not is_prime
    (i+i+1 .. num).step(i+1) { |i| sieve[i] = false }
  end

  puts sieve.each_index.select { |i| sieve[i] }.map { |i| i+1 }.inject(:+)

end

make_sieve(2_000_000)

вывод

142913828923
person Borodin    schedule 09.08.2013