Минимизация страницы Python

​Аналогичный по задачам, но реализованы по другим принципам на Python код минимизации страницы. Продолжение предыдущего поста с реализацией на php. Главное отличие от предыдущей версии здесь мы разбиваем потоковый парсером html и на обрабатываем содержимое тегов. Для сжатия стилей и скриптов используется внешний код для минимизации из webassets.

Минимизация страницы

Маленький код для оптимизации страницы при ее отдаче. Хотел добавить прямо сюда - но blogspot портит отображение кода и никакие pre/code не спасают. Поэтому будет iframe:-) Точка входа: html_compress, параметры я думаю понятны без комментариев.

Позволяет убрать все ненужные пробельные символы из страницы. Ключевая особенность - ничего не нужно менять в странице - код может вызываться через ob_start - изменений внутри кода производить не нужно. Можно настраивать, что именно нужно удалять (оптимизировать).

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

Для css все попроще CSSMin использую не последнюю версию, а немного устаревшую 2.0.2.2 - особых требований нет - главное чтобы не ломало.

Откуда взял начальную версию уже не помню, похоже отсюда.

Также рекомендую обратить внимание на PSS - по описанию его можно использовать вместо CDN с дополнительным плюсом он оптимизирует страницу перед выдачей. И гуглу удобно он всегда получат обновления вашего сайта когда они реально обновились и заходить на него им не нужно.

Асинхронно выводить на экран?

Или маленькая мысль о том:

так ли X-протокол безнадежно устарел.

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

В общем идея такая: в отдельном потоке держать обработку списка задач которые синхронно отсылаются на сервер (возможно похоже на случай с Beos, где в app-server запущен еще один дополнительный поток на каждое окно, если верить некоторым публикациям), если потребность в них отпала - пользователь или кто то еще изменил существенно прорисовку зачем продолжать? Так мы можем определить, что за секунду мы прорисовываем 1000 примитивов и постепенно прорисовывать их пока не закончиться временной лимит, или кто-то не отменит прорисовку. В результате того как сейчас работает X протокол мы можем, если пользователь был не очень активен последнее время - с устройств ввода не было событий мы можем спокойно поставить проверку на ввод после n-го элемента(или по времени смотря что раньше произойдет), что выведет проверку на состояние каждые 1 секунду, и когда появляется активность ставить проверку на десятые доли секунды. Думаю это существенно снизит нагрузку на процессор.

Для OpenGL- есть примерно подобная идея - создавать буфер для списка отображаемых объектов (буфер глубины), но не для конечных точек, а для больших объектов. И отбрасывать сразу целыми объектами, и если мы не попадаем в какой-то лимит отображения за время, например кадров секунду, отбрасывать все мелкие объекты(или те которые большие, но далеко) и следующий кадр рисовать уже без них, так как в основном все кадры подобны это должно дать несколько дерганое время прорисовки кадров, которое стремится оптимизироваться под соотношение размер элемента/время кадра. Правда я не уверен, есть ли сейчас отбрасывание объектов сразу при начале заполнения очереди, но отбрасывания по размерам объектов (не примитивов) я не слышал, и в классическом рисунке графического конвейера его не видно.

Псевдослучайное сжатие

Пост который я давно хотел написать,

и пишу чтобы не забыть...

Это было давно, как теперь кажется, я учился в университете и полдня мне рассказывали интересные штуки(кроме случаев когда рассказывали не очень).

И на предмете защита информации, или как-то подобно называвшемся, очень часто предметы имели длинные названия, которые все сокращали до очень кратких фраз, была у нас тема псевдослучайные последовательности на основе xor и регистров сдвига. Это очень простые по логике устройства умевшие генерировать n-1 чисел, где n это 2 в степени разрядности регистра сдвига. Почему на одно число меньше, если это очень хорошее число установить в регистре сдвига, то он будет всегда выдавать только его. Все остальные числа спокойно переходили одно в другое по случайному закону, но всегда по одной последовательности. Ну зато они и псевдослучайная последовательность. Разнообразие этих генераторов немного все таки ограничено, так некоторые варианты, как я помню можно упростить до более простых.

Ну так вот нужно было по части последовательности определить конфигурацию генератора. Для этого нужна половина максимального периода и провести какие-то сложные вычисления с использованием мнимой единицы. У меня что-то эти вычисления не сходились. Поэтому я решил пойти по другому пути придумать свой алгоритм. На бумаге он очень хорошо сходился и главное давал результат гораздо быстрее сложных математических расчетов.

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

После того как выписали - вычитаем из первой строки вторую(в общем-то для данной сложения по модулю 2 это равнозначно сложению.) И перебираем какие значения формул настроек генератора могут выдать подобный бит, нам их при половине полной последовательности хватит так она всегда больше чем разрядность регистра, кроме совсем тривиальных случаев.


Как я выше указал мы берем от совсем минимальной длины регистра сдвига до максимально возможной для данной последовательности - мы где-то можем примерно проверить разрядность до длины полученной последовательности-2. Причина в том что на полной последовательности мы ничего проверить не можем, на -1 мы можем хоть уже делать предположения, о том какие настройки возможны, на -2 можем начать отбрасывать точно не подходящие и прогнозировать множество возможных вариантов. Но так как мы начинаем с минимального - мы делаем предположение основываясь множестве уравнений полученных вычитанием верхней строки из строки расположенной на 1 строку ниже. Чем длиннее предполагаемая разрядность, тем меньше уравнений и больше множество вариантов. И начиная с минимальной разрядности мы отбрасываем варианты.

В моем случае для простых случаев в рамках 4 бита регистр, 8 бит полупоследовательность - это выполняется быстрее и по сложности проще. Но зато благодаря этому я нашел пару неточностей в решениях полученных другими (были возможны более короткие регистры) и главное сдал лабу.

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

P.S.: Я мог конечно что-то забыть и здесь есть неточности, но все же пока все не забыл, постарался максимально  правильно все описать.

Упрощение списка координат

Иногда нужно упростить список координат, например вывод kml(kmz) на маленьких уровнях увеличения - большая точность отображения не нужна, зато скорость очень важна.

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

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

Более хорошая версия - проход по точкам и высчитывается минимальное растояние между точками, если оно слишком мало, то увеличиваем его до минимально допустимого.

Затем запускается цикл по точкам и добавляются только те точки, которые располагаются на расстоянии от последней добавленной точки больше, чем минимально допустимое полученное на предыдущим шаге. Эту операцию повторяют пока количество точек не станет меньше максимально допустимого (вычисляется в общем-то на глаз, до тех пор пока время пересчета допустимо по времени ожидания и дефекты в контурах карт еще мало заметны). Также итерации могут продолжаться пока в контуре более 3 точек и площадь полигона больше допустимого для отображения, меньше можно просто отбрасывать(можно считать, что площадь линейно зависима от произведения минимального расстояния на количество точек, что, конечно, геометрически не всегда верно). Для упрощения математической сложности модно считать что расстояние равно не квадрату различий между точками((x1-x2)^2 + (y1-y2)^2 ), а сумме расстояний по координатам по модулю(|(x1-x2)| + |(y1-y2)|), что опять таки не всегда верно, но зато быстро.