AlgART / Java libraries
AlgART и обработка изображений: некоторые элементарные приемы
Даниэль Алиевский, 2007
ОГЛАВЛЕНИЕ
- Введение
- AlgART-массивы
- AlgART-матрицы
- Матрицы и generics: extends или не extends?
- Двумерные изображения: Image2D
- Часть I. Чтение и создание изображения: класс SimplestTutorialDemo
- Конверсия RGB-изображения в полутоновое
- Вычисление средней яркости самым плохим способом: покоординатный цикл
- Вычисление средней яркости чуть менее плохим способом: цикл по массиву
- Вычисление средней яркости: пора вспомнить о пользователе
- Вычисление средней яркости: учимся писать эффективно
- Вычисление средней яркости: библиотечная функция все-таки лучше
- Генерация константного изображения простейшим способом: цикл по массиву
- Генерация константного изображения: произвольная разрядность результата
- Генерация константного изображения: да здравствует лень!
- Генерация константного изображения: ленимся грамотно
- Генерация константного изображения: сколько можно лениться?
- Генерация константного изображения: да будет цвет!
Введение
В этой статье мы рассмотрим некоторые простейшие приемы применения библиотек AlgART
на примере нескольких Java-классов — специально написанных примеров,
анализирующих и обрабатывающих двумерные растровые изображения.
Речь пойдет, главным образом, о пакете net.algart.arrays —
"сердце" библиотек AlgART.
Надо сразу сказать: библиотеки AlgART нетривиальны и обширны. С помощью нескольких примеров вполне овладеть ими нельзя, но можно "почувствовать" и научиться решать элементарные задачи. Исчерпывающую информацию об AlgART API можно найти в комментариях JavaDoc. Создавая библиотеки, я старался делать JavaDoc-комментарии максимально подробными и, по-возможности, снабжал простейшими примерами кода.
Ниже, при разборе примеров, я буду давать нужные пояснения к используемым
классам, интерфейсам и методам.
Однако при чтении рекомендуется иметь "под рукой" полный справочник JavaDoc
и просматривать комментарии к разбираемым методам.
Кроме того, рекомендуется в самом начале просмотреть обзорный комментарий к пакету
net.algart.arrays (package summary).
Перед тем, как двигаться дальше, я вкратце опишу три основных сущности (объекта),
необходимых для работы с изображениями средствами AlgART.
Это линейный массив, матрица и собственно изображение,
представленные соответственно интерфейсами Array, Matrix<? extends Array>
и Image2D.
1. AlgART-массивы
Интерфейс Array — базовый интерфейс библиотеки net.algart.arrays,
описывающий так называемый AlgART-массив.
(Далее под "массивом" мы почти всегда будем пониимать именно AlgART-массив.)
Его можно рассматривать как далеко развитый аналог таких стандартных классов,
как ArrayList и java.nio.Buffer.
В AlgART-массиве можно хранить любые типы данных, причем в отличие от ArrayList
хранение примитивных типов будет эффективным.
Адресация массива 63-битовая: все индексы и размеры имеют тип long.
Соответственно, размеры AlgART-массивов не ограничены лимитом 2 GB.
Даже на 32-разрядных OS библиотека позволяет легко создавать массивы произвольного размера:
для этого автоматически и прозрачно для программиста задействуются дисковые файлы.
Массивы могут хранить произвольные типы элементов (например, строки),
но для обработки изображений нас будут интересовать исключительно массивы,
элементы которых принадлежат к одному из 8 стандартных примитивных типов:
boolean, char, byte, short,
int, long, float и double.
Да, даже long и double:
хоть и маловероятно, что для описания яркости пиксела потребуется такая точность,
однако проще и естественнее универсально отработать все разрядности Java, чем
вводить искусственные ограничения. На деле тип char в данном случае совершенно бесполезен
(в нашей библиотеке он равнозначен short), однако для полноты поддерживается и он.
В иерархии интерфейсов пакета net.algart.arrays такие массивы представлены
следующими подынтерфейсами интерфейса Array:
PArray(обеспечивает доступ к массиву только на чтение) иUpdatablePArray(расширяетPArray, добавляя возможности модификации элементов).
У этих интерфейсов, в свою очередь, есть подынтерфейсы для представления каждого конкретного примитивного типа,
например, BitArray (массив boolean-элементов, т.е. битов),
ByteArray, ShortArray или UpdatableFloatArray, UpdatableCharArray.
Есть даже подынтерфейсы, описывающие группы примитивных типов, например, PFixedArray:
массив элементов любого из 6 примитивных типов boolean, char, byte, short, int, long.
Однако чаще всего мы будем использовать базовые интерфейсы
PArray и UpdatablePArray,
обеспечивающие универсальную обработку данных любого типа и разрядности.
(Есть также и подынтерфейсы, обеспечивающие, подобно ArrayList, изменение длины массива,
но при обработки изображений они требуется редко.)
Про AlgART-массивы можно рассказывать очень долго — почти вся библиотека "выстроена" именно вокруг них.
Однако нам пора переходить к следующему понятию - матрице.
Желающие узнать про основные возможности массивов — читайте package summary к пакету
net.algart.arrays и документацию к конкретным классам и интерфейсам.
2. AlgART-матрицы
Как это и принято, растровые изображения, при использовании библиотек AlgART,
будут представлены матрицами. В отличие от сложной и обширной концепции AlgART-массива,
AlgART-матрица — очень простое понятие, представленное единственным интерфейсом Matrix.
Матрица в библиотеке AlgART всегда хранится в линейном массиве,
строка за строкой (по аналогии с такими языками программирования, как C или Pascal).
Соответственно, чтобы перейти от понятия линейного массива к понятию матрицы, достаточно "добавить"
к массиву набор размерностей вдоль каждой координаты.
В библиотеке AlgART такое "добавление" производится простейшим возможным способом:
композицией. А именно, AlgART-матрица представляет собой всего-навсего пару:
- AlgART-массив (хранящий элементы матрицы);
- набор размеров матрицы.
Соответствующий интерфейс Matrix весьма лаконичен:
он предоставляет доступ к этому массиву и к набору размеров,
а также содержит минимальный набор полезных методов, например,
для вычисления линейного индекса в массиве по индексам в матрице.
Пора заметить: AlgART-матрицы (как и массивы языков C и Паскаль) изначально многомерны.
Для работы с изображениями, конечно, нужны двумерные матрицы.
Однако хорошо написанные алгоритмы обработки матриц
чаще всего не содержат кода, специфического для случая именно двух измерений.
Например, фильтры, сглаживающие изображение, можно без изменений применить
к трехмерным матрицам, описывающим некую физическую среду,
и даже к четырехмерным матрицам, описывающим нечто совсем таинственное.
Возможен и вырожденный случай — одномерные матрицы.
Они могут использоваться, например, когда модуль, обрабатывающий тип Matrix,
нужно применить к обычному линейному массиву.
Размеры матрицы, как и длина линейного массива, представлены типом
long. Не потому, что это реально необходимо
(хотя теоретически можно представить себе потребность в 30-гигабайтной матрице
3x10 000 000 000),
а потому, что так проще: меньше приходится приводить типы.
Наступление эпохи 64-разрядных процессоров, вероятно, очень скоро сделает операции с типом long
такими же быстрыми, как и с типом int;
так зачем же вводить лишние ограничения?
Впрочем, посвеместное применение типа long требует повышенной аккуратности:
будьте бдительны!
Следует помнить, что при сложении, вычитании или умножении размеров или адресов
возможно целочисленное переполнение с получением нелепого результата.
По этой причине, скажем, в классе Arrays,
содержащем библиотеку "полезных" методов, предусмотрена специальная функция longMul
для перемножения long-чисел с проверкой на переполнение.
Применяйте ее! При сложении и вычитании обычно все проще: так, при сложении 2 неотрицательных
чисел типа long однозначным признаком переполнения является отрицательность суммы.
Все размерности матрицы можно получить соответствующими методами
интерфейса Matrix.
Конечно же, контракт интерфейса Matrix
(заявленный в JavaDoc и свято соблюдаемый в реализациях)
гарантирует, что длина AlgART-массива, хранящего элементы матрицы,
всегда равна произведению размерностей.
Линейный индекс любого элемента матрицы в этом массиве вычисляется по формуле ix+iy*dimX+iz*dimX*dimY+...,
где ix, iy, iz, ... — индексы элемента в многомерной матрице,
а dimX, dimY, ... — соответствующие размерности.
Для двумерного случая формула упрощается до ix+iy*dimX.
Имеется метод index, вычисляющий линейный индекс по этой формуле.
3. Матрицы и generics: extends или не extends?
Последнее, что следует сказать про матрицы: интерфейс Matrix обладает
generics-параметром — типом хранимого массива. Так, матрица элементов примитивного типа описывается как
Matrix<? extends PArray>,
а матрица, допускающая изменение элементов, как
Matrix<? extends UpdatablePArray>.
Применение generics, как обычно, позволяет улучшить контроль типов и свести к минимуму
необходимость явных приведений типов.
Тут у читателя, особенно недостаточно владеющего технологией generics, может возникнуть резонный вопрос.
Почему Matrix<? extends PArray>, а не просто Matrix<PArray>?
На первый взгляд кажется, что второй, более очевидный вариант вполне равноценен первому.
Ведь, действительно, с переменной типа Matrix<PArray>
можно делать в точности то же самое, что и с Matrix<? extends PArray>:
а именно, извлекать массив типа PArray.
На самом деле равноценность кажущаяся.
Попробуйте создать список java.util.ArrayList, содержащий несколько матриц.
(На практике такие списки, действительно, частенько необходимы — в алгоритмах,
обрабатывающих сразу серию матриц.)
Вы убедитесь, что
List<Matrix<? extends PArray>> и
List<Matrix<PArray>> —
совершенно разные и несовместимые друг с другом вещи.
Список первого типа нельзя присвоить переменной второго типа (и наоборот).
Список первого типа нельзя передать в метод, аргумент которого объявлен как список второго типа (и наоборот).
В список второго типа нельзя добавить матрицу типа Matrix<? extends PArray>
(правда, можно наоборот).
Это поведение подробно разбирается в хороших учебниках по Java.
Что же предпочесть: вариант с обобщающим "? extends" или более простые "с виду"
Matrix<PArray> и Matrix<UpdatablePArray>?
Представьте себе функцию, которая принимает матрицу на входе, обрабатывает и возвращает другую матрицу на выходе. (Кстати, это типичная ситуация при обработке изображений.) Хотя бы вот эту:
public Matrix<PArray> myFunction(Matrix<PArray> m) {
return m; // что может быть проще
}
Написав такую функцию, вы быстро убедитесь, что не можете применить ее
ни к матрице типа Matrix<UpdatablePArray>, ни к матрице конкретного байтового типа
Matrix<ByteArray>.
Иначе говоря, общее правило должно быть таким:
в качестве аргументов методов всегда лучше использовать конструкцию
Для результатов методов, а также при объявлении переменных ситуация не столь однозначна.
Формально, нет никаких проблем, если метод, например, вернет конкретный
Matrix<UpdatablePArray>:
безусловно, такой результат можно будет использовать повсюду, где "подошел" бы тип
Matrix<? extends UpdatablePArray>.
Однако библиотеки AlgART предпочитают и в этом случае использовать
более общий тип с
Почему? По той же причине, по которой в языке Java принято максимально строго
контролировать типы — для минимизации будущих ошибок.
Если бы метод какого-нибудь полезного интерфейса (вроде Image2D,
к которому мы сейчас перейдем) вернул результат конкретный типа
Matrix<UpdatablePArray> или
Matrix<PArray>, возник бы соблазн присвоить
его переменной такого же типа. Далее сей соблазн мог бы "распространиться":
если большинство переменных вашего класса или пакета имеют тип Matrix<PArray>,
почему бы не объявить где-нибудь метод с аргументом такого типа?
Более того, по мере развития вашего кода могут появиться списки матриц,
скажем, List<Matrix<PArray>>.
Все будет замечательно до тех пор, пока не понадобится применить ваши классы
к матрице с массивом другого типа.
Вероятнее всего, это окажется передача в метод, принимающий аргумент
Matrix<PArray>, матрицы Matrix<UpdatablePArray>.
Или, еще хуже, попытка построить список из матриц более частного типа,
скажем, занести в список List<Matrix<PArray>>
конкретную Matrix<BitArray>.
И в этот момент весь ваш код придется переписывать —
переводить его на "правильные рельсы" Matrix<? extends PArray>.
Автор, между прочим, в процессе разработки библиотек пару раз "наступал" на эти грабли.
Гораздо лучше ограничить себя с самого начала и всегда применять конструкцию "? extends". Что и сделано в библиотеках AlgART.
Подробнее про матрицы читайте JavaDoc-документацию к интерфейсу Matrix.
4. Двумерные изображения: Image2D
Вообще говоря, абстракции матрицы уже достаточно, чтобы создавать практически любые алгоритмы обработки изображений.
(Обращаю внимание: я говорю не о разработке графических пакетов типа Photoshop, где работа с цветом исключительно важна, а о математических алгоритмах, предназначенных для обработки и анализа изображений. Именно таким алгоритмам посвящена данная статья. Алгоритмы, как правило, работают именно с матрицами.)
Действительно, полутоновое изображение (наиболее популярный тип для задач анализа и распознавания)
всегда можно представить числовой матрицей, содержащей яркости пикселов.
Цветное изображение очевидным образом представляется несколькими "параллельными" матрицами одинакового размера,
содержащими цветовые составляющие для каждого пиксела.
Так, RGB-изображение можно представить как систему из 3 матриц,
содержащих red-, green- и blue-компоненты.
Прочие цветовые модели — HSL, HSV, ARGB, CMYK, YUV, XYZ, ... —
также сводятся к системе матриц, как правило, 3 или 4.
Соответственно, для представления любого изображения можно всегда использовать либо переменную типа
Matrix<? extends PArray> (в случае полутонового изображения),
либо (в зависимости от алгоритма) 3 или 4 такие переменные,
либо очень простой класс с 3 или 4 полями типа Matrix<? extends PArray>,
созданный специально для группы алгоритмов, нетривиально обрабатывающих цветность
(например, конвертирующих HLS в RGB).
На самом деле, в рамках пакета net.algart.arrays и его подпакетов так оно и есть.
Все базовые алгоритмы, рассчитанные на работу с изображениями и реализованные в этом пакете и подпакетах,
как правило, работают с единственной матрицей, представляющей полутоновое изображение.
При желании, эти методы можно вызвать для любой выбранной цветовой
компоненты или для всех цветовых компонент по очереди.
Скажем, простейшее сглаживание цветной RGB-картинки (удаление мелкого аддитивного шума)
сводится к применению соответствующего библиотечного метода по очереди к трем матрицам,
представляющим цветовые компоненты.
Иначе говоря, я вынужден огорчить пользователей, привыкших к пакетам типа java.awt или JAI. В библиотеках AlgART отсутствует поддержка цветности. Такую цену пришлось заплатить за алгоритмическую мощь и универсальность библиотек применительно к массивам и матрицам. По-настоящему качественная, современная реализация понятия цветности сделала бы сроки выхода библиотек AlgART абсолютно неприемлемыми. Надо сказать, что изображения и не являются основной и единственной областью применения библиотек. AlgART-массивы и матрицы с тем же успехом могут использоваться практически в любых численных расчетах: например, при решении систем линейных уравнений или физическом моделировании.
Однако, если все же говорить о применении библиотек AlgART к обработке изображений,
то совсем игнорировать цветность было бы неправильно.
Большая часть изображений, встречающихся в реальной жизни — полученные,
например, со сканера, фотоаппарата или видеокамеры — как правило, цветные.
Было бы неудобно, если бы вообще отсутствовал какой-либо стандартный класс,
позволяющий хранить такое изображение и передавать его универсальным алгоритмам,
рассчитанным на обработку AlgART-матриц (например, фильтрующим помехи или выделяющим контура частиц).
Такой класс — точнее, интерфейс — действительно существует.
Это интерфейс Image2D,
расположенный в отдельном пакете com.simagis.images.color
и описывающий либо полутовое, либо цветное двумерное изображение.
Данный интерфейс расположен вне пакета net.algart:
формально он не входит в состав библиотек AlgART.
Иначе говоря, автор библиотек AlgART старательно открещивается от всяких упреков
по поводу этого интерфейса. Если он покажется вам убогим, почему бы вам не написать свой?
Интерфейс Image2D практически тривиален.
Image2D — это просто либо одна AlgART-матрица
Matrix<? extends PArray>
(содержащая яркости пикселов полутонового изображения),
либо три таких матрицы (R, G и B-компоненты) с идентичными размерами, объединенные в одном объекте.
Имеются методы извлечения матриц
Никакие другие модели, кроме RGB, не поддерживаются.
Единственная цель существования интерфейса —
обеспечить простой способ хранения изображений
и применения к ним алгоритмов, умеющих обрабатывать матрицы.
Для RGB-картинок такое применение практически тривиально:
как правило, это либо простой покомпонентый вызов метода,
рассчитанного на тип Matrix<? extends PArray>,
для каждой из 3 матриц R, G, B, либо — что более типично для задач анализа —
получение матрицы яркостей пикселов по стандартной формуле 0.299r+0.587g+0.114b
и применение метода уже к ней.
Такую матрицу яркостей, в случае цветного изображения,
автоматически возвращает метод
Интерфейса Image2D достаточно для большинства алгоритмов обработки и анализа,
включая всевозможную фильтрацию, выделение границ, структуры, анализа частиц и других геометрических объектов.
Алгоритмы, которые нуждаются в специальном анализе других типов цветности,
например, HLS, оперируют другими классами, обычно аналогичными Image2D.
Далее в этой статье мы будем рассмотривать примеры алгоритмов,
обрабатывающих объекты типа Image2D.
Часть I. Чтение и создание изображения: класс SimplestTutorialDemo
Далее мы рассмотрим — с душераздирающей подробностью —
маленький и очень простой класс SimplestTutorialDemo.
Это специально написанный учебный класс, состоящий из static-методов
и решающий настолько тривиальные задачи, насколько я смог придумать.
Зато он решает их множеством способов, начиная с самых простых и кончая самыми правильными.
В процессе совершенствования способа решения вы сможете шаг за шагом
ознакомиться с фундаментальными концепциями библиотек AlgART.
Если есть возможность, рекомендую открыть исходник этого класса в какой-нибудь оболочке, позволяющей легко получать JavaDoc-комментарии к любому вызываемому библиотечному методу: изучение этих комментариев может помочь пониманию. Исходный файл класса доступен здесь: SimplestTutorialDemo.java.
Прежде чем начинать разбор класса, надо сделать одно замечание.
Все методы этого класса (и прочих учебных классов, рассматриваемых в этой статье),
используют специальную аннотацию @Name, импортируемую из пакета
com.simagis.plugin3.
Об этом следует упомянуть, главным образом, для того, чтобы вы не обращали на нее внимания.
Никакого влияния на исполнение кода она не оказывает,
и никакого значения для понимания используемых приемов она не имеет.
На самом деле эта аннотация нужна для единственной цели:
приписать параметрам методов символьные имена,
которые, в отличие от обычных имен аргументов методов, сохраняются в скомпилированном байт-коде
и доступны для внешнего приложения, вызывающего этот класс.
Благодаря информации об именах параметров такое приложение может упростить запуск методов,
предоставляя визуальный интерфейс для настройки конкретных параметров.
Примером такого приложения является :
система обработки изображений, ради которой, в значительной степени, создавались обсуждаемые библиотеки.
Эта система позволяет также создавать и визуализировать изображения типа Image2D,
что, как легко видеть, довольно полезно, если вы хотите проверить рассматриваемые методы на практике.
1. Конверсия RGB-изображения в полутоновое
Не думайте, что я на самом деле собираюсь описывать, как решается такая задача.
Пока рано. Речь идет всего лишь о вызове готового метода, предусмотренного
в интерфейсе Image2D.
Итак, вот наш первый пример:
public static Image2D toGrayscale(Context context, @Name("image")Image2D image) {
ImageContext imageContext = context.as(ImageContext.class);
Matrix<? extends PArray> m = image.i();
Image2D result = imageContext.newGrayscaleImage2D(imageContext, m);
return result;
}
Уже декларация метода требует от нас остановиться и внимательно рассмотреть его первый параметр.
Что это за Context?
Имею честь представить концепцию контекста, реализованную в библиотечном пакете
net.algart.contexts.
Расскажу о контекстах в двух словах. Как обычно, желающие могут прочитать обстоятельные
JavaDoc-комментарии в документации к пакету.
Если очень коротко, контекст алгоритма (или, в общем случае, контекст произвольных вычислений или других операций) — это информация, которая не настолько важна, чтобы служить входными данными или параметрами алгоритма, но которая в то же время способна оказать влияние на его работу.
Наверно, самый очевидный пример контекста — сама Java-машина
(или операционная система в языках типа C/C++). Именно она отвечает за
исполнение любого оператора new, отводящего блок памяти,
а без такого оператора затруднительно написать даже самый простейший алгоритм.
Внутренняя информация JVM, прежде всего, доступный объем памяти в "куче",
безусловно, влияет на работу любого алгоритма, хотя формально не содержится в его входных параметрах.
Действительно, при одном количестве памяти алгоритм выдаст OutOfMemoryError,
а при другом — сработает нормально.
Это означает, что в принципе можно считать JVM неявным параметром,
передаваемым каждому алгоритму. (Кстати, неявное становится явным,
когда мы пишем native-метод Java-класса на языке C:
каждому native-методу передается указатель на среду исполнения Java-машины.)
JVM и ее память — контекст глобальный, общий для всего Java-приложения.
Такой контекст не надо как-то специально передавать в библиотечные классы,
решающие те или иные задачи.
Другим примером глобального контекста может служить файловая система:
с помощью системного свойства (System.getProperty)
алгоритм, требующий непомерных объемов временных данных,
может узнать каталог временных файлов операционной системы
и сохранить наиболее "тяжелые" временные объекты на диске.
Еще один пример — логгеры java.util.logging:
они настраиваются глобально для всего приложения и при этом иногда используются внутри алгоритмов.
Если вы прочитали package summary к пакету net.algart.arrays,
вы могли обратить внимание, что эта библиотека использует немало контекстной информации подобного рода,
передаваемой через системные свойства (system properties).
К сожалению, не всякую информацию, полезную для исполнения алгоритма, можно передать "глобально", настраивая те или иные системные свойства, глобальные константы и т.п. Скажем, рассмотрим типичную проблему: показать пользователю ход исполнения алгоритма. Ведь не все алгоритмы заканчивают работу в долю секунды. Что, если решаемая задача требует нескольких минут или даже часов? Еще хуже, если требуемое время сильно и сложным образом зависит от параметров. В этом случае, когда пользователь выбрал неудачные параметры алгоритма, надо дать ему понять, что задача будет решаться не меньше часа и неплохо бы ее прервать (или пойти обедать).
Как "научить" абстрактный математический алгоритм, например,
решающий систему уравнений или фильтрующий изображение,
показывать проценты своего исполнения?
Глобальные настройки приложения (вроде каталога временных файлов) здесь не спасают:
у приложения может быть несколько окон, и в каждом может параллельно исполняться свой алгоритм,
требующий отдельного визуального элемента для вывода процентов.
Можно, конечно, передать функции (или классу) специальный параметр, скажем, JProgressBar,
если вам не жаль уродовать изящную архитектуру чисто алгоритмического модуля
столь "приземленными" деталями.
Но что делать, если, кроме процента выполнения, понадобится что-то еще?
Например, специальный слушатель, реагирующий на кнопку Stop и останавливающий расчеты?
(Стандартный вызов Thread.interrupt, увы, в текущей версии Java несовместим
с библиотекой net.algart.arrays: об этом можно прочесть в JavaDoc.)
Возникает ситуация, напоминающая причины, по которым в современные языки добавили механизм исключений.
А именно: чтобы предусмотреть передачу алгоритму всех возможных полезных ему вещей,
нужно загромоздить простой и ясный API вызова алгоритма передачей всех этих вещей.
Интерфейс Context, передаваемый первым параметром в наш самый первый метод —
это в меру изящное (будем надеяться) решение, предлагаемое библиотеками AlgART.
Сам по себе интерфейс Context почти тривиален
и не позволяет алгоритму узнать ничего "полезного".
Основной метод этого интерфейса выглядит так:
public <T extends Context> T as(Class<T> contextClass);
Этот метод — своего рода "шлюз", позволяющий алгоритму узнать практически все, что угодно.
Идея в том, что метод as возвращает некий
частный контекст — экземпляр некоторого наследника Context.
А вот этот наследник уже может иметь практически полезные методы, необходимые алгоритму.
Предполагается, что вызывающий код
(в нашем случае приложение, вызывающее методы SimplestTutorialDemo)
передаст такую реализацию Context, которая сможет вернуть все необходимые
алгоритму частные контексты. Создаются такие реализации достаточно просто.
Более того, набор поддерживаемых контекстов может загружаться в виде сервис-провайдеров
и определяться уже после компиляции конечного приложения.
Желающие могут посмотреть JavaDoc к пакету net.algart.contexts
или исходники законченных примеров, такие, как SimpleImageContext.
Первая же строчка вызываемого метода выполняет операцию извлечения частного контекста.
Это вызов метода второго варианта as:
ImageContext imageContext = context.as(ImageContext.class);
Методу as передается класс ImageContext.class
— конкретный частный контекст, нужный нашему алгоритму.
Единственная его задача — создание экземпляра Image2D по имеющейся AlgART-матрице
или набору AlgART-матриц. Что и делается в конце нашего метода toGrayscale:
Image2D result = imageContext.newGrayscaleImage2D(imageContext, m);
Что произойдет, если реализация Context, переданная приложением в наш метод,
"не умеет" возвращать экземпляры ImageContext?
В этой ситуации будет возбуждено необъявляемое исключение UnsupportedContextException.
Если вернуться к аналогии с виртуальной машиной (в качестве "неявного" контекста),
эту ошибку можно сравнить с ситуацией, когда мы исполняем Java-приложение на виртуальной
машине, не поддерживающей нужный набор библиотечных классов (скажем,
на если мы запускаем программу на устаревшей версии JVM,
или если мы пытаемся выполнить J2EE-программу на виртуальной машине J2SE).
Правильно документированный класс должен декларировать
в JavaDoc-комментариях полный набор необходимых ему контекстов —
так же, как обычно декларируется необходимая классу версия Java.
(Наш учебный класс, ради простоты, вообще не снабжен документацией.)
Большинство классов требуют, как минимум, поддержки стандартых контекстов,
реализуемых стандартным классом DefaultContext (см. JavaDoc).
ImageContext — типичный пример частного контекста-фабрики.
Мы и далее будем сталкиваться с ситуациями, когда для генерации экземпляров абстрактных интерфейсов
привлекаются частные контексты-фабрики.
(Сравните: первым рассмотренным выше примером контекста была JVM, реализующая оператор new,
т.е. базовый оператор-фабрику языка Java.)
Такой подход значительно повышает гибкость системы.
Приложение, вызывающее алгоритмический метод, который должен вернуть некую сущность
— реализацию интерфейса,
может передать через контекст такую фабрику, которая будет создавать экземпляры наиболее
удобного для приложения типа.
Так, реализация ImageContext, передаваемая системой ,
создает такие Image2D, которые изначально "умеют" храниться в ячейках таблиц SIMAGIS.
Это значительно упрощает интеграцию в систему классов вроде нашего
SimplestTutorialDemo (в терминах SIMAGIS они называются "плагинами").
Фабрики — далеко не единственный пример контекстной информации.
В дальнейших методах мы увидим, как из параметра типа Context,
как "чертики из коробочки", "выскакивают" самые различные частные контексты,
сообщающие алгоритму необходимые дополнительные сведения или позволяющие сделать
другие полезные вещи.
Возможно, вы обратили внимание на первый параметр метода newGrayscaleImage2D.
Это... вновь контекст! Казалось бы, зачем? Ведь внутри метода newGrayscaleImage2D
мы уже располагаем контекстом, а именно, imageContext, который можно извлечь
при помощи ключевого слова this.
У такого поведения есть глубинные причины, связанные с применением так называемых контекстов подзадач,
генерируемых с помощью специального класса SubtaskContext —
об этом будет идти речь далее в разделе "Генерация константного изображения".
Из JavaDoc-комментариев к этому классу вы можете узнать, что, оказывается, ссылка this
в методах контекстов не всегда является ссылкой на тот объект, чей метод мы вызываем.
В частности, если imageContext был создан методом as у контекста подазачи
(SubtaskContext), то внутри метода newGrayscaleImage2D ссылка this,
как это ни кажется странным, будет указывать не на контекст подзадачи, а на исходный контекст, умеющий
создавать изображения. Во избежание подобных проблем, ссылка на контекст всегда передается явно в качестве
первого параметра метода — и это правильная, хорошая и рекомендуемая практика при работе с контекстами.
Собственно, мы рассмотрели почти весь метод toGrayscale.
Он ведь абсолютно тривиален. Все, что здесь происходит, помимо
получения контекста и возврата результата, это выделение яркостной компоненты изображения:
Matrix<? extends PArray> m = image.i();
Если входное изображение image было цветое (RGB),
то матрица m будет содержать
яркости каждого пиксела, рассчитанные по формуле 0.299r+0.587g+0.114b.
Если полутоновое, то m будет содержать непосредственно значения интенсивности пикселов.
Как в действительноти это реализовано, мы пока рассматривать не будем:
решение подобных задач будет темой одной из следующих глав.
После получения m, метод контекста newGrayscaleImage2D превращает
полученную матрицу обратно в экземпляр Image2D, уже заведомо полутоновой.
Он и возвращается методом.
2. Вычисление средней яркости самым плохим способом: покоординатный цикл
Надо полагать, читатель уже изрядно устал. Уже столько всего рассказано, а мы ведь до сих пор не сделали ровно ничего интересного. Мы даже пока не пробовали решить столь простую задачу, как чтение численного значения яркости конкретного пиксела.
Что ж, вот наш следующий метод:
public static double meanOf_1(Context context, @Name("image")Image2D image) {
Matrix<? extends PArray> m = image.i();
PArray a = m.array();
long dimX = m.dimX();
long dimY = m.dimY();
double sum = 0.0;
for (long i = 0; i < dimY; i++) {
for (long j = 0; j < dimX; j++) {
long index = m.index(j, i);
sum += a.getDouble(index);
}
}
return sum / (dimX * dimY);
}
Вычисление средней яркости всех пикселов — наверно, самая простая возможная задача анализа изображения. Попробуем разобрать приведенный выше пример решения этой задачи: наверно, самый очевидный из всех возможных (правда — забегая вперед — и чуть ли не самый худший).
Как и раньше, в качестве первого параметра здесь передается контекст.
Однако он никак не используется. На самом деле это редчайшее исключение.
В реальных, не учебных методах контекст нужен почти всегда.
Параметр Context в декларации метода сохранен "на всякий случай".
Когда вы сами будете писать практические методы, если даже вам покажется,
что контекст не нужен, на всякий случай всегда включайте его в список параметров.
Вполне возможно, что по мере будущего развития и усложнения метода контекст все же понадобится,
а изменить декларацию будет уже нельзя по соображениям совместимости.
Кстати, заметим: по негласной традиции, контекст всегда должен передаваться самым первым параметром.
Первый оператор метода нам уже знаком: это получение матрицы интенсивностей m.
В случае цветного изображения, это фактически означает автоматическую конверсию в
"ближайшее по яркости" полутоновое изображение.
Очень многие промышленные алгоритмы анализа и распознавания изображений
начинаются с такого оператора: достаточно редко цветовая информация настолько важна,
что реально помогает проанализировать (например, измерить) изображенные предметы.
Следующим оператором мы "спускаемся" еще на один шаг по иерархии вложенных объектов:
получаем из матрицы m линейный AlgART-массив a, хранящий
(строка за строкой) все элементы матрицы. Напомню, что AlgART-матрица
— всего-навсего пара "AlgART-массив" + "набор размерностей".
Поэтому метод извлечения массива, dimX и dimY.
Посмотрим на следующий далее цикл.
Для каждой пары координат i и j вычисляется индекс в линейном
массиве a, и затем по индексу из массива извлекается вещественное числа,
которое прибавляется к общей сумме sum:
long index = m.index(j, i);
sum += a.getDouble(index);
(Напоминаю: все индексы и размеры в AlgART-массивах и AlgART-матрицах 63-разрядные,
поэтому используется тип long.)
На что здесь надо обратить внимание? Прежде всего, на порядок аргументов метода index.
Первым идет индекс по x-координате (т.е. j), вторым — по y (т.е. i).
Если бы мы имели дело с трехмерной матрицей, следующим аргументом был бы индекс по z.
Это необходимо запомнить.
Если бы матрица хранилась в двумерном Java-массиве m[][],
то, вероятно, порядок употребления индексов был бы обратный: m[i][j]
(хотя, разумеется, это вопрос вкуса программиста).
Далее, обратите внимание на число аргументов метода index.
Если вы заглянете в интерфейс Matrix, вы увидите, что это —
метод с переменным числом параметров (vararg).
Что произойдет, если вы случайно укажете недостаточное или слишком большое количество аргументов?
Согласно JavaDoc-комментариям к Matrix, методы этого интерфейса,
в том числе index, ведут себя так, как будто число измерений матрицы бесконечно.
Но при этом все размеры матрицы "за пределами" истинного числа размерностей считаются равными 1,
а все недостающие аргументы метода index подразумеваются равными 0.
Так, наша двумерная матрица "очень похожа" на трехмерную матрицу
dimX x dimY x 1 и на четырехмерную матрицу
dimX x dimY x 1 x 1.
Мы имеем право вместо IndexOutOfBoundsException:
у нашей матрицы если только одна, нулевая "плоскость" в трехмерном пространстве
и только одна, нулевая "гиперплоскость" в четырехмерном.
Перейдем теперь к следующему оператору: Matrix<? extends PArray> говорит о том,
что мы имеем дело с любым из 8 примитивных типов Java.
Интерфейс PArray — общий предок всех частных интерфейсов,
описывающих массивы конкретных примитивных типов. В тех интерфейсах,
например, ByteArray, имеются специальные методы для получения значений нужной разрядности:
getByte для ByteArray, getBit (результат boolean)
для BitArray, и т.д.
Но уже в самом общем интерфейсе PArray объявлен метод getDouble,
позволяющий прочитать числовое значение любой разрядности с автоматической
конверсией к типу double.
Правила конверсии четко специфицированы в JavaDoc.
Обратите на них внимание: их надо запомнить!
Наиболее важно для нас следующее:
по соглашению библиотеки AlgART, типы данных byte и short
везде, где возможно, интерпретируются как беззнаковые.
Иначе говоря, cчитается, что каждый элемент AlgART-массива ByteArray
содержит целое число от 0 до 28−1=255,
а каждый элемент AlgART-массива ShortArray
содержит целое число от 0 до 216−1=65535.
(Однако, типы int и long считаются знаковыми:
изменяющимися от -231 до 231−1 и от -263 до 263−1
соответственно.)
В частности, для элемента байтового массива,
содержащего двоичное число 11111111, метод getDouble возвращает 255
(а не −1, как можно было бы подумать).
Да, это противоречит традиции языка Java, в котором все
целочисленные типы данных всегда знаковые.
Но это намного удобнее почти во всех алгоритмах,
имеющих дело с массивами 8- или 16-битовых целых чисел.
В частности, это удобно при работе с изображениями.
Ведь яркость пиксела описывается неотрицательным числом.
При разрядности int или long вполне можно "пожертвовать"
последним 32-м (64-м) битом и представлять пикселы неотрицательными значениями
Java-типов int и long. И действительно,
для реальных изображений при такой разрядности наш объект Image2D всегда
будет содержать 0 в старшем (знаковом) бите каждого элемента.
Однако 8- и даже 16-битовая точность не настолько велика, чтобы игнорировать один бит.
Здесь гораздо удобнее использовать для представления неотрицательной яркости все 8 или 16 битов.
Разумеется, при необходимости (и желании) вам ничто не мешает проинтерпретировать 8- и 16-битовые элементы AlgART-массивов и матриц в классическом (для Java) смысле, как знаковые величины. Это потребовало бы некоторого усложения кода: проверки, что мы имеем дело с конкретным частным подынтерфейсом, и соответствующего приведения типа. Например:
long index = m.index(j, i);
double value;
if (a instanceof ByteArray) {
value = (byte)((ByteArray)a).getByte();
// getByte() возвращает тип int, а не byte, причем
// этот int-результат неотрицательный (0..255),
// в соответствии с соглашениями библиотеки.
// Поэтому необходим дополнительный оператор
// приведения типа: (byte)(...)
} else if (a instanceof ShortArray) {
value = (short)((ShortArray)a).getShort();
// getShort(), аналогично, возвращает неотрицательный
// int (0..65535), поэтому необходим оператор
// приведения типа: (short)(...)
} else {
value = a.getDouble(index);
}
sum += value;
На практике, однако, такая необходимость вряд ли будет встречаться часто.
На этом мы заканчиваем разбор метода. Последний его оператор вполне тривиален: конечно, средняя яркость есть сумма всех элементов, деленная на их количество, т.е. на dimX * dimY.
3. Вычисление средней яркости чуть менее плохим способом: цикл по массиву
Пора заняться усовершенствованием нашего алгоритма. На самом деле, наш цикл, который смотрелся бы вполне уместно при обработке классического двумерного массива Java, при обработке AlgART-матрицы — одно из наихудших решений в плане эффективности. Рассмотренный только что пример полезен с точки зрения обучения, так как знакомит с некоторыми важными концепциями доступа к элементам. Но на практике так писать не следует почти никогда — разве что если быстродействие вас совершенно не интересует.
Самый очевидный недостаток цикла "бросается в глаза", даже если ничего не знать об архитектуре AlgART-массивов. Раз все равно все элементы хранятся в линейном массиве, зачем делать вложенные циклы по x и по y? Ведь их можно просуммировать одним циклом по линейному массиву.
Исправим это:
public static double meanOf_2(Context context, @Name("image")Image2D image) {
Matrix<? extends PArray> m = image.i();
PArray a = m.array();
long length = a.length();
double sum = 0.0;
for (long k = 0; k < length; k++) {
sum += a.getDouble(k);
}
return sum / length;
}
Здесь мы вообще игнорируем размерности матрицы: сразу извлекаем исходный AlgART-массив
и работаем исключительно с ним. Как результат, исчез вызов метода index.
Хотя метод index кажется тривиальным, он все-таки тратил определенное время.
Не только на вычисление индекса (j+dimX*i), но и на проверку аргументов:
как всякий добропорядочный метод, он проверяет, что переданные покоординатные индексы корректны
(не отрицательны и меньше соответствующих размеров матрицы).
В итоге, на моем компьютере новая версия обрабатывает большую 8-битовую картинку
примерно на 30% быстрее.
Заметим, что метод index в действительности используется весьма редко,
особенно во внутренних циклах алгоритма.
Чаще всего элементы "перебираются" последовательно, и на каждой итерации достаточно
просто перейти к следующему элементу линейного AlgART-массива.
И даже когда нужен более сложный порядок анализа элементов,
обычно эффективнее работать непосредственно с индексом в линейном массиве:
например, прибавлять к нему заранее заготовленные смещения, соответствующие тем или иным
сдвигам координтат в матрице.
Дополнительным преимуществом нового алгоритма оказалась нечувствительность к числу измерений. Без каких-либо изменений такой цикл способен вычислить среднее значение и 3-мерной матрицы, и 1-мерного массива. Как уже говорилось, такая универсальность присуща очень многим профессиональным алгоритмам обработки AlgART-матриц.
4. Вычисление средней яркости: пора вспомнить о пользователе
Наш метод решает слишком простую задачу, чтобы выполняться долго. Тем не менее, последняя его реализация еще достаточно плоха и поэтому способна продемонстрировать проблемы, возникающие у сложных "долгоиграющих" алгоритмов. По крайней мере, если передать нашему методу матрицу, сравнимую по размерам с оперативной памятью компьютера, алгоритм "задумается" весьма ощутимо. Может быть, на несколько секунд или даже минут.
Что может предпринять пользователь в это время? Да ничего. Или сидеть и ждать, или переключиться на другую задачу. Наш цикл не содержит никаких операторов, которые позволили бы его прервать или хотя бы показать, какой процент работы уже готов.
Перед тем как переходить к дальнейшей оптимизации метода, вспомним про контексты и ликвидируем указанные недостатки. А именно, "научим" алгоритм прерываться и показывать проценты исполнения. На самом деле, правила хорошего тона требуют, чтобы такие вещи умел практически любой профессиональый алгоритм — за исключением гарантированно быстрых методов, вроде решения одного квадратного уравнения или вставки одного элемента в сбалансированное дерево.
Итак:
public static double meanOf_3(Context context, @Name("image")Image2D image) {
ProgressUpdater pu = context.as(ProgressUpdater.class);
InterruptionContext ic = context.as(InterruptionContext.class);
Matrix<? extends PArray> m = image.i();
PArray a = m.array();
long length = a.length();
double sum = 0.0;
for (long k = 0; k < length; k++) {
sum += a.getDouble(k);
if ((k & 0xFFFF) == 0) { // equivalent to k%65536==0
ic.checkInterruption();
pu.updateProgress((double)(k + 1) / (double)length, false);
}
}
return sum / length;
}
Здесь мы получаем два частных контекста:
контекст прогресса ProgressUpdater и
контекст прерываний InterruptionContext,
и используем их, чтобы решить две задачи:
визуализацию хода исполнения и возможность прерывания алгоритма.
Если мы вызовем метод meanOf_3 из "доброжелательной" системы,
такой, как ,
предоставляющей "умные" реализации всех стандартных и многих нестандартных частных контекстов,
то система сможет "красиво" показать исполнение нашего цикла в виде — например,
"полоски прогресса" (JProgressBar) — и остановить наш цикл при помощи соответствующей кнопки
в пользовательском интерфейсе.
Но что делать, если же мы захотим вызвать этот метод из более простой программы, в которой не предусмотрены средства для визуализации хода исполнения и прерывания работы?
В этом случае к нашим услугам "контекст-заглушка",
возвращаемый методом DefaultContext,
реализующего сразу несколько стандартных, общеупотребительных частных контекстов,
которые предусмотрены в пакете net.algart.contexts и могут понадобиться
практически в любой задаче.
Нужные нам сейчас ProgressUpdater и InterruptionContext
относятся к их числу и поддерживаются объектом ProgressUpdater не покажет никаких процентов исполнения,
а частный контекст InterruptionContext не поможет остановить вычисления.
Однако наш метод, по крайней мере, не выдаст исключения и решит свою задачу.
(Впрочем, на самом деле контекст-заглушка не совсем тривиален.
Если он используется для получения стандартных контекстов, реализуемых классом
DefaultContext, то, и правда, возвращаемые контексты не делают ничего "умного".
Но если мы потребуем от контекста-заглушки вернуть нестандартный контекст,
такой как использованный в первом нашем примере ImageContext,
то контекст-заглушка предпримет дополнительную попытку обслужить запрос,
обратившись к набору так называемых сервис-провайдеров.
С помощью этой техники внешнее приложение способно обеспечить "заглушками"
даже нестандартные контексты, возможно, применяемые в библиотечных модулях.
Подробнее см. JavaDoc-комментарии к классам AbstractContext и
DefaultContext.)
Теперь рассмотрим, как ProgressUpdater и
InterruptionContext используются в алгоритме.
В нашем методе мы время от времени,
а именно, раз в 65536 итераций, обращаемся к методам этих интерфейсов:
if ((k & 0xFFFF) == 0) { // equivalent to k%65536==0
ic.checkInterruption();
pu.updateProgress((double)(k + 1) / (double)length, false);
}
Метод InterruptionContext проверяет тот факт, что пользователь пытается
остановить вычисления: например, что была нажата кнопка Stop.
В этом случае метод выбрасывает исключение net.algart.contexts.InterruptionException,
в результате чего метод естественным образом завершается.
Программа может отловить это исключение, чтобы удостовериться, что метод действительно был прерван
и, например, сообщить об этом пользователю.
Обратите внимание: в отличие от стандартного InterruptedException,
исключение InterruptionContext необъявляемое. Это не случайно.
Вспомните: по определению, контекст — это дополнительная,
факультативная информация, не настолько важная, чтобы влиять на контракт метода.
Быть может, мы захотим применять данный метод для обработки сравнительно небольших изображений,
где он работает считанные миллисекунды. В этом случае возможность прервать его
не только не нужна, но может даже оказаться вредной, нарушающей логику вызывающего кода.
(Наш метод, кстати, действительно работает почти мгновенно для любого
изображения "добропорядочных" размеров, скажем, 1024x1024.)
В такой ситуации нормальным решением является передача контекста, не умеющего прерываться,
например InterruptionException было объявляемым,
его пришлось бы добавить в декларацию метода и тем самым потребовать
от пользователей обработки — например, перехвата.
Получилось бы крайне нелогично:
программа вызывает наш метод с полной гарантией, что InterruptionException
произойти не может, а тем не менее анализировать это исключение необходимо.
Пришлось бы писать код наподобие следующего, категорически осуждаемого
всеми учебниками по Java:
double mean;
try {
mean = SimplestTutorialDemo.meanOf_3(DefaultContext.getInstance(), image);
// "пустышка" DefaultContext.getInstance()
// заведомо не позволит методу прерваться
} catch (InterruptionException ex) {
// страшное и ужасное решение: игнонируем исключение
}
Чтобы не нужно было писать такие ужасы, исключение
InterruptionException сделано необъявляемым (RuntimeException).
Перейдем к методу ProgressUpdater
объявлен следующим образом:
public void updateProgress(double readyPart, boolean force);
Смысл его достаточно прост: хорошая реализация контекста прогресса
должна в этом методе показать пользователю, что готовая часть вычислений составляет
readyPart (величина от 0.0 до 1.0).
В самом простейшем случае, данный метод может вывести на экран надпись вроде следующей:
Параметр force не столь очевиден.
Дело в том, что алгоритмы, работающие с контекстом прогресса,
обычно вызывают метод updateProgress часто.
Как правило, нет никакого смысла при каждом вызове реально обновлять
соответствующий графический элемент, такой как JProgressBar.
Не только нет смысла, но и опасно: так можно "из лучших побуждений" замедлить
алгоритм в сотни раз.
Передавая в качестве этого параметра значение false,
алгоритм "говорит" приложению:
данное обновление прогресса можно проигнорировать,
так как я скоро либо снова вызову updateProgress, либо закончу вычисленияВ этом случае считается, что приложение имеет право пропустить очередное обновление экранного элемента, если с последнего обновления прошло мало времени (скажем, меньше 10 миллисекунд).
Как правило, это совершенно нормальное поведение, и поэтому чаще всего
в качестве параметра force передается false.
Но существуют ситуации, когда это не так. А именно, может оказаться, что алгоритм собирается
выполнить какую-то "долгоиграющую" операцию, не сопровождающуюся
регулярным обращением к контексту прогресса.
Например, это может быть выделение большого блока памяти, или обращение к
"долгому" методу сторонней библиотеки, не поддерживающей контексты AlgART.
В этом случае полезно гарантировать, что визуальный элемент, показывающий прогресс
выполнения, обновится, и индикатор JProgressBar не "застрянет"
в каком-то случайном предыдущем положении. Для этого достаточно вызвать
updateProgress с параметром force=true.
Например, в нашем методе можно было бы гарантировать такой вызов при последней
итерации цикла:
if ((k & 0xFFFF) == 0 || k == length - 1) {
ic.checkInterruption();
pu.updateProgress((double)(k + 1) / (double)length, k == length - 1);
}
Напоследок заметим, что "не слишком частое" обращение к контекстам — это общее правило,
которому рекомендуется всегда следовать. Было бы грубой ошибкой
вызывать методы ic.checkInterruption и pu.updateProgress
при каждой итерации внутреннего цикла, которая в нашем случае
требует лишь считанных тактов процессора.
Да, качественная реализация контекста, наверно, предоставит достаточно быстродействующие методы,
но вряд ли они будут работать совсем "мгновенно".
Умеренным решением является обращение к таким контекстам, как
ProgressUpdater и InterruptionContext,
не реже, чем каждые 10–100 миллисекунд — чтобы обеспечить плавное изменение "полоски прогресса"
и практически мгновенную останвку вычислений — но и не чаще, чем, скажем, раз в несколько микросекунд.
Вызов один раз в 65536 итераций простого суммирования — подходящий компромисс.
5. Вычисление средней яркости: учимся писать эффективно
Наши предыдушие решения базировались на методе getDouble.
Это простой путь, поэтому мы начали именно с него.
Но, к сожалению, это не очень эффективно.
Как мы увидим в данном разделе, нашу задачу можно решить в десятки раз быстрее.
Метод getDouble, а также его "близнецы" из частных интерфейсов,
описывающих конкретные типы массивов —
ByteArray.getByte, ShortArray.getShort и т.д. —
в современной реализации, в среднем, расходуют до сотни тактов процессора.
На сегодняшних персональных компьютерах это означает десятки наносекунд.
(Это средняя цифра для случая последовательного чтения массива.
Обращение "вразброс" к элементам большого массива может работать значительно медленнее.)
Для сравнения, простое обращение к обычному массиву Java,
благодаря оптимизатору Java HotSpot,
обычно требует считанных тактов, может быть, даже одного такта
(если нужный элемент "попадает" в кэш процессора).
Операция суммирования — основное действие, выполняемое нашим циклом —
тоже укладывается в несколько тактов, даже для вещественных чисел.
Почему же метод getDouble такой медленный?
Тут полезно немного отвлечься от нашего алгоритма вычисления средней яркости
и рассказать кое-что о том,
что стоит "за кулисами" внешне простого метода getDouble.
Вспомните: AlgART-массивы имеют 63-битовую адресацию (индексы типа long).
Один массив способен хранить практически сколь угодно большой объем данных,
ограниченный лишь оперативной и дисковой памятью.
И это достаточно важно: уже сегодня объемы оперативной памяти в несколько гигабайтов
для простой "персоналки" вполне типичны, и эту память надо уметь эффективно использовать.
Даже обычные "плоские" изображения в некоторых случаях превышают по объему гигабайт,
а для трехмерных, пространственных моделей такие объемы — норма.
Для адресации же байтового массива, более длинного, чем 2 Гб,
32-битовый тип int оказывается недостаточным.
В отличие от AlgART-массивов, все стандартные структуры языка Java,
предназначенные для хранения последовательности элементов,
имеют 31-битовую адресацию (тип индекса int) и изначально ограничены
примерно 2 миллиардами элементов. Это касается и стандартных массивов языка,
и класса ByteBuffer из java.nio, и коллекций из java.util.
Есть только одно очевидное исключение: классы для работы с файлами,
такие как RandomAccessFile.
Все это означает, что 63-битовая адресация AlgART-массивов, реализованная в рамках
языка Java, достигается далеко не бесплатно.
Чтобы преодолеть 2-миллиардный лимит, библиотака AlgART ассоциирует массив
с дисковым файлом (как правило, временным, удаляемым при завершении программы).
Файл делится на относительно небольшие блоки, размером по несколько мегабайтов.
Всякий раз, когда происходит обращение к AlgART-массиву, в частности, через метод getDouble,
система определяет соответствующий блок файла и мапирует его, вызовом FileChannel.map,
в буфер типа ByteBuffer.
Затем обращение переадресуется к методам
класса ByteBuffer (или его аналогов для других примитивных типов:
ShortBuffer, IntBuffer, и т.д.).
Заметим: даже для файлов, не превышающих (предельного для Java) объема 2 Гб,
используются сравнительно маленькие блоки, не более нескольких мегабайтов.
Это необходимо на 32-разрядных операционных системах, которые,
независимо от объема RAM, ограничивают доступное адресное пространства
одной программы лимитом порядка 2 гигабайтов.
Если бы мы попытались отобразить (мапировать) файл размером, скажем, 1 Гб
в единственный ByteBuffer,
вместо того чтобы "дробить" его на маленькие блоки,
то несколько таких AlgART-массивов уже переполнили бы адресное пространство, доступное
всей виртуальной машине Java.
Разумеется, несколько наиболее часто используемых блоков файла кэшируются.
Экземпляры ByteBuffer, отображенные на самые "популярные" блоки,
используются многократно. Переотображение (вызов FileChannel.map)
происходит лишь тогда, когда требуется доступ к новому участку AlgART-массива,
отсутствующему в кэше.
Реальный алгоритм кэширования и переотображения довольно сложен.
Каждый раз, когда мы обращаемся хотя бы к одному элементу массива,
приходится выполнить ряд проверок и, возможно, коррекций внутренних структур данных.
Более того, эти операции обычно синхронизуются,
чтобы сделать возможной параллельную обработку одного AlgART-массива из нескольких потоков.
(Далее мы увидим, что распараллеливание действительно очень полезно и реально повсеместно
применяется библиотеками AlgART на многопроцессорных или многоядерных компьютерах.)
Неудивительно, что вызов getDouble требует некоторого времени.
Возможно, это время сократится в будущих версиях библиотек AlgART и компиляторов Java,
но, вероятнее всего, методы типа getDouble
всегда будут значительно проигрывать простому обращению к Java-массиву
вроде byte[] или short[].
Каков же выход из положения? Для последовательных алгоритмов вроде нашего, просматривающих массив элемент за элементом, решение вполне традиционно — блочный доступ: чтение за один вызов достаточно длинного блока элементов с размещением их в обычном массиве Java. Такой вызов в библиотеках AlgART работает с максимальной эффективностью и дает практически такую же скорость, какую можно было бы получить при прямой работе с Java-массивом (или указателем языка C).
Даже при беглом взгляде на базовый интерфейс Array,
вероятно, вы обратите внимание на метод getData,
который позволяет обеспечить блочный доступ: этот метод читает целый блок последовательных элементов.
Однако, необходимо предупредить читателя:
это не тот метод, который, скорее всего, понадобится вам в прикладных алгоритмах
последовательной обработки массива.
Метод getData (и его "близнец" getBits
из интерфейса BitArray) действительно бывает необходим в низкоуровневых,
сложных программах, реализующих некоторые нетривиальные алгоритмы и абстракции.
Но для прикладных задач, как правило, удобнее — и эффективнее —
применять другую технологию, называемую "буфер данных".
Буфер данных представлен в пакете net.algart.arrays
интерфейсом DataBuffer.
(Не путайте с классом Buffer из java.nio:
между ним и DataBuffer нет ничего общего.)
Экземпляр такого интерфейса возвращается методами buffer,
расположенными в базовом интерфейсе Array.
Подобно самим AlgART-массивам, буфера данных имеют частные разновидности,
соответствующие конкретным типам и представленные 9-ю наследниками DataBuffer:
а именно, DataByteBuffer, DataShortBuffer и т.д.,
заканчивая DataObjectBuffer.
Я настоятельно рекомендую внимательно изучить JavaDoc-комментарий
к интерфейсу DataBuffer.
В этом комментарии подробно описаны основные понятия и приемы, связанные
с использованием буферов данных.
Полное понимание концепции DataBuffer весьма важно
для правильного использования этого удобного и мощного инструмента.
Итак, рассмотрим четвертую реализацию алгоритма подсчета средней яркости,
опирающуюся на применение DataBuffer:
public static double meanOf_4(Context context, @Name("image")Image2D image) {
ProgressUpdater pu = context.as(ProgressUpdater.class);
InterruptionContext ic = context.as(InterruptionContext.class);
Matrix<? extends PArray> m = image.i();
PArray a = m.array();
DataBuffer buf = a.buffer(DataBuffer.AccessMode.READ);
double sum = 0.0;
for (buf.map(0); buf.hasData(); buf.mapNext()) {
ic.checkInterruption();
pu.updateProgress((double)buf.position() / (double)a.length(), false);
if (a instanceof BitArray) {
long[] data = (long[])buf.data();
sum += PackedBitArrays.cardinality(data,
buf.fromIndex(), buf.toIndex());
} else if (a instanceof CharArray) {
char[] data = (char[])buf.data();
for (int k = buf.from(), kMax = buf.to(); k < kMax; k++)
sum += data[k];
} else if (a instanceof ByteArray) {
byte[] data = (byte[])buf.data();
for (int k = buf.from(), kMax = buf.to(); k < kMax; k++)
sum += data[k] & 0xFF;
} else if (a instanceof ShortArray) {
short[] data = (short[])buf.data();
for (int k = buf.from(), kMax = buf.to(); k < kMax; k++)
sum += data[k] & 0xFFFF;
} else if (a instanceof IntArray) {
int[] data = (int[])buf.data();
for (int k = buf.from(), kMax = buf.to(); k < kMax; k++)
sum += data[k];
} else if (a instanceof LongArray) {
long[] data = (long[])buf.data();
for (int k = buf.from(), kMax = buf.to(); k < kMax; k++)
sum += data[k];
} else if (a instanceof FloatArray) {
float[] data = (float[])buf.data();
for (int k = buf.from(), kMax = buf.to(); k < kMax; k++)
sum += data[k];
} else if (a instanceof DoubleArray) {
double[] data = (double[])buf.data();
for (int k = buf.from(), kMax = buf.to(); k < kMax; k++)
sum += data[k];
} else {
throw new AssertionError("Must not occur");
}
}
return sum / a.length();
}
Сразу бросается в глаза, что размер метода резко увеличился.
В нем появилось 8 веток, отвечающих за обработку разных примитивных типов элементов.
Раньше универсальная поддержка всех примитивных типов была "спрятана" в методе
getDouble, имеющемся в интерфейсе PArray.
Конверсия элементов прочих типов в число типа double
занимает так мало времени по сравнению с прочей "кухней", реализуемой
методом getDouble (как и другими методами доступа к одному элементу),
что затратами на конверсию можно было пренебречь.
Но буфера данных DataBuffer, в отличие от методов доступа к одному элементу,
не поддерживают автоконверсии типов.
Это оправдано: буфера данных разработаны для реализации максимально эффективных алгоритмов,
где, как правило, неявное преобразование типов всех элемента нежелательно.
Ценой эффективности является усложнение кода: необходимость повторения почти одинакового кода
для разных примитивных типов.
Код с ветвлением по 8 типам, увы, присущ многим алгоритмам, которые хотят эффективно обработать числовые AlgART-массивы, не теряя при этом универсальности — применимости к любому из восьми примитивных типов. Может быть, когда-нибудь в языке появятся средства, позволяющие упростить написание такого кода для примитивных типов (вроде templates языка C++). Но пока приходится писать 8 веток. Впрочем, как мы увидим в дальнейших главах, при программировании обработки изображений редко приходится "опускаться" до таких приземленных вещей, как работа с отдельными элементами матрицы.
Перейдем к анализу приведенного кода. Рассмотрим первый новый для нас оператор:
DataBuffer buf = a.buffer(DataBuffer.AccessMode.READ);
Смысл оператора достаточно прост: для заданного AlgART-массива a
возвращается буфер данных, соответствующий этому массиву и предназначенный для чтения данных.
Примерно так же, как для коллекции java.util
можно получить соответствующий ей объект Iterator.
Здесь стоит обратить внимание на две вещи. Во-первых, мы явно указываем
режим доступа READ. Зачем?
Это — "подсказка" библиотеке, что нам не понадобится модифицировать массив.
Можно было бы и обойтись без такой подсказки.
Имеется перегруженная версия метода buffer без аргументов, выбирающая
режим автоматически.
Однако существуют ситуации (хоть и не очень типичные),
когда буфер данных с режимом доступа, выбранным по умолчанию, будет работать
медленнее, чем буфер с режимом READ.
Правилом "хорошего тона" является всегда явно указывать, какой режим работы
с буфером данных нам необходим — благо это ничего не стоит.
Кроме возможной оптимизации, это улучшает читабельность кода, ибо явно
указывает на намерения программиста.
Надо заметить, что режим доступа DataBuffer.AccessMode.READ
— это не более чем "подсказка". Такой режим никоим образом не гарантирует,
что возвращенный буфер данных не позволит изменить элементы массива.
(Для получения таких гарантий нужна другая технология: метод Array. См. JavaDoc, в частности, комментарий к пакету — package summary.)
Если вы все же попытаетесь, пользуясь буфером данных в режиме READ,
модифицировать исходный массив,
может быть, это получится, может быть, ваша попытка будет проигнорирована,
а может быть, изменится лишь часть массива — это не оговорено документацией.
Все, что можно сказать: реализация DataBuffer постарается,
по возможности, сэкономить время, избегая ненужных вам операций записи данных в массив.
Вторая вещь, о которой иногда полезно задуматься — размер буфера (capacity).
Иначе говоря, число последовательных элементов AlgART-массива, которые
будут "за один раз" читаться из массива в буфер и сохраняться
в обычной памяти (массиве) языка Java.
По умолчанию, выбирается некоторый "разумный" размер, обеспечивающий
почти оптимальную скорость обмена с AlgART-массивом: вероятнее всего
(но отнюдь не обязательно) несколько тысяч элементов.
Вы можете задать этот объем "вручную": у метода buffer
есть соответствующие перегруженные версии.
Так, при дальнейшей оптимизации нашего метода было бы невредно явно задать размер буфера,
чтобы гарантировать, что буфер не будет длиннее 215−1=32767 элементов.
Это позволило бы просуммировать в одном цикле, заведомо без переполнения,
все элементы типа byte или short,
используя переменную-сумматор типа int.
Впрочем, на данном этапе мы не будем настолько углубляться в оптимизацию.
Идем дальше. Обратите внимание на организацию цикла:
for (buf.map(0); buf.hasData(); buf.mapNext()) {
. . .
}
Напоминает итераторы по коллекциям java.util, не правда ли?
Однако есть и отличия. Прежде всего, буфер данных ориентирован на произвольный,
а не последовательный доступ, поэтому его можно — и нужно — явно "позиционировать"
на некоторый участок AlgART-массива. Так как мы собираемся обрабатывать массив
в естественном порядке, слева направо, то цикл начинается с позиционирования
буфера на начало массива: map.
Чаще всего это
При переходе к следующей итерации цикла вызывается метод map, вычислив следующую позицию
в массиве: в JavaDoc приведен соответствующий пример цикла.
Но вариант с map или mapNext.
При последнем вызове mapNext "сдвинет" буфер на позицию,
равную длине AlgART-массива. Это корректная ситуация, но буфер в этом случае
считается пустым. Соответственно, метод false, и цикл естественным образом завершится.
Рассмотрим теперь тело цикла. Вначале идет уже знакомое нам обращение к контекстам прерываний
и прогресса. (Удобнее вызвать контекст прогресса в начале, а не в конце цикла,
так как количество уже обработанных данных оказывается равным текущей начальной
позиции буфера, возвращаемой методом
Далее начинается ветвление по типам элементов. Все ветки начинаются с вызова
метода ByteArray
это будет массив byte[], для ShortArray — массив short[],
и т.д. С различными типами Java-массива нужно работать по-разному:
это главная причина, по которой необходимы 8 веток.
Заметим, что затребованный фрагмент AlgART-массива вовсе не обязательно
окажется в начале Java-массива buffer.
Но
С массивом, полученным методом READ
это может привести к изменениям в исходном массиве.
Существует важный частный случай AlgART-массивов: так называемые простые массивы,
являющиеся "оболочкой" вокруг самых обыкновенных, стандартных массивов Java.
Такие AlgART-массивы часто применяются, например, для оптимизации.
В случае простого AlgART-массива метод asImmutable,
то DataBuffer не позволит нарушить неизменяемость: в этом случае
DataBuffer будет копировать данные в отдельный Java-массив.)
Первая из 8 веток цикла посвящена случаю битового массива: BitArray.
Это самый сложный случай, поскольку биты в AlgART-массивах, так же как и в буферах
данных, упакованы в 64-битовые целые числа типа long.
Соответственно, метод long[].
Обрабатывать такой упакованный массив "вручную" было бы крайне неудобно.
Так, простейшее чтение бита с индексом index выражается следующим громоздким оператором:
(data[(int)(index >>> 6)] & (1L << (index & 63))) != 0
К счастью, в составе пакета net.algart.arrays предусмотрен специальный
класс PackedBitArrays, содержащий сервисные функции для большинства
задач, возникающих при обработке битов, упакованных в массивы long[].
В нашем примере мы используем готовую высокоэффективную функцию cardinality,
решающую в точности нашу задачу: подсчет количества единичных битов
(или, что то же самое, суммы) в произвольном фрагменте упакованного битового массива.
Все прочие ветки алгоритма похожи друг на друга и практически очевидны. Но, вероятно,
вы заметили, что вместо методов
Методы long.
Ведь обычный Java-массив long[] может
содержать более 231−1 битов. Например, даже 32-разрядные версии Java
в состоянии создать массив long[] длиной в гигабайт, а это уже 233 битов.
И хотя маловероятно, что вам потребуется DataBuffer такого объема
(впрочем, кто знает, какими "порциями" мы будем обрабатывать сверхбольшие массивы
через несколько лет в 64-разрядных OS), корректный код для случая битов должен
опираться на 64-разрядные методы
В противоположность битовому случаю, для всех остальных типов элементов
мы имеем дело с обычным, неупакованным Java-массивом byte[], short[] и т.д.
В нем по определению не может быть более 231−1 элементов,
более того, для его индексации пригоден только тип int, но не long.
Чтобы не заставлять программиста всякий раз приводить результаты методов
int, интерфейс DataBuffer
предусматривает 32-битовые версии этих методов
В заключение, обратите внимание на операторы "& 0xFF" и "& 0xFFFF"
при обработке типов byte и short.
Эти операторы нужны, чтобы, подобно предыдущим версиям нашего метода,
обработать 8- и 16-битовые элементы как беззнаковые.
Метод getDouble выполнял такую коррекцию внутри себя,
теперь же мы должны выполнить преобразование явно.
Мы закончили рассмотрение первого примера обработки AlgART-массива,
построенного на применении DataBuffer.
Относительная сложность такого решения окупается с лихвой:
на моем компьютере новый метод работает примерно в 10 раз быстрее,
чем предыдущий вариант.
6. Вычисление средней яркости: библиотечная функция все-таки лучше
Последний разобранный нами вариант подсчета среднего достаточно эффективен. Можно было бы выполнить ряд очевидных оптимизаций, например, заменить, где возможно, вещественное сложение целочисленным. Но это уже не так интересно.
На самом деле, если мы хотим найти оптимальное решение некоторой задачи, в 90% случаев нужно последовать классическому рецепту: поискать готовое решение в библиотеках. Почти наверняка оно окажется не хуже вашего. А если даже оно не оптимально, вероятнее всего, алгоритм будет оптимизирован в одной из следующих версий библиотки.
Как и следовало ожидать, такая простая задача, как суммирование элементов массива,
уже предусмотрена в библиотеках AlgART.
Это метод sumOf библиотечного класса Arrays.
С его использованием решение нашей задачи записывается совсем лаконично:
public static double meanOf_5(Context context, @Name("image")Image2D image) {
ArrayContext arrayContext = new DefaultArrayContext(context);
Matrix<? extends PArray> m = image.i();
PArray a = m.array();
double sum = Arrays.sumOf(arrayContext, a);
return sum / a.length();
}
По сравнению с предыдущими примерами, здесь добавилось только одно понятие.
Это контекст массивов: интерфейс ArrayContext.
На самом деле ArrayContext реализует ту же самую концепцию,
что и контексты типа Context, рассмотренные нами раньше.
Но ArrayContext, расположенный, в отличие от Context,
в пакете net.algart.arrays, несколько проще.
ArrayContext — это как бы "пакет net.algart.contexts в миниатюре".
В отличие от нетривиальной системы интерфейсов и классов,
здесь мы имеем дело всего с одним интерфейсом —
реализующим, однако, практически все задачи,
необходимые при работе с массивами на уровне пакета net.algart.arrays.
В модулях, ориентированных исключительно на обработку AlgART-массивов и матриц,
часто достаточно работать с ArrayContext.
Более мощный пакет net.algart.contexts обычно привлекается,
когда, кроме AlgART-массивов, необходимы другие сущности, такие, как
необходимые нам изображения Image2D
(про которые ArrayContext, конечно, ничего не "знает").
Разумеется, общий контекст Context допускает автоматическое
преобразование к ArrayContext. В нашем примере преобразование выполняется
в первой строчке:
ArrayContext arrayContext = new DefaultArrayContext(context);
Именно такой контекст, ArrayContext, следует передавать
вычислительным функциям пакета net.algart.arrays,
в частности, функции Arrays.sumOf.
Насколько наш новый метод лучше предыдущего, выполняющего суммирование "вручную"?
Конечно, библиотечная функция Arrays.sumOf содержит мелкие оптимизации
вроде целочисленного суммирования, которыми мы пренебрегли в учебном методе
meanOf_4.
Но главное преимущество sumOf — распараллеливание вычислений.
Вообще, распараллеливание — одно из важных достоинств большинства расчетных методов, предусмотренных в библиотеках AlgART. Современые компьютеры часто оснащены несколькими процессорами либо многоядерными процессорами, позволяющими параллельно выполнить несколько задач, например, просуммировать несколько фрагментов одного большого AlgART-массива. Для этого достаточно создать несколько потоков и поручить каждому выполнение своей части задачи. Таким образом на многопроцессорном или многоядерном компьютере можно добиться многократного ускорения вычислений.
При помощи пакета java.util.concurrent распараллеливание
программируется довольно просто. Более того,
для распареллеливания обработки массивов в большинстве случаев
можно использовать библиотечный класс Arrays.ParallelExecutor,
который "берет на себя" большую часть рутинной работы по организации
совместной работы потоков и взаимодействию с контекстом ArrayContext.
Профессиональный метод Arrays.sumOf, действительно,
опирается на этот класс.
Деталями распараллеливания — например, количеством параллельных потоков
— тоже управляет соответствующий контекст
(либо часть ArrayContext, либо независимый интерфейс
net.algart.contexts.ArrayThreadPoolContext).
В JavaDoc вы можете найти детали такого управления.
Если вы решите задействовать параллельность в своих собственных вычислительных методах,
рекомендую посмотреть, как реализован в библиотеке метод sumOf
(или один из похожих методов, скажем, rangeOf)
и изучить документацию к Arrays.ParallelExecutor.
Даже если ParallelExecutor окажется для ваших целей недостаточен,
в любом случае рекомендую использовать ArrayThreadPoolContext:
тогда приложения смогут управлять вашим распараллеливанием таким же образом,
как и распараллеливанием в библиотеках AlgART.
7. Генерация константного изображения простейшим способом: цикл по массиву
Мы научились получать на входе алгоритма изображения, представленные AlgART-матрицами, и анализировать несколькими способами значения яркостей пикселов (т.е. элементы матрицы). Рассмотрим теперь обратную задачу: создание нового изображения и заполнение его какими-то значениями, для начала — некоторой числовой константой.
Начнем с простейшего, хотя и неэффективного способа: поэлементного присваивания элементов. Мы уже говорили, что для таких задач поокординатный цикл по матрице (по y и по x) никакого смысла не имеет, разве что вам хочется слегка замедлить алгоритм. Начнем с цикла по линейному массиву: аналога разобранного выше простейшего способа вычисления суммы элементов в очень похожем цикле.
public static Image2D constant_1(Context context,
@Name("dimX")long dimX, @Name("dimY")long dimY,
@Name("value")float value)
{
ArrayMemoryContext amc = context.as(ArrayMemoryContext.class);
MemoryModel mm = amc.getMemoryModel();
Matrix<UpdatableFloatArray> m = mm.newFloatMatrix(dimX, dimY);
UpdatableFloatArray a = m.array();
long length = a.length();
for (long k = 0; k < length; k++) {
a.setFloat(k, value);
}
ImageContext imageContext = context.as(ImageContext.class);
Image2D result = imageContext.newGrayscaleImage2D(imageContext, m);
return result;
}
В отличие от предыдущих примеров, мы собираемся решить новую для нас задачу:
создать "с нуля" AlgART-матрицу (т.е. отвести память),
элементы которой мы будем заполнять константным значением.
Размеры матрицы и желаемое значение — это аргументы метода dimX,
dimY, value.
AlgART-матрица, также как и AlgART-массив — это интерфейс.
Для создания экземпляров матриц и массивов, в соответствии с хорошими традициями шаблона Factory,
служит класс под названием MemoryModel... впрочем, нет, не класс, а опять интерфейс!
Почему интерфейс и почему MemoryModel?
MemoryModel, или модель памяти — фундаментальное понятие библиотек AlgART.
Архитектура AlgART-массивов изначально спроектирована так, чтобы физический способ хранения данных
был легко и произвольно расширяем.
Этот способ хранения называется моделью памяти.
Основная задача интерфейса MemoryModel — служить фабрикой,
создающей экземпляры массивов и матриц любого желаемого типа и размера.
В зависимости от того, какая реализация MemoryModel применяется
(т.е. какая выбрана конкретная модель памяти),
будут создаваться различные реализации массивов и матриц:
практически неотличимые друг от друга с точки зрения использования,
но совершенно разные по "внутреннему устройству".
Например, существует простая модель памяти: класс SimpleMemoryModel,
реализующий интерфейс MemoryModel.
В этом случае AlgART-массив — всего лишь "оболочка" вокруг обычного Java-массива,
хранящегося в Java-куче. Это самый эффективный вариант с точки зрения быстродействия,
но такие массивы ограничены размерами памяти JVM и предельной длиной 231−1 элементов
(несколько больше для битовых массивов, за счет упаковки битов в long-значения).
Но есть и альтернативная, большая модель памяти LargeMemoryModel.
Здесь AlgART-массив реально представляет собой дисковый файл, а операции доступа к его элементам
приводят к отображению фрагментов файла в память: мы рассказывали об этом
выше, когда разбирали механизм работы метода getDouble.
Этот вариант несколько медленнее, но не накладывает никаких ограничений на размер массивов,
за исключением естественного предела — свободного места на диске —
и чисто теоретического лимита на число элементов 263−1
(т.е. более 9 миллионов терабайт).
Другой интересный пример модели памяти (впрочем, не имеющий прямого отношения к обработке изображений)
— комбинированная модель памяти CombinedMemoryModel.
Она предназначена для хранения массивов объектов, а не примитивных типов,
и позволяет хранить AlgART-массив однотипных структур в одном или нескольких других AlgART-массивах,
уже состоящих из элементов примитивных типов.
Например, AlgART-массив объектов типа "точка" (2 числа x и y, допустим, типа float),
внешне "выглядящий" как обычный массив объектов и похожий на классический ArrayList,
при помощи такой модели можно сохранить в AlgART-массиве float-значений,
в котором поочередно будут записываться x- и y-координаты каждой точки.
Такой способ позволит как сэкономить память — на точку будет израсходовано ровно 2*4=8 байтов,
в отличие от ArrayList или массива объектов Java, где добавятся изрядные накладные
расходы на поддержание отдельного экзепляра объекта — так и преодолеть лимит 2 Гб
и задействовать для хранения точек свободное дисковое пространство.
Разумеется, профессиональное приложение должно каким-то образом выбрать желаемую модель памяти,
которой будет рекомендовано пользоваться библиотечным алгоритмам для создания своих массивов и матриц.
В сложном приложении, возможно, модель памяти будет отличаться от стандартных, предусмотренных
в пакете net.algart.arrays, хотя бы своими настройками
(вроде каталога временных файлов, в котором следует создавать большие массивы).
Для передачи этой информации в алгоритм, как обычно, используется контекст.
Речь идет о частном контексте памяти: класс ArrayMemoryContext.
Его задача — вернуть модель памяти MemoryModel, которую должен
использовать алгоритм для создания любого AlgART-массива или матрицы
(кроме, быть может, совсем маленьких массивов, для которых SimpleMemoryModel
является оптимальным выбором).
Это и происходит в начале нашего метода:
ArrayMemoryContext amc = context.as(ArrayMemoryContext.class);
MemoryModel mm = amc.getMemoryModel();
Если в качестве параметра context в данный метод
передан "контекст-заглушка" net.algart.arrays.globalMemoryModel":
см. метод SimpleMemoryModel.
Располагая экземпляром MemoryModel, нет проблем создать матрицу желаемого
типа и размера. В этом примере мы, не мудрствуя лукаво, создаем вещественную матрицу
типа float:
Matrix<UpdatableFloatArray> m = mm.newFloatMatrix(dimX, dimY);
Тип AlgART-массива в данном случае — UpdatableFloatArray,
т.е. допускающий модифицацию элементов (но не изменение длины) массив вещественных
чисел float.
Следующий цикл вполне тривиален:
long length = a.length(); // можно было бы написать dimX*dimY, но так нагляднее
for (long k = 0; k < length; k++) {
a.setFloat(k, value);
}
Метод setFloat — "брат-близнец" подробно разбиравшегося выше метода
getDouble, объявленный в конкретном интерфейсе UpdatableFloatArray.
С тем же успехом можно было бы использовать setDouble:
чуть более общий метод, объявленный в интерфейсе UpdatablePArray.
В дальнейших разделах мы заменим setFloat более эффективными решениями.
Последние два оператора знакомы нам по первому разобранному нами примеру, когда мы возвращали полутоновой эквивалент RGB-картинки:
ImageContext imageContext = context.as(ImageContext.class);
Image2D result = imageContext.newGrayscaleImage2D(imageContext, m);
Как и там, мы используем частный контекст ImageContext,
чтобы на основании AlgART-матрицы создать изображение типа Image2D.
В качестве результата возвращается полутоновое изображение, яркость всех пикселов которого
равна переданной константе value.
Что значит "яркость равна переданной константе"? На самом деле, вопрос интерпретации вещественного
числа в качестве яркости, на данный момент — вне нашей компетенции.
Это решает программа, которая вызвала наш метод и собирается что-то делать с полученным Image2D:
визуализировать, экспортировать в BMP-файл, делать что-то еще.
(Может быть, это вообще не яркость, а уровень высот в будущей топографической карте,
которую предполагается показать в виде трехмерной поверхности.)
В качестве "разумного умолчания" я рекомендую принять следующее соглашение: для вещественных чисел значение 0.0 соответствует нулевой яркости (черные пикселы), значение 1.0 — максимальной яркости (белые пикселы), значения между 0.0 и 1.0 — промежуточным яркостям. Значения вне диапазона 0.0...1.0 "некорректны" и могут показываться, например, как черные (отрицательные) и белые (большие чем 1.0). Если бы мы создавали изображение с другим типом элементов (что мы и будем делать в следующих разделах), то рекомендуемые соглашения такие:
- тип
byte: яркость увеличивается от 0 (черный цвет) до 28−1=255 (белый); - тип
short: яркость увеличивается от 0 (черный цвет) до 216−1=65535 (белый); напоминаем, что в библиотеках AlgART типыbyteиshortсчитаются беззнаковыми; - тип
char: так же, какshort(хотя кому нужен типcharдля обработки изображений, остается загадкой); - тип
int: яркость увеличивается от 0 (черный цвет) до 231−1 (белый), отрицательные значения в качестве яркости являются некорректными; - тип
long: яркость увеличивается от 0 (черный цвет) до 263−1 (белый), отрицательные значения в качестве яркости являются некорректными; - тип
boolean(битовые массивы): 0 (false) означает черный цвет, 1 (true) — белый.
Подчеркиваю: это лишь рекомендация для визуализации и экспорта в других форматы изображений. Таким соглашениям следует, например, система , хотя там есть возможность, при желании, настроить другие диапазоны для представления яркостей. Для программирования алгоритмов данные соглашения обычно не имеют значения.
8. Генерация константного изображения: произвольная разрядность результата
В предыдущем примере мы создаем вещественную матрицу с элементами фиксированного
типа, а именно float.
На самом деле такое решение редко является приемлемым.
Почему именно float? Потому что так удобнее разработчику — раз аргумент
value такого типа?
А если мы хотим получить байтовое (8-битовое) изображение?
В конце концов, необходимость экономить память и место на диске никто не отменял,
а 8-битовая матрица в 4 раза компактнее.
В "настоящих", серьезных алгоритмах, создающих новое изображение, таких как фильтр удаления шума, тип элементов результата (разрядность) обычно определяется входными данными. Скажем, алгоритм удаления аддитивного шума может создать результирующее изображение с той же разрядностью, что и исходное, или получить желаемый примитивный тип непосредственно в качестве аргумента метода.
Исправимся. Изменим предыдущий метод, чтобы он вернул константное изображение произвольной разрядности, которую мы укажем в параметре. Заодно вспомним о пользователе и добавим контексты прерываний и прогресса, подробно рассмотренные нами ранее.
public static Image2D constant_2(Context context,
@Name("dimX")long dimX, @Name("dimY")long dimY,
@Name("elementType")String elementType, @Name("value")double value)
{
ArrayMemoryContext amc = context.as(ArrayMemoryContext.class);
MemoryModel mm = amc.getMemoryModel();
ProgressUpdater pu = context.as(ProgressUpdater.class);
InterruptionContext ic = context.as(InterruptionContext.class);
Class<?> eType = typeOf(elementType);
Matrix<? extends UpdatablePArray> m =
mm.newMatrix(UpdatablePArray.class, eType, dimX, dimY);
UpdatablePArray a = m.array();
long length = a.length();
for (long k = 0; k < length; k++) {
a.setDouble(k, value);
if ((k & 0xFFFF) == 0) { // equivalent to k%65536==0
ic.checkInterruption();
pu.updateProgress((double)k / (double)length, false);
}
}
ImageContext imageContext = context.as(ImageContext.class);
Image2D result = imageContext.newGrayscaleImage2D(imageContext, m);
return result;
}
Теперь желаемый тип элементов результата — один из 8 примитивных типов Java —
описывается строчным параметром elementType, а значение-заполнитель
value — уже не float, а double,
которым можно описать практически любое значение любого примитивного типа...
Стоп! Почему, собственно, elementType строчный?
Ведь ясно, что нужен параметр типа Class!
На самом деле тут нет никаких "глубокомысленных" причин. Просто так удобнее.
Если вы все-таки когда-нибудь вызовете этот метод (на что я надеюсь) —
или написав собственный тест-утилиту, или применив мощную оболочку
— вам придется как-то задавать этот параметр.
А если даже не вызовете, то во всяком случае этот метод вызывал я,
пока писал этот текст, а об удобстве автора тоже надо подумать.
Удобнее, если значение параметра можно ввести
при исполнении программы, а не "зашивать" в код теста.
Самый простой способ задать примитивный тип (не самый лучший, но зато вполне очевидный) —
набрать его имя, т.е. строчку "boolean", "byte" и т.д.
В учебном классе SimplestTutorialDemo есть простенькая сервисная private-функция
typeOf, преобразующая подобную строку в объект типа Class,
описывающий один из примитивных типов. Эта функция вызывается в нашем методе, чтобы превратить
elementType в переменную eType типа Class
(вернее, Class<?>, в соответствии с традициями современной Java).
Текст typeOf невелик, скучен и потому здесь не приводится. При желании, я полагаю,
вы можете запросто написать десяток подобных функций.
Начало нового метода почти повторяет предыдущий вариант, только добавляется
извлечение уже знакомых нам контекстов прогресса и прерываний.
Затем, как и ранее, мы создаем матрицу при помощи модели памяти mm,
но на этот раз указываем желаемый класс примитивного типа eType.
Это делается почти так же просто, как и создание матрицы конкретного типа:
Matrix<? extends UpdatablePArray> m =
mm.newMatrix(UpdatablePArray.class, eType, dimX, dimY);
Так, так... А зачем тут параметр UpdatablePArray.class?
Согласно здравому смыслу, а также описанному в самом начале понятию матрицы
и традициям нормальных языков программирования, чтобы создать матрицу,
вполне достаточно указать ее размеры и тип элементов!
То, что она окажется Matrix<? extends UpdatablePArray>, уже вытекает
из значения аргумента eType, который, как предполагается
(если функция typeOf написана без ошибок), всегда описывает примитивный тип!
Тут мне остается лишь принести извинения за язык Java. Его технология generics,
по крайней мере в версиях Java 5, 6 и 7, скажем так, кажется автору недостаточно развитой.
Может быть (и многие надеются на это), в следующих версиях ее расширят,
но пока, во избежание трудноуловимых ошибок, generics-методы генерации
порой приходится снабжать "костылями": параметрами типа Class,
с точки зрения логики совершенно избыточными.
Что же все-таки делает этот параметр?
Взгляните на декларацию вызываемого метода newMatrix:
public <T extends UpdatableArray> Matrix<T> newMatrix(
Class<T> arraySupertype, Class<?> elementType, long ...dim);
Давайте попытаемся убрать первый параметр, чтобы сделать метод более "логичным":
public <T extends UpdatableArray> Matrix<T> newMatrix(
Class<?> elementType, long ...dim);
(По секрету: должен сознаться, к стыду своему, что в процессе создания библиотек в одной из ранних версий так оно и было. И на старуху бывает проруха...)
На первый взгляд все нормально: мы можем присвоить результат любой матрице типа Matrix<T>,
где T — произвольный updatable-массив, т.е. допускающий изменения элементов.
(Кстати: конечно, updatable.
Кому нужна свежесозданная матрица, если ее элементам не удастся ничего присвоить.)
Конкретный тип массива T, скажем, UpdatableByteArray, будет определяться типом
элементов elementType, например:
Matrix<UpdatableByteArray> m = mm.newMatrix(byte.class, dimX, dimY);
Будет ли?... А вот и нет. В языке Java, при всей его замечательности в прочих отношениях, информация о generic-типах стирается в момент компиляции. Во время исполнения программы такой оператор присваивания выполняется в точности так, как если бы мы написали просто:
Matrix m = mm.newMatrix(byte.class, dimX, dimY);
Что отсюда следует? Следует возможность написать следующую страшную вещь, которая, что ужаснее всего, без ошибок отработает во время выполнения:
Matrix<UpdatableByteArray> m = mm.newMatrix(short.class, dimX, dimY);
Сам по себе вызов newMatrix, какой бы хитроумной она ни была, не в состоянии
усмотреть в таких параметрах чего-либо "крамольного". Ну просят его создать матрицу с элементами
short, что ж, он и создаст. Откуда же методу newMatrix знать,
что глупый программист собирается присвоить созданную матрицу переменной типа
Matrix<UpdatableByteArray>, а не Matrix<UpdatableShortArray>?
Что будет дальше? Оператор присваивания спокойно отработает —
ведь после "стирания" в нем не осталось никаких намеков на UpdatableByteArray!
Сравните: если бы речь шла об обычных, не "генерализованных" классах и интерфейсах,
то никакого стирания бы не было, а компилятор потребовал бы от нас вставить оператор приведения типа.
При исполнении этого оператора, в случае несоответсвия типов,
произошло бы исключение времени выполнения ClassCastException.
Например:
UpdatableByteArray a = (UpdatableByteArray)mm.newUnresizableArray(
short.class, arrayLen);
// - Генерируется ClassCastException при приведении типа,
// так как метод возвращает тип UpdatableShortArray,
// несовместимый с UpdatableByteArray.
// Если же убрать приведение типов "(UpdatableByteArray)",
// будет синтаксическая ошибка, так как newUnresizableArray
// возвращает UpdatableArray, а не UpdatableByteArray.
Какие были бы последствия описаного метода newMatrix?
Самые печальные. При указании ошибочного типа элементов матрицы
ошибка останется незамеченной и "выплывет" где-то позже.
Возможно, при первой попытке "поработать" с созданной матрицей,
когда мы, скажем, попытаемся присвоить массив UpdatableByteArray.
Компилятор в этом случае не потребует явно приводить тип (как было бы при отсутствии generics),
поскольку "считает", что матрица Matrix<UpdatableByteArray> в принципе
не может содержать никакого другого массива, кроме UpdatableByteArray.
Приведение типа произойдет неявно, и программа выдаст ClassCastException
на "совершенно ровном" месте. Да и то если повезет: скажем, код, ориентированный
на матрицы общего вида Matrix<? extends UpdatablePArray>
выполнится без исключений,
но, быть может, абсолютно неверно, если программист, видя тип конкретной переменной
Matrix<UpdatableByteArray>, существенно использовал 8-битовость элементов.
Правильное решение —
явно передать методу аргумент типа Class<T>, где T —
нужный нам generic-тип. Так и сделано в библиотеке AlgART. Для удобства читателя,
повторим декларацию из интерфейса Matrix:
public <T extends UpdatableArray> Matrix<T> newMatrix(
Class<T> arraySupertype, Class<?> elementType, long ...dim);
(Кстати сказать, аналогичный прием используется
и в других методах, возвращающих результат с generics-параметром,
например, в методе Matrix.cast.)
Что изменилось, когда мы добавили параметр Class<T> arraySupertype?
С одной стороны, теперь метод знает, какой именно тип массива T
должен быть у создаваемой матрицы. Если тип элемента ему не соответствует,
то метод самостоятельно сгенерирует исключение ClassCastException:
ошибка далее не распространится.
С другой стороны, компилятор теперь получил возможность проконтролировать тип результата.
Ведь переданный параметр Class сам обладает параметром T, причем
тем же самым, который указан в качестве параметра матрицы.
Если мы попытаемся "обмануть" метод newMatrix, указав соответствующие друг другу,
но неверные arraySupertype и elementType,
то мы просто не сможем присвоить результат переменной-матрице с неподходящим generics-типом.
Скажем, следующий код попросту не скомпилируется:
Matrix<UpdatableByteArray> m =
mm.newMatrix(UpdatableShortArray.class, short.class, dimX, dimY);
// ошибка: несовместимые параметры T у результата метода и переменной m
В нашем алгоритме мы "заказываем" тип массива UpdatablePArray.class:
Matrix<? extends UpdatablePArray> m =
mm.newMatrix(UpdatablePArray.class, eType, dimX, dimY);
Это значит, что метод newMatrix непременно вернет матрицу,
generics-параметр которой соответствует массиву с элементами примитивного типа, т.е.
является UpdatablePArray или его наследником.
Такую матрицу, естественно, мы имеем право присвоить переменной типа
Matrix<UpdatablePArray> и, конечно же,
переменной более общего типа Matrix<? extends UpdatablePArray>.
Мы выбираем второй, более общий вариант: см. вступление про матрицы и generics.
Дальнейшая часть метода достаточно очевидна.
Производится цикл по массиву и каждому его элементу присваивается значение value.
На этот раз используется общий метод setDouble интерфейса UpdatablePArray,
применимый к массивам любого примитивного типа.
Подобно методу getDouble, метод setDouble позволяет
писать общие, хотя и не самые эффективные алгоритмы, обрабатывающие массивы элементов
любого примитивного типа. Подобно getDouble, этот метод выполняет автоматическое
преобразование типов. И подобно getDouble, этот метод нарушает традиции
языка Java, воспринимая значения типа byte и short как беззнаковые...
Стоп. А правда ли нарушает? Загляните в JavaDoc-комментарий к setDouble.
Как ни странно, в отличие от getDouble, в этом комментарии нет никаких
оговорок насчет типов byte и short. Простым английским языком сказано:
"Sets the element #index by convertion from double,
as xxx
(byte, short, int, long,
float, double or char),
or as value!=0.0 for boolean element type."
В чем дело? Неужели ошибка? Может быть, getDouble и setDouble
не соответствуют друг другу — записав значение методом setDouble,
при чтении методом getDouble мы рискуем получить нечто совершенно другое?
Конечно, никакой ошибки здесь нет — иначе, надо полагать, я бы не стал об этом писать.
Однако разобраться в этом весьма важно, дабы не попасть "впросак" потом,
когда вам понадобится реализовать аналогичную конверсию самостоятельно —
скажем, при заполнении AlgART-массива через DataBuffer.
Чтобы понять, почему в setDouble "все чисто", надо внимательно проанализировать, что
на самом деле делает кажущийся столь простым оператор приведения типа
setDouble.
Пусть value — переменная типа double,
содержащая значение 200, и мы пытаемся выполнить setDouble с таким аргументом
для случая байтового массива UpdatableByteArray.
Мнения библиотек AlgART и языка Java насчет интерпретации такой величины в качестве байта
расходятся. Для нас, "любителей AlgART", это нормальный беззнаковый байт, равный 200,
и в байтовом массиве UpdatableByteArray он должен храниться как 0xC8
(в шестнадцатиричной системе) или 11001000 (в двоичной системе).
Для языка Java, такое значение не может храниться в переменной типа byte:
эти переменные изменяются от −128 до +127, а байт 0xC8 описывает не положительное число 200,
а отрицательное число −56.
Что произойдет, если все же выполнить приведение типа setDouble?
Если вы напишете коротенький тест, вы убедитесь, что
Почему? Потому, что язык Java вначале приводит вещественный тип к
"универсальному" целочисленному типу int, а только потом конвертирует
тип int в более узкие типы byte, short или char.
Именно такое поведение зафиксировано в спецификации языка.
И если приведение double к int сопровождается усечением
слишком больших значений до диапазона Integer.MIN_VALUE..Integer.MAX_VALUE,
то конверсия int в byte (как и всякая конверсия более
широкого целого типа к более узкому) означает всего-навсего отбрасывание старших битов.
В результате 200.0 превращается вначале в положительное int-значение 200
(двоичное 11001000), а уже это число далее превращается в байт, состоящий из тех же самых 8 битов 11001000.
С точки зрения Java, полученный байт равен −56, а с нашей, "беззнаковой" точки зрения
он как раз содержит 200! Иначе говоря, все в порядке: последующий вызов getDouble,
действуя в соответствии с "беззнаковыми" соглашениями, для такого байта вернет правильное
значение 200.0. Т.е. произойдет в точности то, что требуется.
Будьте внимательны! В качестве "универсальной разменной монеты" для целых чисел
язык Java применяет именно int, а не long.
Поэтому, если мы попытаемся повторить те же действия с чрезвычайно большим
(больше Integer.MAX_VALUE) целым значением,
представленным типом double, и переменной (типом элемента) int,
поведение будет другим! Впрочем, по-прежнему согласующимся с документацией
на методы getDouble и setDouble.
А именно, если попытаться привести очень большое число double,
скажем, 1012, к типу int (оператором long
с последующим отбрасыванием "лишних" битов. Вместо этого, оператор Integer.MAX_VALUE.
На этом мы заканчиваем рассмотрение данного примера и переходим к разбору более
эффективных решений, не использующих метод setDouble.
9. Генерация константного изображения: да здравствует лень
Сейчас мы могли бы пойти тем же путем,
что и при вычислении средней яркости:
заменить поэлементный цикл вызовов setDouble использованием
буферов данных (DataBuffer), возможно, добавить распараллеливание.
Однако это довольно скучно. Кроме того, решения, которые мы изложим далее,
во многих случаях оказываются более удобными и эффективными.
Поэтому мы оставим перевод предыдущего примера на технику DataBuffer
читателю в качестве упражнения. В некоторых алгоритмах
такой способ заполнения массива, безусловно, является правильным решением, и невредно
его освоить. На случай, если читатель окажется настолько храбрым
(и при этом недостаточно ленивым — вопреки заголовку параграфа),
что действительно возьмется за это упражнение, дам несколько подсказок.
Цикл заполнения массива m)
при помощи DataBuffer должен быть аналогичен циклу чтения матрицы
через DataBuffer, разобранному нами ваше
в алгоритме вычисления средней яркости. С той очевидной разницей,
что теперь массив
Во-первых, разумеется, режим чтения DataBuffer.AccessMode.READ
(параметр метода a.buffer) теперь не годится. Нужно указать режим
DataBuffer.AccessMode.READ_WRITE. Или ничего не указывать,
вызвав метод
Во-вторых, в конце цикла, после заполнения очередного массива
Будьте внимательны! Если вы забудете вызвать READ, в некоторых случаях ваш метод,
тем не менее, будет работать правильно!
Например, если модель памяти mm, использованная для создания матрицы
— это SimpleMemoryModel.
Напоминаю, что в этом случае AlgART-массив является "оболочкой" вокруг обычного Java-массива.
Соответственно, результат метода
Осталось добавить, что в классе PackedBitArrays вы найдете метод,
нужный для заполнения константой упакованного битового массива.
А также, что на этот раз
поддержка беззнаковости для типов byte
и short не потребует специальных усилий
(в отличие от цикла вычисления суммы, где пришлось использовать операторы
&0xFF и &0xFFFF):
вспомните рассуждения о методе setDouble в конце предыдущего параграфа.
Удачи в решении упражнения!
Перейдем к обещанному альтернативному решению задачи. Вот оно:
public static Image2D constant_3(Context context,
@Name("dimX")long dimX, @Name("dimY")long dimY,
@Name("elementType")String elementType, @Name("value")double value)
{
Class<?> eType = typeOf(elementType);
if (dimX < 0)
throw new IllegalArgumentException("Negative dimX");
if (dimY < 0)
throw new IllegalArgumentException("Negative dimY");
long length = Arrays.longMul(dimX, dimY);
if (length == Long.MIN_VALUE)
throw new TooLargeArrayException();
PArray a;
if (eType == boolean.class) {
a = Arrays.nBitCopies(length, value != 0.0);
} else if (eType == char.class) {
a = Arrays.nCharCopies(length, (char)value);
} else if (eType == byte.class) {
a = Arrays.nByteCopies(length, (byte)value);
} else if (eType == short.class) {
a = Arrays.nShortCopies(length, (short)value);
} else if (eType == int.class) {
a = Arrays.nIntCopies(length, (int)value);
} else if (eType == long.class) {
a = Arrays.nLongCopies(length, (long)value);
} else if (eType == float.class) {
a = Arrays.nFloatCopies(length, (float)value);
} else if (eType == double.class) {
a = Arrays.nDoubleCopies(length, (double)value);
} else {
throw new AssertionError("Must not occur");
}
Matrix<? extends PArray> m = Matrices.matrix(a, dimX, dimY);
ImageContext imageContext = context.as(ImageContext.class);
Image2D result = imageContext.newGrayscaleImage2D(imageContext, m);
return result;
}
По сравнению с предыдущим решением, сразу обращает на себя внимание странная вещь: куда-то пропали контексты прерываний и прогресса. Что это — небрежность автора, которому больше не хочется думать о пользователе?
На самом деле, эти контексты стали не нужны.
По очень простой причине: данный метод выполняется практически мгновеннно.
Вернее, не весь метод, а его основная часть, от начала до вызова
newGrayscaleImage2D — метода, находящегося "вне нашей компетенции"
и поставляемого внешним приложением через контекст ImageContext.
На моем компьютере основная часть метода, создающая AlgART-матрицу m,
отрабатывает примерно за 50 микросекунд,
причем независимо от размеров создаваемой матрицы.
Очевидно, контексты прерываний и прогресса при такой скорости просто не нужны.
(Собственно, их и вставить было бы некуда: в этом решении нет ни циклов,
ни методов, принимающих контексты в качестве аргумента.)
В чем секрет такого "супербыстродействия"? Если вы имели дело с методом
nCopies из класса java.util.Collections, вы, наверно, уже догадались.
Итак — добро пожаловать в мир лени!
На более "официальном" языке применяемый механизм называется
ленивые, или отложенные вычисления.
Это значит, что методы nXxxCopies, являющиеся "сердцем" новой реализации,
сами по себе не выполняют заказанную задачу — заполнение константой
некоторой области памяти. Вместо этого они возвращают реализацию интерфейса
PArray, в которой методы доступа всегда возвращают
элементы, равные заказанной константе. Создание экземпляра такой реализации
почти не требует ни времени, ни памяти. Подобные реализации AlgART-массивов
мы будем называть ленивыми массивами.
Как мы увидим далее, ленивые массивы весьма активно используются при работе с библиотеками AlgART.
Очень многие простые задачи можно выразить "лениво" — созданием
подходящей реализации интерфейса PArray и его частных наследников
ByteArray, ShortArray и т.д.
Существуют специальные классы-"заготовки" AbstractByteArray,
AbstractShortArray и т.д., упрощающие написание таких реализаций.
С помощью этих классов, например, можно было бы очень легко создать не массив-"константу",
а массив, элементы которого вычисляются на основе индекса по некоторой формуле.
Как правило, такой подход позволяет сэкономить как время, так и память.
Приятной новостью оказывается то, что не надо писать сложных и занудных циклов.
Не надо также думать о контекстах прерываний и прогресса.
Об этом придется позаботиться клиентскому коду, когда он захочет
что-то проделать с полученным массивом — например, нарисовать изображение
или посчитать по нему среднюю яркость.
На самом деле, как мы увидим далее,
самая типичная операция, применяемая к ленивым массивам — это.... банальное
копирование их в "настоящие" массивы, создаваемые методами модели памяти MemoryModel:
newMatrix, newArray или newUnresizableArray.
А поскольку для этой задачи предусмотрена готовая функция,
"понимающая" контексты и умеющая распараллеливаться на многопроцессорных системах, то труд программиста
по написанию максимально эффективного кода упрощается весьма заметно.
Автор очень порадовался, когда впервые заметил эту особенность созданных им библиотек.
Но мы забегаем вперед.
Если читатель помнит многословные рассуждения
о мощной и со всех сторон замечательной концепции моделей памяти,
у него может возникнуть резонный вопрос — к какой модели памяти
принадлежат массивы, созданные методами nXxxCopies?
Ответ прост: ни к какой. Array и его наследники —
это интерфейсы, и никто не мешает их реализовать, не задумываясь ни о каких
моделях памяти. В данном случае так оно и есть. Более того, это касается
большинства разновидностей ленивых массивов.
Это оправдано. Модель памяти — достаточно сложная абстракция,
касающаяся прежде всего именно хранения данных. А как раз хранить данные
ленивому массиву не надо: он их вычисляет в момент обращения. Кроме того,
реализация модели памяти обязана предоставить методы-фабрики для массивов
всех уровней изменяемости: Array (доступ на чтение),
UpdatableArray (чтение и запись элементов)
и MutableArray (чтение, запись и изменение длины).
Ленивый же массив, как правило, является неизменяемым и не имеет изменяемых аналогов,
реализующих UpdatableArray и тем более MutableArray.
На что еще стоит обратить внимание в нашем примере?
Наверно, на относительно сложные манипуляции с параметрами dimX
и dimY в самом начале метода.
В предыдущих примерах мы просто передавали эти параметры методу newMatrix,
который выполнял все необходимые проверки на корректность.
Но в библиотеках, по крайней мере в текущей версии, нет средств
создать константную матрицу, есть только методы создания линейного массива
Arrays.nXxxCopies... (Стоп! Это утверждение уже устарело —
в конце концов такой метод все же был добавлен в класс Matrices.
Но для учебных целей будем считать, что такого метода нет.)
Матрица создается уже после полного формирования массива при помощью сервисного метода
Matrices.matrix, конвертирующего массив в матрицу.
Чтобы создать массив, нужно вначале вычислить его длину dimX*dimY.
А чтобы вычислить ее без ошибок, нужно тщательно проверить аргументы.
Помните о переполнении! Вы же не хотите, чтобы, скажем, для параметров
dimX=232 и dimY=232
наш код создал массив длины 0 (такая длина получится
при попытке тривиально перемножить эти long-значения).
Поэтому мы заранее проверяем параметры на неотрицательность,
а для перемножения используем специальную функцию Arrays.longMul,
позволяющую обнаружить факт переполнения.
(Да-да, мы проверяем не положительность размеров, а именно неотрицательность! Нулевой размер матрицы
по любой координате в библиотеках AlgART считается корректным.
Имейте это в виду при написании алгоритмов обработки: они должны быть
готовы "справиться" с нулевыми размерами.)
На самом деле конкретно в этом методе мы могли бы обойтись без проверок dimX
и dimY и даже написать "крамольный" оператор
length=dimX*dimY.
Функция nXxxCopies, даже получив "бессмысленную" длину, не сделает
ничего страшного: в худшем случае вернет массив с неправильной длиной,
не затратив при этом никаких ресурсов.
А следующий за этим вызов Matrices.matrix проверит аргументы на корректность.
Однако, хороший тон требует всегда выполнять все проверки вовремя.
Эта привычка поможет вам в других ситуациях — когда, например,
по заданным размерностям будет создаваться реальный, не ленивый массив, занимающий память,
или когда вам понадобится цикл по такому массиву.
Чем раньше вы обнаружите заведомо "дикие" значения аргументов,
тем раньше программа выведет сообщение об ошибке, вместо того чтобы тратить время и память
на обработку полученного массива.
Скажем, если аргументы dimX и dimY
содержат "двоичный мусор" (случайный набор битов, прочитанный по ошибке из какого-нибудь файла),
то их произведение, вычисленное оператором dimX*dimY,
с вероятностью 1/2 окажется неотрицательным, т.е. корректной величиной в качестве
возможной длины массива. Причем, очевидно, астрономически большой.
Если же заранее проверить аргументы, как это сделано в нашем примере,
то сработает либо проверка на отрицательность, либо
— с почти стопроцентной вероятностью — проверка на переполнение:
случайные long значения при перемножении почти наверняка не "уложатся" в 63 бита.
10. Генерация константного изображения: ленимся грамотно
У предыдущего примера есть очевидный недостаток: мы вынуждены были написать
8 веток для всех примитивных типов. Конечно, это неудобно.
Когда мы решали задачу вычисления яркости, от написания 8 веток нас
в конце концов "спасла" библиотечная функция Arrays.sumOf,
которая "понимала" любой примитивный тип элементов.
Нет ли и здесь библиотечной функции, которая поможет нам избавиться
от громоздкого ветвления по типам?
Да, есть. И это несколько неожиданная функция, позволяющая, на самом деле,
решить куда более обширный класс задач, чем генерация константного изображения.
Представляю вам функцию asCoordFuncMatrix,
представитель "великого и ужасного" семейства функций ленивой генерации матриц:
public static Image2D constant_4(Context context,
@Name("dimX")long dimX, @Name("dimY")long dimY,
@Name("elementType")String elementType, @Name("value")double value)
{
Class<?> eType = typeOf(elementType);
Class<? extends PArray> aType = Arrays.type(PArray.class, eType);
Func f = ConstantFunc.getInstance(value);
Matrix<? extends PArray> m = Matrices.asCoordFuncMatrix(f, aType, dimX, dimY);
ImageContext imageContext = context.as(ImageContext.class);
Image2D result = imageContext.newGrayscaleImage2D(imageContext, m);
return result;
}
Ядро нового решения состоит всего из двух строчек:
Func f = ConstantFunc.getInstance(value);
Matrix<? extends PArray> m = Matrices.asCoordFuncMatrix(mm, f, aType, dimX, dimY);
Прежде всего: что такое Func? Это чрезвычайно общий интерфейс из нового для нас пакета
net.algart.math.functions.
Интерфейс Func представляет собой абстрактную математическую
функцию f, получающую на вход произвольный набор вещественных чисел-аргументов
и возвращающую вещественное число-результат.
Основной метод этого интерфейса объявлен так:
public double get(double ...x);
Здесь x — аргументы математической функции f, и метод get должен
вернуть результат применения функции к этим аргументам, т.е.
x).
В пакете net.algart.math.functions предусмотрен ряд реализаций интерфейса
Func, соответствующий наиболее употребительным математическим функциям.
Например, Func.MAX: метод get обрабатывает произвольное число аргументов
и возврашает максимальное из переданных чисел. Или Func.ABS_DIFF: у этой функции
должно быть не менее двух аргументов, и метод get возвращает модуль разности первых двух
|x0-x1|.
(По соглашению, метод get игнорирует лишние аргументы,
если таковые переданы, но имеет право потребовать наличия хотя бы некоторого количества
аргументов, как в случае Func.ABS_DIFF и многих других функций.)
Второй "кирпичик" нового решения — метод asCoordFuncMatrix.
Этот метод создает матрицу, каждый элемент которой является результамом применения заданной функции Func
к координатам (индексам) элемента.
Например, можно создать матрицу, каждый элемент которой будет содержать произведение
координат x и y (трехмерный график гиперболоида).
Или произвольную линейную комбинацию ax+by+c (плоскость в трехмерном пространстве).
Или вообще любую функцию от координат, если вы сами реализуете интерфей Func.
В нашем случае мы применяем простейшую возможную функцию: константу,
т.е. функцию, не имеющую аргументов и всегда возвращающую одно и то же число.
Вещественное значение константы — аргумент метода ConstantFunc.getInstance.
Метод asCoordFuncMatrix, подобно Arrays.nXxxCopies,
возвращает ленивый результат. (На это, кстати, указывает префикс "as":
возвращается представление аргументов, в данном случае функции, а не новая матрица.)
Реализация AlgART-массива, лежащего в основе полученной матрицы,
запоминает переданную функцию,
и при каждой попытке чтения своих элементов вычисляет эту функцию для
соответствующих координат элемента в матрице.
Эта концепция весьма общая и мощная. Реализуя разные варианты интерфейса Func
(что, как правило, очень просто), мы получаем возможность с помощью всего одного
стандартного метода asCoordFuncMatrix выполнять самые разнообразные
операции над координатами. Вплоть до весьма неочевидных!
В частности, если воспользоваться еще одним методом, Matrices.asInterpolationFunc,
выполняющим "обратную" задачу — представление матрицы в виде функции Func —
то можно выполнять произвольные преобразования координат: сжатие, растяжение, повоторы,
более общие аффинные, проективные и любые другие.
Для этого достаточно написать функцию-конвертор, основанную на другой функции и вызывающую ее,
но с соответствующим изменением набора аргументов (в данном случае координат).
Концепция функции несравненно проще понятия AlgART-матрицы (интерфейс Func
почти тривиален), и реализовать его весьма просто.
Более того, в пакете net.algart.math.functions уже
предусмотрено несколько стандартных операторов, выполняющих подобные "превращения" функций,
в частности, линейный оператор LinearOperator, обеспечивающий аффинные преобразования координат,
и проективный оператор ProjectiveOperator, обеспечивающий проективные преобразования координат.
Если превратить матрицу в функцию с помощью Matrices.asInterpolationFunc,
затем к этой функции применить линейный оператор, а полученную функцию передать методу
Matrices.asCoordFuncMatrix, то тем самым мы выполним аффинное преобразование
координат изображения. В частности, поворот или масштабирование.
И не нужно никаких занудных покоординатных циклов.
Но как же метод asCoordFuncMatrix решает проблему разрядности элементов?
Ведь интерфейс Func "работает" исключительно с типом double!
Требуемая разрядность результата задается аргументом aType.
Это не класс примитивного типа вроде byte.class,
а один из базовых интерфейсов ByteArray, ShortArray и т.д.
Например, чтобы получить в результате байтовую матрицу, мы должны указать ByteArray.class.
Точные соглашения относительно этого параметра, а также способ его получения,
мы обсудим чуть позже. А пока сосредоточимся на правилах конверсии типов,
осущeствляемой методом asCoordFuncMatrix.
Общий алгоритм вычисления элементов результирующей матрицы, реализуемый методом
asCoordFuncMatrix, следующий.
Прежде всего, числовые значения координат элемента (long)
конвертируются в тип double путем традиционного приведения типа.
Затем к этим координатам применяется заданная функция Func:
вызывается ее метод get.
Получается некий результат типа double.
Далее этот результат "разумным" образом преобразуется в заказанный примитивный тип,
определяемый параметром aType.
Что значит "разумным"? Подробности, конечно, абсолютно точно сформулированы в JavaDoc,
но читать эту спецификацию довольно утомительно.
Кратко можно сказать, что при конверсии к целым типам производится
усечение до допустимого диапазона с последующим округлением.
(Округление производится простейшим способом, т.е. "в сторону нуля"
— так же, как в операторе v.)
При этом, согласно общему соглашению библиотек AlgART,
типы byte и short считаются беззнаковыми,
с диапазонами изменения 0..255 и 0..65535.
В отличие от операторов приведения типов Java, старшие биты не отбрасываются даже
для "малых" типов byte и short:
вместо этого при необходимости производится усечение до допустимого диапазона.
Например, в нашем случае, если мы "закажем" в качестве результата байтовую матрицу,
то константа value=157.8 будет округлена до 157 (не до 158!),
отрицательные value дадут 0 (черное изображение в обычной интерпретации),
а все value>255 превратятся в максимальную яркость 255 (белое изображение).
Этим поведением, впрочем, можно управлять, используя перегруженную
версию методуа asCoordFuncMatrix с дополнительным
boolean-параметром truncateOverflows, равным false.
(Только что описанное поведение соответствует "умолчательному" значению true.)
Если этот параметр равен false, поведение, в некотором смысле, меняется на противоположное:
усечение до допустимого диапазона по возможности не производится,
а вместо этого "лишние" старшие биты просто отбрасываются.
Подробнее см. JavaDoc. Впрочем, такой режим является экзотикой:
чаще всего наиболее разумным выбором является описанный выше вариант.
Если результат должен иметь тип boolean (битовая матрица), используется простейшее
соглашение, такое же, как в методах getDouble и setDouble.
Вещественное число, точно равное 0.0 (в смысле оператора ==),
преобразуется в 0 (false), все прочие числа — в 1 (true).
Надо полагать, читатель уже испугался.
Ведь все эти сложные преобразования, наверно, расходуют уйму времени!
Неужели, чтобы всего-навсего заполнить матрицу константным значением,
метод asCoordFuncMatrix предусматривает преобразование каждой координаты в double,
применение к двум double метода Func.get
(который их проигнорирует — это же константа)
и округление результата, с проверкой на попадание в диапазон 0..255?
Конечно, нет. Я не зря с самого начала назвал метод asCoordFuncMatrix "великим и ужасным".
Этот метод, как и его многочисленные "родственники" из класса Matrices,
"знает" о большинстве стандартных функций, реализованных в пакете
net.algart.math.functions, и предусматривает для них специальные реализации
своего ленивого результата.
На самом деле, в нашем случае результат метода asCoordFuncMatrix
будет точно такой же, как в нашем предыдущем решении!
Ибо для случая функции ConstantFunc метод asCoordFuncMatrix, не мудрствуя лукаво,
попросту вызывает один из методов Arrays.nXxxCopies
в соответствии с затребованным типом результата и описанными выше правилами конверсии типов.
(Так что идентичность предыдущему решению все-таки неполная.
Раньше наша константа конвертировалась в требуемый тип по более простым правилам,
не обеспечивающим корректного отсечения для 8- и 16-битовых матриц.)
В сущности, в данном случае asCoordFuncMatrix просто слегка сэкономил нам размер кода.
В более полезных алгоритмах asCoordFuncMatrix становится воистину незаменимым.
Ведь он позволяет "превратить" в матрицу любой затребованной разрядности любую математическую функцию,
которая может иметь весьма сложное "происхождение" — скажем, представлять
собой иную функцию с преобразованными координатами, или среднее арифметическое между серией функций,
или что-то еще.
Причем для всех популярных функций и разрядностей будут использованы
мощные и нетривиальные оптимизации, совершенствующиеся от версии к версии.
Мне осталось, как я обещал выше, прокомментировать параметр aType.
И правда, почему передается класс массива, а не примитивный тип элемента?
Ведь так было бы проще.
Вспомните проблему, с которой мы столкнулись при разборе метода newMatrix
во втором примере генерации константного изображения.
Обратите внимание на декларацию метода asCoordFuncMatrix:
public static <T extends PArray> Matrix<T> asCoordFuncMatrix(
Func f, Class<? extends T> requiredType, long ...resultDim)
Такая декларация позволяет безопасно написать, скажем, следующее:
Matrix<ByteArray> m = Matrices.asCoordFuncMatrix(
f, ByteArray.class, dimX, dimY);
Если бы мы передавали примитивный тип, то компилятор не смог бы проверить его соответствие
generics-типу, необходимому в контексте вызова метода — в данном случае
типу переменной m. Это значит, что нам всегда пришлось бы возвращать
Matrix<? extends PArray>, даже когда мы точно знаем разрядность
результата. Конечно, это менее удобно.
В качестве аргумента requiredType
необходимо передать один из 8 конкретных интерфейсов BitArray, CharArray,
ByteArray, ShortArray, IntArray, LongArray,
FloatArray, DoubleArray.
(Однако, это не должен быть наследник UpdatableArray:
ведь полученный ленивый массив или матрица неизменяемы.)
На практике мы часто располагаем экземпляром массива или матрицы общего вида,
скажем, PArray или Matrix<? extends PArray>,
и хотим построить ленивый массив или матрицу с таким же типом элементов.
В этом случае можно получить нужный тип при помощи методов Array.type()
(в случае массива) или Matrix.type(Class) (в случае матрицы).
Наш метод constant_4 получает на входе примитивный тип элементов
(вернее, его строчное описание).
Соответственно, его необходимо преобразовать в соответствующий тип AlgART-массива.
Это делает сервисная функция Arrays.type:
Class<? extends PArray> aType = Arrays.type(PArray.class, eType);
И опять, как в случае с newMatrix, мы "помогаем" механизму
generics, указывая в методе дополнительный аргумент PArray.class,
который должен быть предком возвращаемого класса.
Если бы не этот параметр, мы смогли бы получить в результате, в лучшем случае,
Class<? extends Array> (данный метод
работает с любыми типами элементов, не только примитивными). А это не то,
что требуется в нашем коде.
Аргумент PArray.class метода Arrays.type выполняет еще одну
полезную функцию — он позволяет выбрать, какой уровень изменяемости массива нам нужен.
Для каждого примитивного типа xxx есть 3 базовых
интерфейса, описывающих AlgART-массив: XxxArray,
UpdatableXxxArray, MutableXxxArray.
Так как мы указали PArray.class, но не UpdatablePArray.class
и не MutablePArray.class, то данный вызов вернет один из интерфейсов
первого типа, обеспечивающих только чтение данных.
Как уже говорилось, именно такой вариант и нужен методу asCoordFuncMatrix.
Для сравнения, в интерфейсе Array предусмотрено три отдельных метода,
возвращающих типы базовых интерфейсов всех уровней изменяемости:
type(), updatableType() и mutableType().
11. Генерация константного изображения: сколько можно лениться?
Нет, лень, безусловно, дело благородное и полезное. Работа не волк, в лес она не убежит, стало быть, делать ее надо настолько поздно, насколько возможно. Но реальность, к сожалению, такова, что иногда лень, когда ей увлекаешься, приводит к печальным результатам: работа вовсе не делается в срок. Или же делается гораздо менее эффективно, чем могла бы.
К ленивым массивам и матрицам сие наблюдение относится в полной мере. Правда, не к константным матрицам, которые мы сейчас разбираем: здесь требуемая работа столь ничтожна, что ее практически всегда совершенно смело можно (и нужно) отложить "на потом". Но заполнение константой — учебная задача, выбранная в силу своей тривиальности. В реальности, вероятнее всего, вам придется сталкиваться с более сложными ленивыми массивами, где реальное вычисление все же требует заметных временных затрат.
Поэтому мы уже сейчас, на нашей учебной задаче, покажем, как следует правильно бороться с ленью. В реальных задачах эта техника, называемая актуализацией копированием, применяется повсеместно.
Прежде всего проиллюстрируем проблему на следующем чрезвычайно простом методе.
Правда, этот метод построен на основе asFuncMatrix, а не asCoordFuncMatrix
(другой представитель "великого и ужасного" семейства).
Отличие от asCoordFuncMatrix заключается в том, что аргументами функции
становятся не координаты элемента, а элементы нескольких других матриц, расположенные
на той же самой позиции.
public static Matrix<? extends FloatArray> asLinearCombination(
double a1, double a2, double a3,
Matrix<? extends FloatArray> m1,
Matrix<? extends FloatArray> m2,
Matrix<? extends FloatArray> m3)
{
Func f = LinearFunc.getInstance(0.0, a1, a2, a3);
return Matrices.asFuncMatrix(f, FloatArray.class, m1, m2, m3);
}
Все довольно просто и изящно. Есть три вещественные матрицы m1, m2, m3
и три вещественных коэффициента a1, a2, a3.
Мы создаем линейную функцию
LinearFunc.getInstance (см. JavaDoc).
Мы применяем эту функцию к матрицам m1, m2, m3
и получаем новую ленивую матрицу, обращение к элементам которой
автоматически приводит к чтению соответствующих элементов m1, m2, m3
и вычислению их линейной комбинации с заданными весами.
Казалось бы, все замечательно. "Великий и ужасный" метод asFuncMatrix "знает"
про линейную функцию LinearFuncи, наверное, подберет самый быстрый алгоритм.
И правда, попытка прочитать, скажем, 10000 последовательных элементов полученной матрицы через метод
Array.getData или через технику DataBuffer
приведет к выполнению наиболее разумного кода: цикл поэлементного суммирования (с заданными весами)
трех Java-массивов типа float.
На современных процессорах при использовании хорошей JVM сумма трех вещественных
произведений вычисляется достаточно быстро.
Пусть это будет L тактов.
(В идеальной реализации, активно использующей SIMD-инструкции современных процессоров,
можно добиться очень малых L. Возможно, со временем так и будет, но
в текущей версии библиотек для JVM на моем компьютере получается L порядка сотни тактов.)
Предположим теперь, что клиентский код активно занимается вычислением поэлементных линейных комбинаций между матрицами. Эта ситуация действительно вероятна, скажем, при простых цветовых преобразованиях. Конверсия между цветовыми моделями RGB, YUV, CMYK и некоторыми другими выражается именно через такие линейные функции и может базироваться на приведенном методе.
Допустим, мы применяем метод asLinearCombination к некоторому набору из K матриц,
созданных в самой обычной модели памяти, скажем, SimpleMemoryModel.
Получаются ленивые матрицы: назовем их матрицами 1-го уровня.
Пусть их тоже будет K.
Допустим, далее мы применяем метод asLinearCombination к этим K матрицам 1-го уровня.
Получаются снова ленивые матрицы: назовем их матрицами 2-го уровня.
Пусть их тоже будет K.
И так далее. В случае упомянутых цветовых преобразований, вероятно, мы
имели бы дело с K=3 матрицами, которые многократно преобразовывались бы
в новые тройки матриц по каждому запросу пользователя "сменить цветовую модель".
Давайте подсчитаем: сколько тактов понадобится, чтобы получить каждый элемент матрицы N-го уровня?
Каждый такой элемент получается за L тактов из 3 элементов других матриц. Каждый из них для своего вычисления требует тоже L тактов, опять из 3 элементов других матриц. И так N раз. Итого получается
t = L+3L+9L+...+3N−1L = (3N−1)L/2.
Экспонента. Иначе говоря, начиная с некоторого уровня N доступ к ленивой матрице
станет невозможно медленным. Скажем, при N=20 уже получится
t = 1743 392 200L,
т.е. много секунд (если не минут) на каждый элемент матрицы.
При N=40 речь пойдет о годах на каждый элемент. И так далее.
Вот вам пример злоупотребления ленью: работа, не сделанная вовремя,
делается чрезвычайно неэффективно или не делается вовсе.
В то же время, очевидно, можно полностью вычислить N наборов из K матриц
за небольшое время, т.е.
Причина экспоненты, конечно, в том, что наша ленивая матрица зависит от нескольких входных матриц.
Если бы была зависимость только от одного аргумента,
то вместо тройки в сумме была бы единица, и получилось бы
t = NL.
В этом случае, в принципе, уже нет снижения эффективности.
Однако при больших N и L получается эффект "работы, не сделанной в срок".
Да, все вызовы метода asLinearCombination отработали "мгновено".
Но за это приходится расплачиваться: после 100 таких вызовов ленивая матрица читается примерно
в 100L раз медленнее, чем обычная, не ленивая матрица, созданная в одной
из традиционных моделей памяти. (Блочное чтение обычной матрицы, как правило,
работает со скоростью порядка 1 такта на элемент.)
Если такую матрицу, скажем, понадобится нарисовать (в качестве изображения),
пользователь будет неприятно удивлен чрезвычайно низкой скоростью.
Очевидно, эффект будет усугубляться по мере роста N,
т.е. числа применений метода к его же результатам.
Описанные проблемы не возникают лишь в нашем вырожденном случае, когда функция, представляющая матрицу, вовсе ни от чего не зависит и L чрезвычайно мало (порядка 1 такта).
Что же делать? Не применять красивую технологию asFuncMatrix / asCoordFuncMatrix
нигде, кроме генерации константного массива, и вернуться к громоздким алгоритмам
заполнения результата, основанным на DataBuffer?
Конечно, нет. Все, что надо — время от время актуализировать полученную ленивую матрицу (или массив). Т.е. попросту копировать ее в обычную матрицу (массив), созданную в традиционной модели памяти. Это практически не усложняет алгоритм и сохраняет все преимущества оптимизаций, реализованных в "великом и ужасном" семействе.
Покажем, как это выглядит на примере нашей задачи:
public static Image2D constant_5(Context context,
@Name("dimX")long dimX, @Name("dimY")long dimY,
@Name("elementType")String elementType, @Name("value")double value)
{
ArrayContext arrayContext = new DefaultArrayContext(context);
MemoryModel mm = arrayContext.getMemoryModel();
Class<?> eType = typeOf(elementType);
Class<? extends PArray> aType = Arrays.type(PArray.class, eType);
Func f = ConstantFunc.getInstance(value);
Matrix<? extends PArray> lazy = Matrices.asCoordFuncMatrix(f, aType, dimX, dimY);
Matrix<? extends UpdatablePArray> m = mm.newMatrix(UpdatablePArray.class,
lazy.elementType(), lazy.dimensions());
Matrices.copy(arrayContext, m, lazy);
ImageContext imageContext = context.as(ImageContext.class);
Image2D result = imageContext.newGrayscaleImage2D(imageContext, m);
return result;
}
Теперь основой решения служат не два оператора, как в предыдущем методе, а четыре:
Func f = ConstantFunc.getInstance(value);
Matrix<? extends PArray> lazy = Matrices.asCoordFuncMatrix(f, aType, dimX, dimY);
Matrix<? extends UpdatablePArray> m = mm.newMatrix(UpdatablePArray.class,
lazy.elementType(), lazy.dimensions());
Matrices.copy(arrayContext, m, lazy);
Теперь после вызова asCoordFuncMatrix явно создается новая матрица тех же размеров и типа,
что и ленивая матрица lazy;
при этом, естественно, используется полученная из контекста модель памяти mm.
Метод создания матрицы newMatrix для нас не нов — мы уже разбирали
его выше, во втором варианте решения нашей задачи.
А вот следующий за этим метод Matrices.copy —
настоящая изюминка ленивых технологий.
Можно сказать, "сердце" большинства алгоритмов, основанных на ленивых технологиях AlgART.
В принципе, это метод не делает ничего необычного. Он просто копирует свой третий аргумент-матрицу
во второй аргумент-матрицу. То же самое можно было бы сделать, написав
UpdatableArray предусматривает столь очевидную
операцию, как копирование данных из другого массива.
Но фокус в том, что сейчас, на самом деле,
вся работа алгоритма выполняется именно методом Matrices.copy!
Ведь что такое копирование? Это последовательное чтение блоков данных из
входного AlgART-массива (как правило, в промежуточный Java-массив) и последующая запись
этих блоков в выходной AlgART-массив. А чтение данных из ленивого массива
подразумевает их фактическое вычисление, т.е. исполнение затребованной
функции f для всех элементов.
Как правило, метод Matrices.copy применяется именно для такой цели —
актуализации ленивой матрицы, т.е. создания обычной, быстродоступной копии,
размещенной в реальной памяти.
А это означает выполнение некоторого алгоритма из весьма широкого класса.
Поэтому методу Matrices.copy совершенно необходим контекст,
позволяющий, как минимум, прерываться, показывать проценты исполнения и распараллеливать вычисления.
Таким контекстом, как и в случае разобранной нами ранее
функции Arrays.sumOf,
служит "array-ориентированный" интерфейс ArrayContext,
передаваемый первым параметром.
Именно ради контекста мы применяем метод Matrices.copy,
а не "низкоуровневый" UpdatableArray.copy.
Действительно, метод Matrices.copy достаточно "умен".
Он поддерживает все перечисленные возможности: прерываться, показывать проценты выполнения
и распараллеливать вычисления. Распараллеливание достигается путем разбиения
копируемого массива (лежащего в основе матрицы) на несколько блоков:
эти блоки копируются в параллельных потоках.
Получается удивительная вещь. Если алгоритм можно выразить в виде
создания ленивого массива или матрицы, то все решение сводится
к реализации необходимой функции Func
и вызову пары методов типа asCoordFuncMatrix / asFuncMatrix
и copy.
При этом автоматически достигается прерываемость, показ процентов и прочие "прелести",
заложенные в метод copy — скажем, его умение выдавать
в лог скорость своей работы.
Много ли алгоритмов сводятся к построению ленивого массива или матрицы?
Гораздо больше, чем может показаться на первый взгляд.
Ведь упоминавшиеся до сих пор методы asCoordFuncMatrix
и asFuncMatrix — лишь частный случай
воплощения общей идеи: построения ленивого массива (выполняющего отложенные вычисления) путем реализации
8 базовых интерфейсов ByteArray, ShortArray и пр.,
описывающих AlgART-массив примитивного типа в варианте "только чтение".
Есть и другие методы, подобные им.
Так, методы Arrays.asShifted и Matrices.asShifted
возвращают ленивое представление исходного массива (матрицы),
циклически сдвинутое на сколько-то позиций.
Например, сдвигая массив на 1 элемент вправо или влево,
можно получить представление массива, в котором на позиции k
будут находиться элементы номер k−1 или k+1 исходного массива.
Совмещая такое представление с asFuncMatrix, можно, скажем,
"сгладить" изображение путем усреднения нескольких соседних элементов матрицы.
Существует также метод asConcatenation,
возвращающий (ленивым образом) результат "сцепления" нескольких массивов.
(Обратная задача — выделение подмассива —
реализована в стандартных методах исходного интерфейса Array,
причем опять же ленивым образом.)
Подобных методов, возвращающих ленивый массив для решения вычислительной задачи,
можно создать очень много.
В результате получается, что весьма широкий класс алгоритмов
можно выразить через создание ленивого массива (или матрицы) с последующей актуализацией
методом copy — или разбить на подзадачи, выражаемые таким образом.
Скажем, сюда относятся разнообразные методы фильтрации изображений,
как линейные, так и нелинейные, различные геометрические преобразования изображений
или трехмерных матриц,
алгебраические операции над обычными двумерными матрицами и одномерными векторами, и т.д.
Поэтому методы Matrices.copy и Arrays.copy действительно
часто оказываются "сердцем" алгоритмических приложений.
Если приложение, обрабатывающее AlgART-матрицы или массивы, о чем-то "задумалось",
это с большой вероятностью может означать, что в данный момент исполняется метод
Matrices.copy или Arrays.copy,
"прогоняя" через себя некоторый алгоритм, реализованный в ленивой технологии.
Итак, Arrays.copy / Matrices.copy —
методы, предназначенные для актуализации ленивых вычислений —
являются основным способом преодоления (вернее сказать, использования)
заложенной в библиотеки лени.
Создавая ленивые массивы или матрицы, следует своевременно их актуализировать.
Но что считать "своевременным"? Допустимы ли вообще методы,
которые, подобно предыдущему нашему примеру constant_4,
возвращают ленивый результат?
Или конечный результат всегда следует актуализировать, как мы сделали это сейчас?
Есть ситуация, когда ответ очевиден. А именно, генерация
константы, когда в качестве функции применяется
ConstantFunc. В данном случае никакого смысла актуализация не имеет,
так как скорость доступа к элементам построенной ленивой матрицы будет
не ниже, а, может быть, даже и выше, чем в случае обычной матрицы.
Пример, разбираемый нами сейчас, нарушает эту рекомендацию —
исключительно в учебных целях, чтобы показать, как следует действовать
в более сложных случаях.
Кроме того, надо заметить, что константный массив, а также более изощренные
ленивые массивы, которые можно построить путем наследования абстрактных классов
AbstractByteArray, AbstractShortArray и пр. —
единственная разновидность массивов, вообще не ограниченных в размере
никакими физическими пределами вроде объема диска.
Если вам действительно нужны подобные сверхбольшие массивы
(скажем, длиной Long.MAX_VALUE=263−1 элементов),
то никакая актуализация попросту невозможна.
Для прочих случаев я не знаю универсального рецепта.
Лично я считаю, что public-методы, возвращающие ленивый массив или матрицу, в принципе допустимы —
если в спецификации четко сформулировано, что происходит при обращениях к их элементам
и насколько эта операция дорогостоящая.
Но если есть вероятность, что к полученному массиву или матрице
будет нужен интенсивный доступ — например, что массив будет передан расчетному алгоритму,
требущему многократных "проходов" по нему —
то лучше заранее предоставить метод-"партнер", выполняющий те же действия,
но с завершающей актуализацией.
Так, наш текущий метод constant_5 (если бы он возвращал
Matrix, а не Image2D) был бы подобным "партнером"
для constant_4.
На практике, конечно, код такого "партнера" обычно куда проще:
он просто вызывает "ленивый" метод и применяет к его результату
Matrices.copy или Arrays.copy.
Кроме того, метод, возвращающий ленивый результат (кроме константы),
лучше начинать с префикса as —
это ясно дает понять, что выполнение метода еще не заканчивает вычисления,
а лишь возврашает некое ленивое представление входных матриц или массивов.
12. Генерация константного изображения: да будет цвет!
В этом параграфе мы придадим законченность нашему методу, "научив" его возвращать цветное изображение, все точки которого имеют заданный цвет. И это будет наш последний пример, решающий сравнительно тривиальную задачу.
Вот "цветная" версия предыдушего метода:
public static Image2D constant_6(Context context,
@Name("dimX")long dimX, @Name("dimY")long dimY,
@Name("elementType")String elementType,
@Name("red")double r, @Name("green")double g, @Name("blue")double b)
{
ArrayContext arrayContext = new DefaultArrayContext(context);
MemoryModel mm = arrayContext.getMemoryModel();
Class<?> eType = typeOf(elementType);
long[] dim = new long[] {dimX, dimY};
Class<? extends PArray> aType = Arrays.type(PArray.class, eType);
Matrix<? extends PArray>
lazyr = Matrices.asCoordFuncMatrix(ConstantFunc.getInstance(r), aType, dim),
lazyg = Matrices.asCoordFuncMatrix(ConstantFunc.getInstance(g), aType, dim),
lazyb = Matrices.asCoordFuncMatrix(ConstantFunc.getInstance(b), aType, dim);
Matrix<? extends UpdatablePArray> mr = mm.newMatrix(UpdatablePArray.class, eType, dim);
Matrices.copy(arrayContext.part(0.0, 1.0 / 3.0), mr, lazyr);
Matrix<? extends UpdatablePArray> mg = mm.newMatrix(UpdatablePArray.class, eType, dim);
Matrices.copy(arrayContext.part(1.0 / 3.0, 2.0 / 3.0), mg, lazyg);
Matrix<? extends UpdatablePArray> mb = mm.newMatrix(UpdatablePArray.class, eType, dim);
Matrices.copy(arrayContext.part(2.0 / 3.0, 1.0), mb, lazyb);
ImageContext imageContext = context.as(ImageContext.class);
Image2D result = imageContext.newRGBImage2D(imageContext, mr, mg, mb);
return result;
}
В основном, все отличия вполне очевидны. Вместо одной константы value
метод получает три константы r, g и b,
описывающие красную, зеленую и синюю компоненты желаемого цвета.
Соответственно, вместо одной матрицы мы строим три ленивых матрицы
lazyr, lazyg, lazyb,
актуализируем их, копируя в обычные матрицы mr, mg, mb,
после чего строим на основе mr, mg, mb изображение
при помощи метода newRGBImage2D контекста ImageContext.
Как и в предыдущем примере, константные ленивые матрицы лучше было бы вообще не актуализировать,
а передать непосредственно методу newRGBImage2D.
Но в учебных целях мы все же выполняем актуализацию.
Почти в любых более сложных задачах это было бы полезно.
В чем же заключаются наши "учебные цели", раз все так просто? Не лучше ли было бы убрать актуализацию и получить "вполне безупречный" метод?
Учебные цели касаются именно актуализации. Заметьте: это первый наш метод,
в котором надо выполнить несколько библиотечных методов, работающих с контекстами.
Здесь мы три раза вызываем метод актуализации Matrices.copy.
И мы видим нечто новое: использование метода контекста part.
Что это такое и зачем это нужно?
Представьте себе, что получится, если мы напишем более просто:
Matrix<? extends UpdatablePArray> mr =
mm.newMatrix(UpdatablePArray.class, eType, dim);
Matrices.copy(arrayContext, mr, lazyr);
Matrix<? extends UpdatablePArray> mg =
mm.newMatrix(UpdatablePArray.class, eType, dim);
Matrices.copy(arrayContext, mg, lazyg);
Matrix<? extends UpdatablePArray> mb =
mm.newMatrix(UpdatablePArray.class, eType, dim);
Matrices.copy(arrayContext, mb, lazyb);
Разумеется, все будет работать. Контекст, переданный методу copy,
как и раньше, позволит обеспечить распараллеливание, прерываемость и даже,
если вызвающее приложение позаботится об этом, вывод процентов исполнения...
Стоп, а какие будут показаны проценты?
Конечно же, неверные! Каждый из трех методов copy передаст контексту
ArrayContext (и далее, через него, контексту прогресса
ProgressUpdater, поддерживаемому приложением)
информацию о процентах своего исполнения.
Которые в каждом из трех методов будут увеличиваться от 0% до 100%.
Если пользователь программы нажмет кнопку, запускающую наш алгоритм,
он, вероятнее всего, увидит, как индикатор выполнения
три раза "пробежит" от начальной позиции до конечной.
Вряд ли это можно считать правильным поведением.
Проблема, как легко видеть, имеет общий характер.
Почти всякая реальная задача, исполняемая по нажатию одной кнопки пользователем,
состоит из каких-то подзадач. Те — из своих подзадач, и так далее.
Лишь на самом нижнем уровне мы приходим к циклам обработки DataBuffer
или библиотечным вызовам вроде sumOf или copy,
где мы имеем возможность указать контексту процент готовности цикла или метода copy.
Какой-нибудь сложный фильтр, удаляющий шум из изображения, может
в конечном счете выражаться через сотни вызовов Matrices.copy,
каждый из которых решает лишь очень маленькую подзадачу полного алгоритма.
Очевидно, нужно что-то вроде иерархии контекстов прогресса,
чтобы изменение процентов готовности от 0% до 100% в "дочернем" контексте
означало лишь некоторое приращение процента готовности в его "родителе".
Именно это и обеспечивает метод part интерфейса ArrayContext.
Методу part передаются два параметра типа double: fromPart
и toPart. Результатом метода является новый, "дочерный" контекст ArrayContext.
Все методы этого контекста тривиальным образом вызывают соответствующие методы исходного контекста,
за одним-единственным исключением. А именно: когда вызывается метод updateProgress
(аналог такого же метода ProgressUpdater), этот метод корректирует переданную
ему информацию о процентах исполнения так, чтобы диапазон изменения процентов
0.0..1.0 преобразовался в диапазон fromPart..toPart.
(Метод updateProgress описывает процент готовности вещественным числом от 0.0 до 1.0,
а не от 0 до 100.)
В нашем примере в результате такой трансформации получается, что первый метод copy
сообщает исходному контексту информацию о процентах исполнения, меняющихся
не от 0% до 100%, а от 0% до ~33.3% (toPart=1.0/3.0).
Второй метод copy сообщает о процентах исполнения, меняющихся
от ~33.3% (fromPart=1.0/3.0) до ~66.6% (toPart=2.0/3.0),
и, наконец, третий метод copy —
о процентах от ~66.6% (fromPart=2.0/3.0) до 100% (toPart=1.0).
Аналогичное преобразование можно произвести и с контекстом, описываемым более общим
интерфейсом Context. Для этого служит специальный класс SubtaskContext.
Прямым аналогом вызова
Заметим, что при вычислениях аргументов метода part следует соблюдать
известную аккуратность. Этот метод генерирует исключение IllegalArgumentException,
если его параметры не удовлетворяют точным неравенствам
x>=0.0 и x<=1.0.
Вещественные вычисления обычно выполняются неточно,
и при расчете "крайних" значений 0.0 и 1.0 легко допустить ошибку.
Скажем, было бы неправильно завести в методе константу p=1.0/3.0
и вызывать метод part как-нибудь так:
part(k * p, (k + 1) * p)
где k — целое число от 0 до 2. Число p=1/3
представляется в компьютере неточно, и нет никаких гарантий, что величина
k=2 не окажется
чуть-чуть больше 1.0.
Если это произойдет, метод part выдаст IllegalArgumentException.
(По секрету: на самом деле в "самом переносимом языке мира", Java, в данной ситуации гарантии есть,
но лучше вам об этом не знать. При других способах расчета toPart вам может не повезти.
Автору однажды не повезло — одна из причин, по которым я остановился на этой детали.)
Чтобы избежать этих неприятностей, лучше всего проверять случаи,
когда параметр fromPart может оказаться равен 0.0 или
когда toPart может оказаться равен 1.0,
и в этих случаях передавать точные double-константы 0.0 и 1.0.
А поскольку подобная проблема возникает регулярно, то у метода part имеется специальная
перегруженная версия:
public ArrayContext part(long from, long to, long total);
Эта версия делает именно то, что мы хотели сделать чуть выше, только аккуратно: а именно, вызывает
part((double)from / (double)total, to==total ? 1.0: (double)to / (double)total);
На этом мы заканчиваем разбор тривиальных задач обработки AlgART-матриц и массивов. Накопленных знаний уже достаточно, чтобы грамотно решать сравнительно сложные и практически полезные задачи.