If no-one has already done it I think it's probably optimal to keep two pointers, one to the next available empty position, one to the current position being checked;

for(int current=0, available=0; current<array.length; current++) {
_if(array[current]!=0) {
__array[available]=array[current];
__available++;
_}
}

forgot also needed to clear out the rest:
do {
_array[available]=0;
} while(++available < array.length);
Should still be O(n) though, if it works

<?php

$array = array();
for($length=0; $length<1000; $length++)
$array[] = rand(0,1);

print 'Unsorted: '.implode(', ',$array).'
';

for($current=0, $available=0; $current<$length; $current++)
if ( $array[$current] != 0 ) {
$array[$available] = $array[$current];
$available++;
}

do {
$array[$available]=0;
} while ( ++$available < $length );

print 'Sorted: '.implode(', ',$array);

die();
?>

Yay, what do I win?

.. oh :-|

if you can sort in php faster than the C# you get a cookie...

<?php

$array = array();
for($length=0; $length<1000; $length++)
$array[] = rand(0,1);

print 'Unsorted: '.implode(', ',$array).'
';
sort($array);
print 'Sorted: '.implode(', ',$array);
?>

(p.s. before this becomes a silly language war I prefer C# to PHP generally, but for 10-liners PHP is easier)

But this wasn't a sorting algorithm. He just wants "white space" values removed.

But I agree with Kestas that a double counter is the *most* efficient means to do this.

Kestas +1

Slight aside, but what language are the php core functions written in?

Probably C++, or Perl which was written in C++ considering PHP is basically scripted Perl.

Actually, if you are using a basic C array, it would be faster to use actual pointers so you aren't doing so much pointer arithmetic each time you use [ ]. Also, ++variable is faster than variable++ so might as well use it when you don't need the original value returned.

I would go with something like this if efficiency is really important.


short array[1000];

// randomly fill array here!!!
//

short * current = &array;
short * available = current;
short * end = current + countof(array);

for ( ; current < end; ++current)
{
__if (*current != 0)
__{
____*available = *current;
____++available;
__}
}

for ( ; available < end; ++available)
{
__++available;
}

I had never heard the pre increment was faster than post increment. Is that true? And have you tried running this? You have tow unattached for loops (i.e. they aren't nested). I don't think it will work.

Yeh sorry, quick google says it is C, with many of the extensions in C++

My code is just a minor modification of kestas' code to use pointers instead of indexes. But I did totally mess up my second loop. Should be...

for ( ; available < end; ++available)
{
__*available = 0;
}

In any case, think about what ++var does versus var++. ++var just increments the value and returns it. var++ has to store aside the original value, then increment the variable, and then return the original value.

By the way, am I the only one here who puts the { on a new line? I really dislike having them at the end of the line.

no language war, though i was going to write the cookie generating script in php, if that is seen as language bias then so be it! :'(

and Ald, i prefer your, {} on new lines, style. Though i don't think the forum is the best place to try it out...

> Slight aside, but what language are the php core functions written in?
Yup C & C++, a weakness in terms of security but often a strength in terms of speed

> Probably C++, or Perl which was written in C++ considering PHP is
> basically scripted Perl.
I don't think Zend has ever used anything remotely related to Perl, except perhaps Perl compatible regular expressions (and I know and like PHP and Perl)

@Alderian I usually do that in large blocks of code where there's lots of space, I think it looks neat when you've got lots of comments etc, but for smaller stuff I usually put it on the same line. I like either way

(No comment on whether ++foo or foo++ is quicker though, I think with modern processors it's probably not much of an issue but I may be wrong)

True. And maybe it gets optimized out in any case when it detects you aren't doing anything with the return value.

foo++ v. ++foo

foo++ returns value then increments existing variable
++foo increments existing variable then return value

Same number of operations, just an issue of order. Maybe in the guts, it has to set aside the original value for the return, but this is a single move operation that takes nanoseconds on a modern processor.

But it has been a few years since I worked in C and pointers are no longer my forte (never really were). Wanna explain why it is right and what the prupose of the last loop on available is for?

Sure. Keep in mind that these variables are defined outside the for loops so exist after the for loop. current and available are both initialized to the start of the array. (I have &array but should really be &array[0], sorry I was in a hurry.)

The first for loop takes increments the current pointer from one end of the array to the other. But the available pointer is only incremented when a non-zero value is found, so it may not have made it to the end of the array

The second for loop just picks up where the first one ended with regard to the available pointer and increments it to the end of the array.

So let's say you have 0, 1, 0, 1. After the first for loop, the array now looks like 1, 1, 0, 1 and available is pointing at the third entry. The second for loop clears the 3rd and 4th entries.

Again, I was just copying Kesta's code and changing it to use pointers instead of array indexes. Really this could be further simplified...

short array[1000];
short * available;
short * current;
short * end = &array[0] + countof(array);

srand(13);
for (current = &array[0]; current < end; ++current)
{
__*current = rand() % 2;
}

for (current = available = &array[0] ; current < end; ++current)
{
__if (*current != 0)
__{
____*available = *current;
____*current = 0;
____++available;
__}
}

And I suppose &array[0] is redundant and I can just use array. For some reason I always try using &array which the compiler errors out on and then I add [0] instead of removing the &.

So lets say you have 0, 1, 3, 9, 0, 4

Following your code you get 1,3,9,4,0,4 then the second loop clears it. Not bad. I like it and it is very efficient, even more so than mine I think and not just because of the pointers, which not every language takes advantage of.

regarding pre and post incrementers: I think the biggest difference is when you're implementing your own types and overloading their operators. The implementation for post requires an additional copy of your class which will be returned, while you then increment your instance. pre inc is just incrementing your instance and returning it - no additional copies. So it's preferable to use the pre unless you specifically WANT the post (I think I've needed that 6 times in 20 years). if you're just looking to increment it though, then pre is more efficient.

fuck off!!

@Alamothe - What's your problem, man?

I'm guessing that Z knows that alamothe hates it when programmers talk about different ways to program things so posted this post just to piss alamothe off. If so, mission succeeded!

But I suppose I could be wrong. :)

> not just because of the pointers, which not every language takes advantage of.

Almost every language has pointers, some of them just call them references. Understanding pointers is integral to understanding how to program.

alamothe's last name must be Massingill