Jump to content
  • Advertisement
Sign in to follow this  
clearly

writing more effective code

This topic is 4516 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

how can i make this code more effective? http://rafb.net/paste/results/eVM0Go11.html i am trying to learn how to write an effective codes.. anyway can any one tell me how can i make this code more effective?

Share this post


Link to post
Share on other sites
Advertisement
#include <iostream>
#include <string>

int main()
{
std::string body = "ovr here over her over hre over here.";
std::string::size_type count = body.find("over here");

if(count == body.npos)
{
std::cout << "Couldn't find string" << std::endl;
}
else
{
std::cout << count << std::endl;
}

return 0;
}



Edit: Bah, ToohrVyk noticed the int vs. size_type before I managed to edit =)

Share this post


Link to post
Share on other sites
Determine if substring finding is what you need (as opposed, to lexing or tokenizing, for instance).

Use std::string.find and profile to see if it constitutes the bottleneck of your program. It probably isn't, so leave it at that.

If std::string.find is too slow, try another STL implementation, such as STLPort, which can be faster.

If it's still too slow, you can try to spend a few weeks writing and testing and debugging a program that may or may not be faster than the STL (usually isn't). The first step is to look into Rabin-Karp, Knuth-Morris-Pratt and Ukkonen's approach to suffix trees, which all have better complexity than your naive search (linear as opposed to quadratic). Implement all three, find the fastest one. Check that it is faster than std::string.find (which probably won't be the case) and keep all four versions around wrapped in a nice abstraction just in case you want to change your mind later on.

Oh, and strlen is faster than Size_Of, and it does not contain bugs.

In general, writing efficient code works as such:

  1. Determine what best suits your needs.
  2. Use a library-provided function to perform it.
  3. Once it works, determine if it is fast enough. If it is, concentrate on optimizing slower parts of the program.
  4. If it is too slow, learn the fastest algorithms around, and adapt them conceptually to your case.
  5. Implement, test, profile. If you succeded in writing faster code, keep it, otherwise revert to the library-provided function or try again.


EDIT: Zao, you meant string::size_type instead of int [rolleyes]

Share this post


Link to post
Share on other sites
nooo you got it all wrong..
i wanted to build a function that will show where the string starts at.. in another string..
i only asked if theres a way to make if more effective..

btw.
if ill use strlen on the function it wont work good cuz its a pointer..

Share this post


Link to post
Share on other sites
Looking at your code, you seem to be trying to avoid using any standard library functions. Is this correct?

If so, I would say the following: it is commendable as a learning exercise to do this sort of thing but you need to bear in mind that standard library implementations can be far more advanced than straightforward C. For example they can take advantage of hardware support and be implemented in assembly.

With this in mind, if you are implementing something like this yourself, your goal should be to make it as clearly readable and reliable as possible, not as fast or efficient as possible, since you will be unlikely to compete with the standard library implementation on these grounds.

I'm not knocking the attempt if it is for an exercise, but if it is for a real application, please bear the above in mind.

HTH Paul

Share this post


Link to post
Share on other sites
Quote:
Original post by clearly
btw.
if ill use strlen on the function it wont work good cuz its a pointer..


Huh? Please clarify.

Share this post


Link to post
Share on other sites
Quote:
Original post by clearly
nooo you got it all wrong..
i wanted to build a function that will show where the string starts at.. in another string..
i only asked if theres a way to make if more effective..

btw.
if ill use strlen on the function it wont work good cuz its a pointer..


strlen will work on pointers.

Anyway I'd make the following improvements (assuming you intentionally avoided library functions) :

// Correct C++: You need to include this for std::cout
#include <iostream>

// Optimization/Const correctness: You can declare the parameter const to make sure you don't modify it, this
// might also make the compiler capable of doing additional optimizations.
long int Size_Of(const char *string)
{
//for (int num=0; *string; *string++,num++);
// Correct C++: num has to be declared outside the for loop for it to be available to the return-statement.
// Some older compilers will allow you to acces num outside its scope.
int num;
// Optimization: prefix ++ is faster than postfix.
// Optimization: No need to dereference the string.
for( num = 0; (*string); ++string,++num);
return num;
}

// Optimization/Const correctness: You can declare the parameters const to make sure you don't modify them, this
// might also make the compiler capable of doing additional optimizations.
long int Find_String_In_String(const char *string,const char *full_string)
{
const int Size_Of_String = Size_Of(string);

// Optimization: prefix ++ is faster than postfix.
// Optimization: No need to dereference the string.
for (int count=0;*full_string;++full_string,++count)
{
// Correct C++: second_count has to be declared outside the for loop for it to be available to the return-statement.
// Some older compilers will allow you to acces second_count outside its scope.
int second_count;
// Optimization: prefix ++ is faster than postfix.
// Optimization: No need to dereference the string.
// Bug: The element psat the last element full_string and string might be dereferenced
// Fix: Start by checking the current *string isn't 0
for (second_count=0;*string &&*full_string == *string &&
*full_string+1 == *string+1 ;++string,++full_string,
++second_count,++count);


if (second_count == Size_Of_String) return count-Size_Of_String;

// Cleaning..
//for (;second_count > 0;second_count--,string--);
// Optimization: second_count and string have been incremented an equal amount of times, so the following is faster:
string -= second_count;
second_count = 0;
}
return -1;
}

int main()
{
int count;
count = Find_String_In_String("over here","ovr here over her over hre over here.");
// Correct C++: cout is in namespace std, so the name is std::cout
if (count < 0)
std::cout << "Couldn't find string";
else
std::cout << count;

return 0;
}

Share this post


Link to post
Share on other sites
i did it only for an exercise.
thanks to all those who showed me how can i make it better..
b.t.w
i ment that u cant use strlen on a pointer like that:

long int Size_Of(char *string)
{
return strlen(string);
}
because it will return the wrong value.


[Edited by - clearly on July 6, 2006 7:19:08 AM]

Share this post


Link to post
Share on other sites
Am I the only one who thinks the bold part is just wrong (in the sense that it doesn't do what the author intended it to)?

for (second_count=0;*string && *full_string == *string &&
*full_string+1 == *string+1 ;++string,++full_string,
++second_count,++count);

I.e. *full_string == *string => *full_string+1 == *string+1 [lol]
Apart from the whole pointer-arithmetic crap that even Intel engineers recommend against ("avoid pointer arithmetic if possible").
Oh, and even though I agree on using pre-increment rather than post-increment in for-loops, this won't do squat to the generated code. There are no side-effects and this is actually a POD. ++count and count++ will generate the same code (at least in release mode).

But back to the offendng statement. For those who still didn't see what I meant:
*full_string evaluates to full_string[0], what does *full_string+1 [sic!] evaluate to?
Right! full_string[0] + 1 [smile].
Substituting "*full_string" and "*string" for A and B results in A == B && (A+1) == (B+1). Well if A equals B and A+1 does not equal B+1, we have a serious hardware problem [lol]

Cheers and use your time to improve your code at the right places (i.e. style, correctness, reliability and readability) instead of taking wild guesses on how to to squeeze a few clocks more out of some code that will probably fall into the 80% subset that the 80:20-rule suggests [wink].

Share this post


Link to post
Share on other sites
Quote:
Original post by clearly
b.t.w
i ment that u cant use strlen on a pointer like that:

long int Size_Of(char *string)
{
return strlen(string);
}
because it will return the wrong value.


Um... yes you can. strlen returns size_t which I'm wildly guessing might be the source of your confusion but it will implicitly convert to int in most realistic cases.


long Size_Of(char *string) // long is the same as long int by the way
{
return static_cast<long>(strlen(string)); // will get rid of warnings
}




This value will only be wrong if the length of the string is greater than the maximum value for a positive long integer, which is very big indeed.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!