Дошли руки и до поддержки столь модного сейчас JavaScript. Выбрана реализация V8, как наиболее трендовая и развиваемая. С помощью бубна и литра колы я скомпилировал V8 под Windows. Забавно оказалось — я всё думал, что придется городить workaround, чтобы поддержать чтение в JavaScript из консоли. Оказалась, что d8 сам всё умеет. Вот пример для нахождения A+B:
var line = readline().split(' ')
print(parseInt(line[0]) + parseInt(line[1]))
Было замечено, что если не поставить перевод строки в конце ввода, то readline вернет undefined. Еще один аргумент в пользу того, что все строки должны заканчиваться переводом.
В качестве небольшого исследования и чтобы потешить свою уверенность в мнении, что все языки без статической типизации бесконечно медленны, я написал реализацию HeapSort на С++, Java и JavaScript для сортировки 107 значений от 0 до 9999999. Видимо, этот бенчмарк неплохо показывает как быстро будут работать ваши решения, если вы пишите их в стиле старого доброго Pascal (всё на массивчиках, без выделений памяти и без мощных встроенных библиотек). Результаты для меня оказались неожиданными:
| Language | Compiler | Running time, ms |
|---|---|---|
| C++ | MinGW 4.7.2 32-bit | 630 |
| C++ | MS VS 2010 32-bit | 650 |
| Java | Oracle Java 6 32-bit | 1060 |
| Java | Oracle Java 7 32-bit | 1050 |
| JavaScript | V8 3.23.0 32-bit | 1700 |
| Pascal | Delphi 7 32-bit | 630 |
| Pascal | FreePascal 2.6.2 32-bit | 730 |
| Python 2 | Python 2.7.4 32-bit | 12500 |
| Python 3 | Python 3.3.2 32-bit | 20000 |
| Ruby | Ruby 1.9.3p0 (2011-10-30, i386-mingw32) 32-bit | 520000 |
| Ruby | Ruby 2.0.0p353 (2013-11-22, i386-mingw32) 32-bit | 345000 |
| Scala | Scala 2.10.3 (over Oracle Java 7 32-bit) | 1550 |
| Go | Go 1.2 32-bit | 1780 |
| D | DMD v2.064.2 32-bit | 800 |
| C# | Mono 2.10.9 32-bit | 850 |
| C# | MS CSC .Net 4.5.1 64-bit | 850 |
| Perl | Perl v5.12.2 for MSWin32-x86-multi-thread | 195000 |
Отставание-то всего ничего! Я конечно понимаю, что такой код можно заанализировать и jit-ом прям в нативный закомпилить, но все же. Впечатляет. Кстати, а Java с её хваленным и нахаченным JIT не на высоте.
Вот я даже запилил микропроект на github, чтобы не потерялось. Предлагаю подключиться и переписать реализацию на ваш любимый язык, а я включу его в исследование. Вот явные ссылки на текущие реализации:
Вы можете оставлять в комментариях ссылки на pastebin или сабмиты в систему. Конечно, будут удобнее пулл реквесты прямо в проект.
Если будете писать свою реализацию, то постарайтесь написать аккуратно и опрятно. Пожалуйста, максимально придерживайтесь вариантов для C++, Java и JavaScript.
UPD 1: С помощью alexei-zayakin добавил Pascal.
UPD 2: С помощью gchebanov Wizmann и juancate добавил Python 2, Python 3, Ruby, Scala, Go.
UPD 3: Вот скомпилированный для Window V8.
UPD 4: Обновил версии некоторых компиляторов, обновил результаты.
UPD 5: Добавил D. Спасибо, Gassa.
UPD 6: Добавил C#. Спасибо, gmogelashvili.
Есть подозрение, что JIT просто не срабатывает на столь кратковременных программах. А время старта VM тут учитывается? Попробуйте скомпилить через Excelsior Jet :-)
Конечно, я пробовал прогревать JVM — разницы особо нет. Мне кажется, что на 107 элементах подкомпилит что надо и так.
http://pastebin.com/Hp9CMPfD Написал на питоне, правда работает очень медленно(при n = 100000 около 2-х секунд). Возможно я что-то не понимаю?
Я Питон не знаю, но точно h = list(range(N)) — это прямой аналог plain-массива?
Да, точно.
Пробовал для проверки заменить на h = numpy.arange(N) (Гарантированно массив со статической типизацией, состоящий из int32)
Замедление на 50%.
http://pastebin.com/QL1fuZ5C
Такой код выглядит более честно(При вычислении времени учитывается выделение памяти), и у меня работает быстрее.
http://pastebin.com/zGDH9s1D
Попытался написать на вариант на хаскеле(з.ы. его я знаю плоховато) без хаков(в.т. и Mutable Arrays) Т.к реализация ссылочная на дереве, а не на массиве немного исправил логику: достаём не последний элемент, а самый левый лист. (Иначе 60% времени занимало вычисление того, что нужно удалить)
При N = 106 выделяет память на куче 5144Мб, 79Мб реально запрошено у ОС, 1.8 сек. сборка мусора, общее время 5.8 сек.
Тут что, никто не пишет на Haskel'е?
Если
data Heap a = Node a (Heap a) (Heap a) | Noneзаменить наdata Heap = Node {-# UNPACK #-} !Int {-# UNPACK #-} !(Heap) {-# UNPACK #-} !(Heap) | None, то локально у меня общее время с 5 секунд уменьшается до 4. :) КодДля Haskell на мой взгляд есть две альтернативы
Пользоваться функциональными кучами, например LeftistHeap, SplayHeap или BinomialHeap. Решение с LeftistHeap локально работает 0.4sec, но это еще не показатель, так как машины у всех разные.
Писать честную пирамидальную сортировку в ST монаде. Код будет практически эквивалентен коду на Си.
Можно использовать более точное начальное значение:
Попытка на Ruby http://pastebin.com/ETr81Z3x Выполняется очень долго
Это сколько в секундах? Интересно сравнить с Python, PHP
Если взять N = 100000, т.е. уменьшить в 100 раз, то у меня версия на Ruby работает 700ms, а вышеприведённая на Python — 1400ms.
Если N = 1000000 (миллион), то Ruby — 11s, Python — 18s
Мне стало интересно сравнить скриптовые языки. У меня получились следующие данные на N=1 000 000:
На моей машине получилось вот так. Данный бенчмарк не претендует на истинность, но возможно кому-то будет интересно
Udp: подредактировал время. сделал по 5 попыток, выбрал минимальное
Так вы на своей же машине прогоните решение на C++ которое выше есть — чтобы иметь "точку отсчёта" так сказать...
Результат для nodejs должен быть раз в 10 меньше
В смысле быстрее чем для C++? Это почему он должен быть таким?
На моём ноуте для N = 1000 000 nodejs работает за 250ms.
А остальное с какой скоростью?
Я обновил пост. Странный провал в производительности на Ruby. Может в Ruby 2 дела получше будут?
я еще на ruby 1.8.7 попробовал, правда с меньшим N, и тоже получил большой провал 65,990 s против ruby 2 (9,899 s) на моей машине
Поставил 2.0.0. Стало лучше, но всё равно крайне медленно.
Попробовал на OS X 10.8 python 3.3 и ruby 2.0, ruby в 2 раза примерно быстрее проходит
Чтобы помочь потешить, вот на PHP. Работает примерно как вышеупомянутая реализация на питоне — с 1млн в "запуске" отрабатывает за 8 сек.
Правда у PHP массивы это не массивы а LinkedHashMap наших аналоги если я верно помню.
Так что возможно дело не в типизации а в реализации. V8 видимо здорово стероидами подмазали разработчики — в джаваскрипте тоже ведь массивчики по-моему нетривиальные в смысле реализации внутренней?
UPD: Нет, кажется чуточку быстрее питона :D
интересно, kphp ускорит работу? и если да, то во сколько раз.
А как легче всего запустить V8 под Windows? Можно ли скачать бинарники или надо из исходников собирать?
Добавил ссылку в пост.
Было бы неплохо, если бы кто-нибудь написал туториал на тему JavaScript-а в олимпиадах — какие-то трюки, ускоренный ввод-вывод, где как писать, как отлаживать итд.
Боюсь и писателя и читателя тюториал такой быстро приведёт в отчаяние. Вот создаём массив, заполняем и пробуем вывести его в цикле двумя способами:
http://ideone.com/MeaKZn
Порядок явно различается, во втором случае выводятся только численные индексы (включая текстовые содержащие число).
И вот тут мы начинаем думать — работают ли оба этих цикла за O(n) или O(max(a)), или ещё как-то? А ведь и реализации разные бывают...
А какое быстродействие при доступе к элементу по индексу? Линейное или логарифмическое? Слишком много загадочных нюансов... :)
Возможно стоит попробовать погонять python под cython
It would be interesting running Python 2 version in PyPy, in my computer (which is worst than codeforces computers) it has almost the same runtime.
Реализация на Go
кстати, не так давно появился релиз Go 1.2 с несколькими важными улучшениями производительности (см. здесь), хотелось бы видеть его на Codeforces
Насколько я понимаю, именно то, что некоторые реализации языков программирования очень плохо кушают файлы, не заканчивающиеся переводом строки — основной и чуть ли не единственный аргумент, почему под Windows надо в СП завершать файлы переводом строки. И мне до сих пор непонятно, как это соответствует конвенции корректности ввода, если это явно не указывать в условии задачи. Например, в 374A - Инна и розовое пони получается, что существует вторая строка входного файла, т.е. входной файл может содержать не только то, что описывается в разделе "входные данные".
Кстати, на школьной олимпиаде в Самаре несколько участников попалось на то, что питон вычитывает через readline() закрывающий перевод строки, если он есть, и не вычитывает, если файл завершается. Поскольку в pdf совершенно очевидно, что в примерах этого перевода строки нет, а на самом-то деле он всегда есть, я совершенно не знал бы что делать, если бы на это пришла апелляция.
Уже неоднократно приводились аргументы, что завершать каждую строку текстового файла переводом удобно.
Еще раз: перевод строки в конце — это аналог \0 в С/C++. В задаче 374A - Инна и розовое пони никаких проблем нет. Там написано "В первой строке входных данных находится шесть целых чисел", что и является правдой. Более того, входные данные не содержат ничего лишнего, т.е. эта строка единственна.
По поводу вашей олимпиады. Конечно, в 2013-м году организаторам надо приложить усилия, чтобы у участников была возможность во время тура послать решение в систему и убедиться, что оно работает на сэмплах. Если этого не было, значит условия проведения так себе.
Кроме того, это хорошая практика на открытии или другом мероприятии перед олимпиадой напомнить какие-то детали. Например, на ЧФ в Саратове я обычно упоминаю об этом переводе.
Если есть подозрение, что участники олимпиады могут быть неподготовлены к каким-то техническим сложностям, надо сделать памятку участника, куда внести эти моменты. Речь не только об этом переводе строки, но и других деталях (например, требование дефолтного пакета в Java). На наших олимпиадах в Саратове мы делаем такую памятку.
Если всё это сделать не получается, то имеет смысл перетестировать решения в двух вариантах тестов и выбрать лучший результат. Это надо сделать для всех, а не только для тех, кто подал жалобу. Хорошо бы потом донести информацию до участников, чтобы подготовить их к будущим участиям.
Почему вы считаете, что в этом файле единственная строка? Явного стандарта на то, что такое этот символ, нет, однако есть стандарт POSIX что должно завершаться (только POSIX-стандарты под win достаточно странно использовать) и есть стандарт Unicode, в котором разъясняются юникодные переводы строк и приведение к ним, в частности, что \r\n или \n или как-еще-перевод-строки желательно переводить в один из двух юникодных символов, причем каждый из них это разделитель (строк и параграфов). Т.е. консорциум Unicode абсолютно уверен (как и все windows-приложения), что endl разделяет строки (аналог
), а не завершает строку.
Ответ на сэмплах с переводом строки не отличается от ответов на сэмплах без перевода строки, так что можно без подобных сарказмов. Проблема всплывает на определенных тестах, участники в итоге на халяве получают 54 вместо 100.
Upd. Что характерно, сэмплы в системе на этот же перевод строки отличаются от сэмплов, указанных в условии — тоже интересная тема для апелляции.
Реализация на OCaml
10^7 elements from 0 to 9999999 or 10^7 elements from 0 to 999999?
that looks like 10^6 only.
sorry, my mistake. i count the number of 9's wrong. i should have confirmed before commenting. :(
this or the same thing?
Hi, Mike.
I'm Wizmann in
UPD 2.I run the initial version of the
Scala heapin Codeforces CUSTOM TEST.The code use @tailrec only take 1157(ms) to finish the job, much faster than the one use
while ... breakwhich cost 2070(ms).I guess there must be some performance problem with the
break commandin Scala. Because raising an exception withScala breakis much slower than a simple jump command withC++ break.I have to say it not quite fair for Scala if you choice to use
while ... breakin the code. :)See: http://daily-scala.blogspot.com/2010/04/break-performance.html
(Sorry for my poor English ^_^)
Thanks, done. Also I've updated Scala to 2.10.3.
Wow I wonder why ruby is so slow? I will try and improve the solution to see if I can get it to perform better.
Почему же никто не обратил внимание на то, что входной массив не шаффлится?
После добавления random_shuffle код на C++ стал работать в 2 раза дольше, на Java — примерно в 2.5 раза.
Да, да, я не забыл, что время нужно мерить с момента начала кода сортировки.
К сожалению, сказать навскидку причину подобного поведения хипсорта я не могу. Может ли кто объяснить?
Он не шаффлится специально. Это же HeapSort, он сначала строит кучу. На этом тесте HeapSort работает O(nlogn) и гарантировано одинаково для всех языковых реализаций.
Так зачем давать такой искусственный бенчмарк, не учитывающий поганую особенность хипсорта: рандомные прыжки по памяти? Ниже я написал чуть больше.
Рандомшаффл с помощью встроенного рандома для каждого языка и то будет лучше, при условии того, что, как я уже написал выше, мы будем измерять только время сортировки.
Ну мы же не средний случай heapsort бенчмаркаем. В решениях часто алгоритмы хорошо попадают в кэш. Здесь же далеко не всё так хорошо попадает, иначе время отличалось бы сильнее.
Ага, но только почему-то даже хорошо написанный квиксорт из VS 2010 на пошаффленном массиве работает медленнее, чем Ваш хипсорт — на отсортированном. Квиксорт, как мы знаем, cache-friendly.
Ну просто pushDown брейкается раньше, вот и все.
Чушь!
Только что посчитал количество итераций цикла while из функции pushDown для обоих случаев, в случае отсортированного массива их даже больше.
Как я сейчас подумал, проблема должна быть в кэш-промахах (хорошо известно, что хипсорт плохо работает на больших массивах именно по этой причине). А в случае предварительно отсортированного массива куча получается весьма "красивой", и доступ к элементам часто осуществляется чуть ли не последовательно.
Да, это второе, что приходит в голову)
Мне кажется, дело в предсказании переходов.
Branch prediction.
Только что проверил — это неправда.
Если проанализировать все переходы в функции pushDown, то выясняется, что для большинства из них очевидно, куда именно обычно происходит переход, вне зависимости от факта отсортированности массива. Вопрос возникает только по поводу условия
h[j + 1] > h[j], но обе его ветви примерно равновероятны в обоих случаях.Так что дело все-таки в кэше.
Кстати, может быть, имеет смысл добавить на тестирующий сервер не только "чистый" V8, а ещё и NodeJS?
А есть мысли как будет выглядеть аналог этой программы для NodeJS?
Конечно. Я написал на эту тему в том числе, у себя в блоге. Если Вам удобнее такое API (readline, print), то вот Вам готовый шаблончик для ноды:
Просто с нодой Вы бонусом получаете ещё кучу вкусностей а-ля require и т.д.
Hi!
Unfortunately, the Ruby implementation is not only very non-idiomatic in terms of code, but it does abuse the assignment operator to perform the exchange. This is why it is slower in the benchmarks. You'll find it performs way better if you take this into account.
Here's a pull request: https://github.com/MikeMirzayanov/binary-heap-benchmark/pull/10
In my testing, this version outperforms Python3 by a factor of 2. No clever tricks added.
Here's an implementation in Haskell: http://pastebin.com/cuFZ6eMi I tried to be very close to the C++ version, but I had to use tail recursion instead of loops. Should perform somewhere between Java and Scala.
It would be better to try and be idiomatic instead of mimicking C++. Otherwise it's neither realistic, nor do you allow Haskell to do it's thing.
I admit heapsort isn't the easiest thing to do ideomaticly in Haskell though :-) There is an implementation here http://hackage.haskell.org/package/heapsort-0.1.0/docs/src/Data-Array-MArray-Heapsort.html
Всегда думал, что С# медленее Java, а он вообще на уровне С++ работает. Почему так? Или я не правильно думал?)
Скорее, странно, что delphi не обгоняет C++. Технически это означает, что компилятор делфы написан намного хуже, поскольку, например, в Паскале есть арифметические циклы, а в C++ нет.
А с чего бы ему обгонять? Арифметический цикл всё равно раскроется в
for (int i = 1; i <= n; i++).А можно поподробнее?
Вот пример цикла на C++:
А вот пример цикла на Паскале:
Компилируем первый код
g++со средними оптимизациями (с-O2, но без-funroll-loops), получаем следующий отрывок ассемблерного кода внутри цикла:Компилируем второй код Free Pascal-ем и получаем следующий отрывок ассемблерного кода внутри цикла:
А теперь вопрос: что же могло получиться принципиально лучше в коде на Паскале, но вот не получилось? Насколько я понимаю, об эквивалентности таких циклов на Паскале и на Си компиляторы знают уже несколько десятилетий... Или под выражением «арифметический цикл» имелось в виду что-то другое?
В .NET'е JIT компилирует байт-код в машинный код, с чего бы ему тормозить. Хотя отставание от C++ имеется, потому что любое обращение к массиву в обязательном порядке сопровождается проверкой границ массива.
Вот вам perl в копилку. http://pastebin.com/nBSKRPzy
У меня локально работает около шести минут, но решение на С++ работает 2100, что в три раза дольше бенчмарка от Майка. Думаю, в две минуты должно зайти здесь.
Извиняюсь, что нет таймстэмпа, я не умею делать его мультиплатформенным.
лол
Как-то так можно засечь время с более-менее высокой точностью.
http://pastebin.com/ZtRhsJQz — здесь код ifsmirnov с патчем.
Спасибо, завтра добавлю.
Спасибо!
Ну, вообще это уже не новость что javascript сейчас разогнали до безумия несмотря на все его косяки. Вот, кстати, из недавнего https://hacks.mozilla.org/2013/12/gap-between-asm-js-and-native-performance-gets-even-narrower-with-float32-optimizations/comment-page-1/
А так вообще абсолютно бессмысленное занятие сравнивать реализации "в лоб" на разных языках. Тот же питон в основном тормозит на переходах си-питон, так что оптимизация в нем совершенно иначе идет чем в Си. Например, что массивы разиндексировать что хеши одинаково по времени в питоне.
И много пишется программ на питоне, где не используются ни массивы ни хэши? Я видел такие, но они совсем короткие были. По моему вполне неплохой тест получился.
Это к чему вообще? Можно относительно быстро работать с массивами на питоне, просто циклы поэлементные лучше избегать, например. А идеальных бенчмарков вообще не бывает, вон там сколько по моей ссылке привели и все разные, так что один хипсорт тут вообще ни о чем.
В олимпиадном программировании часто возникает потребность в поэлементных циклах, поэтому я считаю, что бенчмарк в этом контексте вполне неплох.
Вообще языки сравнивать — это редко когда хорошо, потому что по большей части они для разных задач. Но в олимпиадном программировании задачи-то одни и те же, поэтому и сравнение реализации в лоб кое-что да показывает.
В Си может и часто, а вот сколько я тут задач на питоне загонял, ну, в паре штук от силы были такие проблемы. В хаскеле вон вообще нет никаких циклов и ничего, пишут люди.
Я не говорил, что во всех задачах, я сказал, что во многих. Да, в некоторых из них можно легко от этого уйти. А как посупать с циклами через несколько элементов? Или запоминание позиции в массиве? Или со свапами со следующим или еще каким-нибудь элементом? Ну а как поступать с большиством задач на дп, где индексы являются ключевой информацией? Пока я не могу согласиться с тем, что таких задач мало.
P.S. То, что сдают на хаскеле некоторые задачи я не считаю аргументом, опять же потому что сделать то, что я описал выше, как минимум намного сложнее.
Мыслить надо шире. Помнится, в каком-то RCC где сишники помирали в своих индексах динамики я просто зафигачил все состояние (произвольный кортеж) как ключ в словарь и на ура прошло.
Это что же получается, вы перескочили с объяснения того, что в питоне можно эффективнее работать с массивами и поэтому бенчмарки говно, на то, что у вас был словарь, у которого вы получали элемент по ключу (sic!), да еще и ключем был кортеж. Или я что-то уже не понимаю, или ваш пример ну совсем не в тему.
Это прямой пример на то что в питоне оптимизация делается совершенно иначе. Иногда лучше выкинуть массивы нафиг и взять хитровыдуманный словарь или еще что.
В таком случае напишите, пожалуйста, хорошую реализацию хип-сорта на питоне, очень хочется посмотреть.
Первое что в голову пришло:
Это еще хипсорт, причем раза в два быстрее местного. Но смысла в нем примерно столько же что сразу h.sort() написать, ИМХО.
Честно говоря, это не то, что я хотел бы увидеть( Так не интересно.
Мне нравится питон, он крутой, и я бы хотел увидеть, как можно скиловано реализовать на нем такую штуку, как хипсорт, а вы мне показали, как юзать библиотеку(
Ну, можно почитать исходники библиотеки, она на питоне. Но смысл-то в том что оптимизация тут это сведение всего и вся к встроеным плюшкам и библиотечным функциям. В чистой вычислялке и ежу понятно что питон и рядом с Си не лежал, так можно и в 1000 раз проигрыш получить как нефиг.
Это похоже на сравнение бензопилы и топора.
Ну то есть, не пишут люди чистый хипсорт на питоне. Не для этого он нужен. Отсортировать можно и более эффективно, используя стандартную библиотеку.
http://codeforces.com/blog/entry/10594
Hi everyone, I wrote a blog post on my experience using JavaScript on Codeforces.
Could you please add Java 8 result? Looks like it has ~10% imprevement over 6&7 in this test. Edit: it would also be interesting to see how Scala performs on JVM 8.
what does d8 mean in this blog?
interactive javascript shell integrated into V8
@MikeMirzayanov is it possible to added support at least ECMAScript 5.1? Current version on server is JavaScript 1.8.1 which is already 6 years old...
And I wanna to see the benchmark too ;)
Do you know that they to support it? We need version which:
obvious node.js, no? If you concerned with security you can use node's standart
vmpackage. For example you can exposeprocess.stdinandprocess.stdoutfor user scripts (alsofs.create(Read|Write)Streamfor file I/O) and block everything else.Я вижу что среди поддерживаемых языков появился NodeJS 6.9.1. Это очень круто! Но для ввода/вывода
readlineиprintбольше не работают. Кто знает как читать и выводить? Возможно появилась поддержка чтения/записи в файл?Hi, BigInt primitives are supported in recent V8 engines: https://v8.dev/blog/bigint
I wish it could be added to Codeforces. It's very helpful.
It's actually not possible to solve some of the problems without BigInt. I've already gave up on a couple of contests.
Thank for the information. Why is it? is the performance very bad?
Some of the tests that get applied on a JS-based solution contain very large integers that the old version of the JS runner on this platform simply cannot handle.
JS regular integer manipulation is only accurate up to 2^53, anything beyond that and the calculations do not make sense anymore. (example: 10000000000000000 — 9999999999999999 yields 0 instead of 1) This has been addressed by adding the BigInt library (which is now integrated in most browsers and newer versions of V8) that can handle those big numbers, a library that is not present in the current version of JS in this platform.
You're right. That's why I was wishing Codeforces platform to update the V8 engine.