Являются ли тесты алгоритмов в PHP бессмысленными?

Question

Поскольку PHP проще для меня, я хотел протестировать алгоритмы в нем для удовольствия и решил заняться факториалами.

Рекурсивная функция полностью провалилась по скорости, когда я поднялась до 80! по сравнению с итеративным методом, и она постепенно взлетела вверх, в то время как итеративная имела устойчивую линию, на самом деле это что-то вроде этого (x = factorial, y = секунд ):

Но в C / Java (который я только что реализовал в тесте) показываются те же самые результаты, что они отличаются друг от друга только на 1-5%, почти с такой же скоростью.

Разве бесполезно так тестировать алгоритмы на языках сценариев?

РЕДАКТИРОВАТЬ : для NullUserException:

function factrec($x) {
    if($x <= 1) {
        return $x;
    } else {
        return $x * factrec($x - 1);
    }
}

Answer 1

Совершенно бессмысленно сравнивать алгоритмы на языке сценариев. После выполнения тестов какую реализацию факториала вы бы использовали в PHP? (при условии, что вы не можете использовать встроенный по какой-то причине.)

Это - это довольно бессмысленно для эталонного теста в языке, который имеет существенно отличающиеся особенности от того, в котором вы хотите реализовать алгоритм. Здесь, относительная стоимость вызовов функций и if операторов в PHP значительно искажает результаты (или это мое лучшее предположение в любом случае). Если вы будете осторожны, чтобы понять, почему это происходит, и избегать этого, это все равно может быть плодотворным: как вы заметили, различия будут более преувеличенными. Все сводится к тому, легче ли писать на целевом языке или обходить различия.

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

---

Как отмечает Майк Аксиак в комментариях, вы даже не тестируете здесь разные алгоритмы, вы тестируете две разные реализации одного и того же алгоритма: оставьте работающий продукт более i с n до 1. Делать это на другом языке, нежели цель, почти всегда бессмысленно.

Answer 2

Java и C на несколько порядков быстрее, чем PHP.
Вам понадобится значительно увеличить размер ввода, чтобы увидеть результаты.

Кроме того, как сказал Аарон МакСмут, бессмысленно сравнивать алгоритмына языке, отличном от того, на котором вы планируете его использовать.

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

function factorial($n, $product) {
    if ($n < 1)
        return $product;
    else
        return factorial($n-1, $product*$n);
}

print(factorial(80, 1));

Answer 3

Учитывая, что задание было забавным, оно не может быть бессмысленным!Но попытки заставить PHP выполнять рекурсивные вычисления могут указывать на то, что вы почти готовы попробовать функциональный язык программирования.Вы видели Haskell?Оптимизация вызовов на хвосте, кто-нибудь?

Да ладно, присоединяйтесь к темной стороне.

Answer 4

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

Answer 5

Бенчмаркинг никогда не бывает бессмысленным.Если у вас есть код, написанный на любом языке, который слишком медленный для вашего приложения, вы обнаружите узкие места.Глядя на эти узкие места, вы ищете решения.Одно из решений может заключаться в том, чтобы использовать другую формулировку алгоритма или даже переписать на другом языке.

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

Answer 6

Рекурсивная и итеративная реализация не должна оказывать реального влияния на асимптотику конкретного алгоритма.В некоторых языках (scala, Scheme, Lua, Standard ML, Mozart / Oz, erlang) два могут фактически быть написаны так, чтобы они выполнялись абсолютно одинаково.То есть следующий код схемы:

(define factorial
  (lambda (n acc)
    (if (= n 0) acc
        (factorial (- n 1) (* n acc)))))
(factorial 5 1)
-> 120

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

Answer 7

По моему мнению, если бы я тестировал сам алгоритм , я бы пошел на C / C ++, чтобы получить "сырую мощность", которую он может дать в оптимальных условиях.

С другой стороны, если бы мне пришлось выбирать, какой алгоритм лучше всего работает в определенных условиях, я бы попытался в лучшем случае повторить такое условие.Это должно быть помещено в приложение PHP?Давайте проверим это на PHP, со структурами, предоставленными PHP.Нужно ли работать с контейнерами STL?Я буду тестировать в этом состоянии, а не только с массивами.ИМХО тестирование в реальных условиях - ключ к получению значимых результатов.После получения таких результатов, еще одна хорошая вещь - это настроить такие условия (насколько вы можете изменить их в проекте) и посмотреть, какие эффекты вы получите, чтобы найти лучшую пару условий-алгоритмов.