0

Project Eulerと Sphere Online Judge の問題に取り組みました。この特定の問題では、与えられた 2 つの数値内のすべての素数を見つける必要があります。遅すぎることを除いて、（エラトステネスのふるいに基づいて）有望に見える関数があります。誰かが私の機能を非常に遅くしている原因を見つけて、それを修正する方法を教えてもらえますか? また、一般的な最適化へのアプローチ方法に関するコメント (またはそのようなコメント/書籍/記事などへのリンク) も大歓迎です。

コード：

def ranged_sieve(l, b)
  primes = (l..b).to_a
  primes[0]=nil if primes[0] < 2
  (2..Math.sqrt(b).to_i).each do |counter|
    step_from = l / counter
    step_from = step_from * counter
    l > 3 ? j = step_from : j = counter + counter
    (j..b).step(counter) do |stepped|
      index = primes.index(stepped)
      primes[index] = nil if index
    end
  end
  primes.compact
end
4

2 に答える 2

3

SPOJ（Sphere Online Judges）でのPRIME1問題は、単純に上限までふるいにかけるとタイムアウトになってしまうので、単純にふるいにかけることができないように設計されています。

考えられるアプローチの 1 つは、優れた速度です。標準ふるいにいくつかのオプションを追加することで、タイムアウト制限を十分に下回る速度で実行できます。速度の最適化には以下が含まれます。

  • ふるいの奇数の整数のみを表す (50% のスペース節約)
  • L1 キャッシュ (32 KB) に収まる、キャッシュに適した小さなセグメントにふるい分けます。
  • 小さな素数による保存 (つまり、事前に計算されたパターンをふるいセグメントに吹き付ける)
  • 遅い除算を使用してそれらを再計算する代わりに、セグメント全体の素数ごとに最後 (または次) の作業オフセットを記憶する

これらすべてをまとめると、2^32 の範囲全体をふるいにかける時間が 20 秒程度から 2 秒に短縮され、SPOI タイムアウトを大幅に下回ります。私のペーストビンには、3 つの単純な C++ デモ プログラムがあり、これらの各最適化の動作を調べて、その効果を確認できます。

はるかに単純なアプローチは、必要な作業のみを行うことです。ターゲット範囲の最後の数の平方根までふるいにかけて、すべての潜在的な素因数を取得してから、ターゲット範囲自体のみをふるいにかけます。そうすれば、20 行未満のコードと数ミリ秒の実行時間で SPOJ 問題を解決できます。この種の分割ふるいのデモ .cpp を完成させました(困難な部分は、ふるいではなく、快適にテストするためのテスト フレームと、参照データがほとんどないため 2^64-1 までの適切な動作の検証でした)。 .

ふるい自体はこんな感じ。ふるいはオッズのみのパックされたビットマップであり、ふるいの範囲は堅牢性のためにビット単位で指定されているため (すべて .cpp で説明されています)、次のように (range_start / 2) を渡しますoffset。 

unsigned char odd_composites32[UINT32_MAX / (2 * CHAR_BIT) + 1];   // the small factor sieve
uintxx_t sieved_bits = 0;                                          // how far it's been initialised

void extend_factor_sieve_to_cover (uintxx_t max_factor_bit);       // bit, not number!

void sieve32 (unsigned char *target_segment, uint64_t offset, uintxx_t bit_count)
{
   assert( bit_count > 0 && bit_count <= UINT32_MAX / 2 + 1 );

   uintxx_t max_bit = bit_count - 1;
   uint64_t max_num = 2 * (offset + max_bit) + 1;
   uintxx_t max_factor_bit = (max_factor32(max_num) - 1) / 2;

   if (target_segment != odd_composites32)
   {
      extend_factor_sieve_to_cover(max_factor_bit);
   }

   std::memset(target_segment, 0, std::size_t((max_bit + CHAR_BIT) / CHAR_BIT));

   for (uintxx_t i = 3u >> 1; i <= max_factor_bit; ++i)
   {
      if (bit(odd_composites32, i))  continue;

      uintxx_t n = (i << 1) + 1;   // the actual prime represented by bit i (< 2^32)

      uintxx_t stride = n;         // == (n * 2) / 2
      uint64_t start = (uint64_t(n) * n) >> 1;
      uintxx_t k;

      if (start >= offset)
      {
         k = uintxx_t(start - offset);
      }
      else // start < offset
      {
         uintxx_t before_the_segment = (offset - start) % stride;

         k = before_the_segment == 0 ? 0 : stride - before_the_segment;
      }

      while (k <= max_bit)
      {
         set_bit(target_segment, k);

         // k can wrap since strides go up to almost 2^32
         if ((k += stride) < stride)
         {
            break;
         }
      }
   }
}

SPOJ 問題 (2^32 未満の数値) の場合、すべての変数に符号なし整数で十分であり (つまり、uintxx_t と uint64_t の代わりに uint32_t)、さらに単純化できるものもあります。また、これらの小さな範囲のsqrt()代わりに使用できます。max_factor32()

デモ コードでは、キャッシュに適した小さな手順で とextend_factor_sieve_to_cover()同等の道徳的処理を行います。sieve32(odd_composites32, 0, max_factor_bit + 1)SPOJ の問題では、1 回の sieve32() 呼び出しを使用するだけで済みます。これは、2^32 未満の小さな奇素素因数が 6541 個しかなく、短時間でふるい分けることができるためです。

したがって、この SPOJ 問題を解決する秘訣は、セグメント化されたふるい分けを使用することです。これにより、合計実行時間が数ミリ秒に短縮されます。

于 2014-11-10T09:09:18.057 に答える
0

私は完全には見ていませんが、1つの要因は、特定の値を に置き換え、primes後でnilそれcompactを削除することです。これは無駄です。それを直接実行するだけでdelete_at、2 倍以上高速になります。

def ranged_sieve2(l, b)
  primes = (l..b).to_a
  primes.delete_at(0) if primes[0] < 2
  (2..Math.sqrt(b).to_i).each do |counter|
    step_from = l / counter
    step_from = step_from * counter
    l > 3 ? j = step_from : j = counter + counter
    (j..b).step(counter) do |stepped|
      index = primes.index(stepped)
      primes.delete_at(index) if index
    end
  end
  primes
end

ranged_sieve(1, 100) # => Took approx 8e-4 seconds on my computer
ranged_sieve2(1, 100) # => Took approx 3e-4 seconds on my computer

改善すべきもう 1 つのポイントは、ハッシュを使用すると、関連するサイズが大きくなるため、配列よりもはるかに高速になることです。配列の実装をハッシュに置き換えると、次のようになります。

def ranged_sieve3(l, b)
  primes = (l..b).inject({}){|h, i| h[i] = true; h}
  primes.delete(0)
  primes.delete(1)
  (2..Math.sqrt(b).to_i).each do |counter|
    step_from = l / counter
    step_from = step_from * counter
    l > 3 ? j = step_from : j = counter + counter
    (j..b).step(counter) do |stepped|
      primes.delete(stepped)
    end
  end
  primes.keys
end

これを行うと、オーバーヘッドが原因でrange_sieve3(1, 100)より遅くなります。range_sieve2(1, 100)しかし、数字を大きくするほど優位性が顕著になります。たとえば、コンピューターで次の結果が得られました。

ranged_sieve(1, 1000) # => Took 1e-01 secs
ranged_sieve2(1, 1000) # => Took 3e-02 secs
ranged_sieve3(1, 1000) # => Took 8e-04 secs
于 2012-12-22T15:22:37.473 に答える