Взаимосвязь между оптимизацией кода и сжатием данных

Question

Я искал в Интернете об этом вопросе и нашел, что некоторые исследователи использовали алгоритмы сжатия данных для оптимизации компилятора, такие как кодирование Хаффмана.

Мой вопрос является более общим:

Можно ли считать, оптимизация кода, как с потерями типа сжатия?

Answer 1

На конкретном уровне это яблоки и апельсины. Но на абстрактном уровне это интересный вопрос.

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

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

Другая форма кодирующих чисел - это так называемая «унарная нотация», где есть только одна цифра, а числа представлены повторением. Например, цифры «три» и «четыре» означают «111» и «1111», которые занимают N цифр. Этот код оптимизирован путем переключения на двоичный, как в «011» и «100», который берет log (N) цифр (база 2, конечно).

Аналогом программирования является разница между линейным и двоичным поиском. Линейный поиск выполняет сравнение O (N). Каждое сравнение может дать либо много информации, либо очень мало - в среднем намного меньше, чем немного. Двоичный поиск выполняет сравнение O (log (N)), при этом каждое сравнение дает один бит.

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