Далеко не все алгоритмы можно описать словами без привлечения того же псевдокода. Посмотрите, например, описание CRC32. Фактически это псевдокод, который напрямую переводится в код на любом языке программирования. Так же и с этим алгоритмом кодирования ZX. Подробное объяснение, позволяющее полностью восстановить программу, будет псевдокодом.
Хотите самое общее описание - пожалуйста. Для каждого байта выбирается самый короткий способ его получить исходя из всех предыдущих байтов. Сложность квадратичная.
Ну, досконально я не разбирался, но за пару часов понял примерно следующее.
Базовый анализ
Внешний цикл идёт по всем байтам данных (текущий байт). Внутренний перебирает смещение в обратную сторону максимум на определённую в offset_limit глубину (старый байт). Если текущий и старый байты не совпадают, то проверяется гипотеза копирования литерала. Если байты совпадают и есть литерал с таким смещением, то проверяется гипотеза копирования с последнего смещения. Если байты совпадают и длина совпадающей цепочки больше 1, то проверяется гипотеза копирования с нового смещения. Для проверки гипотезы вычисляется длина блока при соответствующем варианте копирования и, если она меньше, чем уже найденная, то старый оптимальный вариант заменяется на найденный. Последняя построенная цепочка (optimal[input_size - 1]) считается оптимальной и возвращается для записи в архив. Функции assign и allocate нужны для ручного управления памятью и в языках с автоматическим контролем памяти могут быть заменены на присваивание и new соответственно.
Можно и грубже зарыться, но уже просто лень. И таки да, названия переменных и функций вполне себе помогают в анализе этого кода.
И навигация в море стала возможна благодаря гироскопическим навигаторам
А не скажете, какую именно модель гироскопических навигаторов ставили на чайных клипперах? А у Колумба почему они так плохо работали, что он вместо Индии приплыл в Новый Свет?
не путаю, но вы к беседе присоединились выбрав противоположную сторону, а значит вы согласны с этим.
С чего бы это? Я заведомо согласен только с теми утверждениями, которые сам высказывал.
прочитать и понять чужой код это очень сложно
Бывает. Иногда проще оттрассировать код и посмотреть, что происходит при его выполнении. Но плохие имена переменных и функций явно не улучшат понимание. А вот хорошие могут. В том коде, что вы привели, есть функция elias_gamma_bits. Собственно, если вы знаете, что такое гамма-код Элиаса, то названия функции вам хватит, чтобы понять, что она делает. Если её назвать some_func_1, то вам придётся полностью её изучить, да ещё и понять, чему соответствует алгоритм функции.
если написано l = strlen(n) - это даст столько же информации
Ровно до тех пор, пока у вас только одна переменная с похожим именем. Как только у вас появляются l1, l2, l3, l4 и l5, запутаться в них проще простого.
Зайдите в github проекта ZX0 и расскажите мне в деталях что же делает функция optimize(), а то независимо от именования мне совсем непонятен алгоритм.
В деталях с ходу не скажу, но судя по названию и месту, в котором она вызывается, это предварительная подготовка данных для собственно алгоритма сжатия. Если функцию назвать func1 и вызывать её из функции func2, то вы и этого не сможете сказать.
Вы же утверждаете что щелкает алгоритмы как орешки
Безусловно, но вы быстрое понимание кода почему-то связываете с тем как будут обозваны переменные.
Ну если для вас понимание кода никак не связано с названиями переменных и функций, то попробуйте назвать все переменные var1, var2, ... var99, а функции, соответственно, func1, func2, ... func99. Когда я вижу запись nameLen = strlen(name), я понимаю, как сформировано имя переменной и в дальнейшем по коду сразу вижу, что в ней находится. Когда я вижу zzz = myfunc1(xxx), то я должен сначала вспомнить, что же лежит в xxx, затем залезть в myfunc1 и понять, что она делает, и, наконец, запомнить, что именно будет храниться в zzz.
Функции применяются для того, чтобы их можно было переиспользовать с другими параметрами, а не на каждый чих.
Переиспольуемый код - это явный кандидат на вынесение в отдеьльную функцию. Тут спора нет. Но это не единственный кандидат. Например, мы пишем функцию шифрования и в ней есть достаточно большой блок инициализации. Даже учитывая, что этот блок не переиспользуется, так как выполняется в одном месте, а параметров у него может и не быть, IMHO стоит вынести такой блок в отдельную функцию и читаемость от этого улучшится.
Однако проще читать функцию, если она вызывает несколько функций с говорящими названиями, чем то же самое, но в виде простыни кода. Например, если вы видите функцию string strToUpperCase(string s), то вряд ли вам надо погружаться в её код, чтобы понять, что именно она делает. А если к ней ещё и добавлен doc-блок, отображаемый IDE, то описание функции и её аргументов вы увидите при наведении на её вызов. Тут надо только, чтобы разбиение на подфункции не было искусственным. Они должны быть достаточно самодостаточными и законченными по смыслу.
Тут смысл в сокращении длины функции. Слишком длинную сложнее воспринимать. Ну а накладные расходы зависят от языка. В каких-то оптимизатор может превратить вызовы в инлайновые вставки и в скомпилированном виде никаких вызовов не будет. А если вы так хотите экономить, то представьте, что в вашей программе всего в одном месте вызывается, например, приведение строки в верхний регистр. Откажетесь ли вы от библиотечной функции и будете ли переписывать её код внутрь своей функции?
Функции могут применяться даже если они не переиспользуются. Например, какой-то процесс состоит из нескольких шагов. Тогда можно из функции, реализующеё этот процесс, вынести шаги в отдельные подфункции, оставив в основной функции только вызов шагов. Вместо одной длинной функции получим несколько коротких.
То есть вы не знаете, выполнимо ли в принципе ваше требование, но, тем не менее, настаиваете, чтобы кто-то его выполнил.
Ну так опишите тот же CRC32 словами.
Далеко не все алгоритмы можно описать словами без привлечения того же псевдокода. Посмотрите, например, описание CRC32. Фактически это псевдокод, который напрямую переводится в код на любом языке программирования.
Так же и с этим алгоритмом кодирования ZX. Подробное объяснение, позволяющее полностью восстановить программу, будет псевдокодом.
Так что именно "пока никто не смог"?
Хотите самое общее описание - пожалуйста.
Для каждого байта выбирается самый короткий способ его получить исходя из всех предыдущих байтов. Сложность квадратичная.
Нет, я сначала понял часть кода, а потом записал то, что понял в виде псевдокода. Увы, но по другому своё понимание в чью-то голову вложить сложно.
Герц - это уже количество импульсов в секунду. Герц в минуту - это примерно как узел в час. Время в квадрате получается.
Ну, досконально я не разбирался, но за пару часов понял примерно следующее.
Базовый анализ
Внешний цикл идёт по всем байтам данных (текущий байт).
Внутренний перебирает смещение в обратную сторону максимум на определённую в
offset_limitглубину (старый байт).Если текущий и старый байты не совпадают, то проверяется гипотеза копирования литерала.
Если байты совпадают и есть литерал с таким смещением, то проверяется гипотеза копирования с последнего смещения.
Если байты совпадают и длина совпадающей цепочки больше 1, то проверяется гипотеза копирования с нового смещения.
Для проверки гипотезы вычисляется длина блока при соответствующем варианте копирования и, если она меньше, чем уже найденная, то старый оптимальный вариант заменяется на найденный.
Последняя построенная цепочка (
optimal[input_size - 1]) считается оптимальной и возвращается для записи в архив.Функции
assignиallocateнужны для ручного управления памятью и в языках с автоматическим контролем памяти могут быть заменены на присваивание иnewсоответственно.Можно и грубже зарыться, но уже просто лень.
И таки да, названия переменных и функций вполне себе помогают в анализе этого кода.
Кошки целенаправленно выводили себе людей, охотясь за их предками сначала на деревьях, затем в саванне.
А в быту используют такой инструмент, как "реноватор". Тот же самый принцип колебаний режущего инструмента или шлифнасадки на частотах 12000-22000 Гц.
А не скажете, какую именно модель гироскопических навигаторов ставили на чайных клипперах? А у Колумба почему они так плохо работали, что он вместо Индии приплыл в Новый Свет?
С чего бы это? Я заведомо согласен только с теми утверждениями, которые сам высказывал.
Бывает. Иногда проще оттрассировать код и посмотреть, что происходит при его выполнении. Но плохие имена переменных и функций явно не улучшат понимание. А вот хорошие могут. В том коде, что вы привели, есть функция
elias_gamma_bits. Собственно, если вы знаете, что такое гамма-код Элиаса, то названия функции вам хватит, чтобы понять, что она делает. Если её назватьsome_func_1, то вам придётся полностью её изучить, да ещё и понять, чему соответствует алгоритм функции.Но тогда можно любой кусок кода волюнтаристски выделить как отдельную функцию, написать тест и заявить, что этот код используется повторно.
Для этого есть покрытие тестами. И сделать тест инициализации гораздо проще, если она вынесена в отдельную функцию.
Ровно до тех пор, пока у вас только одна переменная с похожим именем. Как только у вас появляются l1, l2, l3, l4 и l5, запутаться в них проще простого.
В деталях с ходу не скажу, но судя по названию и месту, в котором она вызывается, это предварительная подготовка данных для собственно алгоритма сжатия. Если функцию назвать func1 и вызывать её из функции func2, то вы и этого не сможете сказать.
Где я такое утверждал? Вы меня с кем-то путаете.
Ну если для вас понимание кода никак не связано с названиями переменных и функций, то попробуйте назвать все переменные var1, var2, ... var99, а функции, соответственно, func1, func2, ... func99.
Когда я вижу запись
nameLen = strlen(name), я понимаю, как сформировано имя переменной и в дальнейшем по коду сразу вижу, что в ней находится. Когда я вижуzzz = myfunc1(xxx), то я должен сначала вспомнить, что же лежит в xxx, затем залезть в myfunc1 и понять, что она делает, и, наконец, запомнить, что именно будет храниться в zzz.Переиспольуемый код - это явный кандидат на вынесение в отдеьльную функцию. Тут спора нет. Но это не единственный кандидат.
Например, мы пишем функцию шифрования и в ней есть достаточно большой блок инициализации. Даже учитывая, что этот блок не переиспользуется, так как выполняется в одном месте, а параметров у него может и не быть, IMHO стоит вынести такой блок в отдельную функцию и читаемость от этого улучшится.
Однако проще читать функцию, если она вызывает несколько функций с говорящими названиями, чем то же самое, но в виде простыни кода. Например, если вы видите функцию
string strToUpperCase(string s), то вряд ли вам надо погружаться в её код, чтобы понять, что именно она делает. А если к ней ещё и добавлен doc-блок, отображаемый IDE, то описание функции и её аргументов вы увидите при наведении на её вызов.Тут надо только, чтобы разбиение на подфункции не было искусственным. Они должны быть достаточно самодостаточными и законченными по смыслу.
Тут смысл в сокращении длины функции. Слишком длинную сложнее воспринимать.
Ну а накладные расходы зависят от языка. В каких-то оптимизатор может превратить вызовы в инлайновые вставки и в скомпилированном виде никаких вызовов не будет.
А если вы так хотите экономить, то представьте, что в вашей программе всего в одном месте вызывается, например, приведение строки в верхний регистр. Откажетесь ли вы от библиотечной функции и будете ли переписывать её код внутрь своей функции?
Функции могут применяться даже если они не переиспользуются. Например, какой-то процесс состоит из нескольких шагов. Тогда можно из функции, реализующеё этот процесс, вынести шаги в отдельные подфункции, оставив в основной функции только вызов шагов. Вместо одной длинной функции получим несколько коротких.