123
-=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- (c) WidthPadding Industries 1987 0|37|0 -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=- -=+=-
Socoder -> C/C++/C#/Other -> Un-ugly my ReplaceString C function?

Wed, 22 Sep 2010, 10:14
HoboBen
So I've got this C function to replace any string (needle) with a string (replacement) within a string (haystack).

It works, with all the edge cases I've tried it against, and I think it's quite efficient as it doesn't allocate any memory other than one malloc for the result string.

But it's really, really verbose and ugly! Can anyone suggest improvements?

Usage:
printf("New string: %s\n", Pox_ReplaceString("great", "ok", "have a g grea great day and have a great day great"));

printf("New string: %s\n", Pox_ReplaceString("great", "fantastic", "have a g grea great day and have a great day great"));



(edit: For comparison, and because I feel like boasting, Cobra's Replace takes 1.929 seconds for 1000,000 iterations, Blitz3D takes 1.269, while mine takes 0.337 on a 0.6Ghz slower CPU! )

-=-=-
blog | work | code | more code
Wed, 22 Sep 2010, 12:13
Afr0
How comes Cobra's slower than Blitz3D?
Wed, 22 Sep 2010, 12:16
HoboBen
Cobra really falls down on string manipulation (although it's only ~50% slower than Blitz, hardly orders of magnitude, and string manipulation in *any* language is slow).

-=-=-
blog | work | code | more code
Wed, 22 Sep 2010, 13:45
Jayenkai
Looks very efficient!
Every time I find myself thinking "Why not use...", it's usually a basic String function that's the answer, and since I'm trying to avoid those (because, you obviously have, and I'm not going to argue with that!) then I can't seem to think enough to make it any neater!
or rather...
Not without plain compacting, and making things into those unreadable horrible one-line "double if" things.. eeuw!
At least this is vaguely readable!


I wonder..
In Cobra, if you switch to ascii character numbers, make an array of those numbers (like a C string does), then did this function style stuff to the numbers, and then flipped it back into a string afterwards... Would that prove to be any quicker than faffing about with the strings?

-=-=-
''Load, Next List!''
Wed, 22 Sep 2010, 13:55
HoboBen
@Jay, I've actually thought about re-implementing Cobra strings with banks (perhaps with UTF8 support), so that's an interesting idea and I may well attempt it soon.

StackOverflow couldn't come up with anything other than the fact that I can avoid strlen(haystack) since I'm looping through it anyway.

I'm mainly surprised by how long it is in terms of lines of code (three-and-a-half screens!), but nobody else seemed surprised (maybe that's normal for C!!!). I've got far more important functions that fit into ten lines, but I guess ReplaceString is heading to quite a low level compared to other functions.

For any future googlers, here's my revised version:



-=-=-
blog | work | code | more code
Wed, 22 Sep 2010, 14:28
Afr0
Unless you really mind mixing C and C++ code, you should be able (?) to use the boost::regex class to do what this function already does, but faster.


-=-=-
Afr0 Games

Project Dollhouse on Github - Please fork!
Wed, 22 Sep 2010, 14:51
Jayenkai
I don't think that was the point, Afr0.
Wed, 22 Sep 2010, 15:04
Afr0
Heh... he wanted suggestions of improvement. Apparently I read that as 'Suggestion of improvement either in terms of code or alternatives...!'

Oh well, I suggested an alternative at least!

-=-=-
Afr0 Games

Project Dollhouse on Github - Please fork!
Thu, 23 Sep 2010, 02:06
Cower
I'm not sure what you're using to get your timing, but try mine:



Interface is pretty much the same, so probably test-able. I'm just curious to see how it compares.
Thu, 23 Sep 2010, 06:43
HoboBen
Thanks Cower... I'm afraid yours seg faults after ~1000 iterations so I couldn't compare them. Here's my test (uncomment/comment parts in main() to see the difference):



-=-=-
blog | work | code | more code
Thu, 23 Sep 2010, 09:19
Cower
Interesting that it'd segfault only after so many iterations. O_o
Thu, 23 Sep 2010, 13:38
Cower
After fixing mine up a bit, it takes 12141ms for 10,000,000 iterations. So, that comes to about 0.0012141ms per call. Yours takes about 3680ms, which is about 0.000368ms per call, which is damned impressive. So, I modified mine:



Which resulted in this:


So about 0.000384ms per call on average for yours, and 0.000398ms for mine.

And the bit of code used for timing is incredibly primitive, so not a lot going on there.

Thu, 23 Sep 2010, 15:11
HoboBen
Thanks Cower

I'm very shocked that mine stood up to the test!

I also noticed, unless you wrap ReplaceString in free(), e.g.

free(ReplaceString("nice", "fantastic", s));

It will leak memory! (Especially over 10,000,000 iterations!)

-=-=-
blog | work | code | more code
Thu, 23 Sep 2010, 15:42
Cower
Leaking memory is fine for testing speed in this case.
Fri, 24 Sep 2010, 07:51
HoboBen
Got rid one of the calls to strlen... reasonably faster

|edit| Apparently this version is broken... I printf'd the wrong test! |edit|

-=-=-
blog | work | code | more code
Fri, 24 Sep 2010, 08:30
Cower
Only problem with your new version is it doesn't work. >_>



Aside from that, mine's currently faster at 0.000327ms per call:

|edit| Just shaved 100ms off the total |edit|


Fri, 24 Sep 2010, 08:58
HoboBen
The game is on!!!

Fixed my faster version, so that it actually works:



edit: Much slower than yours now though!

-=-=-
blog | work | code | more code
Fri, 24 Sep 2010, 10:03
Cower
New version, down to 0.000310 ms/call average.



Also added comments, but I don't think they'll help much.
Fri, 24 Sep 2010, 15:31
Afr0


Wait... I'm confused. How come dereferencing the pointer in this manner doesn't simply replace the content stored with '\0'?

-=-=-
Afr0 Games

Project Dollhouse on Github - Please fork!
Fri, 24 Sep 2010, 15:39
Cower
I'm not sure what you're asking. It does put a null character in, so I'm not entirely sure why you think it doesn't, or what it is you think it does...
Fri, 24 Sep 2010, 16:10
Afr0
Initially it looked to me like it would replace the entire string with '\0', but I suppose it only puts '\0' at the specific address in memory that you increased in the function...

-=-=-
Afr0 Games

Project Dollhouse on Github - Please fork!
Fri, 24 Sep 2010, 17:27
JL235
Afr0 but I suppose it only puts '\0' at the specific address in memory that you increased in the function...

Yes, I'm pretty sure it's doing this. The pointer refers to the beginning of the string and he's replacing it with '\0', so now the string is terminated right at the start (and so is empty).
Fri, 24 Sep 2010, 17:43
Cower
so now the string is terminated right at the start (and so is empty).

Wrong. Try again.
Sat, 25 Sep 2010, 07:35
HoboBen
Terminated at the end, I think.

Also, thanks v. much for commenting it, Cower - I understand it much better now.

-=-=-
blog | work | code | more code
Sun, 26 Sep 2010, 20:47
Afr0
Terminated at the end, I think.


Yeah, that's pretty much what I said. And obviously that's what's happening, I was just a little confused as to how it was happening.

-=-=-
Afr0 Games

Project Dollhouse on Github - Please fork!