Решая квалификацию КРОК мне было лень в С писать некоторые функции руками, возиться с типами и прочим, поэтому я решил сдать задачу на PHP.
У меня возникло два вопроса:
1) Почему самописная ф-ция bitand() работает многократно медленнее, чем встроенный "&"?
2) Как выделяется память на двумерный массив, получаемый при explode()?
И вопрос не по языку: может кто-нибудь объяснить подробно, как собрать HipHop PHP(Все мануалы в сети безнадежно устарели)
Вот они, люди сдающие алгоритмику на PHP
Могу ошибаться, но: 1. смотря, конечно, что внутри bitand, но в любом случае у вызова функции большой overhead по сравнению со стандартной операцией 2. внутри в php все завязано на си-шной структуре zval. Так что создаться zval для массива, который будет хранить ссылки на другие zval-ы (элементы массива). Может оказаться полезной статья http://habrahabr.ru/post/141093/
1) Функция здесь. Всякие оптимайзы, типо не передавать параметры, не использовать функцию как таковую, а вставить блок кода, array_walk ситуацию не решали. Прирост на больших тестах где-то в 4 раза.
Посмотрел код. Как я понимаю, вы собственно числа перевели в итоге в строки из 0 и 1, и поэтому пришлось писать свой bitand... Это очень жестокое решение, ведь понятно, что работать со строками (вернее работать отдельно с каждым символом в строке) — это на несколько порядков дольше битовых операций между двумя числами. И небольшой нюанс:
Вы пройдетесь по всему списку ip-адресов, даже если после первых k+1 адресов у вас окажется k+1 сетей для текущей маски. Скорее всего вы вылетаете вот в этом месте, слишком много считаете. В своем решение я проверял, а не стало ли у нас больше сетей, чем требуется после каждого шага, и если это происходили, то начинал проверять другую маску. Мой говнокод на Python — можете посмотреть, если интересно. Сделать что-то аналогичное на php не проблема.
Не-не, там вылетало по памяти в самом начале из-за двумерного массива(у PHP свои ограничение < установленного ML).
Я на тот вариант функции накрутил потом кучу оптимайзов, в итоге всё равно: Один и два
В обоих случаях мы выполняем побитовое И для двух строк. Откуда такая разница в скорости (>4 раз на больших тестах)?
UPD. Если кто-нибудь поможет с ХипХопом буду мегаблагодарен. Итересно насколько всё будет быстрее работать.
http://pastebin.com/djGEYxbW — вот небольшой тест. Понятно, что сравниваю нативную & и реализацию на if (работаю над символами, как у вас). Запуск на codeforces.ru дает:
Почти в два раза медленнее. Все сводится к тому, что операция выполняется всяко быстрее условного перехода. Ну, дальше можно глубже копать, но в данном случае, наверное, смысла особо не имеет.
См. правку. Не всегда (обратите внимание — немного изменил генератор): Кстати, если сделать ~~~~~$arr[$i] = (rand() % 3 === 1 ? '0' : '1');~~~~~ вообще чудеса будут происходить. Сдаётся мне, rand() не совсем честный и microtime не совсем(точнее совсем не) точный.
Кстати как CF насчитывает время тогда?
Наверняка Codeforces смотрит CPU time, а не wall time. В этом случае не учитывается время ожидания выполнения (например, если выполняется другой процесс или если мы ждём завершения ввода/вывода), и результат отображает собственно время выполнения самой программы.