Производительность умножения массива Пирсона

Question

Я вычисляю корреляцию Пирсона (средний рейтинг пользователя / элемента) много раз, используя мой текущий код, производительность очень плохая:

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, но это модификация стандарта, и его невозможно использовать. Есть ли способ ускорить его? Как его можно оптимизировать с точки зрения сложности времени?

Answer 1

Добавление ответа на MSE - изменение Pow(x,2) в diff*diff это определенно то, что вы хотите сделать, вы также можете избежать ненужной проверки границ в самом внутреннем цикле. Это может быть сделано с помощью указателей в 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;
    }

Answer 2

Лучший способ решить проблемы с производительностью - это, по возможности, избегать вычисления как можно большего количества корреляций. Если вы используете корреляции как часть другого вычисления, может быть возможно использовать математику, чтобы устранить необходимость в некоторых из них.

Вам также следует подумать, сможете ли вы использовать квадрат корреляции Пирсона вместо самой корреляции Пирсона. Таким образом, вы можете сохранить свои звонки на Math.Sqrt(), которые обычно довольно дороги.

Если вам нужно взять квадратный корень, вы должны использовать sqrtDenomX а также sqrtDenomY опять же, а не пересчитать квадратные корни.

Answer 3

Единственная возможная оптимизация, которую я вижу в вашем коде, заключается в следующем коде. Если вы все еще ищете лучшую производительность, вы можете использовать векторизацию SIMD. Это позволит вам использовать полную вычислительную мощность процессора

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;
    }