24

JavaScriptでエラトステネスのふるいアルゴリズムを書こうとしています。基本的に、私は文字通り以下の手順に従いました。

  1. 2 から (n-1) までの連続する整数のリストを作成する
  2. 最初の素数 p を 2 とします
  3. p から開始して、p の増分でカウントアップし、これらの各数 (p および p の倍数) を削除します
  4. リストの次の番号に移動し、2、3、4 を繰り返します。
  5. 意図せずに削除された素数をリストに戻す

これが私が思いついたものです：

function eratosthenes(n){
var array = [];
var tmpArray = []; // for containing unintentionally deleted elements like 2,3,5,7,...
var maxPrimeFactor = 0;
var upperLimit = Math.sqrt(n);
var output = [];

// Eratosthenes algorithm to find all primes under n

// Make an array from 2 to (n - 1)
//used as a base array to delete composite number from
for(var i = 2; i < n; i++){
    array.push(i);
}

// Remove multiples of primes starting from 2, 3, 5,...
for(var i = array[0]; i < upperLimit; i = array[0]){
    removeMultiples: 
    for(var j = i, k = i; j < n; j += i){
        var index = array.indexOf(j);
        if(index === -1)
            continue removeMultiples;
        else
            array.splice(index,1);
    }
    tmpArray.push(k);
}
array.unshift(tmpArray);
return array;
}

小さい数では機能しますが、100 万を超える数では機能しません。私は Node.js を使用してテストしましたが、プロセスは終わりがないように見え、メモリ エラーは表示されませんでした。私はここで解決策を読みました（JavaScriptでも）が、まだ完全には理解できません。

質問: 100 万以上の十分に大きな数に対してこれを機能させるにはどうすればよいですか?

4

6 に答える 6

47

線形時間で実行されるArray#indexOfやなどの配列操作関数を使用することで、エラトステネスのふるいを大幅に遅くしています。Array#splice両方の操作に O(1) を使用できる場合。

以下は、従来のプログラミング手法に従ったエラトステネスのふるいです。

var eratosthenes = function(n) {
    // Eratosthenes algorithm to find all primes under n
    var array = [], upperLimit = Math.sqrt(n), output = [];

    // Make an array from 2 to (n - 1)
    for (var i = 0; i < n; i++) {
        array.push(true);
    }

    // Remove multiples of primes starting from 2, 3, 5,...
    for (var i = 2; i <= upperLimit; i++) {
        if (array[i]) {
            for (var j = i * i; j < n; j += i) {
                array[j] = false;
            }
        }
    }

    // All array[i] set to true are primes
    for (var i = 2; i < n; i++) {
        if(array[i]) {
            output.push(i);
        }
    }

    return output;
};

ここで実際の例を見ることができn = 1 000 000ます。

于 2013-03-18T07:32:44.857 に答える
16

この質問は、「多数」とは何かの定義において、低い側では少しけちであり、現在の答えが機能する約 100 万から始まることを受け入れます。ただし、ふるいにかけられる要素ごとに 1 つの 8 バイト数 (64 ビットの倍精度実数) と、見つかった素数ごとに別の 8 バイト数のように、非常に多くのメモリを使用します。その答えは、JavaScript 実行マシンで使用できるメモリの量を超えるため、たとえば約 2 億 5000 万以上の「多数」には機能しません。

「無限」(無制限) のページ セグメント化エラトステネスふるいを実装する次の JavaScript コードは、ビットパックされた 16 キロバイトのページ セグメント化ふるいバッファー (1 ビットは 1 つの潜在的な素数を表す) を 1 つだけ使用し、 base は、現在のページ セグメントの現在の最大数の平方根まで素数を増やします。実際に見つかった素数は、ストレージを必要とせずに順番に列挙されます。また、偶数の素数は 2 だけであるため、奇数の複合材料のみをふるいにかけることで時間を節約できます。

var SoEPgClass = (function () {
  function SoEPgClass() {
    this.bi = -1; // constructor resets the enumeration to start...
  }
  SoEPgClass.prototype.next = function () {
    if (this.bi < 1) {
      if (this.bi < 0) {
        this.bi++;
        this.lowi = 0; // other initialization done here...
        this.bpa = [];
        return 2;
      } else { // bi must be zero:
        var nxt = 3 + 2 * this.lowi + 262144; //just beyond the current page
        this.buf = [];
        for (var i = 0; i < 2048; i++) this.buf.push(0); // faster initialization 16 KByte's:
        if (this.lowi <= 0) { // special culling for first page as no base primes yet:
          for (var i = 0, p = 3, sqr = 9; sqr < nxt; i++, p += 2, sqr = p * p)
            if ((this.buf[i >> 5] & (1 << (i & 31))) === 0)
              for (var j = (sqr - 3) >> 1; j < 131072; j += p)
                this.buf[j >> 5] |= 1 << (j & 31);
        } else { // other than the first "zeroth" page:
          if (!this.bpa.length) { // if this is the first page after the zero one:
            this.bps = new SoEPgClass(); // initialize separate base primes stream:
            this.bps.next(); // advance past the only even prime of 2
            this.bpa.push(this.bps.next()); // keep the next prime (3 in this case)
          }
          // get enough base primes for the page range...
          for (var p = this.bpa[this.bpa.length - 1], sqr = p * p; sqr < nxt;
            p = this.bps.next(), this.bpa.push(p), sqr = p * p);
          for (var i = 0; i < this.bpa.length; i++) { //for each base prime in the array
            var p = this.bpa[i];
            var s = (p * p - 3) >> 1; //compute the start index of the prime squared
            if (s >= this.lowi) // adjust start index based on page lower limit...
              s -= this.lowi;
            else { //for the case where this isn't the first prime squared instance
              var r = (this.lowi - s) % p;
              s = (r != 0) ? p - r : 0;
            }
            //inner tight composite culling loop for given prime number across page
            for (var j = s; j < 131072; j += p) this.buf[j >> 5] |= 1 << (j & 31);
          }
        }
      }
    }
    //find next marker still with prime status
    while (this.bi < 131072 && this.buf[this.bi >> 5] & (1 << (this.bi & 31))) this.bi++;
    if (this.bi < 131072) // within buffer: output computed prime
      return 3 + ((this.lowi + this.bi++) * 2);
    else { // beyond buffer range: advance buffer
      this.bi = 0;
      this.lowi += 131072;
      return this.next(); // and recursively loop just once to make a new page buffer
    }
  };
  return SoEPgClass;
})();

上記のコードは、次の JavaScript コードによって指定された制限まで素数をカウントするために利用できます。

window.onload = function () {
  var elpsd = -new Date().getTime();
  var top_num = 1000000000;
  var cnt = 0;
  var gen = new SoEPgClass();
  while (gen.next() <= top_num) cnt++;
  elpsd += (new Date()).getTime();
  document.getElementById('content')
    .innerText = 'Found ' + cnt + ' primes up to ' + top_num + ' in ' + elpsd + ' milliseconds.';
};

上記の 2 つの JavaScript コードを app.js という名前のファイルに配置し、同じフォルダーにある whatever.html という名前の次の HTML コードを配置すると、その HTML ファイルを開いてブラウザーでコードを実行できるようになります。

<!DOCTYPE html>

<html lang="en">
  <head>
    <meta charset="utf-8" />
    <title>Page Segmented Sieve of Eratosthenes in JavaScript</title>
    <script src="app.js"></script>
  </head>
  <body>
    <h1>Page Segmented Sieve of Eratosthenes in JavaScript.</h1>

    <div id="content"></div>
  </body>
</html>

このコードは、Google Chrome の V8 エンジンなどの Just-In-Time (JIT) コンパイルを使用する JavaScript 実行エンジンで実行すると、数十秒で 10 億の範囲にふるい分けることができます。極端なホイール因数分解と最低ベース素数のページ バッファーの事前カリングを使用することで、さらにゲインを得ることができます。この場合、実行される作業量をさらに 4 分の 1 に減らすことができます。つまり、素数を数えることができます。数秒で最大 10 億 (カウントには、ここで使用されているように列挙は必要ありませんが、ページ セグメント バッファーで直接ビット カウント手法を使用できます)。

EDIT_ADD:

TypedArray と ECMAScript 2015 の asm.js 最適化 (現在はすべての一般的なブラウザーでサポートされています) を使用し、コードを次のように変更することで、実行速度を 3 倍以上高速化できます。

"use strict";
var SoEPgClass = (function () {
  function SoEPgClass() {
    this.bi = -1; // constructor resets the enumeration to start...
    this.buf = new Uint8Array(16384);
  }
  SoEPgClass.prototype.next = function () {
    if (this.bi < 1) {
      if (this.bi < 0) {
        this.bi++;
        this.lowi = 0; // other initialization done here...
        this.bpa = [];
        return 2;
      } else { // bi must be zero:
        var nxt = 3 + 2 * this.lowi + 262144; // just beyond the current page
        for (var i = 0; i < 16384; ++i) this.buf[i] = 0 >>> 0; // zero buffer
        if (this.lowi <= 0) { // special culling for first page as no base primes yet:
          for (var i = 0, p = 3, sqr = 9; sqr < nxt; ++i, p += 2, sqr = p * p)
            if ((this.buf[i >> 3] & (1 << (i & 7))) === 0)
              for (var j = (sqr - 3) >> 1; j < 131072; j += p)
                this.buf[j >> 3] |= 1 << (j & 7);
        } else { // other than the first "zeroth" page:
          if (!this.bpa.length) { // if this is the first page after the zero one:
            this.bps = new SoEPgClass(); // initialize separate base primes stream:
            this.bps.next(); // advance past the only even prime of 2
            this.bpa.push(this.bps.next()); // keep the next prime (3 in this case)
          }
          // get enough base primes for the page range...
          for (var p = this.bpa[this.bpa.length - 1], sqr = p * p; sqr < nxt;
            p = this.bps.next(), this.bpa.push(p), sqr = p * p);
          for (var i = 0; i < this.bpa.length; ++i) { // for each base prime in the array
            var p = this.bpa[i] >>> 0;
            var s = (p * p - 3) >>> 1; // compute the start index of the prime squared
            if (s >= this.lowi) // adjust start index based on page lower limit...
              s -= this.lowi;
            else { // for the case where this isn't the first prime squared instance
              var r = (this.lowi - s) % p;
              s = (r != 0) ? p - r : 0;
            }
            if (p <= 8192) {
              var slmt = Math.min(131072, s + (p << 3));
              for (; s < slmt; s += p) {
                var msk = (1 >>> 0) << (s & 7);
                for (var j = s >>> 3; j < 16384; j += p) this.buf[j] |= msk;
              }
            }
            else
              // inner tight composite culling loop for given prime number across page
              for (var j = s; j < 131072; j += p) this.buf[j >> 3] |= (1 >>> 0) << (j & 7);
          }
        }
      }
    }
    //find next marker still with prime status
    while (this.bi < 131072 && this.buf[this.bi >> 3] & ((1 >>> 0) << (this.bi & 7)))
      this.bi++;
    if (this.bi < 131072) // within buffer: output computed prime
      return 3 + ((this.lowi + this.bi++) << 1);
    else { // beyond buffer range: advance buffer
      this.bi = 0;
      this.lowi += 131072;
      return this.next(); // and recursively loop just once to make a new page buffer
    }
  };
  return SoEPgClass;
})();

事前に型指定された ECMAScript プリミティブ配列を使用して、配列内の整数を直接使用することでオーバーヘッドを回避し (float 表現を使用してスペースを浪費することも回避します)、ビット操作を引き起こす際に asm.js を使用して利用可能な型ヒントも使用するため、高速化が機能します。符号なし整数/バイトを使用します。同様に、配列割り当ての時間を節約するために、ふるい配列を 1 回割り当て、新しいページ セグメントごとにゼロにするだけになりました。ローエンドの 1.92 ギガヘルツ CPU では、約 50 秒ではなく、約 16 秒で 10 億にふるい分けます。同様に、カリング操作の大部分である小さい素数の速度を向上させるために、内部合成数表現 (ビット パック ビット) を単純化するようにアルゴリズムが変更されています。

現在、費やされた時間の約 60% が、見つかった素数の列挙に費やされていることに注意してください。これは、各セグメントページの配列内のゼロビットの数を合計するだけで、見つかった素数をカウントするためのこのようなふるいの通常の使用で大幅に削減できます。これが行われた場合、10 億にふるいにかける時間は、このローエンド CPU で 7 秒近くになり、さらにいくつかの最適化が可能になる可能性があります (すべてのタイミングは、Google Chrome バージョン 72 V8 JavaScript エンジンを使用しており、常に改善されており、それ以降のバージョンはより高速に実行される可能性があります)。

TBH さん、私は個人的に、JavaScript を「現代的な」言語にするために必要なすべての拡張機能と複雑さを備えており、特に動的型付けが好きではありません。そのため、Microsoft の TypeScript が数年前に登場したときにそれを受け入れました。上記のコードは、静的に型指定されたオブジェクト指向プログラミング (OOP) に重点を置いた、TypeScript からの出力としてのコードの変更です。「プロトタイプ」にメソッドを追加する標準的な方法による「次の」インスタンスメソッドの呼び出しは、単に関数を呼び出すよりもはるかに遅くなる可能性があるので、テストしたところ、このランナブルでまさにそうであることがわかりました列挙を単純な出力クロージャ関数に変更するだけで、見つかった素数を約 2.5 倍高速に列挙できます。

これで、見つかった素数の数を数えるだけで、素数の列挙を完全になくすことができます。これは、上記の改善を行っても、見つかった素数の列挙には、実際に行うのとほぼ同じ時間がかかることを示しています。このアルゴリズムを使用したふるい分けにより、実行可能なコードへの上記の 2 つのリンクの実行時間の差として列挙時間を決定できます。

現在のほとんどの CPU は、現在使用しているタブレット Windows CPU (1.92 ギガヘルツの Intel x5-Z3850 およびJavaScript は、リンクを表示しているマシンで実行されます。

これにより、JavaScript は、JVM や DotNet に実装された同じアルゴリズムよりも少しだけ遅くなります。もちろん、C/C++、Rust、Nim、Haskell、Swift、このローエンド CPU でこのアルゴリズムを約 2 秒で実行できる FreePascal、Julia など。WebAssembly は、ブラウザーの実装にもよりますが、このアルゴリズムを JavaScript よりも約 2 倍から 3 倍高速に実行できます。同様に、WebAssembly の仕様が完全に完成し、実装された場合、使用される有効なコアの数によってさらに利益を得るために、マルチスレッドのサポートが提供される予定です。

END_EDIT_ADD

EDIT_ADD_MORE_AND_LATER_EVEN_MORE:

上記のかなり小さな変更を行って、見つかった素数を列挙するのではなく効率的にカウントするだけで、ふるい分けに比べてカウント時間がわずかなオーバーヘッドになります。最大ホイール因数分解を使用するために、より広範な変更を行う価値があります ( 「オッズのみ」の 2 だけでなく、210 の潜在的な素数のスパンをカバーするホイールの 3、5、および 7 によって)、また、小さなふるい配列の初期化で事前にカリングする必要がないようにします。 11、13、17、および 19 の次の素数で選別します。これにより、ページ分割されたふるいを使用する場合の合成数カリング操作の数が約 4 分の 1 から 10 億の範囲に減少し、各カリング操作での操作が減少するため、約 4 倍の速度で実行されるように記述できます。上記のコードと同じ速度。

210 スパンのホイール因数分解を効率的に行う方法は、「オッズのみ」のふるい分けを効率的に行うこの方法に従うことです。上記の現在のアルゴリズムは、2 つの平面から 1 つのビットパック平面をふるい分けて、もう一方の平面をふるい分けると考えることができます。 2 より大きい偶数のみが含まれているため、削除できます。210 スパンの場合、11 以上の可能な素数を表すこのサイズの 48 ビットパック配列を定義できます。他のすべての 162 プレーンには、2、3、5、または 7 の因数である数値が含まれているため、必要ありません。考慮されます。このように、より少ないメモリ要件でふるい分けするのと同じくらい効率的です（「オッズのみ」と比較して半分以上、1 つの 48 プレーン「ページ」がプレーンあたり 16 キロバイト = 131072 ビットを表す場合と同じくらい効率的です） 27,525 の範囲である 210 倍、

上記の拡張コードは数百行あり、ここに投稿するには長いですが、ローエンドの Intel 1.92 ギガヘルツ CPU で、Google V8 JavaScript エンジン (約 4) を使用して、2 秒以内に 10 億までの素数を数えることができます。ネイティブ コードで実行される同じアルゴリズムよりも 5 倍遅くなります。これは JavaScript でできることの限界であり、「ループ アンローリング」や (もちろん) マルチプロセッシングなどのさらに高度な手法は利用できません。ただし、約 1.4 秒で実行される、このローエンド CPU 上の Atkin のふるいの手作業で最適化されたリファレンス C 実装とほぼ一致するには十分です。

追加:別の StackOverflow answer の実行可能なスニペットと、そのスレッドへのクロスリンクされた他の回答で、 これをさらに詳細に説明しました。

上記のコードは約 160 億の範囲まで非常に効率的ですが、他の改善により、数万で数万の範囲まで効率を維持することができます。より高速な CPU で JavaScript を使用して数日。この範囲の素数の数は 1985 年まで知られておらず、当時のコンピューターはエラトステネスのふるいをその範囲で十分高速に実行できるほど強力ではなかったため、数値解析手法によって決定されたため、これは興味深いことです。妥当な時間。

私の現在の「アンチ JavaScript」およびプロ関数型コーディング スタイルのバイアスにより、F# (必要に応じて OOP もサポートする静的に型付けされた ML の「関数型」言語) の実装である Fable を使用してこのコードを記述します。生成されたコードは、JavaScript で直接記述された場合とほぼ同じくらい高速になる可能性があります。

Fable を使用して (Elmish React インターフェースを使用して) Chrome V8 JavaScript エンジンでコードを実行できることを示すために、上記の最後のリンクのように純粋な JavaScript を記述するのとほぼ同じ速度で実行できることを示すために、上記のアルゴリズムを含む Fable オンライン IDE へのリンクを次に示します。. これは純粋な JavaScript よりもわずかに遅く実行され、JavaScript 出力の「コード」ビューはその理由を示しています。Tail Call Optimizations (TCO) 用に生成されたコードは、JavaScript のように単純なループではありません。手動で調整するのは簡単です。狭い内側のカリング ループだけを同じ速度にするためのコードです。このコードは、配列コンテンツの変更と、必要に応じてシーケンス ジェネレーター関数を除いて関数型で記述されています。これらの関数は、理解しやすいように JavaScript と同じ形式になっています。コードのこのストリーミング ジェネレーター部分が F# シーケンスを使用するように記述されていて、目に見える変更がなければ、ほぼ同じ速度で動作します。

上記の Fable コードは純粋な F# であるため、DotNet Core から JavaScript ジェネレーターとして Fabulous ライブラリを使用して実行することも、DotNet Core で直接実行することでマルチプラットフォームで実行し、少し高速化することもできます。

END_EDIT_ADD_MORE_AND_EVEN_MORE

要約すると、秒単位で数百万までの素数を見つけることができるあらゆる種類のアルゴリズムがありますが、実行時間のオーダーで数十億までの素数を決定するには、効率的なページ セグメント化配列ベースのエラトステネスのふるいアルゴリズムが必要です。 .

于 2014-12-10T09:12:01.687 に答える
0

このアルゴリズムはok 2 - big test # time=498.815ms、100 万あたり数ミリ秒 ( )かかります。

module.exports.fast = function eratosthenes (max) {
  let sqrt = Math.sqrt(max)
  let sieve = new Array(max).fill(0)

  for (let primeCandidate = 2; primeCandidate < sqrt; primeCandidate++) {
    if (sieve[primeCandidate] === true) {
      continue // already processed
    }
    for (let multiple = primeCandidate * primeCandidate; multiple < max; multiple += primeCandidate) {
      if (sieve[multiple] === 0) {
        sieve[multiple] = true
      }
    }
  }

  return sieve
    .map((isPrime, i) => ({ i, isPrime })) // find the number associated with the index
    .filter(({ i, isPrime }) => isPrime === 0 && i >= 2) // remove not prime numbers
    .map(({ i }) => i) // output only the values
}

eratosthenes(1000000)78498素数の配列を返します。

于 2020-09-24T21:48:18.257 に答える