8

エラトステネスのふるいを実装しようとしていますが、ふるい配列に関する一般的な質問があります。

私はふるいをかなりの回数 (C で) 実装しており、ふるいとしてuint8_t(out of <stdint.h>) の配列を常に使用していました。これは、ふるいにかける各数値に 8 ビットが使用されるため、1 ビットで十分なはずですが、かなりメモリ効率が悪いです。

Cでこれをどのように行うのですか？ビットの配列が必要です。uint8_t任意の型 ( 、uint16_t、uint32_t、 )の配列をほとんど作成し、uint64_tビット マスクなどを使用して単一のビットにアクセスすることができました。

パフォーマンスを低下させずにビットにアクセスするには、どのデータ型を優先し、どの操作を使用する必要がありますか?

PS: これは単なるBitArray 実装の複製ではないと思います。質問はエラトステネスのふるいに固有のものであり、その主な性質は効率的である必要があるためです (メモリ使用だけでなく、アクセスにおいても)。ふるい分けプロセスをより効率的にするために、さまざまなトリックを使用できるのではないかと考えていました...

4

2 に答える 2

3

Weather Vane がコメントで述べたように、2 を除くすべての偶数は非素数であるため、1 つおきの数のみを考慮することで追加のスペースを節約できます。

したがって、ビット配列では、各ビットは奇数を表します。

これは、この手法を使用して数年前に行った実装です。

#include <stdio.h>
#include <stdlib.h>
#include <fcntl.h>
#include <time.h>
#include <math.h>
#include <stdint.h>

uint8_t *num;
int count = 0;
FILE *primefile;

int main(int argc, char *argv[])
{
  int i,j,root;
  time_t t;

  if (argc>1) count=atoi(argv[1]);
  if (count < 100) {
    fprintf(stderr,"Invalid number\n");
    exit(1);
  }
  if ((num=calloc(count/16,1))==NULL) {
    perror("calloc failed");
    exit(1);
  }
  if ((primefile=fopen("primes.dat","w"))==NULL) {
    perror("Coundn't open primes.dat");
    exit(1);
  }
  t=time(NULL);
  printf("Start:\t%s",ctime(&t));
  root=floor(sqrt(count));
  // write 2 to the output file
  i=2;
  if (fwrite(&i,sizeof(i),1,primefile)==0) {
    perror("Couldn't write to primes.dat");
  }
  // process larger numbers
  for (i=3;i<count;i+=2) {
    if ((num[i>>4] & (1<<((i>>1)&7)))!=0) continue;
    if (fwrite(&i,sizeof(i),1,primefile)==0) {
      perror("Couldn't write to primes.dat");
    }
    if (i<root) {
      for (j=3*i;j<count;j+=2*i) {
        num[j>>4]|=(1<<((j>>1)&7));
      }
    }
  }
  t=time(NULL);
  printf("End:\t%s",ctime(&t));
  fclose(primefile);
  return 0;
}

これnumは、検索の上限に基づいて動的に割り当てられるビット配列です。したがって、1000000000 (10 億) までのすべての素数を検索すると、64000000 (6400 万) バイトのメモリが使用されます。

主な表現は次のとおりです。

「通常の」ビット配列の場合:

セットビットi：

num[i>>3] |= (1<<(i&7);
// same as num[i/8] |= (1<<((i%8));

チェックビットi：

(num[i>>3] & (1<<(i&7))) != 0
// same as (num[i/8] & (1<<(i%8))) != 0

他のすべての数値を追跡しているだけなのでi、2 で割ります (または同等に、右に 1 シフトします:

num[i>>4] |= (1<<((i>>1)&7);
// same as num[(i/2)/8] |= (1<<(((i/2)%8));

(num[i>>4] & (1<<((i>>1)&7))) != 0
// same as (num[(i/2)/8] & (1<<((i/2)%8))) != 0

上記のコードには、除算と 2 の累乗によるモジュラスがビット シフトとビットごとの AND マスクに置き換えられるマイクロ最適化がいくつかありますが、ほとんどのコンパイラはそれを行う必要があります。

于 2016-06-27T19:19:46.080 に答える
2

最大のネイティブ型 (おそらくuint64_t) が最高のパフォーマンスを発揮する傾向があります。ビットマスクを配列に格納するか、ビットシフトによってオンサイトで生成できます。直観に反して、オンサイト生成は、キャッシュ/メモリ アクセス特性が優れているため、パフォーマンスが向上する可能性があります。いずれにせよ、かなり一般的な方法でコーディングを開始し (たとえば、純粋な C を使用している場合は型マクロを定義する)、さまざまなバージョンをテストすることをお勧めします。

結果の一部を (永続的または非永続的に) キャッシュすることも、悪い考えではないかもしれません。

于 2016-06-27T19:19:03.857 に答える