计算表示稀疏向量的地图之间的距离 C++
Compute distance between maps that represent sparse vectors c++
简介和源代码
我正在尝试计算两个维度为 169647 的稀疏向量之间的余弦相似度。作为输入,这两个向量表示为 <index, value>
形式的字符串.只有向量的非零元素被赋予索引。
x = "1:0.1 43:0.4 100:0.43 10000:0.9"
y = "200:0.5 500:0.34 501:0.34"
首先我们使用函数splitVector
将x和y分别转化为两个vectors<float>.
。然后我们使用函数 cosine_similarity
计算距离。没关系 split
功能。我正在使用它以防万一您希望 运行 代码。
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
void split(const string& s, char c,vector<string>& v) {
string::size_type i = 0;
string::size_type j = s.find(c);
while (j != string::npos) {
v.push_back(s.substr(i, j-i));
i = ++j;
j = s.find(c, j);
if (j == string::npos)
v.push_back(s.substr(i, s.length()));
}
}
float cosine_similarity(const std::vector<float> & A,const std::vector<float> & B)
{
float dot = 0.0, denom_a = 0.0, denom_b = 0.0 ;
for(unsigned int i = 0; i < A.size(); ++i)
{
dot += A[i] * B[i] ;
denom_a += A[i] * A[i] ;
denom_b += B[i] * B[i] ;
}
return dot / (sqrt(denom_a) * sqrt(denom_b)) ;
}
void splitVector(const vector<string> & v, vector<float> & values)
{
vector<string> tmpv;
string parsed;
for(unsigned int i = 0; i < v.size(); i++)
{
split(v[i], ':', tmpv);
int idx = atoi(tmpv[0].c_str());
float val = atof(tmpv[1].c_str());
tmpv.clear();
values[idx] = val;
}//end for;
}//end function
int main()
{
//INPUT VECTORS.
vector<string> x {"1:0.1","43:0.4","50:0.43","90:0.9"};
vector<string> y {"20:0.5","40:0.34","50:0.34"};
//STEP 1: Initialize vectors
int dimension = 169647;
vector<float> X;
X.resize(dimension, 0.0);
vector<float> Y;
Y.resize(dimension, 0.0);
//STEP 2: CREATE FLOAT VECTORS
splitVector(x, X);
splitVector(y, Y);
//STEP 3: COMPUTE COSINE SIMILARITY
cout << cosine_similarity(X,Y) << endl;
}
问题和建议的解决方案
初始化和填充 vector<float>
是个问题。执行时间真的很长。我正在考虑在 C++ 中使用 std::map<int,float>
结构。其中 X 和 Y 将表示为:
std::map<int,float> x_m{ make_pair(1,0.1), make_pair(43,0.4), make_pair(50,0.43), make_pair(90,0.9)};
std::map<int,float> y_m{ make_pair(20,0.5), make_pair(40,0.34), make_pair(50,0.34)};
为此,我使用了以下函数:
float cosine_similarity(const std::map<int,float> & A,const std::map<int,float> & B)
{
float dot = 0.0, denom_a = 0.0, denom_b = 0.0 ;
for(auto &a:A)
{
denom_a += a.second * a.second ;
}
for(auto &b:B)
{
denom_b += b.second * b.second ;
}
for(auto &a:A)
{
if(B.find(a.first) != B.end())
{
dot += a.second * B.find(a.first)->second ;
}
}
return dot / (sqrt(denom_a) * sqrt(denom_b)) ;
}
问题
- 你能帮我计算复杂度吗?
- 第二个提议的使用地图的函数会降低复杂度吗?
- 您认为解决方案如何?
说N = 169647,两者在实践中的维度分别是m,n,分别.
关于您的问题:
原来的复杂度是Θ(N2).
您提出的解决方案的复杂度是 O((m + n) log(max(m, n)),它可能会小得多; 使用 std::unordered_map
代替,您可以将其减少到预期的 O(m + n).
听起来不错,但一如既往 - YMMV。您应该在整个应用程序的上下文中分析此操作(以查看它是否是一个问题)以及此操作中的步骤。
稀疏向量的常见表示是一个简单的索引数组和一个值,或者有时是一对索引和值的数组,因为通常您需要访问索引和值(除非您不这样做比如矢量长度/归一化或类似的)。建议使用其他两种形式:使用 std::map
和 std::unordered_map
.
结论请看文末
基准
我为这四种表示实现了向量运算长度和内积(点积)。此外,我以 OP 问题中建议的非常直接的方式实现了内积,并改进了对向量实现的余弦距离计算。
完整代码
我已经 运行 对这些实现进行了基准测试。您可以从这个 link 中查看我的代码,我从那里获取了以下数字(尽管比率与我自己机器上的 运行 非常匹配,只是更高 RunCount
更均匀地分布随机输入向量)。以下是结果:
结果
Explanation of the output of the benchmark:
pairs: implementation using (sorted) std::vector of pairs
map'd: implementation using std::map
hashm: implementation using std::unordered_map
class: implementation using two separate std::vector for indices and values respectively
specl dot (naive map): dot product using map.find instead of proper iteration
specl cos (optimised): cosine distance iterating only once over both vectors
Columns are the percentage of non-zeros in the random sparse vector (on average).
Values are in terms of the vector of pairs implementation
(1: equal runtime, 2: took twice as long, 0.5: took half as long).
inner product (dot)
5% 10% 15% 25%
map'd 3.3 3.5 3.7 4.0
hashm 3.6 4.0 4.8 5.2
class 1.1 1.1 1.1 1.1
special[1] 8.3 9.8 10.7 10.8
norm squared (len2)
5% 10% 15% 25%
map'd 6.9 7.6 8.3 10.2
hashm 2.3 3.6 4.1 4.8
class 0.98 0.95 0.93 0.75
cosine distance (cos)
5% 10% 15% 25%
map'd 4.0 4.3 4.6 5.0
hashm 3.2 3.9 4.6 5.0
class 1.1 1.1 1.1 1.1
special[2] 0.92 0.95 0.93 0.94
测试中的实施
除了 special[2]
的情况,我使用了以下余弦距离函数:
template<class Vector>
inline float CosineDistance(const Vector& lhs, const Vector& rhs) {
return Dot(lhs, rhs) / std::sqrt(LenSqr(lhs) * LenSqr(rhs));
}
容器对
这里是 Dot
对排序的 vector<pair<size_t,float>>
和 map<size_t,float>
的实现:
template<class PairContainerSorted>
inline float DotPairsSorted(const PairContainerSorted& lhs, const PairContainerSorted& rhs) {
float dot = 0;
for(auto pLhs = lhs.begin(), pRhs = rhs.begin(), endLhs = lhs.end(), endRhs = rhs.end(); pRhs != endRhs;) {
for(; pLhs != endLhs && pLhs->first < pRhs->first; ++pLhs);
if(pLhs == endLhs)
break;
for(; pRhs != endRhs && pRhs->first < pLhs->first; ++pRhs);
if(pRhs == endRhs)
break;
if(pLhs->first == pRhs->first) {
dot += pLhs->second * pRhs->second;
++pLhs;
++pRhs;
}
}
return dot;
}
这是 Dot
无序映射和 special[1]
的实现(等于 OP 的实现):
template<class PairMap>
inline float DotPairsMapped(const PairMap& lhs, const PairMap& rhs) {
float dot = 0;
for(auto& pair : lhs) {
auto pos = rhs.find(pair.first);
if(pos != rhs.end())
dot += pair.second * pos->second;
}
return dot;
}
执行LenSqr
:
template<class PairContainer>
inline float LenSqrPairs(const PairContainer& vec) {
float dot = 0;
for(auto& pair : vec)
dot += pair.second * pair.second;
return dot;
}
向量对
请注意,我将这对向量打包到结构中(或class
)SparseVector
(查看完整代码了解详情):
inline float Dot(const SparseVector& lhs, const SparseVector& rhs) {
float dot = 0;
if(!lhs.idx.empty() && !rhs.idx.empty()) {
const size_t *itIdxLhs = &lhs.idx[0], *endIdxLhs = &lhs.idx[0] + lhs.idx.size();
const float *itValLhs = &lhs.val[0], *endValLhs = &lhs.val[0] + lhs.val.size();
const size_t *itIdxRhs = &rhs.idx[0], *endIdxRhs = &rhs.idx[0] + rhs.idx.size();
const float *itValRhs = &rhs.val[0], *endValRhs = &rhs.val[0] + rhs.val.size();
while(itIdxRhs != endIdxRhs) {
for(; itIdxLhs < endIdxLhs && *itIdxLhs < *itIdxRhs; ++itIdxLhs, ++itValLhs);
if(itIdxLhs == endIdxLhs)
break;
for(; itIdxRhs < endIdxRhs && *itIdxRhs < *itIdxLhs; ++itIdxRhs, ++itValRhs);
if(itIdxRhs == endIdxRhs)
break;
if(*itIdxLhs == *itIdxRhs) {
dot += (*itValLhs) * (*itValRhs);
++itIdxLhs;
++itValLhs;
++itIdxRhs;
++itValRhs;
}
}
}
return dot;
}
inline float LenSqr(const SparseVector& vec) {
float dot = 0;
for(float v : vec.val)
dot += v * v;
return dot;
}
special[2]
简单地计算两个向量的平方范数,同时在内积期间迭代它们(查看完整代码以获取详细信息)。我已经添加了这个来证明一个观点:缓存命中很重要。如果我只是更有效地访问我的内存(当然,如果你优化了其他路径,同样如此),我可以用一对向量一个来击败向量对的天真方法。
结论
请注意,所有经过测试的实现(除了具有 O(k*logk)
行为的 special[1]
之外)都表现出理论上的 运行 时间行为 O(k)
,其中 k
是稀疏向量中 non-zeros 的数量:对于地图和向量来说,这是微不足道的,因为 Dot
的实现是相同的 并且无序地图实现了这一点通过在 O(1)
中实施 find
摊销。
为什么地图不是稀疏向量的错误工具?对于 std::map
,答案是迭代树结构的开销,对于 std::unordered_map
,对于 find
,答案是随机内存访问模式,两者都会在缓存未命中期间导致巨大的开销。
要揭开 std::unordered_map
相对于 std::map
的理论优势,请查看 special[1]
的结果。这是 std::unordered_map
击败的实现,不是因为它更适合问题,而是因为使用 std::map
的实现是 sub-optimal.
简介和源代码
我正在尝试计算两个维度为 169647 的稀疏向量之间的余弦相似度。作为输入,这两个向量表示为 <index, value>
形式的字符串.只有向量的非零元素被赋予索引。
x = "1:0.1 43:0.4 100:0.43 10000:0.9"
y = "200:0.5 500:0.34 501:0.34"
首先我们使用函数splitVector
将x和y分别转化为两个vectors<float>.
。然后我们使用函数 cosine_similarity
计算距离。没关系 split
功能。我正在使用它以防万一您希望 运行 代码。
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
void split(const string& s, char c,vector<string>& v) {
string::size_type i = 0;
string::size_type j = s.find(c);
while (j != string::npos) {
v.push_back(s.substr(i, j-i));
i = ++j;
j = s.find(c, j);
if (j == string::npos)
v.push_back(s.substr(i, s.length()));
}
}
float cosine_similarity(const std::vector<float> & A,const std::vector<float> & B)
{
float dot = 0.0, denom_a = 0.0, denom_b = 0.0 ;
for(unsigned int i = 0; i < A.size(); ++i)
{
dot += A[i] * B[i] ;
denom_a += A[i] * A[i] ;
denom_b += B[i] * B[i] ;
}
return dot / (sqrt(denom_a) * sqrt(denom_b)) ;
}
void splitVector(const vector<string> & v, vector<float> & values)
{
vector<string> tmpv;
string parsed;
for(unsigned int i = 0; i < v.size(); i++)
{
split(v[i], ':', tmpv);
int idx = atoi(tmpv[0].c_str());
float val = atof(tmpv[1].c_str());
tmpv.clear();
values[idx] = val;
}//end for;
}//end function
int main()
{
//INPUT VECTORS.
vector<string> x {"1:0.1","43:0.4","50:0.43","90:0.9"};
vector<string> y {"20:0.5","40:0.34","50:0.34"};
//STEP 1: Initialize vectors
int dimension = 169647;
vector<float> X;
X.resize(dimension, 0.0);
vector<float> Y;
Y.resize(dimension, 0.0);
//STEP 2: CREATE FLOAT VECTORS
splitVector(x, X);
splitVector(y, Y);
//STEP 3: COMPUTE COSINE SIMILARITY
cout << cosine_similarity(X,Y) << endl;
}
问题和建议的解决方案
初始化和填充 vector<float>
是个问题。执行时间真的很长。我正在考虑在 C++ 中使用 std::map<int,float>
结构。其中 X 和 Y 将表示为:
std::map<int,float> x_m{ make_pair(1,0.1), make_pair(43,0.4), make_pair(50,0.43), make_pair(90,0.9)};
std::map<int,float> y_m{ make_pair(20,0.5), make_pair(40,0.34), make_pair(50,0.34)};
为此,我使用了以下函数:
float cosine_similarity(const std::map<int,float> & A,const std::map<int,float> & B)
{
float dot = 0.0, denom_a = 0.0, denom_b = 0.0 ;
for(auto &a:A)
{
denom_a += a.second * a.second ;
}
for(auto &b:B)
{
denom_b += b.second * b.second ;
}
for(auto &a:A)
{
if(B.find(a.first) != B.end())
{
dot += a.second * B.find(a.first)->second ;
}
}
return dot / (sqrt(denom_a) * sqrt(denom_b)) ;
}
问题
- 你能帮我计算复杂度吗?
- 第二个提议的使用地图的函数会降低复杂度吗?
- 您认为解决方案如何?
说N = 169647,两者在实践中的维度分别是m,n,分别.
关于您的问题:
原来的复杂度是Θ(N2).
您提出的解决方案的复杂度是 O((m + n) log(max(m, n)),它可能会小得多; 使用
std::unordered_map
代替,您可以将其减少到预期的 O(m + n).听起来不错,但一如既往 - YMMV。您应该在整个应用程序的上下文中分析此操作(以查看它是否是一个问题)以及此操作中的步骤。
稀疏向量的常见表示是一个简单的索引数组和一个值,或者有时是一对索引和值的数组,因为通常您需要访问索引和值(除非您不这样做比如矢量长度/归一化或类似的)。建议使用其他两种形式:使用 std::map
和 std::unordered_map
.
结论请看文末
基准
我为这四种表示实现了向量运算长度和内积(点积)。此外,我以 OP 问题中建议的非常直接的方式实现了内积,并改进了对向量实现的余弦距离计算。
完整代码
我已经 运行 对这些实现进行了基准测试。您可以从这个 link 中查看我的代码,我从那里获取了以下数字(尽管比率与我自己机器上的 运行 非常匹配,只是更高 RunCount
更均匀地分布随机输入向量)。以下是结果:
结果
Explanation of the output of the benchmark: pairs: implementation using (sorted) std::vector of pairs map'd: implementation using std::map hashm: implementation using std::unordered_map class: implementation using two separate std::vector for indices and values respectively specl dot (naive map): dot product using map.find instead of proper iteration specl cos (optimised): cosine distance iterating only once over both vectors Columns are the percentage of non-zeros in the random sparse vector (on average). Values are in terms of the vector of pairs implementation (1: equal runtime, 2: took twice as long, 0.5: took half as long). inner product (dot) 5% 10% 15% 25% map'd 3.3 3.5 3.7 4.0 hashm 3.6 4.0 4.8 5.2 class 1.1 1.1 1.1 1.1 special[1] 8.3 9.8 10.7 10.8 norm squared (len2) 5% 10% 15% 25% map'd 6.9 7.6 8.3 10.2 hashm 2.3 3.6 4.1 4.8 class 0.98 0.95 0.93 0.75 cosine distance (cos) 5% 10% 15% 25% map'd 4.0 4.3 4.6 5.0 hashm 3.2 3.9 4.6 5.0 class 1.1 1.1 1.1 1.1 special[2] 0.92 0.95 0.93 0.94
测试中的实施
除了 special[2]
的情况,我使用了以下余弦距离函数:
template<class Vector>
inline float CosineDistance(const Vector& lhs, const Vector& rhs) {
return Dot(lhs, rhs) / std::sqrt(LenSqr(lhs) * LenSqr(rhs));
}
容器对
这里是 Dot
对排序的 vector<pair<size_t,float>>
和 map<size_t,float>
的实现:
template<class PairContainerSorted>
inline float DotPairsSorted(const PairContainerSorted& lhs, const PairContainerSorted& rhs) {
float dot = 0;
for(auto pLhs = lhs.begin(), pRhs = rhs.begin(), endLhs = lhs.end(), endRhs = rhs.end(); pRhs != endRhs;) {
for(; pLhs != endLhs && pLhs->first < pRhs->first; ++pLhs);
if(pLhs == endLhs)
break;
for(; pRhs != endRhs && pRhs->first < pLhs->first; ++pRhs);
if(pRhs == endRhs)
break;
if(pLhs->first == pRhs->first) {
dot += pLhs->second * pRhs->second;
++pLhs;
++pRhs;
}
}
return dot;
}
这是 Dot
无序映射和 special[1]
的实现(等于 OP 的实现):
template<class PairMap>
inline float DotPairsMapped(const PairMap& lhs, const PairMap& rhs) {
float dot = 0;
for(auto& pair : lhs) {
auto pos = rhs.find(pair.first);
if(pos != rhs.end())
dot += pair.second * pos->second;
}
return dot;
}
执行LenSqr
:
template<class PairContainer>
inline float LenSqrPairs(const PairContainer& vec) {
float dot = 0;
for(auto& pair : vec)
dot += pair.second * pair.second;
return dot;
}
向量对
请注意,我将这对向量打包到结构中(或class
)SparseVector
(查看完整代码了解详情):
inline float Dot(const SparseVector& lhs, const SparseVector& rhs) {
float dot = 0;
if(!lhs.idx.empty() && !rhs.idx.empty()) {
const size_t *itIdxLhs = &lhs.idx[0], *endIdxLhs = &lhs.idx[0] + lhs.idx.size();
const float *itValLhs = &lhs.val[0], *endValLhs = &lhs.val[0] + lhs.val.size();
const size_t *itIdxRhs = &rhs.idx[0], *endIdxRhs = &rhs.idx[0] + rhs.idx.size();
const float *itValRhs = &rhs.val[0], *endValRhs = &rhs.val[0] + rhs.val.size();
while(itIdxRhs != endIdxRhs) {
for(; itIdxLhs < endIdxLhs && *itIdxLhs < *itIdxRhs; ++itIdxLhs, ++itValLhs);
if(itIdxLhs == endIdxLhs)
break;
for(; itIdxRhs < endIdxRhs && *itIdxRhs < *itIdxLhs; ++itIdxRhs, ++itValRhs);
if(itIdxRhs == endIdxRhs)
break;
if(*itIdxLhs == *itIdxRhs) {
dot += (*itValLhs) * (*itValRhs);
++itIdxLhs;
++itValLhs;
++itIdxRhs;
++itValRhs;
}
}
}
return dot;
}
inline float LenSqr(const SparseVector& vec) {
float dot = 0;
for(float v : vec.val)
dot += v * v;
return dot;
}
special[2]
简单地计算两个向量的平方范数,同时在内积期间迭代它们(查看完整代码以获取详细信息)。我已经添加了这个来证明一个观点:缓存命中很重要。如果我只是更有效地访问我的内存(当然,如果你优化了其他路径,同样如此),我可以用一对向量一个来击败向量对的天真方法。
结论
请注意,所有经过测试的实现(除了具有 O(k*logk)
行为的 special[1]
之外)都表现出理论上的 运行 时间行为 O(k)
,其中 k
是稀疏向量中 non-zeros 的数量:对于地图和向量来说,这是微不足道的,因为 Dot
的实现是相同的 并且无序地图实现了这一点通过在 O(1)
中实施 find
摊销。
为什么地图不是稀疏向量的错误工具?对于 std::map
,答案是迭代树结构的开销,对于 std::unordered_map
,对于 find
,答案是随机内存访问模式,两者都会在缓存未命中期间导致巨大的开销。
要揭开 std::unordered_map
相对于 std::map
的理论优势,请查看 special[1]
的结果。这是 std::unordered_map
击败的实现,不是因为它更适合问题,而是因为使用 std::map
的实现是 sub-optimal.