Случайны выбор дневника Раскрыть/свернуть полный список возможностей


Найдено 4617 сообщений
Cообщения с меткой

алгоритмы - Самое интересное в блогах

Следующие 30  »
rss_rss_hh_new

[Из песочницы] Анализ аудио-кодека ROAD

Суббота, 24 Сентября 2016 г. 14:00 (ссылка)

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



Далее будут рассмотрены заявленные уникальные свойства и произведено несколько тестовых измерений.



Обзор свойств



Предпрослушивание



В статье описывается довольно сложная формула для объяснения этого свойства, но на самом деле всё намного проще. По факту это свойство означает, что компрессии подвергается не весь сигнал, а только его часть, что продемонстрировано на следующем изображении:







Здесь зелёным цветом помечен исходный сигнал, синим — усреднённый по некоторому количеству точек (семплов) и сохраняемый в явном виде, и красным — остаток, подвергаемый сжатию.



В сильно грубом приближении можно сказать, что сжимается лишь высокочастотная часть сигнала. Более точно в частотной области разделение на усреднённый и остаточный сигналы будут выглядеть, например, так (для 4-кратного усреднения в 48 кГц):







Или так (для 32-кратного усреднения в 48 кГц):







Ещё более точный вид будет зависеть от конкретного взятого сигнала. Например, для синусоиды из самого первого изображения:







Здесь усреднение привело к появлению гармоник в противофазе в обоих сигналах, которые взаимокомпенсируются при сложении. Очевидно, что при изменении фазы или амплитуды гармоники в одном из сигналов (например, в результате сжатия) полной компенсации происходить уже не будет и приведёт к искажению исходного сигнала. Далее это будет показано на конкретных измерениях.



Частичная совместимость



Это свойство явно следует из предыдущего. Так как часть сигнала хранится без сжатия, её можно воспроизвести, игнорируя закодированную часть. Автор преподносит это как достоинство, но оно выглядит крайне сомнительным. Если вы скачали аудио-файл, который не воспроизводится плеером – понятно, что не хватает какого-то кодека. Но если файл воспроизводится с ухудшенным качеством – то логичнее предположить, что так и должно быть или он повреждён, чем искать кодек, улучшающий его звучание.



Разгон



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



Качество ресемплера определяется степенью подавления паразитных гармоник за пределами оригинальной полосы частот. Далее будет показано, что данный кодек таким качеством не обладает.



Расширение динамического диапазона



А здесь уже происходит явная подтасовка фактов. При оцифровке аудио-сигнала происходит не просто уменьшение динамического диапазона – появляются шумы квантования, которые имеют нелинейный характер. Их довольно-таки сложно отфильтровать, поэтому на практике они просто маскируются техниками dithering и noise shaping.



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



Недетерминированное декодирование



Исходя из описания можно было бы предположить, что каждый раз после декодирования мы получаем немного разный результат. Однако реальное сравнение показало, что результаты идентичны. Это значит, что по факту это свойство не имеет никакого значения – с тем же успехом можно увидеть недетерминированность в том, в каком порядке складывать цифры 2 и 3 для получения цифры 5.



Испытание на тестовых данных



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



Для измерения будут использоваться синтезированные сигналы длительностью 65536 семплов (для удобства последующего Фурье-анализа). Результаты измерений будут представлены как во временной (зелёным цветом), так и в частотной (синим цветом) области в виде логарифмической амплитудно-частотной характеристики.



На всякий случай
Изменение амплитуды на 3 дБ примерно равно изменению в 1.7 раза.

Изменение амплитуды на 6 дБ примерно равно изменению в 2 раза.

Изменение амплитуды на 12 дБ примерно равно изменению в 4 раза.



При кодировании использовались следующие параметры:




  • Maximum sample length of rang = от 4 до 32, для каждого производилось отдельное измерение;

  • Length of encoding superframe = 8 (при использовании значения по-умолчанию, 10, файл обрабатывался не полностью и обрезался по правой границе);

  • Relative shifting between domains = 1 (по-умолчанию).



MLS – Maximum Length Sequence



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



После измерения по виду АЧХ можно оценить отклик системы на каждой отдельно взятой частоте по отклонению её амплитуды от 0 дБ.



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



Исходный сигнал:











Результаты измерений:



sample length = 4:







sample length = 8:







sample length = 16:







sample length = 32:







Здесь хорошо виден спад и сильное зашумление на высоких частотах, возрастающих с увеличением параметра sample length (который, вероятно, определяет количество усредняемых точек).



Логарифмический свип-тон (sweep-tone)



Представляет из себя синусоиду с постоянно увеличивающейся или уменьшающейся частотой.



Здесь с уменьшением частоты амплитуда уменьшается, чтобы компенсировать наклон АЧХ (в линейном свип-тоне это не требуется), а также наложено сглаживающее окно.

Его часто используют, чтобы помимо частотного отклика оценить ещё и нелинейные искажения (distortion). Здесь мы никаких коэффициентов считать не будем, а просто оценим результат визуально.



Исходный сигнал:











Результаты измерений:



sample length = 4:











sample length = 8:











sample length = 16:











sample length = 32:











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



На АЧХ в то же время видно, что она не просто теряется – а замещается гармониками (которые неизбежно возникают при децимации усреднением) и шумом.



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



Последовательность из 8 тонов



Содержит ноты «ля» от контроктавы (55 Гц) до «ля» пятой октавы (7040 Гц).



Исходный сигнал:











Результаты измерений:



sample length = 4:











sample length = 8:











sample length = 16:











sample length = 32:











Здесь мы уже можем однозначно утверждать о наличии выраженных гармонических искажений. Поскольку синусоида – это чистый тон, любое её искажение приводит к появлению гармоник — их хорошо видно (на частоте 5 кГц в первом графике, например).



Рассмотрим синусоиду с частотой 440 Гц из последнего замера чуть ближе:







Здесь можно увидеть, что она собрана из кусочков от других синусоид. Также хорошо видно и разрывы на краях блоков.



Испытание «разгона» и расширения динамического диапазона



В декодере есть возможность увеличить частоту дискретизации в 2 или 4 раза и глубину квантования до 24 бит. Испытаем эту возможность на предыдущем сигнале (с параметром sample length = 4):











По форме сигнала видно, что он претерпел ещё бо

https://habrahabr.ru/post/310872/?utm_source=habrahabr&utm_medium=rss&utm_campaign=best

Метки:   Комментарии (0)КомментироватьВ цитатник или сообщество
rss_rss_hh_new

[Перевод] Структуры данных для самых маленьких

Пятница, 23 Сентября 2016 г. 16:23 (ссылка)

James Kyle как-то раз взял и написал пост про структуры данных, добавив их реализацию на JavaScript. А я взял и перевёл.



Дисклеймер: в посте много ascii-графики. Не стоит его читать с мобильного устройства — вас разочарует форматирование текста.







Сегодня мы узнаем всё о структурах данных.



«Оооооой как интересно...», да?



Да уж, не самая сочная тема на сей день, однако крайне важная. Не для того, чтобы сдавать курсы наподобие CS101, а чтобы лучше разбиратьсяв программировании.



Знание структур данных поможет вам:

— Управлять сложностью своих программ, делая их доступней для понимания.

— Создавать высокопроизводительные программы, эффективно работающие с памятью.



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



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



Чтобы познакомиться со структурами данных, мы реализуем некоторые из них.Не беспокойтесь, код будет лаконичен. На самом деле, тут больше комментариев,а кода между ними — раз, два и обчёлся.




============================================================================
,.-'`'-.,.-'`'-.,.-'`'-.,.-'`'-.,.-'`'-.,.-'`'-.,.-'`'-.,.-'`'-.,.-'`'-.,.-'
============================================================================




Что такое структуры данных?



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



Чтобы понять, почему так происходит, сперва поговорим об алгоритмах.




/*** ===================================================================== ***\
** - АЛГОРИТМЫ ----------------------------------------------------------- **
* ========================================================================= *
* *
* ,--,--. ,--,--. *
* ,----------. | | | | | | _____ *
* |`----------'| | | | | | | | | ,------. *
* | | | | | | | | ,--. | o o | |`------'| *
* | | ,| +-|-+ | | +-|-+ |` | | |_____| | | *
* | | ,:==| | |###|======|###| | |====#==#====#=,, | | *
* | | || `| +---+ | | +---+ |' ,,=#==#====O=`` ,| | *
* | | || | | | | | | ``=#==#====#=====|| | *
* `----------' || | | | | | | |__| `| | *
* | | ``=| |===`` `--,',--` `--,',--` /||\ `------' *
** \_/ \_/ / / \ \ / / \ \ //||\\ |_| |_| **
\*** ===================================================================== ***/




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



Структуры данных реализованы с помощью алгоритмов, алгоритмы — с помощьюструктур данных. Всё состоит из структур данных и алгоритмов, вплотьдо уровня, на котором бегают микроскопические человечки с перфокартамии заставляют компьютер работать. (Ну да, у Интела в услужениимикроскопические люди. Поднимайся, народ!)



Любая данная задача реализуется бесконечным количеством способов.Как следствие, для решения распространённых задач изобрели множестворазличных алгоритмов.



Например, для сортировки неупорядоченного множества элементов существуетдо смешного большое количество алгоритмов:



Сортировка вставками, Сортировка выбором, Сортировка слиянием, Сортировка пузырьком, Cортировка кучи, Быстрая сортировка, Сортировка Шелла, Сортировка Тима, Блочная сортировка, Поразрядная сортировка…




Некоторые из них значительно быстрее остальных. Другие занимают меньшепамяти. Третьи легко реализовать. Четвёртые построены на допущенияхотносительно наборов данных.



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



Для сравнения производительности алгоритмов используется грубое измерениесредней производительности и производительности в худшем случае,для обозначения которых используется термин «О» большое.




/*** ===================================================================== ***\
** - О БОЛЬШОЕ ----------------------------------------------------------- **
* ========================================================================= *
* a b d *
* a b O(N^2) d *
* O(N!) a b O(N log N) d c *
* a b d c *
* a b d c O(N) *
* a b d c *
* a b d c *
* a b d c *
* ab c O(1) *
* e e e e ec d e e e e e e e e *
* ba c d *
* ba c d f f f f f f f *
** cadf f d f f f f f O(log N) **
\*** ===================================================================== ***/




«О» большое — обозначение способа приблизительной оценки производительностиалгоритмов для относительного сравнения.



О большое — заимствованное информатикой математические обозначение,определяющее, как алгоритмы соотносятся с передаваемым им некоторымколичеством N данных.



О большое характеризует две основные величины:



Оценка времени выполнения — общее количество операций, которое алгоритм проведёт на данном множестве данных.

Оценка объёма — общее количество памяти, требующееся алгоритму для обработки данного множества данных.



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



Вот некоторые распространённые значения О большого:



Имя               Нотация    Что вы скажете, припрись они к вам на вечеринку
----------------------------------------------------------------------------
Константная O(1) ОХРЕНЕННО!!
Логарифмическая O(log N) КРУТО!
Линейная O(N) НОРМАС.
Линейно-
логарифмическая O(N log N) БЛИИИН...
Полиномиальная O(N ^ 2) ОТСТОЙ
Экспоненциальная O(2 ^ N) ОТВРАТИТЕЛЬНО
Факториальная O(N!) ТВОЮЖМАТЬ




Чтобы дать представление, о каких порядках чисел мы говорим, давайте взглянем,что это будут за значения в зависимости от N.



           N = 5            10             20             30
-----------------------------------------------------------------------
O(1) 1 1 1 1
O(log N) 2.3219... 3.3219... 4.3219... 4.9068...
O(N) 5 10 20 30
O(N log N) 11.609... 33.219... 84.638... 147.204...
O(N ^ 2) 25 100 400 900
O(2 ^ N) 32 1024 1,048,576 1,073,741,824
O(N!) 120 3,628,800 2,432,902,0... 265,252,859,812,191,058,636,308,480,000,000




Как видите, даже при относительно небольших числах можно сделать *дофига*дополнительной работы.



Структуры данных позволяют производить 4 основных типа действий:доступ, поиск, вставку и удаление.



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



                          Доступ      Поиск       Вставка      Удаление
------------------------------------------------------------------------
Массив O(1) O(N) O(N) O(N)
Связный список O(N) O(N) O(1) O(1)
Двоичное дерево поиска O(log N) O(log N) O(log N) O(log N)




Или даже…



                          Доступ       Поиск      Вставка      Удаление
------------------------------------------------------------------------
Массив ОХРЕНЕННО НОРМАС НОРМАС НОРМАС
Связный список НОРМАС НОРМАС ОХРЕНЕННО ОХРЕНЕННО
Двоичное дерево поиска КРУТО КРУТО КРУТО КРУТО




Кроме того, некоторые действия имеют разную «среднюю» производительность ипроизводительность в «самом худшем случае».



Идеальной структуры данных не существует. Вы выбираете самую подходящую,основываясь на данных и на том, как они будут обрабатываться. Чтобы сделатьправильный выбор, важно знать различные распространённые структуры данных.




/*** ===================================================================== ***\
** - ПАМЯТЬ -------------------------------------------------------------- **
* ========================================================================= *
* _.-.. *
* ,'9 )\)`-.,.--. *
* `-.| `. *
* \, , \) *
* `. )._\ (\ *
* |// `-,// *
* ]|| //" *
** hjw "" "" **
\*** ===================================================================== ***/




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



Фрагмент памяти можно представить так:




Значения: |1001|0110|1000|0100|0101|1010|0010|0001|1101|1011...
Адреса: 0 1 2 3 4 5 6 7 8 9 ...




Если вы задумывались, почему в языках программирования отсчётначинается с 0 — потому, что так работает память. Чтобы прочитать первыйфрагмент памяти, вы читаете с 0 до 1, второй — с 1 до 2. Адресаэтих фрагментов соответственно равны 0 и 1.



Конечно же, в компьютере больше памяти, чем показано в примере, однакоеё устройство продолжает принцип рассмотренного шаблона.



Просторы памяти — как Дикий Запад. Каждая работающая на компьютере программахранится внутри одной и той же *физической* структуры данных.Использование памяти — сложная задача, и для удобной работы с нейсуществуют дополнительные уровни абстракции.



Абстракции имеют два дополнительных назначения:



— Сохраняют данные в памяти таким образом, чтобы с ними было эффективно и/или быстро работать.

— Сохраняют данные в памяти так, чтобы их было проще использовать.




/*** ===================================================================== ***\
** - СПИСКИ -------------------------------------------------------------- **
* ========================================================================= *
* * _______________________ *
* ()=(_______________________)=() * *
* * | | *
* | ~ ~~~~~~~~~~~~~ | * * *
* * | | *
* * | ~ ~~~~~~~~~~~~~ | * *
* | | *
* | ~ ~~~~~~~~~~~~~ | * *
* * | | *
* * |_____________________| * * *
* ()=(_______________________)=() *
** **
\*** ===================================================================== ***/




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



Список — представление пронумерованной последовательности значений,где одно и то же значение может присутствовать сколько угодно раз.



Начнём с пустого блока памяти, представленного обычным JavaScript-массивом.Также нам понадобится хранить значение длины списка.



Заметьте, что мы хотим хранить длину отдельно, поскольку в реальностиу «памяти» нет значения length, которое можно было бы взять и прочитать.



class List {

constructor() {
this.memory = [];
this.length = 0;
}

//...
}




Первым делом нужно получать данные из списка.



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



Сложность операции доступа в список — O(1) — «ОХРЕНЕННО!!»



get(address) {
return this.memory[address];
}




У списков есть порядковые номера, поэтому можно вставлять значенияв начало, середину и конец.



Мы сфокусируемся на добавлении и удалении значений в начало иликонец списка. Для этого понадобятся 4 метода:



— Push — Добавить значение в конец.

— Pop — Удалить значение из конца.

— Unshift — Добавить значение в начало.

— Shift — Удалить значение из начала.



Начнём с операции «push» — реализуем добавление элементов в конец списка.



Это настолько же легко, как добавить значение в адрес, следующийза нашим списком. Поскольку мы храним длину,вычислить адрес — проще простого. Добавим значение и увеличим длину.



Добавление элемента в конец списка — константа O(1) — «ОХРЕНЕННО!!»



push(value) {
this.memory[this.length] = value;
this.length++;
}




Далее, реализуем метод «pop», убирающий элемент из конца нашего списка.



Аналогично push, всё, что нужно сделать — убрать значениеиз последнего адреса. Ну, и уменьшить длину.



Удаление элемента из конца списка — константа O(1) — «ОХРЕНЕННО!!»



pop() {
// Нет элементов — ничего не делаем.
if (this.length === 0) return;

// Получаем последнее значение, перестаём его хранить, возвращаем его.
var lastAddress = this.length - 1;
var value = this.memory[lastAddress];
delete this.memory[lastAddress];
this.length--;

// Возвращаем значение, чтобы его можно было использовать.
return value;
}




«Push» и «pop» работают с концом списка, и в общем-то являютсяпростыми операциями, поскольку не затрагивают весь остальной список.



Давайте посмотрим, что происходит, когда мы работаем с началом списка,с операциями «unshift» и «shift».



Чтобы добавить новый элемент в начало списка, нужно освободить пространстводля этого значения, сдвинув на один все последующие значения.




[a, b, c, d, e]
0 1 2 3 4

https://habrahabr.ru/post/310794/?utm_source=habrahabr&utm_medium=rss&utm_campaign=best

Метки:   Комментарии (0)КомментироватьВ цитатник или сообщество
rss_rss_hh_new

[Перевод] Структуры данных для самых маленьких

Пятница, 23 Сентября 2016 г. 16:23 (ссылка)

James Kyle как-то раз взял и написал пост про структуры данных, добавив их реализацию на JavaScript. А я взял и перевёл.



Дисклеймер: в посте много ascii-графики. Не стоит его читать с мобильного устройства — вас разочарует форматирование текста.







Сегодня мы узнаем всё о структурах данных.



«Оооооой как интересно...», да?



Да уж, не самая сочная тема на сей день, однако крайне важная. Не для того, чтобы сдавать курсы наподобие CS101, а чтобы лучше разбиратьсяв программировании.



Знание структур данных поможет вам:

— Управлять сложностью своих программ, делая их доступней для понимания.

— Создавать высокопроизводительные программы, эффективно работающие с памятью.



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



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



Чтобы познакомиться со структурами данных, мы реализуем некоторые из них.Не беспокойтесь, код будет лаконичен. На самом деле, тут больше комментариев,а кода между ними — раз, два и обчёлся.




============================================================================
,.-'`'-.,.-'`'-.,.-'`'-.,.-'`'-.,.-'`'-.,.-'`'-.,.-'`'-.,.-'`'-.,.-'`'-.,.-'
============================================================================




Что такое структуры данных?



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



Чтобы понять, почему так происходит, сперва поговорим об алгоритмах.




/*** ===================================================================== ***\
** - АЛГОРИТМЫ ----------------------------------------------------------- **
* ========================================================================= *
* *
* ,--,--. ,--,--. *
* ,----------. | | | | | | _____ *
* |`----------'| | | | | | | | | ,------. *
* | | | | | | | | ,--. | o o | |`------'| *
* | | ,| +-|-+ | | +-|-+ |` | | |_____| | | *
* | | ,:==| | |###|======|###| | |====#==#====#=,, | | *
* | | || `| +---+ | | +---+ |' ,,=#==#====O=`` ,| | *
* | | || | | | | | | ``=#==#====#=====|| | *
* `----------' || | | | | | | |__| `| | *
* | | ``=| |===`` `--,',--` `--,',--` /||\ `------' *
** \_/ \_/ / / \ \ / / \ \ //||\\ |_| |_| **
\*** ===================================================================== ***/




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



Структуры данных реализованы с помощью алгоритмов, алгоритмы — с помощьюструктур данных. Всё состоит из структур данных и алгоритмов, вплотьдо уровня, на котором бегают микроскопические человечки с перфокартамии заставляют компьютер работать. (Ну да, у Интела в услужениимикроскопические люди. Поднимайся, народ!)



Любая данная задача реализуется бесконечным количеством способов.Как следствие, для решения распространённых задач изобрели множестворазличных алгоритмов.



Например, для сортировки неупорядоченного множества элементов существуетдо смешного большое количество алгоритмов:



Сортировка вставками, Сортировка выбором, Сортировка слиянием, Сортировка пузырьком, Cортировка кучи, Быстрая сортировка, Сортировка Шелла, Сортировка Тима, Блочная сортировка, Поразрядная сортировка…




Некоторые из них значительно быстрее остальных. Другие занимают меньшепамяти. Третьи легко реализовать. Четвёртые построены на допущенияхотносительно наборов данных.



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



Для сравнения производительности алгоритмов используется грубое измерениесредней производительности и производительности в худшем случае,для обозначения которых используется термин «О» большое.




/*** ===================================================================== ***\
** - О БОЛЬШОЕ ----------------------------------------------------------- **
* ========================================================================= *
* a b d *
* a b O(N^2) d *
* O(N!) a b O(N log N) d c *
* a b d c *
* a b d c O(N) *
* a b d c *
* a b d c *
* a b d c *
* ab c O(1) *
* e e e e ec d e e e e e e e e *
* ba c d *
* ba c d f f f f f f f *
** cadf f d f f f f f O(log N) **
\*** ===================================================================== ***/




«О» большое — обозначение способа приблизительной оценки производительностиалгоритмов для относительного сравнения.



О большое — заимствованное информатикой математические обозначение,определяющее, как алгоритмы соотносятся с передаваемым им некоторымколичеством N данных.



О большое характеризует две основные величины:



Оценка времени выполнения — общее количество операций, которое алгоритм проведёт на данном множестве данных.

Оценка объёма — общее количество памяти, требующееся алгоритму для обработки данного множества данных.



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



Вот некоторые распространённые значения О большого:




Имя Нотация Что вы скажете, припрись они к вам на вечеринку
----------------------------------------------------------------------------
Константная O(1) ОХРЕНЕННО!!
Логарифмическая O(log N) КРУТО!
Линейная O(N) НОРМАС.
Линейно-
логарифмическая O(N log N) БЛИИИН...
Полиномиальная O(N ^ 2) ОТСТОЙ
Экспоненциальная O(2 ^ N) ОТВРАТИТЕЛЬНО
Факториальная O(N!) ТВОЮЖМАТЬ




Чтобы дать представление, о каких порядках чисел мы говорим, давайте взглянем,что это будут за значения в зависимости от N.



           N = 5            10             20             30
-----------------------------------------------------------------------
O(1) 1 1 1 1
O(log N) 2.3219... 3.3219... 4.3219... 4.9068...
O(N) 5 10 20 30
O(N log N) 11.609... 33.219... 84.638... 147.204...
O(N ^ 2) 25 100 400 900
O(2 ^ N) 32 1024 1,048,576 1,073,741,824
O(N!) 120 3,628,800 2,432,902,0... 265,252,859,812,191,058,636,308,480,000,000




Как видите, даже при относительно небольших числах можно сделать *дофига*дополнительной работы.



Структуры данных позволяют производить 4 основных типа действий:доступ, поиск, вставку и удаление.



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



                          Доступ      Поиск       Вставка      Удаление
------------------------------------------------------------------------
Массив O(1) O(N) O(N) O(N)
Связный список O(N) O(N) O(1) O(1)
Двоичное дерево поиска O(log N) O(log N) O(log N) O(log N)




Или даже…



                          Доступ       Поиск      Вставка      Удаление
------------------------------------------------------------------------
Массив ОХРЕНЕННО НОРМАС НОРМАС НОРМАС
Связный список НОРМАС НОРМАС ОХРЕНЕННО ОХРЕНЕННО
Двоичное дерево поиска КРУТО КРУТО КРУТО КРУТО




Кроме того, некоторые действия имеют разную «среднюю» производительность ипроизводительность в «самом худшем случае».



Идеальной структуры данных не существует. Вы выбираете самую подходящую,основываясь на данных и на том, как они будут обрабатываться. Чтобы сделатьправильный выбор, важно знать различные распространённые структуры данных.




/*** ===================================================================== ***\
** - ПАМЯТЬ -------------------------------------------------------------- **
* ========================================================================= *
* _.-.. *
* ,'9 )\)`-.,.--. *
* `-.| `. *
* \, , \) *
* `. )._\ (\ *
* |// `-,// *
* ]|| //" *
** hjw "" "" **
\*** ===================================================================== ***/




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



Фрагмент памяти можно представить так:




Значения: |1001|0110|1000|0100|0101|1010|0010|0001|1101|1011...
Адреса: 0 1 2 3 4 5 6 7 8 9 ...




Если вы задумывались, почему в языках программирования отсчётначинается с 0 — потому, что так работает память. Чтобы прочитать первыйфрагмент памяти, вы читаете с 0 до 1, второй — с 1 до 2. Адресаэтих фрагментов соответственно равны 0 и 1.



Конечно же, в компьютере больше памяти, чем показано в примере, однакоеё устройство продолжает принцип рассмотренного шаблона.



Просторы памяти — как Дикий Запад. Каждая работающая на компьютере программахранится внутри одной и той же *физической* структуры данных.Использование памяти — сложная задача, и для удобной работы с нейсуществуют дополнительные уровни абстракции.



Абстракции имеют два дополнительных назначения:



— Сохраняют данные в памяти таким образом, чтобы с ними было эффективно и/или быстро работать.

— Сохраняют данные в памяти так, чтобы их было проще использовать.




/*** ===================================================================== ***\
** - СПИСКИ -------------------------------------------------------------- **
* ========================================================================= *
* * _______________________ *
* ()=(_______________________)=() * *
* * | | *
* | ~ ~~~~~~~~~~~~~ | * * *
* * | | *
* * | ~ ~~~~~~~~~~~~~ | * *
* | | *
* | ~ ~~~~~~~~~~~~~ | * *
* * | | *
* * |_____________________| * * *
* ()=(_______________________)=() *
** **
\*** ===================================================================== ***/




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



Список — представление пронумерованной последовательности значений,где одно и то же значение может присутствовать сколько угодно раз.



Начнём с пустого блока памяти, представленного обычным JavaScript-массивом.Также нам понадобится хранить значение длины списка.



Заметьте, что мы хотим хранить длину отдельно, поскольку в реальностиу «памяти» нет значения length, которое можно было бы взять и прочитать.



class List {

constructor() {
this.memory = [];
this.length = 0;
}

//...
}




Первым делом нужно получать данные из списка.



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



Сложность операции доступа в список — O(1) — «ОХРЕНЕННО!!»



get(address) {
return this.memory[address];
}




У списков есть порядковые номера, поэтому можно вставлять значенияв начало, середину и конец.



Мы сфокусируемся на добавлении и удалении значений в начало иликонец списка. Для этого понадобятся 4 метода:



— Push — Добавить значение в конец.

— Pop — Удалить значение из конца.

— Unshift — Добавить значение в начало.

— Shift — Удалить значение из начала.



Начнём с операции «push» — реализуем добавление элементов в конец списка.



Это настолько же легко, как добавить значение в адрес, следующийза нашим списком. Поскольку мы храним длину,вычислить адрес — проще простого. Добавим значение и увеличим длину.



Добавление элемента в конец списка — константа O(1) — «ОХРЕНЕННО!!»



push(value) {
this.memory[this.length] = value;
this.length++;
}




Далее, реализуем метод «pop», убирающий элемент из конца нашего списка.



Аналогично push, всё, что нужно сделать — убрать значениеиз последнего адреса. Ну, и уменьшить длину.



Удаление элемента из конца списка — константа O(1) — «ОХРЕНЕННО!!»



pop() {
// Нет элементов — ничего не делаем.
if (this.length === 0) return;

// Получаем последнее значение, перестаём его хранить, возвращаем его.
var lastAddress = this.length - 1;
var value = this.memory[lastAddress];
delete this.memory[lastAddress];
this.length--;

// Возвращаем значение, чтобы его можно было использовать.
return value;
}




«Push» и «pop» работают с концом списка, и в общем-то являютсяпростыми операциями, поскольку не затрагивают весь остальной список.



Давайте посмотрим, что происходит, когда мы работаем с началом списка,с операциями «unshift» и «shift».



Чтобы добавить новый элемент в начало списка, нужно освободить пространстводля этого значения, сдвинув на один все последующие значения.




[a, b, c, d, e]
0 1 2 3 4

https://habrahabr.ru/post/310794/

Метки:   Комментарии (0)КомментироватьВ цитатник или сообщество
rss_rss_hh_new

Сжатие мобильной графики в формат ETC1 и открытая утилита

Вторник, 20 Сентября 2016 г. 14:06 (ссылка)

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







Формат ETC1 обязателен к поддержке на всех Android-устройствах с OpenGL ES 2.0 и является хорошей отправной точкой оптимизации потребляемой оперативной памяти. По сравнению с форматами PNG, JPEG, WebP загрузка текстур ETC1 осуществляется без интенсивных расчетов обычным копированием памяти. Также улучшается производительность игры по причине меньших размеров данных текстур пересылаемых из медленной памяти в быструю.



На любом устройстве с OpenGL ES 3.0 возможно использование текстур в формате ETC1, являющимся подмножеством улучшенного формата ETC2.



Использование сжатых текстур в формате ETC1



Формат ETC1 содержит только компоненты цвета RGB, поэтому он подходит для непрозрачных фонов, которые рекомендуется рисовать с отключенным Alpha-blending.



Что делать с прозрачной графикой? Для нее задействуем две текстуры ETC1 (далее — 2xETC1):



— в первой текстуре храним исходный RGB;

— во второй текстуре храним исходную альфу (далее — A), скопировав ее в компоненты RGB.



Тогда в пиксельном шейдере 2xETC1 восстановим цвета таким образом:



uniform sampler2D u_Sampler;
uniform sampler2D u_SamplerAlpha;

varying vec2 v_TexCoords;
varying vec4 v_Color;

void main() {
   vec4 sample = texture2D(u_Sampler, v_TexCoords);
   sample.a = texture2D(u_SamplerAlpha, v_TexCoords).r;
   gl_FragColor = sample * v_Color;
}


Особенности подготовки атласов перед сжатием в формат ETC1



Формат ETC1 использует независимые блоки 4x4 пикселя, поэтому положение помещаемых в атлас элементов желательно выравнивать на 4 пикселя, чтобы исключить попадание разных элементов в общий блок.



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



В случае полигональных атласов элементы разводятся на приемлемое расстояние. Все блоки ETC1 при размере 4x4 состоят из пары полосок 2x4 или 4x2, поэтому даже расстояние в 2 пикселя может иметь хороший изолирующий эффект.



Чем можно качественно сжать в формат ETC1?



Имеется выбор среди бесплатных утилит:



ETC2Comp;

Mali GPU Texture Compression Tool;

PVRTexTool;

rg-etc1.



Для качественного сжатия графики приходится задавать perceptual метрику, учитывающую особенности восприятия, а также выбирать медленные режимы best и slow. Один раз попробовав качественно сжать текстуру 2048x2048 понимаешь, что это долгий процесс… Возможно поэтому многие разработчики ограничиваются быстрыми альтернативами medium и fast. Можно ли сделать лучше?



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



Идеи качественного сжатия в формат ETC1



Формат ETC1 является форматом с независимыми блоками. Поэтому мы используем классический подход сжатия отдельных блоков, который хорошо распараллеливается. Конечно, можно пытаться улучшить стыковку блоков, рассматривая наборы блоков, но в таком случае потребуется информация о принадлежности элементам атласа и резко возрастает вычислительная сложность задачи.



Для сравнения результатов сжатия подходит утилита dssim.



Для каждого блока придется перебрать все 4 возможные режима кодирования, чтобы найти наилучший, в коде функция CompressBlockColor:



— две полоски 2x4, каждая имеющая свой базовый 4-битный цвет, в коде вызовы CompressBlockColor44(…, 0);

— две полоски 4x2, каждая имеющая свой базовый 4-битный цвет, в коде вызовы CompressBlockColor44(…, 1);

— две полоски 2x4, первая имеющая базовый 5-битный цвет, вторая отличающаяся базовым цветом от первой в диапазоне 3-бит, в коде вызовы CompressBlockColor53 (…, 2);

— две полоски 4x2, первая имеющая базовый 5-битный цвет, вторая отличающаяся базовым цветом от первой в диапазоне 3-бит, в коде вызовы CompressBlockColor53 (…, 3).














2x4, 444+444 4x2, 444+444 2x4, 555+333 4x2, 555+333


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



PixelError = 0.715158 * (dstG - srcG)^2 + 0.212656 * (dstR - srcR)^2 + 0.072186 * (dstB - srcB)^2


Перейдем к целочисленным значениям, умножив коэффициенты на 1000 и округлив. Тогда начальная ошибка блока 4x4 составит kUnknownError  = (255^2) * 1000 * 16 + 1, где 255 — максимальная ошибка цветовой компоненты, 1000 – фиксированная сумма весов, 16 — количество пикселей. Такая ошибка укладывается в int32_t. Можно заметить, что целочисленное квадрирование близко по смыслу учету гаммы 2.2.



У PSNR есть слабые места. Например, кодирование заливки цветом c0 выбором из палитры c1 = c0 - d и c2 = c0 + d вносит одинаковую ошибку d^2. Это означает случайный выбор между c1 и c2 влекущий всевозможные шашки.



Для улучшения результата финальный расчет в блоке выполним по SSIM. В коде это делается в функции ComputeTableColor с использованием макросов SSIM_INIT, SSIM_UPDATE, SSIM_CLOSE, SSIM_OTHER, SSIM_FINAL. Идея в том, что для всех решений с наилучшим PSNR (в найденном режиме кодирования) выбирается решение с наибольшим SSIM.



Для каждого режима кодирования блока придется перебрать все возможные комбинации базовых цветов. В случае независимых базовых цветов функция CompressBlockColor44 выполняет независимое сжатие полосок двумя вызовами функции GuessColor4.



Функция GuessColor4 выполняет перебор отклонений и компонент базового цвета:



for (int q = 0; q < 8; q++)
   for (int c0 = 0; c0 < c0_count; c0++) // G, c0_count <= 16
       for (int c1 = 0; c1 < c1_count; c1++) // R, c1_count <= 16
           for (int c2 = 0; c2 < c2_count; c2++) // B, c2_count <= 16
               ComputeErrorGRB(c, q);


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



for (int qa = 0; qa < 8; qa++)
   for (int qb = 0; qb < 8; qb++)
       AdjustColors53(qa, qb);


Функция AdjustColors53 выполняет перебор компонент двух базовых цветов:



for (int a0 = 0; a0 < a0_count; a0++) // G, a0_count <= 32
   for (int a1 = 0; a1 < a1_count; a1++) // R, a1_count <= 32
       for (int a2 = 0; a2 < a2_count; a2++) // B, a2_count <= 32
           ComputeErrorGRB(a, qa);

           for (int d0 = Ld0; d0 <= Hd0; d0++) // G, d0_count <= 8
               for (int d1 = Ld1; d1 <= Hd1; d1++) // R, d1_count <= 8
                   for (int d2 = Ld2; d2 <= Hd2; d2++) // B, d2_count <= 8
                       b = a + d;
                       ComputeErrorGRB(b, qb);


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



В случае графики 2xETC1 полностью прозрачные пиксели в общем случае могут иметь произвольный цвет RGB, который будет умножен на нулевую альфу.





Незначащие пиксели мы можем не учитывать, поэтому отфильтруем их в самом начале, в коде это вызовы FilterPixelsColor. С другой стороны, не всякий прозрачный пиксель является незначащим, вспомним хотя бы защитную рамочку в 1-2 пикселя и эффект отбеливания границ.



Поэтому сделаем трафарет, в котором ноль будет означать незначащий пиксель, а положительная величина покажет значимый пиксель. Трафарет создается на основе канала A применением обводки, чаще размера 1 или 2 пикселя, в коде это функция OutlineAlpha.



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

                         



Таким образом, сжатие 2xETC1 можно представить следующими шагами, реализованными в функции EtcMainWithArgs:



1) сжимаем канал A в формат ETC1;

2) распаковываем сжатый канал A обратно;

3) делаем обводку видимого, где A > 0, получая трафарет;

4) сжимаем каналы RGB в формат ETC1 с учетом трафарета.



Идеи ускорения качественного сжатия в формат ETC1



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



Для формата с независимыми блоками легко реализуется инкрементальное сжатие. Например, когда сохранились результаты предыдущего сжатия.



В данном случае упаковщик пытается прочитать выходной файл, распаковать его и рассчитать имеющуюся ошибку, это будет начальным решением. Если же файла нет, то берется начальное решение из нулей. В коде это LoadEtc1, CompressBlockColor, MeasureHalfColor.



Последующие шаги должны пытаться улучшить имеющееся решение алгоритмами по возрастанию сложности. Поэтому сначала вызываются быстрые CompressBlockColor44, лишь затем медленные CompressBlockColor53. Такая цепочечная конструкция в перспективе позволит интегрировать сжатие в формат ETC2.



Перед началом перебора вложенными циклами есть смысл найти решение в разрезе цветовых компонент. Дело в том, что наилучшее решение не может иметь ошибку меньше, чем суммарная ошибка наилучших решений для каждой из компонент G, R, B. Часто результирующая ошибка будет существенно больше, что характеризует нелинейность и сложность алгоритма ETC1.



Решения в разрезе цветовых компонент представлены структурами GuessStateColor и AdjustStateColor. Для каждого значения из таблицы отклонений g_table рассчитываются ошибки полосок Half и сохраняются в поля node0, node1, node2. Причем в GuessStateColor в индексах [0x00..0x0F] хранятся рассчитанные ошибки для всех возможных базовых цветов g_colors4, а в индексе [0x10] наилучшее решение. Для AdjustStateColor наилучшее решение хранится в индексе [0x20], все возможные базовые цвета берутся из g_colors5.



Расчет ошибки по компонентам цвета осуществляется функциями ComputeLevel, GuessLevels, AdjustLevels на основе таблиц g_errors4, g_errors5, предварительно рассчитанных функцией InitLevelErrors.



Перебор цветовых компонент есть смысл сделать в порядке возрастания вносимой ими ошибки, для этого осуществляется сортировка полей node0, node1, node2 функциями SortNodes10 и SortNodes20.



Для ускорения самой сортировки применяются сортирующие сети, рассчитанные на тематическом сайте.



Перед выполнением сортировки есть смысл отбросить большие ошибки, превышающие найденное решение. При этом заметно уменьшается количество элементов в полях node0, node1, node2, что существенно ускоряет сортировку и дальнейший перебор.



Третий вложенный цикл по цветовым компонентам G, R, B можно попытаться отсечь, найдя наилучшее решение для текущих G, R функцией ComputeErrorGR, которая в 2 раза быстрее функции ComputeErrorGRB. Это, кстати, горячие места в профилировщике.



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



Этим занимаются функции Walk и Bottom.



64 вызова функции AdjustColors53 могут привести к повторным вызовам функций ComputeErrorGR и ComputeErrorGRB с одинаковыми параметрами базового цвета, поэтому будем кэшировать результаты вызовов. В свою очередь, для быстрой инициализации кэша можно использовать ленивые вычисления по третьему цветовому компоненту.



В структуре AdjustStateColor поля ErrorsG, ErrorsGR и поле ErrorsGRB очищаемое LazyGR дают существенный прирост производительности.



После различных алгоритмических улучшений пришло время использовать SIMD, в данном случае опубликовано решение на целочисленном SSE4.1. Данные одного пикселя храним как int32x4_t.



Команды _mm_adds_epu8 и _mm_subs_epu8 удобны для расчета четырехцветной палитры из базового цвета и отклонений.



В функциях ComputeErrorGRB и ComputeErrorGR сначала применяются частично развернутые циклы, оптимизированные командой _mm_madd_epi16, так как в большинстве случаев достаточно ее разрядности. В случае же больших погрешностей работает второй цикл на «медленных» командах _mm_mullo_epi32.



Функция ComputeLevel рассчитывает ошибку сразу для четырех значений базового цвета.



Для сжатия одного канала A можно упростить полученный код сжатия RGB. Будет заметно меньше вложенных циклов и повысится производительность.



Достигнутые результаты



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



В скриптах формирования атласов и самой утилите сжатия уделяется внимание вопросам предотвращения артефактов и повышения качества сжатой графики.



На удивление, вместе с повышением качества сжатой графики удалось ускорить само сжатие! В нашем проекте Gardenscapes сжатие атласов в формат ETC1 на процессоре Intel Core i7 6700 занимает 24 секунды. Это быстрее генерации самих атласов и в несколько раз быстрее предыдущей утилиты сжатия в режиме fast. Предложенное инкрементальное сжатие происходит за 19 секунд.



В заключение приведу пример сжатия текстуры 8192x8192 RGB представленной утилитой EtcCompress под Win64 на процессоре Intel Core i7 6700:



x:\>EtcCompress
Usage: EtcCompress [/retina] src [dst_color] [dst_alpha] [/debug result.png]

x:\>EtcCompress 8192.png 1.etc /debug 1.png
Loaded 8192.png
Image 8192x8192, Texture 8192x8192

Compressed 4194304 blocks, elapsed 11372 ms, 368827 bps
Saved 1.etc
Texture RGB wPSNR = 42.796053, wSSIM_4x2 = 0.97524678

Saved 1.png

x:\>EtcCompress 8192.png 1.etc /debug 2.png
Loaded 8192.png
Image 8192x8192, Texture 8192x8192

Loaded 1.etc
Compressed 4194304 blocks, elapsed 6580 ms, 637432 bps
Saved 1.etc
Texture RGB wPSNR = 42.796053, wSSIM_4x2 = 0.97524678

Saved 2.png

x:\>fc /b 1.png 2.png
Сравнение файлов 1.png и 2.png
FC: различия не найдены


Надеемся, что утилита поможет качественно и быстро сжимать мобильную графику.
Original source: habrahabr.ru (comments, light).

https://habrahabr.ru/post/310484/

Метки:   Комментарии (0)КомментироватьВ цитатник или сообщество
rss_rss_hh_new

Введение в futures-rs: асинхронщина на Rust [перевод]

Суббота, 17 Сентября 2016 г. 13:11 (ссылка)



Этот документ поможет вам изучить контейнер для языка программирования Rust — futures, который обеспечивает реализацию futures и потоков с нулевой стоимостью. Futures доступны во многих других языках программирования, таких как C++, Java, и Scala, и контейнер futures черпает вдохновение из библиотек этих языков. Однако он отличается эргономичностью, а также придерживается философии абстракций с нулевой стоимостью, присущей Rust, а именно: для создания и композиции futures не требуется выделений памяти, а для Task, управляющего ими, нужна только одна аллокация. Futures должны стать основой асинхронного компонуемого высокопроизводительного ввода/вывода в Rust, и ранние замеры производительности показывают, что простой HTTP сервер, построенный на futures, действительно быстр.





Эта публикация является переводом официального туториала futures-rs.



Эта документация разделена на несколько разделов:




  • "Здравствуй, мир!";

  • Типаж future;

  • Типаж Stream;

  • Конкретные futures и поток(Stream);

  • Возвращение futures;

  • Task и future;

  • Локальные данные задачи.



Здравствуй, мир!



Контейнер futures требует Rust версии 1.10.0 или выше, который может быть легко установлен с помощью Rustup. Контейнер проверен и точно работает на Windows, macOS и Linux, но PR'ы для других платформ всегда приветствуются. Вы можете добавить futures в Cargo.toml своего проекта следующим образом:



[dependencies]
futures = { git = "https://github.com/alexcrichton/futures-rs" }
tokio-core = { git = "https://github.com/tokio-rs/tokio-core" }
tokio-tls = { git = "https://github.com/tokio-rs/tokio-tls" }


Примечание: эта библиотека в активной разработке и требует получения исходников с git напрямую, но позже контейнер

будет опубликован на crates.io.

Здесь мы добавляем в зависимости три контейнера:




  • futures — определение и ядро реализации Future и Stream;

  • tokio-core — привязка к контейнеру mio, предоставляющая конкретные

    реализации Future и Stream для TCP и UDP;

  • tokio-tls — реализация SSL/TLS на основе futures.



Контейнер futures является низкоуровневой реализацией futures, которая не несёт в себе какой-либо среды выполнения или слоя ввода/вывода. Для примеров ниже воспользуемся конкретными реализациями, доступными в tokio-core, чтобы показать, как futures и потоки могут быть использованы для выполнения сложных операций ввода/вывода с нулевыми накладными расходами.



Теперь, когда у нас есть всё необходимое, напишем первую программу. В качестве hello-world примера скачаем домашнюю

страницу Rust:



extern crate futures;
extern crate tokio_core;
extern crate tokio_tls;

use std::net::ToSocketAddrs;

use futures::Future;
use tokio_core::reactor::Core;
use tokio_core::net::TcpStream;
use tokio_tls::ClientContext;

fn main() {
let mut core = Core::new().unwrap();
let addr = "www.Rust-lang.org:443".to_socket_addrs().unwrap().next().unwrap();

let socket = TcpStream::connect(&addr, &core.handle());

let tls_handshake = socket.and_then(|socket| {
let cx = ClientContext::new().unwrap();
cx.handshake("www.Rust-lang.org", socket)
});
let request = tls_handshake.and_then(|socket| {
tokio_core::io::write_all(socket, "\
GET / HTTP/1.0\r\n\
Host: www.Rust-lang.org\r\n\
\r\n\
".as_bytes())
});
let response = request.and_then(|(socket, _)| {
tokio_core::io::read_to_end(socket, Vec::new())
});

let (_, data) = core.run(response).unwrap();
println!("{}", String::from_utf8_lossy(&data));
}


Если создать файл с таким содержанием по пути src/main.rs и запустить команду cargo run, то отобразится HTML главной страницы Rust.



Примечание: Rustc 1.10 компилирует этот пример медленно. С 1.11 компиляция происходит быстрее.

Этот код слишком большой, чтобы разобраться в нём сходу, так что пройдёмся построчно.

Взглянем на функцию main():



let mut core = Core::new().unwrap();
let addr = "www.Rust-lang.org:443".to_socket_addrs().unwrap().next().unwrap();


Здесь создается цикл событий, в котором будет выполняться весь ввод/вывод. После преобразуем имя хоста "www.Rust-lang.org" с использованием метода to_socket_addrs из стандартной библиотеки.



Далее:



let socket = TcpStream::connect(&addr, &core.handle());


Получаем хэндл цикла событий и соединяемся с хостом при помощи TcpStream::connect. Примечательно, что TcpStream::connect возвращает future. В действительности, сокет не подключен, но подключение произойдёт позже.



После того, как сокет станет доступным, нам необходимо выполнить три шага для загрузки домашней страницы Rust-lang.org:




  1. Выполнить TLS хэндшэйк. Работать с этой домашней страницей можно только по HTTPS, поэтому мы должны подключиться к порту 443 и следовать протоколу TLS.




  2. Отправить HTTP GET запрос. В рамках этого руководства мы напишем запрос вручную, тем не менее, в боевых программах следует использовать HTTP клиент, построенный на futures.




  3. В заключение, скачать ответ посредством чтения всех данных из сокета.



Рассмотрим каждый из этих шагов подробно.

Первый шаг:



let tls_handshake = socket.and_then(|socket| {
let cx = ClientContext::new().unwrap();
cx.handshake("www.Rust-lang.org", socket)
});


Здесь используется метод and_then типажа future, вызывая его у результата выполнения метода TcpStream::connect. Метод and_then принимает замыкание, которое получает значение предыдущего future. В этом случае socket будет иметь тип TcpStream.

Стоит отметить, что замыкание, переданное в and_then, не будет выполнено в случае если TcpStream::connect вернёт ошибку.



Как только получен socket, мы создаём клиентский TLS контекст с помощью ClientContext::new. Этот тип из контейнера tokio-tls представляет клиентскую часть TLS соединения. Далее вызываем метод handshake, чтобы выполнить TLS хэндшейк. Первый аргумент — доменное имя, к которому мы подключаемся, второй — объект ввода/вывода (в данном случае объект socket).



Как и TcpStream::connect раннее, метод handshake возвращает future. TLS хэндшэйк может занять некоторое время, потому что клиенту и серверу необходимо выполнить некоторый ввод/вывод, подтверждение сертификатов и т.д. После выполнения future вернёт TlsStream, похожий на расмотренный выше TcpStream.



Комбинатор and_then выполняет много скрытой работы, обеспечивая выполнение futures в правильном порядке и отслеживая их на лету. При этом значение, возвращаемое and_then, реализует типаж Future, поэтому мы можем составлять цепочки вычислений.



Далее отправляем HTTP запрос:



let request = tls_handshake.and_then(|socket| {
tokio_core::io::write_all(socket, "\
GET / HTTP/1.0\r\n\
Host: www.Rust-lang.org\r\n\
\r\n\
".as_bytes())
});


Здесь мы получили future из предыдущего шага (tls_handshake) и использовали and_then снова, чтобы продолжить вычисление. Комбинатор write_all полностью записывает HTTP запрос, производя многократные записи по необходимости.



Future, возвращаемый методом write_all, будет выполнен, как только все данные будут записаны в сокет. Примечательно, что TlsStream скрыто шифрует все данные, которые мы записывали, перед тем как отправить в сокет.



Третья и последняя часть запроса выглядит так:



let response = request.and_then(|(socket, _)| {
tokio_core::io::read_to_end(socket, Vec::new())
});


Предыдущий future request снова связан, на этот раз с результатом выполнения комбинатора read_to_end. Этот future будет читать все данные из сокета и помещать их в предоставленный буфер и вернёт буфер, когда обрабатываемое соединение передаст EOF.



Как и ранее, чтение из сокета на самом деле скрыто расшифровывает данные, полученные от сервера, так что мы читаем

расшифрованную версию.



Если испонение прервётся на этом месте, вы удивитесь, так как ничего не произойдёт. Это потому что всё, что мы сделали, основано на future вычислениях, и мы на самом деле не запустили их. До этого момента мы не делали никакого ввода/вывода и не выполняли HTTP запросов и т.д.



Чтобы по-настоящему запустить futures и управлять ими до завершения, необходимо запустить цикл событий:



let (_, data) = core.run(response).unwrap();
println!("{}", String::from_utf8_lossy(&data));


Здесь future response помещается в цикл событий, запрашивая у него выполнение future. Цикл событий будет выполняться, пока не будет получен результат.



Примечательно, что вызов core.run(..) блокирует вызывающий поток, пока future не сможет быть возвращен. Это означает, что data имеет тип Vec. Тогда мы можем напечатать это в stdout как обычно.



Фух! Мы рассмотрели futures, инициализирующие TCP соедениение, создающие цепочки вычислений и читающие данные из сокета. Но это только пример возможностей futures, далее рассмотрим нюансы.



Типаж Future



Типаж future является ядром контейнера futures. Этот типаж представляет асинхронные вычисления и их результат.



Взглянем на следующий код:



trait Future {
type Item;
type Error;

fn poll(&mut self) -> Poll;

// ...
}


Я уверен, что определение содержит ряд пунктов, вызывающих вопросы:




  • Item и Error;

  • poll;

  • комбинаторы future.



Разберём их детально.



Item и Error



type Item;
type Error;


Первая особенность типажа future, как вы, вероятно, заметили, это то, что он содержит два ассоциированных типа. Они представляют собой типы значений, которые future может получить. Каждый экземпляр Future можно обработать как Result.



Эти два типа будут применяться очень часто в условиях where при передаче futures и в сигнатурах типа, когда futures будут возвращаться.



Для примера, при возвращении future можно написать:



fn foo() -> Box u32, Error = io::Error>> {
// ...
}


Или, когда принимаем future:



fn foo(future: F)
where F: Future io::Error>,
F::Item: Clone,
{
// ...
}


poll



fn poll(&mut self) -> Poll;


Работа типажа Future построена на этом методе. Метод poll — это единственная точка входа для извлечения вычисленного в future значения. Как пользователю future вам редко понадобится вызывать этот метод напрямую. Скорее всего, вы будете взаимодействовать с futures через комбинаторы, которые создают высокоуровневые абстракции вокруг futures. Однако знание того, как futures работают под капотом, будет полезным.



Подробнее рассмотрим метод poll.



Обратим внимание на аргумент &mut self, который вызывает ряд ограничений и свойств:




  • futures могут быть опрошены только одним потоком единовременно;

  • во время выполнения метода poll, futures могут изменять своё состояние;

  • после заврешения poll владение futures может быть передано другой сущности.



На самом деле тип Poll является псевдонимом:



type Poll = Result, E>;


Так же взглянем, что из себя представляет перечисление Async:



pub enum Async {
Ready(T),
NotReady,
}


Посредством этого перечисления futures могут взаимодействовать, когда значение future готово к использованию. Если произошла ошибка, тогда будет сразу возвращено Err. В противном случае, перечисление Async отображает, когда значение Future полностью получено или ещё не готово.



Типаж Future, как и Iterator, не определяет, что происходит после вызова метода poll, если future уже обработан. Это означает, что тем, кто реализует типаж Future, не нужно поддерживать состояние, чтобы проверить, успешно ли вернул результат метод poll.



Если вызов poll возвращает NotReady, future всё ещё требуется знать, когда необходимо выполниться снова. Для достижения этой цели future должен обеспечить следующий механизм: при получении NotReady текущая задача должна иметь возможность получить уведомление, когда значение станет доступным.



Метод park является основной точкой входа доставки уведомлений. Эта функция возвращает Task, который реализует типажи Send и 'static, и имеет основной метод — unpark. Вызов метода unpark указывает, что future

может производить вычисления и возвращать значение.



Более детальную документацию можно найти здесь.



Комбинаторы future



Теперь кажется, что метод poll может внести немного боли в ваш рабочий процесс. Что если у вас есть future, который должен вернуть String, а вы хотите конвертировать его в future, возвращающий u32? Для получения такого рода композиций типаж future обеспечивает большое число комбинаторов.



Эти комбинаторы аналогичны комбинаторам из типажа Iterator, и все они принимают future и возвращают новый future.



Для примера, мы могли бы написать:



fn parse(future: F) -> Box>
where F: Future + 'static,
{
Box::new(future.map(|string| {
string.parse::().unwrap()
}))
}


Здесь для преобразования future, возвращающий тип String, во future, возвращающий u32, используется map. Упаковывание в Box не всегда необходимо и более подробно будет рассмотрено в разделе возвращений futures.



Комбинаторы позволяют выражать следующие понятия:




  • изменение типа future (map, map_err);

  • запуск другого future, когда исходный будет выполнен (then, and_then, or_else);

  • продолжение выполнения, когда хотя бы один из futures выполнился (select);

  • ожидание выполнения двух future (join);

  • определение поведения poll после вычислений (fuse).



Использование комбинаторов похоже на использование типажа Iterator в Rust или futures в Scala. Большинство манипуляций с futures заканчивается использованием этих комбинаторов. Все комбинаторы имеют нулевую стоимость, что означает отсутствие выделений памяти, и что реализация будет оптимизирована таким образом, как будто вы писали это вручную.



Типаж Stream



Предварительно мы рассмотрели типаж Future, который полезен в случае вычисления всего лишь одного значения в течение всего времени. Но иногда вычисления лучше представить в виде потока значений. Для примера, TCP слушатель производит множество TCP соединений в течение своего времени жизни. Посмотрим, какие сущности из стандартной библиотеки эквиваленты Future и Stream:




















# items Sync Async Common operations
1 [Result] [Future] [map], [and_then]

https://habrahabr.ru/post/310234/

Метки:   Комментарии (0)КомментироватьВ цитатник или сообщество
SoftLabirint

Монтажные кодеки и алгоритмы компрессии (2016) Мастер-класс » SoftLabirint.Ru: Скачать бесплатно и без регистрации - Самые Популярные Новости Интернета

Четверг, 15 Сентября 2016 г. 12:58 (ссылка)
softlabirint.ru/video/video...klass.html


Монтажные кодеки и алгоритмы компрессии (2016) Мастер-класс

Те, кто пытается снимать видео своим фотоаппаратом, всегда приходят в недоумение от связки «контейнер + содержимое». Если в фотографии принято, что у файла TIFF расширение .tif и хранится в нем тоже TIFF, то в мире видео расширение .mov, называется оно QuickTime и хранится в нем кодек h265. С этим еще можно разобраться самостоятельно, но как быть с остальным?



Мастер-класс даст ответы на самые популярные вопросы: например, какой кодек выбрать для сжатия файлов, если съемка велась на DSLR? Какой кодек подойдет лучше для режима прокси?



Начнем мы с терминологии, затем посмотрим, как реализованы алгоритмы сжатия и как устроена межкадровая и внутрикадровая компрессия, а главное – какая от них польза (или вред). Поговорим о потерях цвета, происходящие при съемке в кодеке h264, и насколько они критичны. Обсудим судьбу нового кодека h265. Узнаем, что лучше: ProRes или DNxHD ? Цель – разобраться с некоторыми мифами: что такое «стандартная авишка» и почему ее не существует, почему нельзя помочь человеку, у которого «Премьер» не проигрывает «обычный видос», и так далее. На этом мастер-классе вы сможете решить накопившиеся вопросы и упорядочить отрывочные знания, полученные из разных источников, часто противоречивые и бессистемные.



Чему Вы научитесь:

-Ориентироваться в кодеках и форматах файлов.

-Понимать, как работают различные алгоритмы компрессии.

-Оценивать, насколько теряется цвет в изображении (важно для цветкора).

-Выбирать кодеки для работы так, чтобы система не тормозила.

-Сжимать файлы без потери качества.



Программа мастер-класса:

*Понятия «кодек», «контейнер» и «расширение».

*Алгоритмы компрессии.

*Внутрикадровая и межкадровая компрессия.

*Что такое GOP и Long-GOP. Всегда ли «длиннее – значит лучше»?

*Цветоразностная компрессия.

*Волшебные цифры 4:4:4, 4:2:2, 4:2:0 – что это и какая от них польза?

*Битрейт. Понятие и назначение. CBR, VBR и прочее.

*«Зоопарк» форматов: ProRes, DNxHR, H.264, AVC – как в этом разобраться и не сойти с ума.

*Пиксели: а всегда ли они квадратные?



+ Бонус:

Технологические процессы монтажа.



Чему вы научитесь?

-Ориентироваться в технологическом процессе (от этапа получения отснятого материала до сдачи готового ролика).

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

-Моделировать технологический процесс для своих условий.

 



Монтажные кодеки и алгоритмы компрессии (2016) Мастер-класс



Монтажные кодеки и алгоритмы компрессии (2016) Мастер-класс



Монтажные кодеки и алгоритмы компрессии (2016) Мастер-класс






Информация о видеокурсе

Название: Монтажные кодеки и алгоритмы компрессии

Автор: Дмитрий Ларионов

Год выхода: 2016

Жанр: Видеокурс

Язык: Русский

Выпущено: Россия

Продолжительность: ~6 часов



Файл

Формат: MP4

Видео: AVC, 1362x766, ~180 Kbps

Аудио: AAC, 192 Kbps, 48.0 KHz

Размер: 1.18 Gb



Скачать: Монтажные кодеки и алгоритмы компрессии (2016) Мастер-класс >>>



 



Подписка на новости сайта…

http://feeds.feedburner.com/Soft-Labirint

http://feeds.feedburner.com/Soft-Labirint?format=xml

https://feedburner.google.com/fb/a/mailverify?uri=Soft-Labirint

Метки:   Комментарии (0)КомментироватьВ цитатник или сообщество
rss_rss_hh_new

Почему не нужно сваливать на неточность O-оценок свои проблемы

Четверг, 15 Сентября 2016 г. 04:10 (ссылка)

А ты учел константу в О-большом?

На написание данного поста меня подвигла недавняя публикация этого и вот этого переводов, в которых авторы в интеллигентной форме выражают свое недовольство по поводу того, как O-оценки вычислительной сложности классических, казалось бы, алгоритмов вступили в диссонанс с их практическим опытом разработки. Основным предметом критики послужила модель памяти, в рамках которой эти оценки были получены — она, де, не учитывает особенности иерархической организации по принципу быстродействия, которая имеет место быть в современных вычислительных системах. От чего и произрастают все последующие неприятности. И судя по наблюдаемой реакции благодарных читателей, авторы далеко не одиноки в своем негодовании и желании «наехать» на классиков с их О-большими. Так возможно, действительно стоит отправить на свалку истории выкладки дядек в белых халатах, сделанные ими для ламповых тугодумающих и пышащих жаром машин, и дать дорогу молодым амбициозным моделям, более точно отражающим анатомию современного «железа»?



Давайте разбираться



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



Введем определение. Пусть и — две вещественные функции, определенные на множестве . Тогда из следует, что найдется такое положительное число , что для всех справедливо . Такое обозначение называют -нотацией, а O называют символом Бахмана, либо просто "О-большим".



Из этого определения сразу имеется несколько следствий:



1. Если для всех имеет место , то из " следует, что . В частности, имеем, что умножение на константу не меняет O-оценку.



Проще говоря, при умножении O-выражения на константу символ Бахмана эту константу «съедает». Это означает, что знак равенства в выражении, включающем в себя O-оценку, нельзя интерпретировать как классическое «равенство» значений и к таким выражениям нельзя применять математические операции без дополнительных уточнений. В противном случае мы бы получили странные вещи по типу следующей: . Это следствие произвольности константы, которая «прячется» за символом Бахмана.



2. Если ограничена на , то есть существует такое число , что для всех выполняется , то .



Переводя с математического на русский и взяв для простоты в качестве конечный интервал числовой прямой, имеем следующее: если функция на заданном интервале не уходит в бесконечность, то самое бессмысленное, что можно о ней еще сказать — это то, что ей соответствует O(1). Это совершенно ничего нового не говорит о ее поведении.



Угадай мою сложность

Голубая линия это O(

https://habrahabr.ru/post/310038/

Метки:   Комментарии (0)КомментироватьВ цитатник или сообщество
rss_rss_hh_new

[Из песочницы] Применение нелинейной динамики и теории Хаоса к задаче разработки нового алгоритма сжатия аудио данных

Вторник, 13 Сентября 2016 г. 17:00 (ссылка)

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



Чего вы не найдёте здесь:




  • Сложных уравнений. Цель данной публикации является представление идей и видение задачи. И как любое видение оно во многом абстрактно;

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



Что вы найдёте здесь:




  1. Краткий обзор применения фрактальных преобразований к задаче сжатия данных с потерями;

  2. Необычная интерпретация фрактальных преобразований;

  3. Ссылки на реальный код компрессора и декомпрессора аудио данных посредством фрактальных преобразований (декомпрессор представлен в форме плагина для аудио плейера Winamp);

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



Думаю, что для большинства читателей этой публикации данная задача покажется странной. Обычно, понятие фрактала связывают с красивыми картинками — результатами выполнения фрактальных преобразований, именуемыми также фрактальными (или «странными») аттракторами. Однако, внимательное изучение фрактальных преобразований позволяет понять, что фракталы это не только красивые изображения. Фрактальные преобразования определяют проекции элементов в замкнутом множестве. Таким множествами могут быть цветные точки в 2.5 D пространстве, набор точек на 2 D плоскости, или набор дискретных выборок аудио потока в 1.5 D пространстве.



Я заинтересовался фрактальными преобразованиями с момента написания диссертации на соискания степени кандидата технических наук. Тема диссертации была — «Алгоритмы сокращения вычислительной сложности фрактального анализа в системах обработки визуальных данных». Диссертация была с успехом защищена и принята к публикации LAP LAMBERT Academic Publishing. Иногда встречаю ссылки на неё на сайтах Amazon и Ozon.



Я потратил много времени на изучение как теоретических основ, так и практических результатов исследований фрактальных преобразований и обнаружил только две попытки развития фрактальных преобразований до уровня индустриальных стандартов:




  1. Video codec — 'ClearVideo' by company Iterated System Incorporated.

  2. Image/video codec — 'FIASCO' by Ullrich Hafner.



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



Математические основы



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



Z(n+1) = Zn^2 + C where n = 1, 2, 3,…





Таким образом, очень сложная визуализация может быть достигнута очень простым выражением. Это приводит к следующему вопросу — возможно ли построить реальное изображение посредством фрактального преобразования? Данный вопрос был разрешён утвердительно. Более точно, можно найти такое фрактальное преобразование, которое способно построить изображение с искажениями меньшем или равными любому предопределённому значению. Это означает, что сгенерированное изображение может отличаться от оригинального на величину, неотличимую зрителем благодаря избыточности визуальной информации изображения. Таким образом, фрактальное кодирование изображения является технологией обработки изображения с потерей качества.



В книге — Amazon или Ozon можно найти точное доказательства применимости фрактального преобразования к задачам обработки изображений – теорема «Коллажа» Майкла Брансли.



PIFS



Вы можете спросить – как выполнить фрактальное кодирование (или более точно – фрактальный анализ)? Визуализация фрактального множества Мандельброта весьма впечатляет, но оно было разработано после многих лет исследований. Попытка найти подходящее фрактальное преобразование путём простого перебора бесперспективна. Решение данной проблемы было предложено Майклом Брансли и его аспирантами (Майклом Брансли в дальнейшем основал Iterated Systems Incorporated). Они предложили блочную схему фрактального преобразования. С точки зрения выполнения фрактальных преобразований не существует различий в применимости фрактальных преобразований к множеству точек или к множеству блоков точек — partitioned iterated function systems (PIFS). Подобная схема базируется на извлечении копии точек из одной части множества точек, применении преобразований к копии и вставка результат в другую часть множества – это отличает данный подход от фрактальных преобразований для отдельных точек. PIFS схему можно представить в следующем виде:







где F – оригинальное множество точек, D и R множества областей точек из F, — преобразование одной области из множества D и область множества R. Множества и определяют искомые фрактальные преобразования. Важно отметить, что если фрактальное преобразование для фрактального множества Мандельброта базируется на одном уравнении фрактального преобразования и идеи глобального самоподобия (то есть подобие всего множества любой его части), то PIFS схема базируется на группе фрактальных преобразований и идеи локальном подобии отдельных областей множества.



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



Для понимания данного различия требуется обратить внимание на три главных свойства фрактальных преобразований:




  1. фрактальное преобразование является рекурсивным – оно основано на идее неограниченного применении данного преобразования к множеству;

  2. фрактальное преобразование является сжимающим – это значит, результат всегда меньше оригинала;

  3. пространство фрактальное преобразование компактно – все преобразования над множеством отражается на само множество (самоподобие).



По аналогии с фрактальным преобразованием множества Манделброта, PIFS преобразование для реальных изображений можно представит в следующем виде:





где – преобразование в пространстве точек изображения, – сжимающее преобразование вектора с длинной в вектор с длинной , но что означают переменные и ? Переменные и описывают преобразование на плоскости, но каждая точка реального изображения имеет специальное значение – интенсивность собственной яркости которая должна быть рассмотрена как часть пространства фрактального преобразования: – сжимающее преобразование яркости и – смещение интенсивности яркости (по аналогии уравнении прямой – f(y) = y*s+o).



Что делать с этом уравнением? Очень просто – выполнить данное выражение для всех групп преобразований (, , , ) что должно заполнить множество R, заполняющее все изображение F. И ещё раз, и ещё раз (рекурсивное выполнение), до бесконечности. В реальности, всё намного проще – после каждого рекурсивного выполнения итерации синтеза фрактального множества расстояние между точками уменьшается (сжимающее свойство фрактального преобразования), но если для аналитического пространства нет ограничений в делимости, то для дискретного пространства цифровых изображений новые точки будут попадать в отсечённое пространство между соседними выборками. Это случится после рекурсивных итераций PIFS.



Ожидаемый вопрос – как найти упомянутые коэффициенты , ,  для системы фрактальных преобразований? Задача подобного поиска может быть автоматизирована исходя из следующего уравнения:





задача поиска заключается в поиске пары , которая минимизирует длину вектора отклонения . Если установить экстремальное значение допустимого отклонения равное 0, то можно вывести следующие приближения для и :







Данные выражения позволяют рассчитать оптимальные значения и , но неизвестными переменными остаются и пары . К сожалению, на настоящий момент отсутствуют аналитические решения для этих переменных – остаётся только задавать множества и пар , и перебирать их комбинации для минимизации уравнения:





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



Аудио



Предвижу вопрос – всё выше описанное интересно, но причём тут звук и сжатие звуковых данных? Я полагаю многие уже поняли, что для фрактального анализа природа множеств не имеет значения – множество пикселей на плоскости или множество выборок из звукового потока. Если накапливать выборки входного звукового потока в буфере и затем обрабатывать их как отдельные множества, то можно сформировать систем фрактальных преобразований, из которых можно синтезировать фрактальные множества, приближённые к оригинальным выборкам звукового потока. Что и было реализованно в моём проекте, который включает кодер ROAD и декодер (в форме плагина для Winamp) — тестовые аудио файлы: Origa — Inner Universe 4Samples.road.wav и Alpha — Revolution in Paradise 4Samples.road.wav. Новый алгоритм сжатия звуковых данных позволил разработать формат с пятью уникальными свойствами:




  1. Предпрослушивание. Данный термин звучит странно, но я решил использовать его по аналогии с термином «Предпросмотр» из описания формата сжатия изображения JPEG2000. Но что это может значить для аудио файла? Если взглянуть на выражение для расчёта коэффициента , то можно увидеть что оно рассчитывается на основе усреднения значений соседних выборок. В результате, через подстановку можно получить следующее выражение:





    Это выражение показывает важный факт – часть коэффициентов фрактальных преобразований можно рассматривать как усреднённое значение пикселей изображения или выборок звукового потока. Это значение является «точкой роста» фрактального множества. Фрактальные преобразования нуждаются в подобных точках. Однако, при использовании PIFS для анализа звуковых данных можно ограничить размеры областей в 4 точки–выборки – это позволяет получить усреднённый звуковой поток в низкочастотной области (к примеру для оригинальной частоты звукового потока в 48000 Гц, усреднённый поток имеет частоту в 12000 Гц). В результате, сжатый поток можно прослушать с ухудшенным качеством без декодирования. Полагаю что данное свойство можно определить как «Предпрослушивание».




  2. Частичная совместимость. Из возможности организации отдельного низкочастотного потока звуковых данных из коэффициентов фрактальных преобразований возникает вопрос – как это реализовать? Можно резервировать отдельный участок потока данных, но факт что данный поток является несжатым потоком данных, приводит к идее, что данный поток может быть дополнительно сжат другим алгоритмом и упакован в известный индустриальный формат. В этом случае файл может быть воспроизведён в аудио проигрывателе, совместимым с индустриальным форматом с ухудшенным качеством. Данную идею можно реализовать в форме стека компрессоров. В моём проекте был выбран формат WAVE от Майкрософт. Этот формат не включает сжатие, но позволяет на практике реализовать стек форматов и частичную совместимость:






  3. Разгон. Идея данного свойства заключается в увеличении частоты декодированного аудио потока. Понять идею реализации данного свойства можно если рассмотреть почему данное свойство невозможно реализовать во многих индустриальных форматах. К примеру рассмотри формат mp3 – при попытке удвоения частоты декодированного аудио потока требуется увеличить базис обратного дискретно-косинусного преобразования с 128 до 256, но сжатые данные включают данные только для 128. Это приводит к проблеме неполноты базиса ортогонального преобразования. Подобная проблема возникает и с форматами на основе линейного предсказания. Однако, для фрактального анализа дело обстоит иначе. Рассмотренные ранее коэффициенты , , не связаны с размером базиса преобразования: и – скаляры интенсивности, – преобразование в пространстве – смещение, отражение и т.п… Близкой аналогией являются растровые и векторные форматы изображений: если в растровых форматах предполагается наличие одного аппроксимирующего базиса и исследуется его реакция на дискретное изображение, то в векторных форматах изображение синтезируется из системы уравнений. По аналогии, большинство индустриальных форматов сжатия звуковых данных исследуют реакцию аппроксимирующего базиса на входные звуковые данные и при декодировании восстанавливают звуковые данные по реакции из принципа обратимости аппроксимирующего базиса с конечной импульсной характеристикой. В тоже время, как фрактальный аппроксимирующий базис является рекурсивным с бесконечной импульсной характеристикой, синтезирующий результирующее фрактальное множество. Это важное отличие – коэффициенты , , определяют уравнения PIFS. В результате, возможно выбирать размер базиса и синтезировать больше выборок звукового потока в единицу времени чем было в оригинальном звуковом потоке. Подобный результат можно наблюдать при масштабировании векторных форматов изображений. Данное свойство реализовано в плагине для Winamp.






  4. Расширение динамического диапазона. Это логичное продолжение свойства увеличения частоты декодированного звукового потока – при увеличении разрядности потока с 16 бит до 32 бит новые выборки звукового потока будут синтезированы в расширенном диапазоне.




  5. Недетерминированное декодирование. Система PIFS предполагает множество фрактальных преобразований устанавливающих локальные подобия. Исходя из ранее рассмотренных выражений можно сделать вывод, что каждое из множества фрактальных преобразований может быть выполнено независимо, но возникает вопрос – в каком порядке их следует выполнять? Логично выполнять в порядке, в котором был проведён фрактальный анализ, но данное заключение ошибочно – каждое фрактальное преобразование эквивалентно любому другому из множества. Данная идея выражена в реализации выбора очередного фрактального преобразования генератором случайных чисел. Для большинства индустриальных форматов обратимость алгоритмов сжатия является главным требованием, но фрактальные преобразования избавлены от подобного условия.






Интерпретация



Многие математические концепции имеют физические интерпретации. К примеру –  и окружность круга или натуральный логарифм и спиральная раковина моллюска. Часто указывают на связь фрактальных множеств с ростом кристалов или деревьев. Однако я бы хотел бы представить мою собственную интерпретацию фрактальных преобразований.



Я предлагаю рассмотреть базовое выражение фрактального преобразования PIFS:





Данное выражение можно представить в виде следующей схемы:





Учитывая тот факт, что указанное выражение описывает операции с векторами, рассмотрим схему операций над каждым элементом вектора:





Я полагаю что многие читатели увидят схожесть данной схемы со схемой искусственного нейрона:





преобразования и можно рассматривать как функцию сложения по входу, – чувствительность искусственного нейрона по входу, – уровень смещения — возбуждения искусственного нейрона. Внимательный читатель может указать, что чувствительность искусственного нейрона определяется для каждого входа, в то время как определяется как скаляр для всех входов. Также читатель укажет на необходимость на выходе функции для определения состояния искусственного нейрона в терминах Бинарной (Булевой) логики: активен или неактивен. Но являются ли такие требования важными? Допустимо ли, что бы чувствительность искусственного нейрона для всех входов была одинакова? Да, существуют алгоритмы обучения искусственных нейронных сетей с подобным правилом. Допустимо ли не бинарное значение на выходе искусственного нейрона? В начале развития теории искусственных нейронных сетей, когда схемы строились на транзисторах, конденсаторах и резисторах, и от них требовалось решать несложные задачи из области распознавания – к примеру распознавание почтовых индексов на почтовых конвертах и открытках с помощью перцептрона. Но с развитием нечёткой логики и открытием преимуществ «нечётких решений» (soft decisions) над «чёткими решениями» (hard decisions) необходимость подобной функции можно поставит под сомнение.



Что же получиться, если взглянуть на фрактальные преобразования с точки зрения теории искусственных нейронных сетей? Каждые элемент вектора может быть рассмотрен как один искусственный нейрон. В этом случае векторе может быть рассмотрен как слой искусственных нейронов с общими свойствами. Однако, таких «слоёв» может быть несколько тысяч для небольшого изображения. Преобразование на плоскости может быть интерпретировано как трассировка связей между искусственными нейронами. Искусственная нейронная сеть с трассировкой связей–топологии между слоями искусственных нейронов для каждой индивидуальной задачи – звучит весьма необычно, не так ли? Какими особенностями могут могут обладать подобные искусственные нейронные сети:




  1. Рекурсивность – результат работы искусственной нейронной сети становится входными данными для неё самой до установления равновесного состояния – называемого для фрактальных преобразований «аттрактором».




  2. Спиральная топология – условие локального самоподобия.








  3. Случайный выбор последовательности выполнения преобразований — слоёв.




  4. Предпрослушивание – возможность установки исходного уровня искусственной нейронной сети из реального источника: изображение или звук низкого качества.




  5. Разгон – простое масштабирование существующей искусственной нейронной сети путём добавления или удаления искусственных нейронов из каждого слоя без необходимости пересчёта конфигурации искусственной нейронной сети. Это позволяет создавать более детальное состояние сети с генерацией новых деталей.




Как можно назвать подобную искусственную нейронную сеть – рекурсивная, масштабируемая, асинхронная, не детерминированная искусственная нейронная сеть с трассировкой топологии и «мягким» решением. Интересным фактом является то, что уже существует искусственная нейронная сеть с подобными свойствами — искусственная нейронная сеть Хопфилда. Эта искусственная нейронная сеть Хопфилда также рекурсивна, также сходиться к устойчивому состоянию и может быть асинхронна. Однако она включает один слой, не включает трассировку топологии и не формирует «мягкое» решение. Интересно то, что фрактальные преобразования, как и искусственная нейронная сеть Хопфилда обладают общими свойствами фильтрации – восстановления повреждённых образов (конечно, фрактальные преобразования могут работать с реальными изображениями):









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



Заключение



На этом можно закончить данную статью. Надеюсь, высказанные идеи обратят ваше внимание на экзотическую область фрактальных преобразований.
Original source: habrahabr.ru.

https://habrahabr.ru/post/309906/?utm_source=habrahabr&utm_medium=rss&utm_campaign=best

Метки:   Комментарии (0)КомментироватьВ цитатник или сообщество

Следующие 30  »

<алгоритмы - Самое интересное в блогах

Страницы: [1] 2 3 ..
.. 10

LiveInternet.Ru Ссылки: на главную|почта|знакомства|одноклассники|фото|открытки|тесты|чат
О проекте: помощь|контакты|разместить рекламу|версия для pda