1

I am currently programming in c and I was wondering if there's a smart way of filtering an array to make another array satisfying certain conditions.

An example problem would be: Given an array of random integers of size 10, generate an array containing only even numbers that were in the array.

Since it is difficult to know how many elements satisfy the condition, I am checking through the array twice, once counting the number of elements that satisfy the condition, and then actually putting the corresponding elements into the array.

One other thing I tried is making an integer array of size 10, storing all indices satisfying the conditions on the first run and then just reading off the elements in the array of the desired index when copying desired elements into the array.

In general, the array may be huge and checking conditions may be expensive, so I don't think this method would do well.

I feel like there should be smarter & more efficient ways to do this. Could you help me out?

Improve this question
4
  • Assume worst case and allocate enough memory to copy the whole array? Or is that not a suitable approach? Do you have a good approximation as to the size of the original array? Commented Apr 21, 2014 at 9:37
  • 2
    You can use dynamic memory allocation. Commented Apr 21, 2014 at 9:40
  • 1
    Make something like c++ vector. How to replicate vector in c? Commented Apr 21, 2014 at 9:48
  • By the way, is it possible to use dynamic memory allocation in CUDA? Commented Apr 21, 2014 at 10:07

2 Answers 2

Reset to default
4

In general, you have a speed-memory trade-off when it comes to performance.

In your two-loop version you are sacrificing speed for memory, while in the single-loop version you are sacrificing memory for speed.

You could try something like dynamically allocating the space every so many elements. For example, you allocate 5 elements worth of space, and when it's full you allocate an additional 5 elements, and so on. Unfortunately allocating space dynamically can take a significant portion of time.

I don't know of any other method than what you have described, though there may be something out there. In C++, for example, you could use a vector, which automatically resizes itself to accept new values in a method similar to what I've described.

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

1 Comment

"[…] though there may be something out there. In C++ […]" That would be std::copy_if from the <algorithm> header in c++11
2

dynamically allocate memory for a int.
everytime you get a element satisfying the condition and add the element to a dynamically allocated array of integer.
use realloc() to increase the size of the int array pointed by some pointer and add the new element to that array.
use counter to know the number of elements in array.

Improve this answer

3 Comments

shouldn't you use vector instead?
@Vladp Note the tag, this is c.
sorry, but still, allocating each single element is a waste, use vector approach and allocate more each time (1,2,4,8,...) this is much cheaper that way.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.