void condense_by_removing (char *z_terminated, char char_to_remove)
{
int i, index;
for (i = 0, index = 0; i <= strlen(z_terminated); ++i) {
if(z_terminated[i] != char_to_remove) {
z_terminated[index++] = z_terminated[i];
}
}
}
int main ()
{
char dt[] = "Now is the winter of our discount tents";
condense_by_removing (dt, 'u');
printf ("%s\n", dt);
}
Points for the <= copying of the termination character :)
You do make two passes over the string (one for strlen and one for the copy loop), also you assume the compiler will optimize the caching of the return value of the strlen function, if it doesn't your performance will be horrible.
It's actually O(2n), so that works out to O(n) but it does have a 50% penalty, assuming an optimizing compiler.
Bwhite is not all wrong though, on a non-optimizing compiler you are hitting the string every time in the loop because of the strlen, and then it is O(n^2).
on a non-optimizing compiler you are hitting the string every time in the loop because of the strlen
In practice, what assumptions one should make here about optimizing compilers?
It seems like it would take a lot of compiler intelligence to figure out that even though we are modifying the string in place, we are never terminating the string, and thus strlen() remains constant. Thus my instinct would be to never use it in a loop like this.
But maybe current compilers are actually this smart? I just compiled with gcc -O3 and looked at the result with objump -S, but I'm not familiar enough with the assembly to figure out how it's handling things here.
By contrast, my instinct was to do this with in a single pass with two incrementing pointers. I'm not sure if the code is clearer (http://gist.github.com/416170), but at least the assembly turns out simple enough to read!
> In practice, what assumptions one should make here about optimizing compilers?
> It seems like it would take a lot of compiler intelligence to figure out that even though we are modifying the string in place, we are never terminating the string, and thus strlen() remains constant. Thus my instinct would be to never use it in a loop like this.
You're completely right, I just tried it on several gcc settings and it is O(n^2) every time. I thought the 'n' is invariant across the execution of the loop but it might be changed because we're modifying the string and the compiler realizes that and re-runs strlen every time.
> By contrast, my instinct was to do this with in a single pass with two incrementing pointers. I'm not sure if the code is clearer (http://gist.github.com/416170), but at least the assembly turns out simple enough to read!
That's pretty much what I sent in as a solution, and I figure there will be a lot of them isomorphic with yours.
Count on it, I am always very hesitant to post code on HN, realizing that if I'm not fresh or have tested the code that I'll be mercilessly hacked to little bits. It's fun though, I think my personal record is 5 bugs in 2 lines...
This is exactly why I contribute tens of thousands of lines to F/OSS projects.
Your mettle has never truly been tested until you have hundreds of developers, from around the world, pointing out your idiocy in an excruciatingly specific manner. After your ego has been throughly decimated, then you can improve.
This is closer to how I would do it in practice.
void condense_by_removing (char *z_terminated, char char_to_remove)
{
char *next = z_terminated;
while (1) {
while (*z_terminated == char_to_remove) ++z_terminated;
if (!(*next++ = *z_terminated++) ) break;
}
}
This won't work, if the first char of z_terminated == char_to_remove.
I have a similar solution farther down the page. Not many people seem to like doing it with pointer manipulation.
EDIT: We should both probably add
if(!char_to_remove) return;
at the top since we'll get a seg fault if someone tries to be sneaky and passes the zero-terminator. And then might as well check if z_terminated is NULL while we're at it. Or is there a better way to handle it?
Apropos your first example it really was O(n^2) all the time, I just ran a bunch of tests on various optimization settings and the strlen gets called every iteration of the loop.
void condense_by_removing (char *z_terminated, char char_to_remove) { int i, index;