Re: question about data movement
- From: Paul Donnelly <paul-donnelly@xxxxxxxxxxxxx>
- Date: Sat, 09 Feb 2008 21:55:20 -0600
Jeff Lait <torespondisfutile@xxxxxxxxxxx> writes:
On Feb 9, 8:37 pm, cyrus.pilc...@xxxxxxxxx wrote:
Suppose we have an array of size N with positions 0 through n < N-1
already filled with data. (For simplicity, assume that the unfilled
positions were previously initialized to zero, and real data can never
be zero.) We want to insert a new value into position 0, so
everything else needs to be moved over to a higher index.
The obvious answer is to reverse the "sense" of your array so rather
than inserting at position zero you will be appending to the array.
Indeed. Although I might have said that the obvious answer was not to
use a language that made you deal with this yourself, this is a good
answer too.
Although, if for some bizarre reason you *really* don't want to store n,
the cost of searching an array for the lowest unused position is going
to be negligable, especially compared to copying every one of its
elements (which may itself be negligable, depending on how many elements
you're storing and how often you need to insert/delete an element).
Another issue with the copying approach is that without knowing the
number of elements currently in your array, you have no way of knowing
whether an insertion will overflow your array. If I've got a five
element array with all five positions filled, and I try to add another,
then the algorithm below will happily churn through the array until it
gets to index 4 and realizes that there's more data than storage
space. Actually, it won't even notice the problem, and will happily
overwrite whatever lies after arr in memory.
for (i=0; val1 !=0; i++) {
val2 = arr[i];
arr[i] = val1;
i++;
if (val2 == 0) break;
val1 = arr[i];
arr[i] = val2;
}
The above also contains some things that I consider to be bad style.
Messing with your loop counter inside the loop body is one. It's
confusing, error-prone, and easy to miss when you read the
code. Breaking from a loop is another. If you're using break in a loop,
it's a sign that perhaps your algorithm could be neater. The names val1
and val2 are ambiguous, and in fact the two variables switch jobs
halfway through the loop. A for loop is used when the actual termination
condition would be more clearly indicated by a while loop. If you
examine that code, it's basically packing two copies into each iteration
of the for loop, but you have to actually work the code on paper to find
that out. Something like:
#define ARRAY_SIZE 5;
int array[ARRAY_SIZE];
void
add_to_array(int new_value)
{
int i = 0;
int current = new_value;
int next;
while((i < ARRAY_SIZE) && (current != 0))
{
next = array[i];
array[i] = current;
current = next;
i++;
}
}
would be more to my liking. But notice that this code still suffers from
the fatal array overflow bug! It checks to make sure it's not writing
outside the array at least, but if the array fills up, too bad! The last
value is silently discarded, which is probably not the desired
behavior. It's possible to watch for this condition, copy everything
back, and return an error code when you discover that your data won't
fit, but actually doing so would be ludicrous!
In short, you REALLY, REALLY need to either store the array's fullness
or at least check it *before* you start copying.
#define ARRAY_SIZE 5;
#define PUSH_SUCCESSFUL 1;
#define PUSH_FAILED 0;
int array[ARRAY_SIZE];
int
add_to_array(int new_value)
{
int i;
int fullness = 0;
for (i = 0; i < ARRAY_SIZE; i++)
if (array[i]) fullness++;
if (fullness < ARRAY_SIZE)
{
array[fullness] = new_value;
return PUSH_SUCCESSFUL;
} else {
return PUSH_FAILED;
}
}
Of course, you should work any of my code on paper and unit test it if
you want to use it. I can't guarantee that stuff I type into posts
without testing will work as intended. And, now that I think of it,
counting down from the maximum array size would be slightly quicker when
the array is more than half full.
Since this was meant as a general programming question, I'll give a
general answer too. You seem to be worrying WAY too much about
efficiency, but in all the wrong places. You're willing to copy every
element in an array without even checking to make sure the array is big
enough first, but you're not willing to do the check or use the trivial
amount of memory it would take to keep track of your array's
fullness.
You need to focus more on generating correct, easy to read code before
you worry about optimization. And when you *do* optimize, ALWAYS profile
your code first, during, and after. Speculation about what code will
compile into is completely useless unless you are extremely familiar
with your compiler and with writing optimized assembly. Even then, what
matters is how fast it *actually* runs, and whether that speed is fast
enough just as it is. It may (probably will) turn out that most of the
routines that *could* be written more efficiently don't need to
be. Still, you do have to be aware when you're picking an algorithm
that's just plain bad. Copying a whole array on every single insertion
or deletion is never, ever going to be the most efficient choice.
.
- References:
- question about data movement
- From: cyrus . pilcrow
- Re: question about data movement
- From: Jeff Lait
- question about data movement
- Prev by Date: Re: question about data movement
- Next by Date: Re: stringification of numbers in C++
- Previous by thread: Re: question about data movement
- Next by thread: Re: question about data movement
- Index(es):
Relevant Pages
|
