Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > C/C++: Общие вопросы > Представления многомерных массивов

Автор: marcusmae 30.11.2007, 00:32

Здравствуйте, друзья,

Пока не поздно решил посоветоваться. Казалось бы, массивы - несложное дело, одна из основ. Но чем они больше и чем больше с ними работаешь, тем интереснее становится smile

Допустим, у нас есть тензор, задающий поле вещественных значений. Для простоты, одинаковой размерности по всем направлениям. Этот тензор мог бы хранить, например, результаты работы какой-нибудь численной схемы, когда, имея трёхмерное поле значений на предыдущем шаге, требуется пересчитать значения на следующий. Пусть наша схема работает, скажем, по 9-точечному шаблону, то есть, для расчёта нового значения во внутренней (не граничной) точке поля (i,j,k) требуется задействовать 9 точек предыдущего поля : (i,j,k), (i-1,j,k), (i+1,j,k), (i,j-1,k), (i,j+1,k), (i,j,k-1), (i,j,k+1). Этот пересчёт как-то там работает, неважно как :

Код


inline double F(double c, double l, double r, double u, double d,
                double f, double b);

Предмет интереса - представление динамического массива и манера обхода его элементов. Первый способ состоит в простом заведении массива массивов массивов :

Код


double*** vals;

Работать с ним просто и удобно :

Код


double*** MoveNext1(unsigned int dim, double*** vals) {

    const unsigned long dim2 = dim * dim;
    double*** result = new double**[dim];

    for (unsigned int k = 1; k < dim - 1; k++)
    {
        result[k] = new double*[dim];
        for (unsigned int j = 1; j < dim - 1; j++)
        {
            result[k][j] = new double[dim];
            for (unsigned int i = 1; i < dim - 1; i++)
                result[k][j][i] = F(vals[k][j][i],
                    vals[k][j][i-1], vals[k][j][i+1],
                    vals[k][j-1][i], vals[k][j+1][i],
                    vals[k-1][j][i], vals[k+1][j][i]);

        }
    }
    return result;
}

Так уж это хорошо? = Я думаю, не очень. Массив по первой звезде - это массив указателей на указатели, второй массив - тоже, и только по третьей звезде от адреса машина отсчитывает смещение и получает значение элемента. Все массивы количеством размерность в квадрате могут быть сколь угодно разбросаны в куче (и в страничной памяти), и, вероятно, при таком представлении скорость работы не самая высокая. Для сравнения - второй вариант - векторизация :

Код


double* MoveNext2(unsigned int dim, double* vals) {

    const unsigned long dim2 = dim * dim;
    double* result = new double[dim*dim*dim],
        *resultPtr = result + dim2 + dim + 1, *valsPtr = vals + dim2 + dim + 1;

    for (unsigned int k = 1; k < dim - 1; k++)
        for (unsigned int j = 1; j < dim - 1; j++)
        {
            for (unsigned int i = 1; i < dim - 1; i++)
            {
                *resultPtr = F(    *valsPtr,
                    *(valsPtr-1), *(valsPtr+1),
                    *(valsPtr - dim), *(valsPtr + dim),
                    *(valsPtr - dim2), *(valsPtr + dim2));
                resultPtr++; valsPtr++;
            }
            resultPtr += 2 * (dim + 1); valsPtr += 2 * (dim + 1);
        }
    return result;
}

Здесь трёхмерное поле заводится как одномерный вектор, в котором строки X идут одна за одной, образовывая последовательно плоскости XY, а последовательность плоскостей является самим трёхмерным полем. Добор по указателям выглядит диковато только на первый взгляд. Можно наделать всяких хитрых и удобных макросов, и запись примет вполне читабельный вид. Вектор значений, в отличие от первого способа, непрерывен, и для перемещения по нему достаточно сложений и вычитаний.

Какой из способов на Ваш взгляд лучше и почему? Правильно ли я думаю, что второе представление должно значительно быстрее работать на больших размерностях? Какие преимущества и недостатки Вы видите помимо приведённых? Как предпочитаете пользоваться многомерными массивами - может быть существуют другие способы?

Автор: archimed7592 30.11.2007, 04:38

Цитата(marcusmae @ 30.11.2007, 00:32

)

Какой из способов на Ваш взгляд лучше и почему? Правильно ли я думаю, что второе представление должно значительно быстрее работать на больших размерностях?

Правильно.

Цитата(marcusmae @ 30.11.2007, 00:32

)

Какие преимущества и недостатки Вы видите помимо приведённых?

У второго варианта один недостаток - непривычный способ обращения к элементам. В частности, в С++ эта "проблема" решается классовой обёрткой так, что ты и не заметишь, что работаешь с "оптимизированным" динамическим массивом.
Собственно говоря, статический массивы, размерности которых известны во время компиляции так и хранятся.

Добавлено через 1 минуту и 3 секунды
Кстати, в бусте такая обёрточка есть: http://boost.org/libs/multi_array/doc/user.html (если, конечно, приемлем С++ с его "тормозами" и буст с его "неповоротливостью").

Автор: marcusmae 30.11.2007, 18:33

archimed7592, спасибо за ответ.

Цитата(archimed7592 @ 30.11.2007, 04:38

)

Кстати, в бусте такая обёрточка есть

Ага, в общем случае пригодится, спасибо. Для этого конекретного случая макросы очень помогли : символы типа левый, правый, центральный, верхний, нижний, ближний и дальний - _L, _R, _C, _U, _D, _F, _B.

Код


#define _R(center) (center+1)

...

double rightValue = *_R(val);

Сразу стала видна симметрия и другие свойства алгоритма. Нашёл несколько мелких ошибок smile

Цитата(archimed7592 @ 30.11.2007, 04:38

)

если, конечно, приемлем С++ с его "тормозами"

Не считаю плюсовый код сильно тормозным. Кавычки здесь по этому поводу? smile

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