Все про неё, любимую.

Итак. Я скачал раздельно датафиды по всем годам и обработал их - отдельно - тем же сумматором, что и в предыдущем случае, убавилось только количество столбиков (теперь 10). Отсечка прежняя: не менее 3 матчей, в которых участник появлялся и не менее 3 задач.

График отвечает на вопрос "берем наугад участника топкодера со средним рейтингом между N-1 и N децилями (если не знаете что это такое http://ru.wikipedia.org/wiki/Дециль#.D0.94.D0.B5.D1.86.D0.B8.D0.BB.D1.8C), берем наугад его задачу по которой было Submit или Compiled, какова вероятность, что использовалась Java?" Справа подписано количество учтенных участников.

В 2001 году статистика вероятно, была с ошибками, в более поздней я ошибок не нашел, поэтому начинаю с 2002 года. Что же такое произошло между 2003 и 2004 годом? По вот этой http://www.tiobe.com/index.php/content/paperinfo/tpci/index.html штуке 2003 год был годом языка, который я называть не буду (и вообще это оффтопик). Правда, какое отношение это имеет к Topcoder, данных не имеется.

По поводу новичков. Казалось бы, если на каком-то языке пишет много новичков, то со временем, новичок должен превратиться в опытного и вообще частота использования языка должна от этого расти, а не убывать. А распределение уже много лет как не меняет форму!

В отличие от предыдущих, этот пост именно про Java. Топкодер, как известно, дает нам datafeeds, по которым можно подсчитать статистику какого-нибудь рода. Вот здесь и подсчитана зависимость по 50 последним SRM'ам частоты использования Java. Для задач, для которых участник произвел Submit, или только Compiled, топкодер указывает язык в датафиде для SRM'а. Это лучше, чем default language в профиле, т.к. он не у всех указан и его нет в датафидах.

Участники, у которых было <3 участий в SRM-ах из выборки, или менее 3 submit or compiled, не учитывались. Остальные были поделены на 20 столбиков и в каждом столбике считалось среднее арифметическое частоты использования Java для каждого участника. На оси X подписано правое граничное значение рейтинга для каждого столбика.

Исходный файл скрипта-скачивателя и парсера приаттачен к рисунку (RARPNG). Рекомендуется использовать Linux или cygwin для запуска.

http://img188.imageshack.us/img188/701/graph1v.png

[p.s. не совсем понятный интерфейс CodeForces - я думал, что сервер хранит копию картинки]

Кажется, видна корреляция. Поставьте мне кучу минусов за неправду.

_{К сожалению, вставка самой картинки получилась не очень хорошо}

http://img89.imageshack.us/img89/8982/olympmathhumanitarian.jpg

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

Каждый код прогонялся три раза в 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://mirror.codeforces.com/blog/entry/254#comment-3033 про двухмерные массивы в C#

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

я заинтересовался другими способами использования массива, а потом немного решил погонять и другие языки, заодно проверив фразу Петра о том, что Java медленнее C#

теперь решил сделать измерение корректным и выложить исходники 

p.p.s.любители Java ухитрилось заминусовать даже мой коммент со ссылкой на бенчмарк, где Java быстрее C/C++. Очевидно, что Java коррелирует с биполярностью мышления и скудостью ума. Для вас еще есть замечательный пост о гибкой Java: http://mirror.codeforces.com/blog/entry/312

По следам обсуждения

http://mirror.codeforces.com/comments/264#comment-3078

На c# умножаем две квадратных матрицы. В одном случае - каждая матрица хранится в массиве массивов, в другом - в двухмерном массиве.

[дисклеймер: эти измерения подобны измерению числа оборотов двигателя на холостом ходу, а не средней скорости автомобиля в условиях гонки, и т.п., проводились один раз и т.п.]

Я взял код maslowmw, изменил size на 500, убрал распечатку времени (что дает несущественную разницу) и понес гонять его в Topcoder Practice Room. К моему удивлению, действительно в той версии дотнета, что установлена на топкодере, двухмерный массив оказался медленнее массива массивов. Меня это заинтересовало и я решил провести измерения других вариантов. Вот они, а выводы делайте сами.

c#:
[i][j]: 1.328s 

[i][j]: 1.156s % size = const int
[i,j]: 1.516s
[i*size+j]: 0.875s

[i*size+j]:  0.703s % size = const int

c++:
int [][]: 0.266s % const int, global
int **: 0.791s
[i*size+j]: 0.286s % where size = const int
[i*size+j]: 0.695s % where size = input parameter
vector<vector<int>> : 0.478s % where size = const int
vector<vector<int>> : 0.608s % where size = input parameter

java:
[i][j]: 1.927s
[i*size+j]: 1.306s

p.s. мэнтайнерам сайта: создайте FAQ по оформлению. и еще, при переходе из почты по ссылке на русский коммент, а активен английский, то коммент разумеется не видно, что запутывает.

Recently one of codeforces participants mentioned Java as 'flexible'. (he did not specify what he was comparing it with).

As a sceptic, I wish it to be demonstrated in problem which I have been interested long time ago.

Words I have for default font in Arena applet are not printable. It is difficult to read, which especially affects challenge phase. After I found something better, my rating grew from 1500-1700 to 2100. An ideal solution would be to use custom font (after all, humans are different). Unfortunately, tools for creating vector fonts are overcomplicated and/or expensive, and vector fonts are not needed at all in this case because the font needed will never go to printer or any other high resolution device. Raster fonts are very easy and fast to edit, but as you have might already guessed, Arena applet running under Sun's JVM does not allow to use them. I know that open JRE/JVM implementations exist. So, what is possible to do?

p.s. любители Java, все срочно выстраиваемся в очередь и минусуем пост, проблему-то решить вы не можете

На каждом поле шахматной доске либо лежит, либо не лежит зёрнышко. Тюремщик случайно выбирает поле на доске и показывает на него первому игроку. Тот должен по выбрать поле на доске по своему усмотрению и, если оно пустое, поставить на него дополнительное зерно, либо если оно уже есть, убрать его с доски. После чего первого уводят, приводят второго, который должен определить (с первой попытки), какую клетку выбрал тюремщик.

Как и во всех задачах подобного рода, обмен информацией между игроками после начала игры невозможен. Гарантируется, что на доске после 1-го игрока и до 2-го ничего не меняется и доска не поворачивается.

В решении Исенбаева http://www.topcoder.com/stat?c=problem_solution&rm=302833&rd=14174&pm=10420&cr=22221928

есть такой фрагмент

if (10000000000000000L / a < b) {
return Long.MAX_VALUE;
}
long g = gcd(a, b);
long t = a / g;
return t * b;

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

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

UPD: что насчет C# ?

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

В машинном коде процессоров x86 и многих других существует механизм, также называемый исключениями. Через него осуществляется много полезных вещей, таких как виртуальная память, отображаемые на память файлы, эмуляция не поддерживаемых аппаратно инструкций (использовалось на VAX, где решено было сократить систему команд процессора и эмулировать редко используемые команды, использовалось на x86 без FPU, используется в NTVDM), отладочные функции и т.д. Если среда и язык не поддерживают такие механизмы, то реализация кода, используещего ту же функциональность, была бы в значительно длинее.

В отличие от процессорных исключений, в языковых исключениях управление передается "наверх" до внешнего блока, который "поймает" исключение (в ЛИСПе более богатая модель, но в большинстве языков этого нет). При этом контекст, в котором произошла ошибка, будет уничтожен. Что уже делает этот механизм непригодным для реализации ряда "вкусностей". Есть и другие проблемы. Например, отловить момент, когда не хватает памяти, по таким исключениям невозможно -- в средах с виртуальной памятью выделение памяти всегда завершается успешно, а ошибка возникает при попытке обращения к ней.

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