C - Most efficient method of filtering an integer array

Question

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

iterating and then seting a qointer to the first non zero item is good enough — No Idea For Name
– No Idea For Name, Commented Aug 6, 2013 at 20:50
You really don't need to check if ptr != NULL before freeing it. malloc()ating the sieve is superfluous as well - since you don't return it from any function, you should use an automatic array instead: int sieve[size]. — user529758
– user529758, Commented Aug 6, 2013 at 20:50
Oh, yes this program will probably be searching above 100,000. Plus, isn't malloc()'ing the array to the heap and passing a pointer to the helper functions far more efficient than passing them the entire array? — Dalton
– Dalton, Commented Aug 6, 2013 at 20:55
Why do you think there is a faster way to filter out the zeros than to step through the array and copy out the non-zeros? (If need be you can copy the non-zeros into the "bottom" of your source array, to save the need to allocate a new array, then realloc the array to the new size when done.) — Hot Licks
– Hot Licks, Commented Aug 6, 2013 at 20:58
Given this structure, you can't really filter faster than inspecting each element. But you could combine the filter and print into a single step, and save one pass through the data. — AShelly
– AShelly, Commented Aug 6, 2013 at 21:04

MAnyKey · Accepted Answer · 2013-08-06 21:09:55Z

4

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.

answered Aug 6, 2013 at 21:09

MAnyKey

5674 silver badges11 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

twalberg · Accepted Answer · 2013-08-06 21:17:08Z

1

You can transform your array in place to compact all the non-zero entries at the front. Something like this, which returns the number of non-zero elements found (off the top of my head - not fully tested, but should illustrate the idea - in particular, size should probably be verified to be sane):

int compact(int array[], int size)
{ int current = 0, nextpos = 0;

  while (current < size)
  { if (array[current])
    { int tmp = array[nextpos];         // or use a properly defined swap()
      array[nextpos] = array[current];  // but this will be just as fast...
      array[current] = tmp;
      ++nextpos;
    }
    ++current;
  }
  return nextpos;
}

answered Aug 6, 2013 at 21:17

twalberg

63k12 gold badges95 silver badges88 bronze badges

Collectives™ on Stack Overflow

C - Most efficient method of filtering an integer array

2 Answers 2

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related