3 ms·

Interesting. I didn't try to do the assignment when I read the first part, but just tried it now before looking at the second part. When I started to write the

by anatoly 16y ago

Interesting. I didn't try to do the assignment when I read the first part, but just tried it now before looking at the second part. When I started to write the main loop, I felt uneasy when I realized I'd be doing unnecessary copying in the common case when char_to_remove is never found. My code ended up a tad more complex than yours due to desire to avoid that: void condense_by_removing(char *z_terminated, char char_to_remove) { char *p = z_terminated; for (; *z_terminated != 0; ++z_terminated) { if (*z_terminated != char_to_remove) { if (z_terminated != p) *p = *z_terminated; p++; } } if (*p != 0) *p = 0; }

dkersten 16y ago
This is what I came up with, but I'm not a C programmer. void condense_by_removing(char* z_terminated, char char_to_remove) { int index; int write = 0; for (index = 0; z_terminated[index]; ++index) { if (z_terminated[index + write] == char_to_remove) { ++write; } if (write > 0) { z_terminated[index] = z_terminated[index + write]; } } } Or, getting rid of index: void condense_by_removing(char* z_terminated, char char_to_remove) { int write = 0; for (; *z_terminated; ++z_terminated) { if (*(z_terminated + write) == char_to_remove) { ++write; } if (write > 0) { *z_terminated = *(z_terminated + write); } } }
- anatoly 16y ago
  I see what you're trying to do, but it won't work this way. Since your termination condition is z_terminated[index], you must never look beyond index, yet you access [index+write]. This alone means the code's buggy. The second version is similarly flawed. Note that your code instantly becomes much easier to understand if you rename the variable 'write' to 'gap'.
  - dkersten 16y ago
    Ehh, good point. :-/ The second version is identical to the first, except that it ises the z_terminated pointer instead of a separate index. void condense_by_removing(char* z_terminated, char char_to_remove) { int gap = 0; for (; *(z_terminated + gap); ++z_terminated) { if (*(z_terminated + gap) == char_to_remove) { ++gap; } if (gap > 0) { *z_terminated = *(z_terminated + gap); } } *z_terminated = 0; } Interestingly enough, if I try to remove the common *(z_terminated + gap) expression (which a good compiler should do for me..), I end up with a two pointer version similar to yours.
    - RiderOfGiraffes 16y ago
      Have you sent it in? You should ...
      - dkersten 16y ago
        I missed your post the first time around and only did that today, so I assumed it was too late to send in.
    - deleted 16y ago
      [deleted]
    - dkersten 16y ago
      Replacing the 3 additions of gapin the loop with a single subtraction (and an increment): void condense_by_removing(char* z_terminated, char char_to_remove) { int offset = 0; for (; *z_terminated; ++z_terminated) { if (*z_terminated == char_to_remove) { ++offset; ++z_terminated; } if (offset > 0) *(z_terminated - offset) = *z_terminated; } *(z_terminated - offset) = 0; }
RiderOfGiraffes 16y ago
Have you sent that in? You should ...
nkurz 16y ago
This might be a case where one should benchmark before making changes that make the code more complex. I just threw your code your code into a thrown together cycle counter, and on my system it performs significantly worse than the straightforward solution. My test harness isn't perfect, but with "gcc -O3" on a Core i7, I get something like 20000 cycles to 'condense' a 4096 character random string with the suggested loop, versus 26000 with your more complex approach. With a 4096 character string set up to never contain char_to_remove, I get a practically identical 19500 cycles with both approaches. Thus there seems to be no benefit to the greater complexity.

by anatoly 16y ago

dkersten 16y ago

This is what I came up with, but I'm not a C programmer. void condense_by_removing(char* z_terminated, char char_to_remove) { int index; int write = 0; for (index = 0; z_terminated[index]; ++index) { if (z_terminated[index + write] == char_to_remove) { ++write; } if (write > 0) { z_terminated[index] = z_terminated[index + write]; } } } Or, getting rid of index: void condense_by_removing(char* z_terminated, char char_to_remove) { int write = 0; for (; *z_terminated; ++z_terminated) { if (*(z_terminated + write) == char_to_remove) { ++write; } if (write > 0) { *z_terminated = *(z_terminated + write); } } }

anatoly 16y ago
I see what you're trying to do, but it won't work this way. Since your termination condition is z_terminated[index], you must never look beyond index, yet you access [index+write]. This alone means the code's buggy. The second version is similarly flawed. Note that your code instantly becomes much easier to understand if you rename the variable 'write' to 'gap'.
- dkersten 16y ago
  Ehh, good point. :-/ The second version is identical to the first, except that it ises the z_terminated pointer instead of a separate index. void condense_by_removing(char* z_terminated, char char_to_remove) { int gap = 0; for (; *(z_terminated + gap); ++z_terminated) { if (*(z_terminated + gap) == char_to_remove) { ++gap; } if (gap > 0) { *z_terminated = *(z_terminated + gap); } } *z_terminated = 0; } Interestingly enough, if I try to remove the common *(z_terminated + gap) expression (which a good compiler should do for me..), I end up with a two pointer version similar to yours.
  - RiderOfGiraffes 16y ago
    Have you sent it in? You should ...
    - dkersten 16y ago
      I missed your post the first time around and only did that today, so I assumed it was too late to send in.
  - deleted 16y ago
    [deleted]
  - dkersten 16y ago
    Replacing the 3 additions of gapin the loop with a single subtraction (and an increment): void condense_by_removing(char* z_terminated, char char_to_remove) { int offset = 0; for (; *z_terminated; ++z_terminated) { if (*z_terminated == char_to_remove) { ++offset; ++z_terminated; } if (offset > 0) *(z_terminated - offset) = *z_terminated; } *(z_terminated - offset) = 0; }

RiderOfGiraffes 16y ago

Have you sent that in? You should ...

nkurz 16y ago

This might be a case where one should benchmark before making changes that make the code more complex. I just threw your code your code into a thrown together cycle counter, and on my system it performs significantly worse than the straightforward solution. My test harness isn't perfect, but with "gcc -O3" on a Core i7, I get something like 20000 cycles to 'condense' a 4096 character random string with the suggested loop, versus 26000 with your more complex approach. With a 4096 character string set up to never contain char_to_remove, I get a practically identical 19500 cycles with both approaches. Thus there seems to be no benefit to the greater complexity.