@Vort_

Всем привет.

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

Основной вопрос, на который я пытался получить ответ, - "сколько нужно кода для решения какой-либо конкретной задачи?". Понятно, что в зависимости от целей оптимизации (скорость, читаемость), размер будет разным, но каков минимум? Поначалу можно подумать, что задача проста - напиши код покачественнее, померяй сколько байт исходник вышел да и всё. Да вот только при детальном рассмотрении у такого подхода обнаруживаются проблемы. Во-первых, существуют разные языки программирования и минимальный код для каждого из них будет различаться. Во-вторых, большинство языков дают доступ к библиотекам - как встроенным, так и внешним. Из-за этого получается, что на одном языке программа получится маленькая, так как основную часть задачи будут решать библиотеки, а на другом - большая, так как многое писать надо будет с нуля. Толку от такого измерения мало.

Вроде бы, получить пригодные для сравнения числа можно зафиксировав язык программирования. Но и тут не всё просто. Во-первых, возникает вопрос - измерение для какого языка программирования позволит лучше оценить сложность задачи (выраженную размером кода)? Во-вторых, на языке программирования "кроличья нора" не заканчивается - есть ведь ещё операционная система. Для кроссплатформенных языков получается, что в зависимости от операционной системы приходится активировать разные ветви кода. И выходит, что для одного и того же языка для одной ОС можно просто вызвать функцию, а для другой - нужно писать код самостоятельно. Помимо различий в ОС различается также и оборудование, с которым программе разрешено взаимодействовать. К примеру, внутри процессора на моём компьютере есть полноценная реализация кодирования H.264 видео. Программе надо только выдать нужные команды. Если же процессор попроще, то так сделать не получится. Но сложность задачи кодирования видео при этом ведь не меняется! Что подводит к идее зафиксировать всё.

Однако если к измерению размера программы просто приложить список всего зафиксированного, то применить такое измерение сможет только владелец именно такой системы. Это неудобно. Хотелось бы также иметь возможность обсудить с кем-нибудь сложность задачи, без необходимости предоставлять собеседнику такое же оборудование, как у тебя. Решение - создать виртуальное окружение. Но какое? Так как оценивать хочется именно алгоритм, а не разнообразие библиотек языка/ОС/процессора, то надо бы выбрать что-нибудь попроще.

Так как о существовании окружений попроще я уже знал, то решил не изобретать их с нуля, а просто почитать список. Даже у простоты разнообразия оказалось больше, чем ожидалось. Пришлось выбирать. Чего-то слишком хитрозакрученного не хотелось - сломать мозг (BF) целью не было, поэтому перешёл на следующую страничку - OISC. Перебирать биты поштучно - это хоть и сама простота (FlipJump), но ждать днями пока выполнится алгоритм - это, как по мне, перебор. Хотелось бы хоть и простую систему, но с адекватной скоростью выполнения. По этому критерию подошёл subleq.

Но и на этом подбор окружения не завершается. Спецификация subleq не указывает размеры ни для адресов, ни для данных. Если оставить размеры бесконечными, то с реализацией исполнения такой программы придётся хорошенько повозиться, то есть теряется простота. Да и кодировать тогда программу придётся текстом, что добавляет проблем. Так что разрядность решил зафиксировать. Ещё один вопрос, требующий решения - методы взаимодействия с "внешним миром". Для этих целей можно придумывать дополнительные команды, а можно выделять специальные адреса в памяти. Традиционный метод доступа через память - протягивание всех данных через один или два "порта". Для решения этого вопроса стоит задуматься уже непосредственно об алгоритмах, которые такая виртуальная машина будет исполнять. Так как мне понравилась идея кодирования довольно большого изображения множества Мандельброта с помощью довольно небольшой программы, то и алгоритм я выбрал соответствующий - на входе - ничего, на выходе - картинка. Протягивать картинку через порт мне показалось слишком неестественным, поэтому решил просто выделить картинке место в конце адресного пространства. Выбор алгоритма также позволил определиться с размером указателей и данных. В 1 байт картинку не всунуть, 2 байта - уже лучше, но тоже маловато. 3 байта - уже хватает. Но выбрал всё же 4 - такой вариант будет естественнее для интерпретатора.

Осталось только всё это запрограммировать. Виртуальное окружение хоть и можно сделать на любом языке, но для начала придётся выбрать что-то одно. Так как долго возиться с защитой (чтобы алгоритм из песочницы не убежал) поначалу не хотелось, то решил взять C# - в нём защит хватает по умолчанию. Однако просто выполнить программу и всё - не так интересно, решил дать этой программе цель - сделать не любую картинку, а определённую, и прикрутить к этому функцию оценки схожести изображения. Так как это - программа - то выполняться она может столько, сколько захочет, что неудобно для тестирования, поэтому понадобилось ещё одно условие - ограничение на количество выполненных операций. В итоге, получилась система, которая позволяет на реальном примере поэкспериментировать с оценкой сложности конкретного класса алгоритмов - сжатия изображений с потерями.

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

0

@locm

0

@Vort_

0

@locm

0

@Vort_

Речь о размере указателей. Указатель размером 1 байт может адресовать 256 байт, 2 байта - 65536 байт и так далее.
Так как обычный размер картинок в наши дни - около 1920x1080, то при глубине цвета в 24 бита, получается "сырой" размер - 6220800 байт. Это ещё можно адресовать тремя байтами (максимум - 16777216), но если поднять размер картинки до 4к (3840x2160), то уже не влезет.
В этой теме мне хотелось бы получить отзыв как по самой идее формата файла (для этого и было нужно длинное введение), так и по задаче (представленной как в виде текста, так и в виде тестовой программы, по сути этот текст дублирующей).
Так как идея вставлять в каждую программу телеметрию мне не нравится, то я даже сейчас не знаю, запускал ли кто-нибудь программу, смотрел ли её код (по сути, содержащий условия задачи).
Суть задачи (конкурса) в упаковке фиксированного изображения в файл минимального размера, который соответствует двум условиям: качество декодированного (распакованного) изображения должно быть лучше определённого значения, время распаковки должно быть адекватным (чтобы не проверять решения слишком долго).
Формат файла я разрабатывал относительно универсальным, в заголовке содержатся идентификатор типа файла (SLIF), ширина и высота изображения и размер памяти, выделяемый для subleq кода. Однако, для конкретной задачи эти параметры зафиксированы.
После заголовка идут subleq команды. Каждая команда имеет три параметра - pa, pb и pc. Выполняется она так: интерпретатор читает значения по адресам pa и pb в переменные a и b, записывает в переменную b результат вычитания b-a и помещает её значение по адресу pb. Затем, в зависимости от того, получился результат вычитания отрицательным или нет, идёт переход либо по адресу pc, либо на следующую команду.

0

@TimutGin

Похоже вы решили разгадать загадку цифрового кода Слоота. К сожалению это уже невозможно.

0

@Vort_

Интересная история, спасибо за подсказку.

Нашёл в статье о Sloot Digital Coding System ссылку на теорему Шеннона об источнике шифрования.
И, похоже, понял кое что - сжимаемость зависит от количества чистого шума в изображении / видео.
Только вот вычислить это количество, скорее всего, невозможно.
К примеру, в файл можно записать бинарное представление числа пи (допустим, откуда-то со средины, чтобы в глаза не бросалось) и чистый белый шум.
Если не знать, что в файле пи, - то будет казаться, что его сжимаемость ровно такая же, как и у чистого шума, однако, это, конечно же, не так.

0