Правильный тест должен гарантировать, что обрабатываются одни и те же данные, поэтому я убрал библиотечные генераторы случайных чисел и заменил их явной генерацией. Правильный тест должен проверять корректность результата, поэтому результат умножения теперь используется.
Каждый код прогонялся три раза в topcoder practice room 461 easy. Результаты и код можно посмотреть здесь: http://advgreat.narod.ru/matrices.rar
Если кто-то думает, что я что-то делаю не так -- код в студию.
Мои извинения любителям Java. В прошлый раз я забыл указать ключевое слово final, теперь добавил.
Для C# я попробовал замерить вариант, когда значение size не задается литералом, а берется из входных данных -- в таком случае у компилятора не будет шансов догадаться, что будет это такое при работе программы. Правда, влияние на скорость это оказывает только для С/С++.
Для C# и Java вывод такой:
если нужен двухмерный массив или его аналог, то индексация в
int[,] будет работать медленнее всего
int[][] будет работать немного быстрее
int[] с индексацией вида arr[y*cols + x] будет работать еще быстрее
Для C++, как и ожидалось, индексация в массиве массивов (int **) оказалась медленее, чем в двухмерном массиве (int [][]), никакого преимущества переход с адресации int[][] на развернутое int[] не дает.
Также хочу рассказать тем, кто не знает, что GCC поддерживает VLA. То есть там работает такой код:
int foo(int n) { int arr[n][n]; // все, массив готов и в него можно писать
p.s. Почему я писал этот пост
меня удивила фраза Федора в http://codeforces.com/blog/entry/254#comment-3033 про двухмерные массивы в C#
в результате прогона его кода выяснилось, что он прав, а я ошибался
я заинтересовался другими способами использования массива, а потом немного решил погонять и другие языки, заодно проверив фразу Петра о том, что Java медленнее C#
теперь решил сделать измерение корректным и выложить исходники
p.p.s.любители Java ухитрилось заминусовать даже мой коммент со ссылкой на бенчмарк, где Java быстрее C/C++. Очевидно, что Java коррелирует с биполярностью мышления и скудостью ума. Для вас еще есть замечательный пост о гибкой Java: http://codeforces.com/blog/entry/312
Вообще, скорость java, в отличие от c/c++ сильно зависит от проверяющего сервера. Например (на основании моего небольшого опыта) на uva она довольно тормозная, а на timus и codeforces - быстрая. Например, вот мои результаты для ресурсоемкой задачи C с 8 беты http://codeforces.com/contest/8/problem/C
MS C++ - 140 мс 132644 Кб
GNU C++ - 200 мс 132636 Кб
Java - 330 мс 208880 Кб
Медленнее MS в 2.35 раза, а GCC в 1.65 раза
Если не влом, прогони plz свои тесты на codeforces :)
>Например, вот мои результаты
Неинтересно. Нету исходников.
>Если не влом, прогони plz свои тесты на codeforces :)
Прогони сам. Исходники я выложил.
Итак, тестирование умножения матриц (Java 1.6, G++ 4) на codeforces.ru.
Для каждого языка тестировалось следующее:
1) Наивное умножение на 2d массивах
2) Оптимизированное умножение на 2d массивах
3) Наивное умножение на 1d массивах (ручной подсчет индесов)
4) Оптимизированное умножение на 1d массивах
Под словом "оптимизированное" я понимаю следующую очевидную оптимизацию тройного цикла: вместо с[i][j] += ... сначала сделать int v = c[i][j], далее v += ..., потом с[i][j] = v
Теперь к результатам (по пунктам 1 - 4)
Java: 1250 ms, 670 ms, 800 ms, 550 ms
C++ 190 ms, 170 ms, 170 ms, 170 ms
Видно, что "оптимизация" практически не влияет на С++, но ускоряет Яву в 2 раза
Вывод: в С++ можно использовать 2d массивы не задумываясь о производительности. В Java тоже можно спокойно работать с 2d массивами, но при этом необходимо помнить об их природе - это массив массивов.
Автору поста плюсег - затавил критически взглянуть на используемый инструмент :)
P.S. Исходники здесь http://ifolder.ru/17347525
P.P.S Задача C CF #8 - тут 2d массивов нет, но до кучи дам ссылки на исходники
http://paste.ubuntu.com/416628/
http://paste.ubuntu.com/416630/
http://ifolder.ru/17349840
Добавил шарп, поправил java_plain_opt
В отдельном зачете выступают 2d массивы в C# (Mono)
Naive: 2280 ms
Opt: 1130 ms
Они проигрывают всем, в том числе и массиву массивов в C# (Mono)
Результаты (в том же порядке, что и в предыдущем посте)
C++ 190 ms, 170 ms, 170 ms, 170 ms
Java 1250 ms, 670 ms, 800 ms, 530 ms
C# (Mono) 1260 ms, 830 ms, 780 ms, 480 ms
В общем, результаты C# (Mono) практически совпадают с результатами Java
А я не сравниваю быстродействие языков. Это тестирование пошло от того, КАК ЛУЧШЕ использовать массивы в C#.
>в С++ статические двухмерные массивы по типу A[500][500] на самом деле являются одномернымы
Во-первых, неправильная терминология. Во-вторых, для C# как ни странно, двухмерный массив оказался медленее массива массивов. В-третьих, см. предыдущий пост: умножение через vector<vector<int>> оказалось все равно быстрее, тем таковое в Java.
> стандартные библиотеки
А вот это надо делать с большой осторожностью, потому как может оказаться, что сравниваем теплое с мягким.
А я не сравниваю быстродействие языков. Это тестирование пошло от того, КАК ЛУЧШЕ использовать массивы в C#.
>в С++ статические двухмерные массивы по типу A[500][500] на самом деле являются одномернымы
Во-первых, неправильная терминология. Во-вторых, для C# как ни странно, двухмерный массив оказался медленее массива массивов. В-третьих, см. предыдущий пост: умножение через vector<vector<int>> оказалось все равно быстрее, тем таковое в Java.
> стандартные библиотеки
А вот это надо делать с большой осторожностью, потому как может оказаться, что сравниваем теплое с мягким.
>Вполне ясно, что С++ всегда будет быстрее джава.. всегда
Нет, не всегда. Если постараться, то можно найти случай, когда Java будет быстрее.
>зачем
прочитай постскриптум к посту
Вот например http://shootout.alioth.debian.org/u64/benchmark.php?test=nbody&lang=all
А чем в этом аспекте Java лучше Python или Ruby? Только тем, что на ней больше народу пишет?
Не забываем нажать на красный треугольничек!
Зачем забивать темплэйт для чтения - очевидно, чтобы дальше было удобней писать на соответствующем языке. Обычно несколько минут, потраченные на это, не являются очень большой жертвой.
>а я где-то сказал, что С++ хороший?
Нет. Но из заявлений о корреляции Java со скудостью ума можно сделать вывод, что вы не в восторге от Java. А обо всех языках вы вряд ли так думаете - иначе ВСЕ программисты обладают скудостью ума, что сомнительно. Значит, есть какие-то не очень плохие языки. А будет ли стоять в процитированной вами фразе C++, C# или другой язык, её сути не меняет.
Итак, наша цель - попытаться выжать максимальную скорость из каждого языка в поставленной задаче. Пусть вторая матрица заранее транспонирована. Ниже я поделюсь своими результатами.
На С++ удалось достичь времени около 0.138 (код без оптимизаций давал 0.236). Вот отрывок:
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
{
int* ai = a[i];
int* bj = b[j];
int s = 0;
for (int k = 0; k < N; k++)
s += ai[k] * bj[k];
c[i][j] = s;
}
То есть за скобки (за цикл) вынесены два указателя и счетчик суммы.
На С# время вышло 0.360 (код без оптимизаций на одномерном массиве - 0.703). Отрывок:
for (int i = 0; i < size; i++)
for (int j = 0; j < size; j++)
{
int isz = i * size;
int jsz = j * size;
int s = 0;
for (int k = 0; k < size; k++)
s += a[isz+k] * b[jsz+k];
c[i*size+j] = s;
}
За скобки пришлось вынести два произведения. Удивительно, но компилятор до этого сам не додумался.
Но самый враждебный код получился на Java. Время его работы - тоже 0.360 (код без оптимизаций на одномерном массиве давал 1.121 - в 3 раза больше). Выглядит это как-то так:
for (int i = 0; i < size; i++)
for (int j = 0; j < size; j++)
{
int isz = i * size;
int jsz = j * size;
int s = 0;
for (int t = size / 16; t > 0; t--)
{
s += a[isz++] * b[jsz++];
...
// еще 15 раз эта же строчка
}
for (int t = size % 16; t > 0; t--)
s += a[isz++] * b[jsz++];
c[i*size+j] = s;
}
Тут пришлось вручную раскручивать цикл. Жаль, что на Java нельзя написать девайс Даффа...
Конечно, никакому врагу не пожелаешь оказаться на контесте в ситуации, когда возникает необходимость делать вещи, которые должен бы делать компилятор - раскручивать циклы, вручную инлайнить функции и т. д. Тем не менее полезно держать в голове и такие расклады.
Вообще, я помню, как у нас на Всесибирской олимпиаде после разворачивания цикла от 1 до n, где n <= 6, решение стало работать в полтора раза быстрее и сдалось. Решение было на VS C++.