Jump to content
  • Advertisement
Sign in to follow this  
Alessandro

C++: alternative to std::find

This topic is 2526 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

I need to search into a std::vector<int>, with a size of about 20000. The search needs to be done in opengl-application main loop, and it's extremely slow.
This is my code:


std::vector<int> folliclesArray;

for (int i=0; i<LIMIT; i++)
{
iter = std::find(folliclesArray.begin(), folliclesArray.end(), i);
if (iter!=folliclesArray.end()) dosomething();
}


Please tell me there are alternatives to to this search faster. I've read that std::map would allow to improve perfomances, but didn't understand how to implement that.
Or, would a simple dynamic array be faster than a std::vector ?

Thanks

Share this post


Link to post
Share on other sites
Advertisement
Do you know anything about the contents of the array? Is it sorted? std::vector and a manually managed dynamic array will have almost the same performance in release mode. There may be additional overhead in a debug build, but that overhead is generally due to checks that are appropriate for debug execution.

Share this post


Link to post
Share on other sites
Hi SiCrane, yes the vector content is sorted. I modified the OP code so that maybe it's more understandable what I'm trying to do.

Share this post


Link to post
Share on other sites
Generally speaking, it's ill-advised to do any searches or in some cases sorts in a realtime application (such as a opengl application where you have a desired framerate)

When you hit an array or vector of that size, it will simply take to long to iterate through it every loop to do a search.

So i would suspect you have a design issue rather than looking for a programming solution via alternative method.

Some of the things you need to look at when iterating through alot of elements:

1) how often does this vector change size or sorted (gets re-indexed)?
2) Can you find what you are looking for once, then keep track of that element's index (inserts or deletes after the index are irrelevant, it's only changes < the index)? aka caching the results...
3) do you have to search and iterate every single loop? would every other loop suffice?
4) since your vector is sorted a binary search will be as fast as a map.

I like to deal with vectors almost exclusively and I do everything in my power to reduce the amount of searches and sorts that I possibly can.

Here is a small sample code that might assist you (this is not my code):


int value_to_find;
vector<int> cont; // main container
map<int, size_t> contPos; // position cache
// first see if the value is in cache
map<int, size_t>::const_iterator foundCache = contPos.find(value_to_find);
if (foundCache != contPos.end()) {
do_this();
}
// not in cache, now do brute force search
vector<int>::const_iterator found = cont.find(value_to_find);
if (found != cont.end()) {
// cache the value with its position
contPos[value_to_find] = found - cont.begin();
do_this();
} else { // in neither
do_that();
}

Share this post


Link to post
Share on other sites
In this case, it'd probably just be easiest, instead of searching from the beginning each time, set iter to begin() once, and search from iter to end. If your vector is already sorted, this would prevent you from searching the whole thing every single time. Probably use std::lower_bound for search instead as well.

Share this post


Link to post
Share on other sites
It's also worth ensuring that you have the debugging features of your C++ library disabled. For Visual C++, set _SECURE_SCL=0 and ensure _HAS_ITERATOR_DEBUGGING isn't defined.

Edited to add: there might be a way of avoiding the search entirely. How do you know which values to search for? Can you rearrange your algorithm to know about indices in to the vector/array, rather than values that must be found?

Alternatively, do the ints in the vector have a high degree of contiguity? If so, you could perhaps reduce the number of elements (and therefore work needed to perform a search) by storing ranges? e.g.


struct range
{
int first;
int last;
};

Share this post


Link to post
Share on other sites
[font=courier new,courier,monospace]std::[/font][color=#000000]

[font=courier new,courier,monospace]binary_search[/font] ?

Share this post


Link to post
Share on other sites
Does "dosomething" modify the container? Is there a reason you are doing the same lookup LIMIT times? There might be a higher level change you can make, if you were to give us more information.

Is there any patterns you can take advantage of in your follicles vector? As edd[sup]2[/sup] shows, if it consists of contiguous chunks you could model it as ranges. If it has lots of duplication, then some kind of run length encoding storing (value, count) might be more efficient.

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.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!