Отсутствие информации — это тоже информация

Отсутствие информации — это тоже информация

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

Так, а к чему заголовок то? Сегодня поговорим про бинарную сериализацию, и в целом про одну забавную идею, которая много где используется. Разберём для этого классическую задачку. У нас есть массив [0, 1, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0,2]. Но чтобы задача не была такой сухой представим что это трасса в раннере где:

0 — свободный кусок трассы

1 — это препятствие, которое нужно перепрыгнуть

2 — финиш

Подумаем, как мы можем это сохранить в нашей игре. Допустим нам хочется оптимальности. Первое что приходит в голову (если мы сразу отбросим SO, Json) и т.п. — бинарная сериализация. Конечно этот подход обладает некоторым числом недостатков (поддержка разных версий без стандартизации и т.п.)

Итак, допустим наши числа — это инты. Инт в C# — это Int32, то есть 4 байта. В нашей трассе 15 символов, то есть 60 байт. Но с числами "0", "1" и "2". мы можем сразу взять не тип int, а тип byte. Он весит 1 байт, так что суммарно мы выиграли в 4 раза, то есть до 15 байт. Можно ли ещё что-то сделать?

Во-первых, так нам не нужен финиш в виде отдельного числа, так что отбросим 2. Осталось 14 байт. А вот второе уже будет посложнее. Чуть-чуть изменим кодировку. Байт принимает значения от 0 до 255. Для упрощения мы считаем, что любая трасса начинается с хотя бы одного 0 (по сути в раннере в начало мы всегда можем поставить пустой блок, и это ничего не испортит игроку) И так как у нас всего 2 типа "пустое" и "с препятствием", то мы можем ту же самую трассу вполне записать как

[1, 1, 1, 2, 1, 1, 7] — что уже в типе байт займёт 7 байт вместо 15. Суть такой кодировки к том, что мы знаем что наша трасса начинается с нуля. И знаем что есть только 2 типа. Поэтому каждая цифра массива означает сколько значений следующего типа дальше.

Сначала у нас 1 ноль (то что трасса всегда начинается с нуля важно, чтобы тут не было разночтений)

Потом одна единица

Потом один ноль

Потом две единицы

Потом один ноль

Потом одна единица

И потом семь нулей

И вот мы с 60 байт снизили вес нашей трассы до 7 байт. То есть в почти в 10 раз. И на большом масштабе это уже имеет большое значение. Если же данные не индексируемы можно вообще не писать то, что не представляет ценности. Таким образом в целом созданы многие алгоритмы сжатия. Есть алгоритмы сжатия которые находят паттерны в файлах или данных и составляют словари, которые уже состоят из меньшего числа символов чем паттерн и дальше файл представляет из себя такой словарь + серию сериализованных ключей

Допустим пример выше очень полезен при использовании дельта сжатия, так как его идея заключается в том, что данные часто будут состоять из огромного числа нулей, которые нет смысла писать в виде нулей) И это во многом отвечает на вопрос, как пишутся в 4кб игры с текстурами и в 3д. И по сути все эти идеи на более высокий уровень выводит как раз математика)

В классической разработке это всё не так надо, и скорее просто "прикольное знание". Так как если не тормозит, то и не надо оптимизировать. Стандарты медленнее, во многом хуже, но чаще всего более гибкие и поддерживаемые, чем такие оптимизации. Но когда вам нужно "запихать последний мегабайт графики, чтобы влезть в 100мб ограничения стора" или другая задача повышенной сложности, то такие идеи бывают весьма полезны. Даже на уровне идеи, без знания теоретической базы на тему кодов Хаффмана и других частей теории множеств и теории информации