C - 埃拉托斯特尼筛法 - 位域

Question

C - 埃拉托斯特尼筛法 - 位域

carraysbit-fieldssieve-of-eratosthenessieve

8

我即将实现埃拉托斯特尼筛法，关于筛子数组有一个普遍问题。我已经多次使用C语言实现了筛子（Sieve），并始终使用uint8_t（在<stdint.h>中）作为筛子。这相当于使用了8位来筛选每个数字，尽管一个位就足够了，因此效率很低。

我该如何在C语言中解决这个问题？我需要一个位数组。我可以创建任何类型的数组（uint8_t、uint16_t、uint32_t、uint64_t）并使用位掩码等方式访问单个位。

我应该选择哪种数据类型，并使用什么操作来访问位而不会降低性能？

PS：我不认为这是一个仅仅关于BitArray实现的重复问题，因为该问题具体涉及Eratosthenes筛法，它的主要特性需要高效（不仅在内存使用上，还在访问上）。我在想，也许可以使用不同的技巧来使筛选过程更加高效...

- Matthias

2

@JohnColeman 提到筛法其实很无关紧要：如果第一段被删除，问题仍然有意义（需要进行一些小修改）。即使它不是重复问题，也应该被视为过于广泛或不相关主题而关闭（没有代码，没有在实际问题上展示研究努力）。 - RoadieRich

在问题编辑后，也许可以在CodeReview上分享代码 ;) - Weather Vane

@WeatherVane 我也考虑过这个。谢谢 :) 我认为通过一些巧妙的技巧，也可以留下3和5的倍数。问题在于何时停止/何时技巧变得比实际计算更加复杂/难以计算。 - Matthias

我尝试过只使用2、3，但这使得算法变得更加复杂，因为你必须通过筛子采取不同的步骤。如果这能够解决内存不足的问题，那么16倍的改进是值得实现的。在我解决的一个问题中，即使我意识到感兴趣的范围是可控的，以及测试的最大数字的平方根也是如此，仍然没有足够的内存，所以我实现了两个不连续的数组。 - Weather Vane

使用模30轮（跳过2、3和5）非常普遍，因为每个模有8个候选项，这意味着它们可以很好地适应一个字节。您可以除以30来获取哪个字节，然后按模30结果索引以获取位。有一些模210和模2310的实现，但是这需要更多的工作，而收益却不大。 - DanaJ

显示剩余4条评论

2个回答

2

最大的本地类型（可能是uint64_t）往往表现最佳。您可以将位掩码存储在数组中，也可以通过位移现场生成它们。与直觉相反，现场生成可能会由于更好的缓存/内存访问特性而表现更好。无论如何，最好以相当通用的方式开始编写代码（例如，如果使用纯C，则定义您的类型宏），然后测试不同版本。持久或非持久地缓存一些结果也可能不是坏主意。

- Petr Skocik

谢谢！我会在接下来的几天里报告我的实现情况。 - Matthias

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- dbush · Accepted Answer

正如Weather Vane在他的评论中提到的，你可以通过仅考虑每个其他数字来节省额外的空间，因为所有偶数除了2以外都不是质数。

所以在你的位数组中，每个位代表一个奇数。

这是我几年前使用这种技术实现的一个例子。

#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

在上面的代码中，有一些微小的优化，其中将除法和模数运算替换为位移和按位与掩码，但大多数编译器都应该为您完成这些操作。