Help with optimizations
Author
[size=2]Here is the test: You have an std::vector full of random numbers and some of the numbers are repeated several times randomly. You must find the most efficient[size=2] way to create another vector with all numbers in the list referenced[size=2] only once and ordered from the lowest to the highest.
std::sort followed by std::unique, done. (For better performance you might want to use unique_copy to avoid O(n^2) complexity).
Or just create a set from the data:
std::set<int>(input.begin(), input.end());
The set doesn't allow duplicates, and uses a binary search tree to sort from low to high.
std::set<int>(input.begin(), input.end());
The set doesn't allow duplicates, and uses a binary search tree to sort from low to high.
Or you take Washu's C++ Quiz
I swear, if you get them all straight, I'll buy you a drink
I swear, if you get them all straight, I'll buy you a drink
std::sort followed by std::unique, done. (For better performance you might want to use unique_copy to avoid O(n^2) complexity).
std::unique has O(n) complexity.
Author
Or just create a set from the data:
std::set<int>(input.begin(), input.end());
The set doesn't allow duplicates, and uses a binary search tree to sort from low to high.
std::set definitely appears to be the best way to do it. Now I need a way to get a vector of the locations of values within the first vector that match the given set.
Example: {5,3,2,1,2,5}
Search: 5
Result: {0,5}
Author
Or just create a set from the data:
std::set<int>(input.begin(), input.end());
The set doesn't allow duplicates, and uses a binary search tree to sort from low to high.
I know this is going to sound stupid but how do I read an item from the set? Tried this but it does not work:
DWORD foo= *(theSet.begin() + n);EDIT: This works:
DWORD foo= (DWORD)(&theSet+(n*sizeof(DWORD)));However I assume there must be a better way?...
You know, if you actually had a question you'd probably be better off phrasing your thread title as something other than a pissing contest. In any case, how you read elements from a set depend on how you want to use it. If you're iterating through the elements then you'd use a standard iterator loop:
for (SetType::iterator i = my_set.begin(); i != my_set.end(); ++i) {
// do something with *i
}
Author
You know, if you actually had a question you'd probably be better off phrasing your thread title as something other than a pissing contest. In any case, how you read elements from a set depend on how you want to use it. If you're iterating through the elements then you'd use a standard iterator loop:
for (SetType::iterator i = my_set.begin(); i != my_set.end(); ++i) {
// do something with *i
}
Yeah I already had code that did that and knew there must be a way to optimize it. I should have just tiled it something like "optimize this." Anyway, I was basically trying to create separate index buffers for each subset of my mesh given an attribute buffer.
Here is what I have now:
// Create Index buffers.
std::set<DWORD> usedAttributes(attributes.begin(), attributes.end());
std::vector<std::vector<Ovgl::Face>> index_subsets;
index_subsets.resize(usedAttributes.size());
for( unsigned int i = 0; i < attributes.size(); i++ )
{
unsigned int s = 0;
for( std::set<DWORD>::iterator j = usedAttributes.begin(); j != usedAttributes.end(); ++j)
{
if( attributes == *j )
{
index_subsets[s].push_back(faces);
}
s++;
}
}See anything I can do to optimize that?
std::unique has O(n) complexity.
Oh yeah, true that. I blame being tired for thinking of such a naive implementation.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
