Почему этот код является настолько медленным?

Во внутреннем цикле вы не должны проверять размер, вы не должны делать никаких делений, а итераторы также могут быть дорогостоящими. На самом деле, там неплохо было бы немного развернуться. И, конечно же, вы должны обращать внимание на локальность кеша.

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

Я не мог заставить код скомпилировать, поэтому я не мог точно определить проблемы.

Я изменил алгоритм, чтобы избавиться почти от всего деления с плавающей запятой.

ВНИМАНИЕ: НЕПРОВЕРЕННЫЙ КОД !!!

void CalculateStats()
{
    //OHGOD

    double accum_f;
    double accum_sq_f;
    double new_mean = 0;
    double new_standard_dev = 0;

    int new_min = 256;
    int new_max = 0;

    const int oku = 100000000;
    int accum_ichi = 0;
    int accum_oku = 0;
    int accum_sq_ichi = 0;
    int accum_sq_oku = 0;

    size_t cnt = 0;
    int v1 = 0;
    int v2 = 0;

    v1 = vals.size();

    for(size_t row = 0; row < v1; row++)
    {

            v2 = vals.at(row).size();
            for(size_t col = 0; col < v2; col++)
            {
                    T value = get(row, col);
                    int accum_ichi += value;
                    int accum_sq_ichi += (value * value);

                    // perform carries
                    accum_oku += (accum_ichi / oku);
                    accum_ichi %= oku;
                    accum_sq_oku += (accum_sq_ichi / oku);
                    accum_sq_ichi %= oku;

                    // find new max/min's
                    new_min = value < new_min ? value : new_min;
                    new_max = value > new_max ? value : new_max;
                    cnt++;
            }
    }

    // now, and only now, do we use floating-point arithmetic
    accum_f = (double)(oku) * (double)(accum_oku) + (double)(accum_ichi);
    accum_sq_f = (double)(oku) * (double)(accum_sq_oku) + (double)(accum_sq_ichi);

    new_mean = accum_f / (double)(cnt);

    // standard deviation formula from Wikipedia
    stats_standard_dev = sqrt((double)(cnt)*accum_sq_f - accum_f*accum_f)/(double)(cnt);        

    std::cout << stats_standard_dev << std::endl;
}

Немного опоздал на вечеринку, но пара моментов:

1. Вы эффективно выполняете числовую работу. Я не очень разбираюсь в числовых алгоритмах, но знаю достаточно, чтобы знать, что ссылки и экспертная поддержка часто бывают полезны. Эта ветка обсуждения предлагает некоторые ссылки; и «Числовые рецепты» - стандартная (если датированная) работа.

2. Если у вас есть возможность переделать матрицу, вы можете попробовать использовать valarray и срезы вместо векторов векторов; Одно преимущество, которое сразу приходит в голову, заключается в том, что вам гарантирован плоский линейный макет, что делает предварительную выборку из кеша и инструкции SIMD (если ваш компилятор может их использовать) более эффективными.

As people have mentioned, it might be get(). If it accesses neighbors, for instance, you will totally smash the cache which will greatly reduce the performance. You should profile, or just think about access patterns.

I think that I would rewrite it to use const iterators instead of row and col indexes. I would set up a const const_iterator for row_end and col_end to compare against, just to make certain it wasn't making function calls at every loop end.

If your matrix is stored as a vector of vectors, then in the outer for loop you should directly retrieve the i-th vector, and then operate on that in the inner loop. Try that and see if it improves performance.

I'm nor sure of what type vals is but vals.at(row).size() could take a long time if itself iterates through the collection. Store that value in a variable. Otherwise it could make the algorithm more like O(n³) than O(n²)

Move the .size() calls to before each loop, and make sure you are compiling with optimizations turned on.

I would change how I access the data. Assuming you are using std::vector for your container you could do something like this:

vector<vector<T> >::const_iterator row;
vector<vector<T> >::const_iterator row_end = vals.end();
for(row = vals.begin(); row < row_end; ++row)
{
    vector<T>::const_iterator value;
    vector<T>::const_iterator value_end = row->end();
    for(value = row->begin(); value < value_end; ++value)
    {
        double mean_prev = new_mean;
        new_mean += (*value - new_mean) / (cnt + 1);
        new_standard_dev += (*value - new_mean) * (*value - mean_prev);

        // find new max/min's
        new_min = min(*value, new_min);
        new_max = max(*value, new_max);
        cnt++;
    }
}

The advantage of this is that in your inner loop you aren't consulting the outter vector, just the inner one.

If you container type is a list, this will be significantly faster. Because the look up time of get/operator[] is linear for a list and constant for a vector.

Edit, I moved the call to end() out of the loop.

Слишком много вычислений во внутреннем цикле:

1. Для описательной статистики (среднее, стандартное отклонение) единственное, что требуется, это вычислить сумму значения и суммы квадратов значения . От них можно вычислить две суммы среднего и стандартного отклонения после внешнего цикла (вместе с третьим значением, количество образцов - n ваш новый / обновленный код). В уравнения можно вывести из определений или найти в Интернете, например, в Википедии. Например, среднее значение просто сумма значения , деленная на n. Для версии n (в в отличие от версии n-1 - однако n большое в в этом случае, поэтому не имеет значения, какой из них используется) стандартное отклонение:
   sqrt (n * sumOfSquaredValue - sumOfValue * sumOfValue).
   
   Таким образом, только два с плавающей запятой сложения и одно умножение необходимы в внутренний цикл. Переполнение этих сумм не проблема, так как диапазон для удвоений - 10 ^ 318. В частности, вы будете избавиться от дорогостоящего деления с плавающей запятой , которое профилирование, описанное в другом ответе, показало.

2. Меньшая проблема заключается в том, что минимум и максимум переписывается каждый раз (компилятор может или не может предотвратить это). Как минимум быстро становится маленьким и максимум быстро становится большим, только два сравнения должно произойти для большинства итераций цикла: используйте если утверждения вместо того, чтобы быть уверенным. Можно поспорить, но с другой стороны, сделать это просто.

Вы, безусловно, можете создать приложение только с открытым исходным кодом Flex SDK. Я опубликовал некоторые инструкции по использованию только Flex SDK в Linux. Если вы находитесь на другой платформе, инструкции можно немного изменить.

В сборке Release компилятор оптимизирует проверки диапазона (я не знаю, просто ли он их отбрасывает или выполняет анализ потока на основе ограничений цикла. ), и доступ к векторам превращается в небольшой объем арифметических операций с встроенными указателями без ветвлений.

Никого не волнует, насколько быстро выполняется отладочная сборка. В любом случае вам следует проводить модульное тестирование сборки релиза, так как эта сборка должна работать правильно. Используйте сборку отладки только в том случае, если у вас нет всей необходимой информации, если вы попытаетесь пройти через код.

Опубликованный код выполняется на моем ПК менее чем за 1,5 секунды с тестовыми данными 15000 x 10000 целых чисел, которые все равны 42. Вы сообщаете, что он работает в 230 раз медленнее этого. Используете ли вы процессор с тактовой частотой 10 МГц?

Хотя есть и другие предложения по его ускорению (например, перемещение его для использования SSE, если все значения представляются с использованием 8-битных типов), но явно есть что-то еще, что замедляет его .

На моей машине ни версия, которая поднимала ссылку на вектор для строки и увеличивала размер строки, ни версия, в которой использовался итератор, не давала измеримых преимуществ (с g ++ -O3 с использованием итераторов повторяется 1511 мс; поднятая и оригинальная версия занимают 1485 мс). Отсутствие оптимизации означает, что он выполняется за 7487 мс (исходный), 3496 мс (поднятый) или 5331 мс (итераторы).

Но если вы не работаете на устройстве с очень низким энергопотреблением, или подкачке страниц, или запущенном неоптимизированном коде прикреплен отладчик, он не должен быть таким медленным,

First thing I spotted is that you evaluate vals.at(row).size() in the loop, which, obviously, isn't supposed to improve performance. It also applies to vals.size(), but of course inner loop is worse. If vals is a vector of vector, you better use iterators or at least keep reference for the outer vector (because get() with indices parameters surely eats up quite some time as well).

This code sample is supposed to illustrate my intentions ;-)

for(TVO::const_iterator i=vals.begin(),ie=vals.end();i!=ie;++i) {
    for(TVI::const_iterator ii=i->begin(),iie=i->end();ii!=iie;++ii) {
        T value = *ii;
        // the rest
    }
}

• First, change your row++ to ++row. A minor thing, but you want speed, so that will help
• Second, make your row < vals.size into some const comparison instead. The compiler doesn't know that vals won't change, so it has to play nice and always call size.
• what is the 'get' method in the middle there? What does that do? That might be your real problem.
• I'm not too sure about your std dev calculation. Take a look at the wikipedia page on calculating variance in a single pass (they have a quick explanation of Knuth's algorithm, which is an expansion of a recursion relation).

You should calculate the sum of values, min, max and count in the first loop, then calculate the mean in one operation by dividing sum/count, then in a second loop calculate std_dev's sum

That would probably be a bit faster.

Я только что профилировал его. 90% времени выполнения было в этой строке:

new_mean + = (value - new_mean) / (cnt + 1);