Ç - 过滤整数数组的最有效的方法 [英] C - Most efficient method of filtering an integer array
问题描述
我已经成功地实现埃拉托色尼筛（我知道有寻找素数的方法更快，这只是一个学习锻炼）在C素数，但我还没有发现我的过滤返回素数的数组的一个令人满意的方式对于零。为了说明这一点，运行我的程序时，返回此：
$ ./primesieve
输入搜索限制> 100
0 0 1 2 3 0 5 0 7 0 0 0 11 0 13 0 0 0 17 0 19 0 0 0 23 0 0 0 0 0 29 0 31 0 0 0 0 0 37 0 0 0 41 0 43 0 0 0 47 0 0 0 0 0 53 0 0 0 0 0 59 0 61 0 0 0 0 0 67 0 0 0 71 0 73 0 0 0 0 0 79 0 0 0 83 0 0 0 0 0 89 0 0 0 0 0 0 0 97 0 0
$
我需要过滤的零一些方法。我假设有一些算法不是仅仅遍历返回的数组，并打印出答案之前复制出来的非零元素到第二阵列更有效的，但我一直没能找到一个或拿出一个自己。整数数组malloc分配在堆上，顺便说一句。
这里的code。
编辑：与实施zero_filter（）方法粘贴在决赛code。
EDIT2：完全忘筛只需要搜索到的sqrt（N）...固定在低于code
的#include＆LT;＆stdio.h中GT;
＃包括LT＆;＆stdlib.h中GT;
＃包括LT＆;＆文件ctype.h GT;
＃包括LT＆;＆math.h中GT;
＃包括dbg.h无效init_array（INT筛[]，INT大小）{ INT I; 对于（i = 0; I＆LT;大小;我++）{
筛[I] I =;
} 筛[1] = 0;
}INT prime_filter（INT筛[]，诠释大小，诠释根）{ INT I，J;
INT zero_count = 2; 对于（i = 2; I＆LT;根系;我++）{
如果（筛由[i]！= 0）{
为（J = 2 * I; J＆LT;大小; J + = 1）{
如果（筛[J]！= 0）{
筛[J] = 0;
zero_count ++;
}
}
}
} 返回zero_count;
}无效zero_filter（INT筛[]，INT final_array []，INT大小）{ INT I;
INT J = 0; 对于（i = 0; I＆LT;大小;我++）{
如果（筛由[i]！= 0）{
final_array [J] =筛[I]
J ++;
}
}
}无效print_array（INT final_array []，INT大小）{ INT I; 对于（i = 0; I＆LT;大小;我++）{
的printf（％d个，final_array [I]）;
}
}无效destroy_arrays为（int *筛，为int * final_array）{ 如果（筛）{
免费（筛）;
}
如果（final_array）{
免费（final_array）;
}
}INT主（INT ARGC，CHAR *的argv []）{ 检查（ARGC == 1，无输入要求）; INT大小，根，RV;搜索，返回值//上限 的printf（输入搜索限制＆GT;）;
RV = scanf函数（％d个，＆安培;大小）;
检查（RV = EOF，关于scanf函数输入错误（）！）;
检查（RV = 0，输入错误，预计整！）; 根=（int）的SQRT（尺寸）+ 1; 为int *筛，* final_array;
INT zero_count，new_size; 筛=的malloc（sizeof的（INT）*大小）;
检查（筛= NULL，内存分配错误！）; init_array（筛，大小）;
zero_count = prime_filter（筛，大小，根目录）; new_size =大小 - zero_count; final_array =的malloc（sizeof的（INT）*（new_size））;
检查（final_array = NULL，内存分配错误！）; zero_filter（筛，final_array，大小）;
print_array（final_array，new_size）;
destroy_arrays（筛，final_array）; 的printf（\\ n）;
返回0;错误：
返回-1;
}
我觉得你需要一个像函数的std ::删除在C ++中。据删除就地元素。看看：的std ::删除
如果你不熟悉C ++和模板，这里采用code：
为int *删除（INT *首先，为int *最后，诠释VAL）
{
为int *结果=第一;
而（第一！=最后一个）{
如果（！（*第一== VAL））{
*结果= *第一;
++结果;
}
++第一;
}
返回结果;
}
你可以用这个code调用它：
int数组[N];
为int *结束=删除（数组，数组+ N，0）;
为size_t not_removed_size =结束 - 阵列;在范围//值[数组[0]，...阵列[not_removed_size]）是非零。
I've successfully implemented Eratosthenes' sieve (I know there are faster methods for finding primes, this is just a learning exercise) for prime numbers in C, but I have not found a satisfying way of filtering my returned array of primes for zeros. To illustrate, when run my program returns this:
$ ./primesieve
Input search limit > 100
0 0 2 3 0 5 0 7 0 0 0 11 0 13 0 0 0 17 0 19 0 0 0 23 0 0 0 0 0 29 0 31 0 0 0 0 0 37 0 0 0 41 0 43 0 0 0 47 0 0 0 0 0 53 0 0 0 0 0 59 0 61 0 0 0 0 0 67 0 0 0 71 0 73 0 0 0 0 0 79 0 0 0 83 0 0 0 0 0 89 0 0 0 0 0 0 0 97 0 0
$
I need some method of filtering the zeros. I'm assuming there is some algorithm more efficient than merely iterating over the return array and copying out the nonzero elements to a second array before printing out the answer, but I haven't been able to find one or come up with one myself. The integer array is malloc'd on the heap, by the way.
Here's the code.
Edit: Final code pasted in with zero_filter() method implemented. Edit2: completely forgot the sieve only requires to search up to sqrt(n)... fixed in code below.
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <math.h>
#include "dbg.h"
void init_array(int sieve[], int size) {
int i;
for(i = 0; i < size; i++) {
sieve[i] = i;
}
sieve[1] = 0;
}
int prime_filter(int sieve[], int size, int root) {
int i, j;
int zero_count = 2;
for(i = 2; i < root; i++) {
if(sieve[i] != 0) {
for(j = 2 * i; j < size; j += i) {
if(sieve[j] != 0) {
sieve[j] = 0;
zero_count++;
}
}
}
}
return zero_count;
}
void zero_filter(int sieve[], int final_array[], int size) {
int i;
int j = 0;
for(i = 0; i < size; i++) {
if(sieve[i] != 0) {
final_array[j] = sieve[i];
j++;
}
}
}
void print_array(int final_array[], int size) {
int i;
for(i = 0; i < size; i++) {
printf("%d ", final_array[i]);
}
}
void destroy_arrays(int *sieve, int *final_array) {
if(sieve) {
free(sieve);
}
if(final_array){
free(final_array);
}
}
int main(int argc, char *argv[]) {
check(argc == 1, "No input required");
int size, root, rv; // upper limit on search, return value
printf("Input search limit > ");
rv = scanf("%d", &size);
check(rv != EOF, "Input error on scanf().");
check(rv != 0, "Input error, expected integer");
root = (int) sqrt(size) + 1;
int *sieve, *final_array;
int zero_count, new_size;
sieve = malloc(sizeof(int) * size);
check(sieve != NULL, "Memory allocation error");
init_array(sieve, size);
zero_count = prime_filter(sieve, size, root);
new_size = size - zero_count;
final_array = malloc(sizeof(int) * (new_size));
check(final_array != NULL, "Memory allocation error");
zero_filter(sieve, final_array, size);
print_array(final_array, new_size);
destroy_arrays(sieve, final_array);
printf("\n");
return 0;
error:
return -1;
}
I think you need function like std::remove in C++. It "removes" elements in-place. Have a look: std::remove
If you not familiar to C++ and templates, here adopted code:
int *remove(int *first, int *last, int val)
{
int *result = first;
while (first!=last) {
if (!(*first == val)) {
*result = *first;
++result;
}
++first;
}
return result;
}
And you can call it with this code:
int array[n];
int *end = remove(array, array + n, 0);
size_t not_removed_size = end - array; // values in range [array[0], ... array[not_removed_size]) are non-zeros.
这篇关于Ç - 过滤整数数组的最有效的方法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
