Algorytm Sieve of Eratosthenes w JavaScript działa bez końca dla dużej liczby

Question

Próbowałem napisać algorytm Sieve of Eratosthenes w JavaScript. Zasadniczo po prostu dosłownie następuje czynności:

1. Utwórz listę kolejnych liczb od 2 do (n-1)
2. Niech pierwsza liczba pierwsza p równe 2
3. Począwszy od p, liczyć się z przyrostem p i usuwa każdy z tych numerów (P i wielokrotności P)
4. przejść do następnego numeru na liście i powtórzyć 2,3,4
5. Dodaj nieumyślnie usunięte liczb pierwszych z powrotem do listy

i to, co mam wymyślić:

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; 
} 

działa dla małych ilościach, ale nie dla liczb większych niż jeden milion. Użyłem Node.js do przetestowania, a proces wydaje się nie mieć końca i nie pojawia się błąd pamięci. Czytałem rozwiązanie here (również w javascript), ale nadal nie mogę w pełni go zrozumieć.

Pytanie: Jak to działa dla wystarczająco dużej liczby osób, na przykład miliona i więcej?

Answer 1

Celowo wolniej wykonujesz Sieve of Eratostenes, korzystając z funkcji manipulowania tablicą, takich jak Array#indexOf i Array#splice, która działa w czasie liniowym. Kiedy możesz mieć O (1) dla obu operacji.

Poniżej jest Sito Eratostenesa następujące konwencjonalne praktyki programowanie:

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; 
}; 

You can see a live example for n = 1 000 000 here.

Answer 2

to pytanie jest trochę skąpy zaniżone w definicji tego, co jest „duża liczba” i akceptuje że zaczyna się od zaledwie około miliona, dla którego działa current answer; jednak używa dość dużej ilości pamięci, jak w przypadku jednej 8-bajtowej liczby (podwójna liczba rzeczywista z 64 bitów) dla każdego przesiewanego elementu i kolejnej 8-bajtowej liczby dla każdego znalezionego prime. Ta odpowiedź nie zadziałałaby dla "dużych liczb", powiedzmy około 250 milionów i więcej, ponieważ przekraczałaby ilość pamięci dostępnej dla maszyny wykonawczej JavaScript.

Następujący kod JavaScript implementujący "nieskończoną" (nieograniczoną) stronę Segmentowaną sito Eratostenesa rozwiązuje ten problem, ponieważ wykorzystuje tylko jeden bitowy pakiet przesiewania podzielony na segmenty o wielkości 16 kilobajtów (jeden bit reprezentuje jeden potencjalny numer główny) i tylko wykorzystuje pamięć podstawową dla liczb pierwszych do pierwiastka kwadratowego z bieżącego najwyższego numeru w bieżącym segmencie strony, z rzeczywistymi znalezionymi liczbami pierwszymi wymienionymi w kolejności bez konieczności przechowywania; również oszczędność czasu tylko przez przesiewanie nieparzyste kompozytów jako jedyny nawet Prime 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))) .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; 
})(); 

Powyższy kod można wykorzystać do policzenia liczby pierwsze aż do danego limitu za pomocą następującego kodu 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.'; 
}; 

Jeśli powyższe dwa fragmenty kodu JavaScript zostaną umieszczone w pliku o nazwie app.js w tym samym folderze, co poniższy kod HTML o nazwie cokolwiek.html, będzie w stanie uruchomić kod w przeglądarce otwierając plik HTML w nim:

<!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> 

Kod ten można przesiać do jednego miliarda zakresie jest kilka 10-tych sekund po uruchomieniu na silniku uruchamianie skryptów JavaScript za pomocą kompilacji Just-In-Time (JIT), takiej jak silnik przeglądarki Google Chrome V8. Dalsze korzyści można uzyskać, stosując skrajne rozłożenie koła i wstępne wybieranie buforów stron o najniższych liczbach podstawowych, w którym to przypadku ilość wykonanej pracy można zmniejszyć o kolejny współczynnik równy cztery, co oznacza, że ​​można zliczyć liczbę liczb pierwszych. do miliarda w ciągu kilku sekund (zliczanie nie wymaga wyliczenia, jak tu zastosowano, ale może wykorzystywać tabele z liczbą bitów bezpośrednio na buforach segmentów strony), chociaż kosztem zwiększenia złożoności kodu.

Answer 3

Po prostu dla zabawy, zaimplementowałem algorytm sita Erastoten (uruchamiany z Węzłem) ściśle zgodnie z zasadami TDD. Ta wersja powinna wystarczyć na wywiady, jako szkolne ćwiczenie lub po prostu tak, jak ja - za trochę pogmatwane.

Pozwolę sobie stwierdzić, że zdecydowanie uważam, że zaakceptowaną odpowiedzią powinna być odpowiedź dostarczona przez GordonBGood.

module.exports.compute = function(size) 
{ 
    if (!utils.isPositiveInteger(size)) 
    { 
     throw new TypeError("Input must be a positive integer"); 
    } 

    console.time('optimal'); 
    console.log(); 
    console.log("Starting for optimal computation where size = " + size); 
    let sieve = utils.generateArraySeq(2, size); 

    let prime = 2; 
    while (prime) 
    { 
     // mark multiples 
     for (let i = 0; i < sieve.length; i += prime) 
     { 
      if (sieve[i] !== prime) 
      { 
       sieve[i] = -1; 
      } 
     } 

     let old_prime = prime; 
     // find next prime number 
     for (let i = 0; i < sieve.length; i++) 
     { 
      if ((sieve[i] !== -1) && (sieve[i] > prime)) 
      { 
       prime = sieve[i]; 
       break; 
      } 
     } 

     if (old_prime === prime) 
     { 
      break; 
     } 
    } 
    console.timeEnd('optimal'); 
    // remove marked elements from the array 
    return sieve.filter( 
     function(element) 
     { 
      return element !== -1; 
     }); 
} // compute 

Doceniam każdą sensowną krytykę.

The whole repository can be found on my github account.

Answer 4

będę pisać to jako komentarz do Aleksandra, ale nie mam reputację, aby to zrobić. Jego odpowiedź jest niesamowita, a to po prostu zmienia ją, by była szybsza. Porównałem testując n = 100 000 000.

Zamiast używać wartości "prawda" i "fałsz" w "tablicy", uzyskuję dużą poprawę prędkości, używając 1 i 0. To zmniejszyło mój czas w Chrome z 5000 ms do 4250 ms. Firefox nie uległ zmianie (5600 ms w obu kierunkach).

Następnie możemy wziąć pod uwagę, że nawet liczby nigdy nie będą pierwsze. Umieść 2 na wyjściu z pałki i możesz zrobić i = 3; i + = 2, i j + = i * 2 podczas sita (możemy pomijać parzyste wielokrotności, ponieważ dowolna liczba razy równa jest parzysta), tak długo jak my również i + = 2, podczas gdy pchamy na "wynik" w koniec. To zmniejszyło mój czas w Chrome z 4250 ms do 3350 ms. Firefox skorzystał nieco mniej, spadając z 5600 ms do 4800 ms.

W każdym razie kombinacja tych dwóch poprawek zapewniła mi 33% wzrost prędkości w Chrome i 14% wzrost w Firefoksie. Oto ulepszona wersja kodu Alexandra.

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

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

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

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

    return output; 
};