如何有效地比较向量与C ++？ [英] How to efficiently compare vectors with C++?
问题描述
我需要为C ++中的向量比较函数进行微优化的建议，
它比较两个向量的元素的相等和顺序无关紧要。
template< class T>
static bool compareVectors（const vector< T& a，const vector< T>& b）
{
int n = a.size
std :: vector< bool> free（n，true）;
for（int i = 0; i
for（int j = 0; j< n; j ++）{
if（free [j]& a [i] == b [j]）{
matchFound = true;
free [j] = false;
break;
}
}
if（！matchFound）return false;
}
return true;
}
此函数被大量使用，我正在考虑可能的优化方法。
你能给我一些建议吗？我使用C ++ 11。
感谢
它只是意识到，这个代码只是一种设置等价检查（现在我看到你实际上说，我是一个糟糕的读者！）。这可以简化得多。
template< class T>
static bool compareVectors（vector< T> a，vector< T> b）
{
std :: sort（a.begin（），a.end（））;
std :: sort（b.begin（），b.end（））;
return（a == b）;
}
您需要包含 / code>。
如果你的向量总是相同大小，你可能想在方法开头添加一个断言：
assert（a.size（）== b.size（））;
如果对错误的长度执行此操作， / p>
否则，如果向量长度不等，则向量不能相同，因此只需添加
if（a.size（）！= b.size（））
{
return false;
}
这个技术上的复杂性是 O（n * log（n））因为它主要依赖于排序（通常）是那种复杂性。这比你的 O（n ^ 2）方法更好，但可能会由于所需的副本更糟。如果您的原始向量可以排序，这是不相关的。
如果你想坚持你的方法，这里是我对此的想法：
您可以使用 std :: find b
$ b
template< class T>
static bool compareVectors（const vector< T& a，const vector< T>& b）
{
const size_t n = a.size //使其为const和unsigned！
std :: vector< bool> free（n，true）;
for（size_t i = 0; i
bool matchFound = false;
auto start = b.cbegin（）;
while（true）
{
const auto position = std :: find（start，b.cend（），a [i]）;
if（position == b.cend（））
{
break; //没有找到
}
const auto index = position - b.cbegin（）;
if（free [index]）
{
//找到空闲对
free [index] = false;
matchFound = true;
break;
}
else
{
start = position + 1; // search in the rest
}
}
if（！matchFound）
{
return false;
}
}
return true;
}
另一种可能性是将结构替换为存储空闲位置。你可以尝试一个 std :: bitset 或者只是将使用的索引存储在向量中，并检查匹配是否不在索引向量中。如果这个函数的结果通常是相同的（所以大多数是真的或大多是假的），你可以优化你的数据结构来反映这一点。例如。如果结果通常为false，我将使用已使用的索引列表，因为只需要存储少量索引。
此方法与您的方法。使用std :: find搜索东西有时比手动搜索更好。 （例如，如果数据被排序并且编译器知道它，则这可以是二进制搜索）。
I need advice for micro optimization in C++ for a vector comparison function, it compares two vectors for equality and order of elements does not matter.
template <class T>
static bool compareVectors(const vector<T> &a, const vector<T> &b)
{
int n = a.size();
std::vector<bool> free(n, true);
for (int i = 0; i < n; i++) {
bool matchFound = false;
for (int j = 0; j < n; j++) {
if (free[j] && a[i] == b[j]) {
matchFound = true;
free[j] = false;
break;
}
}
if (!matchFound) return false;
}
return true;
}
This function is used heavily and I am thinking of possible way to optimize it. Can you please give me some suggestions? By the way I use C++11.
Thanks
It just realized that this code only does kind of a "set equivalency" check (and now I see that you actually did say that, what a lousy reader I am!). This can be achieved much simpler
template <class T>
static bool compareVectors(vector<T> a, vector<T> b)
{
std::sort(a.begin(), a.end());
std::sort(b.begin(), b.end());
return (a == b);
}
You'll need to include the header algorithm.
If your vectors are always of same size, you may want to add an assertion at the beginning of the method:
assert(a.size() == b.size());
This will be handy in debugging your program if you once perform this operation for unequal lengths by mistake.
Otherwise, the vectors can't be the same if they have unequal length, so just add
if ( a.size() != b.size() )
{
return false;
}
before the sort instructions. This will save you lots of time.
The complexity of this technically is O(n*log(n)) because it's mainly dependent on the sorting which (usually) is of that complexity. This is better than your O(n^2) approach, but might be worse due to the needed copies. This is irrelevant if your original vectors may be sorted.
If you want to stick with your approach, but tweak it, here are my thoughts on this:
You can use std::find for this:
template <class T>
static bool compareVectors(const vector<T> &a, const vector<T> &b)
{
const size_t n = a.size(); // make it const and unsigned!
std::vector<bool> free(n, true);
for ( size_t i = 0; i < n; ++i )
{
bool matchFound = false;
auto start = b.cbegin();
while ( true )
{
const auto position = std::find(start, b.cend(), a[i]);
if ( position == b.cend() )
{
break; // nothing found
}
const auto index = position - b.cbegin();
if ( free[index] )
{
// free pair found
free[index] = false;
matchFound = true;
break;
}
else
{
start = position + 1; // search in the rest
}
}
if ( !matchFound )
{
return false;
}
}
return true;
}
Another possibility is replacing the structure to store free positions. You may try a std::bitset or just store the used indices in a vector and check if a match isn't in that index-vector. If the outcome of this function is very often the same (so either mostly true or mostly false) you can optimize your data structures to reflect that. E.g. I'd use the list of used indices if the outcome is usually false since only a handful of indices might needed to be stored.
This method has the same complexity as your approach. Using std::find to search for things is sometimes better than a manual search. (E.g. if the data is sorted and the compiler knows about it, this can be a binary search).
这篇关于如何有效地比较向量与C ++？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
