Back to For Beginners

which would be best?

For Beginners

Started by vaneger December 23, 2009 12:36 PM

11 comments, last by alvaro 14 years, 4 months ago

vaneger

100

Author

December 23, 2009 12:36 PM

I have a scoring function that compares two vectors and returns a % of how closely they match. It gets called alot, so I'm trying to figure out the best way to code it for speed. currently it looks like this :


float score(vector<char> &goal,vector<char> &test)
{
	int i = 0;
	float score = 0.000;
	for(i=0;i<1024;i++)
		if(test == goal)
			score++;
	return( (score / 1024.000) * 100.000 );

}

but would something like this be faster ?


float score(vector<char> &goal,vector<char> &test)
{
	int i = 0;
	float score = 0.000;
	for(i=0;i<1024;i+=4)
        {
	     if(test == goal)
		score++;
	     if(test[i+1] == goal[i+1])
               score++;
	     if(test[i+2] == goal[i+2])
               score++;
	     if(test[i+3] == goal[i+3])
               score++;
        }
	return( (score / 1024.000) * 100.000 );

}

Nanoha

2,682

December 23, 2009 12:41 PM

I'd guess they were just as fast/slow as one an other just the second one is pointlessly complicated.

You need to compare each pair in turn and increment a counter if their equal, not really alot you caan do to speed that up. If you could describe what your doing perhaps there's a faster way to do this.

Interested in Fractals? Check out my App, Fractal Scout, free on the Google Play store.

rip-off

11,000

December 23, 2009 12:47 PM

How do the vectors change over time? If they change infrequently, you might be able to cache the results and only recalculate when the values change.

Are the vectors sliding windows? You might be able to keep track of the number of matches that are added and removed rather than iterating across the entire array.

Quote:
but would something like this be faster ?

You need to profile the new and old version, and to compare the results. It might be insightful to look at the generated assembly under a variety of compiler switches.

blog | twitter

vaneger

100

Author

December 23, 2009 12:58 PM

I am taking a vector of chars and swapping section x....x+3 with section y....y+3 and attempting to sort the vector in the fewest swaps possible.

Wan

1,366

December 23, 2009 01:05 PM

Quote:Original post by vaneger
It gets called alot

I think that's the crux of the problem, the operation itself is simple in fairly inexpensive. Somehow removing the need to compare all the elements every single time would be the most obvious improvement.

Quote:but would something like this be faster ?

Well, you can speed this up: [wink]

return (score / 10.24f); *

* Jokes aside, obviously any reasonably smart compiler would already optimize this in some way, especially with a power of two division in there.

shultays

187

December 23, 2009 01:29 PM

I am pretty sure it would be slower

but difference between them would be very small.

MAybe you should do that, whenever you change a value in arrays, recalculate score but you don't have to scan the whole list again. just check the element you are changing. something like

int score;void changeelement(int i, int newvalue){  if(test == goal){    score--; //if they were equal before changing the value decrease the score  }  test = newvalue; //or goal = newvalue  if(test == goal){    score++; //if they are equal after changing the value increase the score  }}

but if you recrate the vertices rather than changing single values this would be even slower

taytay

vaneger

100

Author

December 23, 2009 02:58 PM

so how do i properly profile the code ? I dont have any profiling programs, so what do i need to do to make my own profiling code?

nobodynews

3,128

December 23, 2009 04:30 PM

You should be asking "what profiler application can I get for free and, if none exists, how can I make my own profiling code?" By searching for "Free C++ Code Profiler" the first result showed this. Unless there's a reason you can't use a free piece of software. Even if you don't have an AMD processor you can still use it, I believe.

C++: A Dialog | C++0x Features: Part1 (lambdas, auto, static_assert) , Part 2 (rvalue references) , Part 3 (decltype) | Write Games | Fix Your Timestep!

DevFred

840

December 23, 2009 04:39 PM

There is no point in scaling, just return score; directly.

vaneger

100

Author

December 23, 2009 10:34 PM

I grabbed verySleepy from a link in that site that was posted.

it seems 45% of my time is spend on vector operator[] and 45% is spent on vector begin().
out of my own code 8% is spent on score() no matter which version I use.

So now I'm writing up an evaluation function that will determine if a 4 index section has 2 or more items that can be placed in order and if so then I'll move forward with swapping and scoring.

which would be best?

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

which would be best?

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Reticulating splines