Efficient list compacting
- by Patrik
Suppose you have a list of unsigned ints. Suppose some elements are equal to 0 and you want to push them back. Currently I use this code (list is a pointer to a list of unsigned ints of size n
for (i = 0; i < n; ++i)
{
if (list[i])
continue;
int j;
for (j = i + 1; j < n && !list[j]; ++j);
int z;
for (z = j + 1; z < n && list[z]; ++z);
if (j == n)
break;
memmove(&(list[i]), &(list[j]), sizeof(unsigned int) * (z - j)));
int s = z - j + i;
for(j = s; j < z; ++j)
list[j] = 0;
i = s - 1;
}
Can you think of a more efficient way to perform this task?
The snippet is purely theoretical, in the production code, each element of list is a 64 bytes struct
EDIT:
I'll post my solution. Many thanks to Jonathan Leffler.
void RemoveDeadParticles(int * list, int * n)
{
int i, j = *n - 1;
for (; j >= 0 && list[j] == 0; --j);
for (i = 0; i < j; ++i)
{
if (list[i])
continue;
memcpy(&(list[i]), &(list[j]), sizeof(int));
list[j] = 0;
for (; j >= 0 && list[j] == 0; --j);
if (i == j)
break;
}
*n = i + 1;
}
