Как мне оптимизировать этот кусочек рубинового кода, чтобы он работал быстрее?

Question

Это реализация Сито Эратосфена .

class PrimeGenerator
  def self.get_primes_between( x, y)
    sieve_array = Array.new(y) {|index|
      (index == 0 ? 0 : index+1)
    }

    position_when_we_can_stop_checking = Math.sqrt(y).to_i
    (2..position_when_we_can_stop_checking).each{|factor|
      sieve_array[(factor).. (y-1)].each{|number|
        sieve_array[number-1] = 0 if isMultipleOf(number, factor)
      }
    }

    sieve_array.select{|element| 
      ( (element != 0) && ( (x..y).include? element) )
    }
  end
  def self.isMultipleOf(x, y)
    return (x % y) == 0
  end
end

Теперь я сделал это для «отправки решения проблем, поскольку у вас есть время убить». Я выбрал ruby ​​в качестве моего языка impl .. однако я был объявлен тайм-аут. Я сделал несколько тестов

require 'benchmark'
Benchmark.bmbm do |x|
  x.report ("get primes") { PrimeGenerator.get_primes_between(10000, 100000)}
  end

ruby ​​1.9.1p0 (версия 2009-01-30 21907) [i386-mswin32]

L:\Gishu\Ruby>ruby prime_generator.rb
Rehearsal ----------------------------------------------
get primes  33.953000   0.047000  34.000000 ( 34.343750)
------------------------------------ total: 34.000000sec

                 user     system      total        real
get primes  33.735000   0.000000  33.735000 ( 33.843750)

ruby ​​1.8.6 (2007-03-13 уровень исправления 0) [i386-mswin32]

Rehearsal ----------------------------------------------
get primes  65.922000   0.000000  65.922000 ( 66.110000)
------------------------------------ total: 65.922000sec

                 user     system      total        real
get primes  67.359000   0.016000  67.375000 ( 67.656000)

Так что я переделал это в C # 2.0 / VS 2008 -> 722 миллисекунд

Так что теперь это заставляет меня задуматься, не является ли это проблемой с моей реализацией, или же разница между языками настолько широка? (Я был поражен 1.9 Ruby VM ... пока мне не пришлось сравнивать его с C #:)

UPDATE: В конце концов, это оказалось моей «адаптацией к позору и позору» :) Устранение ненужных итераций цикла было главной оптимизацией. В случае, если кто-то заинтересован в деталях .. вы можете прочитать это здесь ; в любом случае, этот вопрос слишком длинный.

Answer 1

Очевидно, что каждый компьютер будет тестировать это по-своему, но я смог сделать это примерно в 50 раз быстрее на моей машине (Ruby 1.8.6), удалив зацикливание массива с каждым блоком и вызвав цикл, чтобы проверить меньше чисел.

factor=2
while factor < position_when_we_can_stop_checking 
    number = factor
    while number < y-1
      sieve_array[number-1] = 0 if isMultipleOf(number, factor)
      number = number + factor; # Was incrementing by 1, causing too many checks
    end
  factor = factor +1
end

Answer 2

Я бы начал с просмотра вашего внутреннего цикла. sieve_array[(factor).. (y-1)] собирается создавать новый массив каждый раз, когда он выполняется. Вместо этого попробуйте заменить его обычным циклом индексации.

Answer 3

Я не знаю, как она сравнивается по скорости, но это довольно маленькая и простая реализация SoE, которая прекрасно работает для меня:

def sieve_to(n)
  s = (0..n).to_a
  s[0]=s[1]=nil
  s.each do |p|
    next unless p
    break if p * p > n
    (p*p).step(n, p) { |m| s[m] = nil }
  end
  s.compact
end

Возможно еще несколько небольших ускорений, но я думаю, что это довольно хорошо.

Они не совсем эквивалентны, поэтому ваши 10_000 к 1_000_000 будут равны

sieve_to(1_000_000) - sieve_to(9_999)

или что-то близко приближенное.

Во всяком случае, на WinXP с Ruby 1.8.6 (и довольно здоровенными процессорами Xeon) я получаю это:

require 'benchmark'
Benchmark.bm(30) do |r|
  r.report("Mike") { a = sieve_to(10_000) - sieve_to(1_000) } 
  r.report("Gishu") { a = PrimeGenerator.get_primes_between( 1_000, 10_000) }
end

что дает

                                    user     system      total        real
Mike                            0.016000   0.000000   0.016000 (  0.016000)
Gishu                           1.641000   0.000000   1.641000 (  1.672000)

(я перестал вести дело на миллион, потому что мне было скучно ждать).

Так что я бы сказал, что это был твой алгоритм. ; -)

Решение на C # гарантированно будет на несколько порядков быстрее.

Answer 4

Сито Эратосфена прекрасно работает как иллюстративный способ поиска простых чисел, но я бы реализовал его немного по-другому. Суть в том, что вам не нужно проверять числа, кратные уже известным простым числам. Теперь вместо использования массива для хранения этой информации вы также можете создать список всех последовательных простых чисел вплоть до квадратного корня из числа проверяемого вами числа, а затем достаточно просмотреть список простых чисел для проверки простых чисел.

Если вы думаете об этом, это делает то, что вы делаете с образом, но более «виртуальным» способом.

Редактировать: Быстро взломали реализацию того, что я имею в виду (не скопировано из Интернета;)):

  public class Sieve {
    private readonly List<int> primes = new List<int>();
    private int maxProcessed;

    public Sieve() {
      primes.Add(maxProcessed = 2); // one could add more to speed things up a little, but one is required
    }

    public bool IsPrime(int i) {
      // first check if we can compare against known primes
      if (i <= primes[primes.Count-1]) {
        return primes.BinarySearch(i) >= 0;
      }
      // if not, make sure that we got all primes up to the square of i
      int maxFactor = (int)Math.Sqrt(i);
      while (maxProcessed < maxFactor) {
        maxProcessed++;
        bool isPrime = true;
        for (int primeIndex = 0; primeIndex < primes.Count; primeIndex++) {
          int prime = primes[primeIndex];
          if (maxProcessed % prime == 0) {
            isPrime = false;
            break;
          }
        }
        if (isPrime) {
          primes.Add(maxProcessed);
        }
      }
      // now apply the sieve to the number to check
      foreach (int prime in primes) {
        if (i % prime == 0) {
          return false;
        }
        if (prime > maxFactor) {
          break;
        }
      }
      return true;
    }
  }

Использует около 67 мс на моей медленной машине .... тестовое приложение:

class Program {
    static void Main(string[] args) {
        Stopwatch sw = new Stopwatch();
        sw.Start();
        Sieve sieve = new Sieve();
        for (int i = 10000; i <= 100000; i++) {
            sieve.IsPrime(i);
        }
        sw.Stop();
        Debug.WriteLine(sw.ElapsedMilliseconds);
    }
}

Answer 5

Сравните его с ruby-prof. он может выдавать вещи, на которые могут смотреть инструменты, такие как kcachegrind, чтобы увидеть, где ваш код работает медленно.

Затем, как только вы сделаете рубин быстрым, используйте RubyInline, чтобы оптимизировать метод для вас.

Answer 6

Я бы также отметил, что Ruby, по моему опыту, намного медленнее в системах Windows, чем в * nix. Конечно, я не уверен, какой у вас процессор скорости, но запуск этого кода на моем Ubuntu-боксе в Ruby 1.9 занял около 10 секунд, а 1.8.6 - 30.