性能阵列乘法皮尔逊
问题描述:
我计算Pearson correlation(平均用户/项目评分)很多次,使用我当前的代码的表现非常糟糕:性能阵列乘法皮尔逊
public double ComputeCorrelation(double[] x, double[] y, double[] meanX, double[] meanY)
{
if (x.Length != y.Length)
throw new ArgumentException("values must be the same length");
double sumNum = 0;
double sumDenom = 0;
double denomX = 0;
double denomY = 0;
for (int a = 0; a < x.Length; a++)
{
sumNum += (x[a] - meanX[a]) * (y[a] - meanY[a]);
denomX += Math.Pow(x[a] - meanX[a], 2);
denomY += Math.Pow(y[a] - meanY[a], 2);
}
var sqrtDenomX = Math.Sqrt(denomX);
var sqrtDenomY = Math.Sqrt(denomY);
if (sqrtDenomX == 0 || sqrtDenomY == 0) return 0;
sumDenom = Math.Sqrt(denomX) * Math.Sqrt(denomY);
var correlation = sumNum/sumDenom;
return correlation;
}
我使用与MathNet.Numerics
标准Pearson相关,但这是修改标准,而且不可能使用它。有没有办法加快速度?如何优化时间复杂性?
答
添加一些对MSE答案的全部计算能力 - 改变Pow(x,2)
到diff*diff
,绝对是你想要做的事,你也可能希望避免不必要的束缚检查你最内层的循环。这可以使用pointers in C#完成。
可以做到这样:
public unsafe double ComputeCorrelation(double[] x, double[] y, double[] meanX, double[] meanY)
{
if (x.Length != y.Length)
throw new ArgumentException("values must be the same length");
double sumNum = 0;
double sumDenom = 0;
double denomX = 0;
double denomY = 0;
double diffX;
double diffY;
int len = x.Length;
fixed (double* xptr = &x[0], yptr = &y[0], meanXptr = &meanX[0], meanYptr = &meanY[0])
{
for (int a = 0; a < len; a++)
{
diffX = (xptr[a] - meanXptr[a]);
diffY = (yptr[a] - meanYptr[a]);
sumNum += diffX * diffY;
denomX += diffX * diffX;
denomY += diffY * diffY;
}
}
var sqrtDenomX = Math.Sqrt(denomX);
var sqrtDenomY = Math.Sqrt(denomY);
if (sqrtDenomX == 0 || sqrtDenomY == 0) return 0;
sumDenom = sqrtDenomX * sqrtDenomY;
var correlation = sumNum/sumDenom;
return correlation;
}
答
解决您的性能问题的最佳方法可能是避免计算尽可能多的相关性。如果您将相关性用作另一种计算的一部分,则可以使用数学来消除其中一些计算的需要。
您还应该考虑您是否可以使用皮尔逊相关平方而不是皮尔逊相关本身。这样,您可以将电话保存到Math.Sqrt()
,这通常相当昂贵。
如果您确实需要取平方根,您应该再次使用sqrtDenomX
和sqrtDenomY
,而不是重新计算平方根。
答
我在代码中看到的唯一可能的优化是在以下代码中,如果您仍然在寻找更好的性能,那么您可能需要使用SIMD vectorization。它可以让你使用的CPU
public double ComputeCorrelation(double[] x, double[] y, double[] meanX, double[] meanY)
{
if (x.Length != y.Length)
throw new ArgumentException("values must be the same length");
double sumNum = 0;
double sumDenom = 0;
double denomX = 0;
double denomY = 0;
double diffX;
double diffY;
for (int a = 0; a < x.Length; a++)
{
diffX = (x[a] - meanX[a]);
diffY = (y[a] - meanY[a]);
sumNum += diffX * diffY;
denomX += diffX * diffX;
denomY += diffY * diffY;
}
var sqrtDenomX = Math.Sqrt(denomX);
var sqrtDenomY = Math.Sqrt(denomY);
if (sqrtDenomX == 0 || sqrtDenomY == 0) return 0;
sumDenom = sqrtDenomX * sqrtDenomY;
var correlation = sumNum/sumDenom;
return correlation;
}
我觉得这是更好地问这个问题在这里http://codereview.stackexchange.com/ – Sybren
我们可以通过看代码做一些假设,但我们什么不知道这些假设实际上改善了性能。你应该通过一个分析器来运行它,以真正查看导致缓慢的原因。 –