тест с матрицами
От: Pavel Dvorkin Россия  
Дата: 29.09.05 07:23
Оценка: :)
После того, как мне здесь объяснили, что я ничего не понимаю , ушел я с горя в "Философию" и ответил там на одно сообщение, прямого отношения к тематике этого форума не имеющее. Однако черт меня угораздил там мимоходом упомянуть C#, в результате чего Sinclair нашел меня и там (http://www.rsdn.ru/Forum/Message.aspx?mid=1404835&only=1
Автор: Sinclair
Дата: 27.09.05
) и продолжил объяснять мне, что я ничего не понимаю. И состоялась у нас вот такая дискуссия

PD>>К примеру (банальный) решиться мне, скажем, на C# матричные операции производить или же С++ DLL для этого написать, а в Шарпе только вызывать ее.

S>Ты не пробовал, к примеру, вот здесь читать?

PD>Прочитал, спасибо. Увы, этого мне недостаточно. Во-первых, хотелось бы еще знать, сколько памяти они при этом потребили. Во-вторых, здесь используется совсем небольшие объемы данных, а вот что будет при обработке массивов размером в Мбайты ? Насколько эффективен доступ к массивам ? Тебе не хуже меня известно, что даже в чистом С++ при неудачном размере строки масиива (например, 4097 байт) можно сильно проиграть. И т.д. И т.д


Написал я все это, а потом подумал — а чего я, собственно, голословными утверждениями занимаюсь. Сложно, что ли мне это самое умножение матрици самому сделать и посмотреть время. Ну и сделал, и посмотрел.

Вот текст на С++

        float ** a, **b, **c;
    int i,j,k,nSize = 1000;
    float temp;

    int nTimeStart = GetTickCount();
    a = new float*[nSize];
    for( i = 0; i < nSize; i++)
        a[i] = new float[nSize];
    for(i = 0; i < nSize; i++)
        for(j = 0; j < nSize; j++)
            a[i][j] = 1;

    b = new float*[nSize];
    for( i = 0; i < nSize; i++)
        b[i] = new float[nSize];
    for(i = 0; i < nSize; i++)
        for(j = 0; j < nSize; j++)
            b[i][j] = 1;
    
    c = new float*[nSize];
    for( i = 0; i < nSize; i++)
        c[i] = new float[nSize];
    
    for(i = 0; i < nSize; i++)
    {
        for(j = 0; j < nSize; j++)
        {
            temp = 0;
            for( k = 0; k < nSize; k++)
                temp += a[i][k] * b[k][j];
            c[i][j] = temp;
        }
    }

    int nTimeEnd = GetTickCount();
    printf("Time = %d\n", (nTimeEnd - nTimeStart) /1000);


Время работы этой программы на моем Pentium IV 1600 MHz 768 Mb — 33 секунды.

Теперь то же на С#


        float[][] a, b, c;
    int i,j,k,nSize = 10;
    float temp;

    DateTime nTimeStart = DateTime.Now;
    a = new float[nSize][];
    for( i = 0; i < nSize; i++)
        a[i] = new float[nSize];
    for(i = 0; i < nSize; i++)
        for(j = 0; j < nSize; j++)
            a[i][j] = 1;

    b = new float[nSize][];
    for( i = 0; i < nSize; i++)
        b[i] = new float[nSize];
    for(i = 0; i < nSize; i++)
        for(j = 0; j < nSize; j++)
            b[i][j] = 1;
    
    c = new float[nSize][];
    for( i = 0; i < nSize; i++)
        c[i] = new float[nSize];
    
            for(i = 0; i < nSize; i++)
            {
                for(j = 0; j < nSize; j++)
                {
                    temp = 0;
                    for( k = 0; k < nSize; k++)
                        temp += a[i][k] * b[k][j];
                    c[i][j] = temp;
                }
            }
        DateTime nTimeEnd = DateTime.Now;

    Console.WriteLine("Time = {0}", (nTimeEnd - nTimeStart));


Время работы — 4 минуты 6 секунд.

Подумал я и решил попробовать вторую матрицу (b) по столбцам расположить. Поскольку матрицы квадратные, а все элементы равны 1 то достаточно просто сделать вид, что это так, т.е. заменить

temp += a[i][k] * b[k][j];

на

temp += a[i][k] * b[j][к];

Результат — 18 секунд как на С++, так и на С#.

Еще один эксперимент на С# сделал — заменил кусочный массив на цельный, т.е.


            float[,] a, b, c;
            int i,j,k,nSize = 1000;
            float temp;

            DateTime nTimeStart = DateTime.Now;
            a = new float[nSize,nSize];
            for(i = 0; i < nSize; i++)
                for(j = 0; j < nSize; j++)
                    a[i,j] = 1;

            b = new float[nSize, nSize];
            for(i = 0; i < nSize; i++)
                for(j = 0; j < nSize; j++)
                    b[i,j] = 1;
    
            c = new float[nSize,nSize];
    
            for(i = 0; i < nSize; i++)
            {
                for(j = 0; j < nSize; j++)
                {
                    temp = 0;
                    for( k = 0; k < nSize; k++)
                        temp += a[i,k] * b[k,j];
                    c[i,j] = temp;
                }
            }



Результат — 56 секунд. На С++ делать этот тест не стал — лень. .

Итак, имеем

а) матрица а по строкам, матрица b по столбцам — быстродействие C# не хуже С++
б) матрицы целым куском — на С# имеем 3-кратное замедление по сравнению с a)
в) матрица а по строкам, матрица b по строкам — С++ в 2 раза хуже, чем С++ для a), что вполне естественно (ИМХО в основном за счет перегрузки кэша процессора), но C# дает 7-кратный проигрыш по сравнению с С++ и 14-кратный по сравнению с a). Причина понятна — имеем массивы массивов, и на каждом проходе внутреннего цикла идет обращение к другому массиву (другой строке) матрицы b, что, по-видимому, и вызывает этот эффект.

Мой вопрос — если все-таки матрица b должна храниться в формате a),(просьба не обсуждать, зачем это нужно и не советовать выбрать иной формат) можно что-то сделать ? Я не против fixed, но не пойму, как его здесь применить. Рихтер утверждает, что fixed можно применить только к массивам из простых типов, а здесь все же массив массивов.
With best regards
Pavel Dvorkin
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.