Улучшение эффективности моего Решета Эратосфена в Рубине?

Ниже приведена моя реализация решета Эратосфена для поиска простых чисел до параметра верхнего предела.

В настоящее время мой код выполняется примерно за 2 секунды, когда мой параметр равен 2 000 000. Я вижу, что делаю один дополнительный шаг, устанавливая числа равными нулю, а затем уплотняя, а не просто удаляя эти числа за один шаг.

Как бы я это реализовал? У вас также есть какие-либо другие предложения по улучшению скорости моего кода?

def sieve(upper)
  i = 0
  list = (2..upper).to_a

  (2..Math.sqrt(upper)).each do |mult|
    init = mult + i
    (init..upper-1).step(mult) do |index|
      list[index] = nil
    end
    i += 1
  end
  list.compact
end

ruby sieve
person jchi2241    schedule 24.09.2013    source источник
comment
Императивный код быстрее (while циклов), но менее читаем.   -  person Victor Moroz    schedule 25.09.2013
comment
см. этот ответ об использовании эмпирические порядки роста для оценки эффективности программ во время выполнения. Одно точечное измерение ни о чем не говорит. Это ~ n^2.0? ~ n^1.1?   -  person Will Ness    schedule 25.09.2013
comment
Вероятно, вам следует задать этот вопрос на Code Review вместо Stack Overflow. SO предназначен для ремонта сломанных вещей. CR предназначен для улучшения рабочего материала.   -  person the Tin Man    schedule 25.09.2013
comment
Это не решето Эратосфена, которое удаляет только кратные каждому простому числу, то есть следующему оставшемуся числу в списке.   -  person Borodin    schedule 26.09.2013
comment
хорошо, я измерил это для вас (и код из ответа тоже). :)   -  person Will Ness    schedule 27.09.2013

Ответы (1)


arrow_upward
1
arrow_downward

Вы можете пропустить цикл, в котором mult не является простым числом.

def sieve(upper)
  i = 0
  list = (2..upper).to_a
  (2..Math.sqrt(upper)).each do |mult|
    if list[i] #proceed only when mult is prime
      init = mult + i
      (init..upper-1).step(mult) do |index|
        list[index] = nil
      end
    end
    i += 1
  end
  list.compact
end

Это сокращает время выполнения с 1,9 до 0,7 секунды на моей машине. Хотя я уверен, что можно сделать гораздо больше.

person Worakarn Isaratham    schedule 25.09.2013
comment
Следующее улучшение (хотя, вероятно, с меньшим влиянием) — начать с mult^2, а не с 2*mult. :) ... и априори пропускаем четы. - person Will Ness; 27.09.2013