почему не существует метода эффективной компиляции?

Действительно, почему бы и нет. Создай.

Это NP-полная задача.

anonymous (*) (04.04.2005 3:28:06):

> Это NP-полная задача.

Ну да!

И что будет "подсказками"? Как ты сможешь за полиномиальное время сравнить результат двух различных оптимизаций одной и той же NP-HARD задачи?

Это почти та же задача, что и введённая Колмогоровым задача о минимальном алгоритме. Гарантированно минимильный алгоритм находится за экспоненциальное время (от размера сжимаемых данных). Однако, тут всё гораздо хуже, как ты верно заметил - если сам оптимизируемый алгоритм имеет экспоненциальную сложность, то в результате будет O(exp(N)^2), где N - размер исходного алгоритма.

Однако, существует множество более-менее применимых эмпирик, позволяющих находить пусть не лучшее, но *хорошее* решение.

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

WidowMaker:

> Однако, существует множество более-менее применимых эмпирик, позволяющих находить пусть не лучшее, но *хорошее* решение.

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

В данном случае совершенно очевидно, что это даже не NP-задача.

Угу. Worst case для экспоненциальной задачи - exp^2... ОбкакАться можно...

проще всего оптимизировать никогда не останавливающиеся программы:)

Пользуйся Goto и крохотными прогами - рабочими на 100% типа:

на С int main(){ return 0; }

на Pascal'е begin

end.

Шутка. но это одна из самых оптимизированных программ.

мой вопрос был несколько другой -- не поиск оптимального алгоритма (или его хорошей аппроксимации), а "локальная" оптимизация на этапе перевода программы в машинный код (JIT например).

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

Оценка сложности такого алгоритма приводится выше. Читай.

anonymous (*) (05.04.2005 2:14:18):

> возможны ли в принципе такой язык программирования и такой процессор, чтобы программы на этом языке компилировались в оптимальный код простым (в смысле сложности) и способом?

Ассемблер подойдет;)?

А что ты понимаешь под "оптимальным кодом"? Каковы критерии "оптимальности"? Тебя же не интересует минимальная длина получившегося _кода_? Если интересует именно она, то вперед -- хотя Колмогоровская сложность и не вычисляема ;), но компьютер-то -- конечная система, и задача вполне себе NP.

Но тебе ж надо, чтобы программа давала минимальное _время_ на _всех_ входных данных. Что, очевидно, противоречиво по самой постановке вопроса (программа может работать очень быстро при одних входных данных и очень медленно при других. Откуда "идеальный" оптимизирующий алгоритм узнает, что _тебе_ от него надо?).

> возможны ли в принципе такой язык программирования и такой процессор, чтобы программы на этом языке компилировались в оптимальный код простым (в смысле сложности) и способом?

просто этот язык должен быть способен выражать с одной стороны большое кол-во ограничений на написанный код. С другой стороны предоставлять компилятору много свободы -- то есть как можно меньше требовать какого-то строго specified поведения.