Алексей Федосов из 2ГИС написал интересную статью про то, как команда веб-карт оптимизирует генерализацию маркеров в новой версии 2gis.ru.

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

Статья Алексея очень хороший пример того, насколько далеко продвинулся современный веб и какие задачи могут появляться у наших коллег по цеху.

#map #webgl #algorithm #2gis

https://habr.com/ru/company/2gis/blog/442720/

Тай Люис из Lucidchart написал хорошую статью про base64 "Base64 Encoding: A Visual Explanation".

На сегодняшний день base64 используется при внедрении ресурсов в страницы с помощью протокола data:, в source map'ах и там, где необходимо передавать бинарные данные по текстовому протоколу.

В статье описывается работа алгоритма base64 с хорошей визуализацией. В цикле верхнего уровня входной поток данных делится на группы по 24 бита (input groups), которые обрабатываются вложенным циклом. Во вложенном цикле каждая входная группа бьётся на группы по 6 битов. Каждой комбинации битов соответсвует определённый символ, которым кодируется полученная группа. При необходимости во внешнем цикле input group искусственно расширяется до 24 битов с помощью символа =. Именно поэтому в конце base64 последовательности данных можно часто видеть =.

В статье Тай рассказал ещё про пасхалку в Chrome, про которую я не знал. Если ввести в адресную строку chrome://dino, то во весь вьюпорт браузера запустится игра с динозавром, которая доступна в обычном режиме тогда, когда нет доступа к сети (не забудьте нажать пробел). Эта игра хранит все свои ресурсы: изображение и звуки — в base64.

#base64 #algorithm #egg

https://www.lucidchart.com/techblog/2017/10/23/base64-encoding-a-visual-explanation/

Рич Харрис — автор Svelte, Shimport и других библиотек — сегодня твитнул про свою интересную находку в коде three.js.

Если вам нужно удалить один элемент из массива, можно воспользоваться array.splice(index, 1). Но если у вас огромный массив, то splice() будет работать очень медленно, так как будет происходить сдвиг всех элементов (линейная сложность).

Для тех массивов, где порядок элементов не важен, разработчики three.js используют такой код для удаления элемента:

array[index] = array[array.length - 1];
array.pop();

То есть здесь удаляемый элемент заменяется последним элементом массива и последний элемент удаляется (константная сложность).

В комментариях к твиту пишут, что при разработке на ассемблере для RISC-процессора PlayStation 1 подобный трюк был очень распространён.

#algorithm #js #trick

https://twitter.com/rich_harris/status/1125850391155965952?s=21

Попалась на глаза очень прикольная статья Сид Балы про объяснение принципа работы кодека H.264 — "H.264 is Magic". Перевод статьи на русский язык есть на хабре.

H.264 используется при передачи видеопотока, в формате Blu-ray, в телефонах и т.п. При кодировании фрейма производится сжатие с потерями с использованием частотного пространства. Потом производится цветовая субдискертизация, которая обрабатывает закодированные цвета таким образом, чтобы изображение использовало меньшее количество цветов.

После обработки фреймов наступает этап кодирования компенсации движения, когда выделяется базовый фрейм I-frame и последующие фреймы, которые кодируют смещение блоков 16x16 пикселей базового фрейма. Это позволяет эффективно сжимать движущиеся изображения на статичном фоне. После кодирования компенсации движения применяется энтропийное кодирование.

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

#algorithm #video

https://sidbala.com/h-264-is-magic/