Здравствуйте, VladD2, Вы писали:

VD>Здравствуйте, Sinclair, Вы писали:

S>>Да ладно. Никакого предела ускорению программ путём суперкомпиляции нету. Привожу простой пример: делаем разложение чисел на простые множители.
S>>Обычный компилятор компиляет алгоритм, который получает O(exp(N)).

VD>То есть исходно мы имеем супер-нееэффективный алгоритм и путем его переписывания в эффективный получаем значительное ускорение?
Нет. Исходно мы имеем нормальный алгоритм A, который работает для любого инпута x из множества X.

Затем, путем ограничения набора инпутов множеством X'<X мы пытаемся получить частный случай этого алгоритма — A', который работает быстрее, чем A. Но только на инпутах из X'.

VD>Гы-гы. Кремлевский мечтатель. Представим что у алгоритма есть 10 параметров или 2 но с очень большими значениями. В итоге мы получаем или многомерную структуру неопределенного размера стремящуюся к бесконечности, или двухмерную но тоже вылезающую за память компьюетра.
Увы — эта красивая теория подтверждена суровой практикой. Представь, что у алгоритма есть 10 параметров, но в твоей конкретной программе 9 из них фиксированы, и меняется только десятый. Суперкомпилятор будет способен существенно улучшить характеристики этого алгоритма. Вопрос только в том, насколько часто встречаются такие программы.
VD>В общем, это все мечты. Если алгоритм исходно оптимальный, то никакие суперкомпиляторы его не ускорят (а замедлить могут).
Почитай что-нибудь про частичные вычисления.
VD>Вот тебе простой пример. Ускорь алгоритм LL(1)-парсинга.
Ок. Какие ограничения на инпут ты предлагаешь?

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

VD>Нужно понимать, что частные оптимизации мало интересны, так как устанешь затачивать под них компилятор.
Не частные, а частичные. Затачивать ничего не нужно. Всё заточится само.
VD>То что ты описал влет оптимизируется путем тупой мемоизации (в том же Немерле — это ровно один атрибут на метод повесть).
Нет, не всё. Речь же не просто о перечислении значений параметров. К примеру, если известно, что параметром некоторого floating-point алгоритма всегда будут целые числа, то частенько можно его подкрутить так, чтобы он был быстрее. Никакая мемоизация тут не спасёт.

VD>Ну, и как добиться ускорения в 50 раз?
Я тебе написал пример про разложение на множители. Там и 50000 можно получить. Тебе знаком полиномиальный алгоритм разложения на простые множители? Тогда тебя ждет премия Тьюринга.
VD>Я вижу только один способ — писать чудовищно бездарный код и очень умный компилятор.
Может, всё же почитаешь ссылки, прежде чем делать безапелляционные выводы?
Всё наоборот — пишем хороший код, и очень тупой, но тщательный компилятор.