Книга «Стильный Java. Код, который работает всегда и везде»

Привет, Хаброжители! В современном мире разработки успешность приложения уже не определяется параметром «просто работает». Хороший программист должен знать возможности языка, практические приемы проектирования и платформенные средства для достижения максимальной производительности и жизнеспособности программ. Эта книга написана для разработчиков, которые хотят создавать качественный софт. Затронуты все ключевые показатели ПО: скорость, затраты памяти, надежность, удобочитаемость, потоковая безопасность, универсальность и элегантность. Реальные задачи и прикладные примеры кода на Java помогут надежно усвоить концепции. Пройдя все этапы создания центрального проекта книги, вы сможете уверенно выбрать правильный путь оптимизации собственного приложения.

4.4. Черная дыра [Memory4]

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

Я предлагаю хранить и индексы, и объемы воды в одном массиве. Первые — целые числа, вторые — вещественные. Какой тип должен иметь массив? В голову приходят два варианта, приводящие к одинаковым затратам памяти (4 байта на резервуар):

1. Массив типа int, в котором содержимое ячейки должно интерпретироваться как объем воды и его можно делить на постоянную величину (фактически реализация чисел с фиксированной точкой). Например, если все объемы будут делиться на 10 000, они будут определяться с 5 цифрами в дробной части.

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

В листинге 4.12 я выбрал второй вариант, который выглядит проще, хотя, как вы вскоре увидите, у него есть свои недостатки.

Листинг 4.12. Memory4: поле — конструктор не нужен

public class Container {
   private static float[] nextOrAmount;

Как при чтении содержимого ячейки отличать следующие значения от объемов воды? Можно воспользоваться доисторическим трюком и закодировать один из двух случаев положительными числами, а другой — отрицательными. Положительное число можно будет интерпретировать как индекс следующего резервуара, а отрицательное число будет обозначать объем воды в этом резервуаре с обратным знаком. Например, если nextOrAmount[4] == -2.5, это означает, что резервуар 4 является последним в своей группе (или изолированным) и содержит 2,5 единицы воды.

Есть небольшая проблема: в формате с плавающей точкой «положительный нуль» не отличается от «отрицательного». Эту неоднозначность можно устранить, считая, что нуль всегда обозначает объем, и никогда не использовать его в качестве индекса следующего резервуара. Чтобы не терять нулевую ячейку, увеличьте все индексы, хранящиеся в массиве, на 1 (смещение). Например, если за резервуаром 4 следует резервуар 7, nextOrAmount[4] == 8.

На рис. 4.8 представлено распределение памяти этой реализации после выполнения первых трех частей основного сценария. Значение 2,0 в первой ячейке — смещенный указатель на следующий резервуар — означает, что первый резервуар (a) связан с резервуаром под номером 1 (b). Значение –4,0 в третьей ячейке указывает, что c является последним резервуаром в своей группе, а каждый резервуар в этой группе содержит 4,0 единицы воды.


В листинге 4.13 представлен код метода getAmount. Он переходит к следующим значениям, как в связанном списке (вторая строка), пока не найдет последний резервуар в списке, который распознается по отрицательному или нулевому значению. Это значение представляет собой объем воды в резервуаре с обратным знаком. Обратите внимание на –1 в конце третьей строки кода (удаление смещения) и знак минус после return для возврата объема воды с правильным знаком.

У float, использующегося для представления индексов массивов, есть еще один скрытый недостаток. Теоретически индексы массивов могут охватывать весь диапазон неотрицательных 32-разрядных целых чисел: от 0 до 2^31 ‒ 1 (приблизительно 2 млрд, также обозначается Integer.MAX_VALUE). Формат с плавающей точкой имеет существенно больший диапазон, но с изменяющимся разрешением. Расстояние между двумя соседними числами изменяется в зависимости от размера (рис. 4.9). Для малых значений (близких к нулю) следующее число с плавающей точкой расположено чрезвычайно близко. Для больших значений следующее число с плавающей точкой находится дальше. В какой-то момент расстояние превышает 1, и ряд чисел с плавающей точкой начинает пропускать целочисленные значения.

Например, из-за расширенного диапазона тип float способен точно представить число 1E10 (10^10 или 10 млрд), чего не позволяет сделать целочисленный тип. Оба типа могут представить значение 1E8 (100 млн), но если переменная float содержит 1E8, то при увеличении на 1 она останется равной 1E8. У чисел с плавающей точкой не хватает значащих цифр для представления числа 100 000 001.

Расстояние между 1E8 и следующим числом типа float превышает 1. Хотя число 1E8 входит в диапазон чисел float, оно не входит в непрерывный целочисленный диапазон float, то есть в диапазон целых чисел, которые могут быть представлены точно и без разрывов. В табл. 4.7 приведены непрерывные целочисленные диапазоны для большинства числовых примитивных типов.

Неожиданный вопрос 5
Выберите тип данных и исходное значение переменной x таким образом, чтобы цикл
while (x+1==x) {} выполнялся бесконечно.

Использование float в качестве индекса массива — не лучшая идея. Оно сработает, только если индексы остаются в непрерывном целочисленном диапазоне, границы которого заметно меньше Integer.MAX_VALUE. Чтобы уточнить, насколько меньше, нужно учесть, что неотрицательные целые числа содержат 31 значащий бит, тогда как неотрицательные числа с плавающей точкой имеют только 24 значащих бита. Так как 31 – 24 = 7, порог для float в 2^7 = 128 раз меньше Integer.MAX_VALUE.

Если создать более 2^24 резервуаров, начнут происходить странные вещи и потребуется включить проверки времени выполнения в метод newContainer. Но эта глава посвящена потреблению памяти, поэтому будем придерживаться плана и оптимизировать только одно свойство кода за раз, а с факторами надежности подождем до главы 6. Остальной исходный код Memory4 можно найти в репозитории (https://bitbucket.org/mfaella/exercisesinstyle).

4.4.1. Временная сложность и затраты памяти

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

За крайнюю экономию памяти приходится платить замедлением выполнения, как видно из табл. 4.9. Методы connect и addWater должны вычислять размер группы по заданному индексу произвольного резервуара группы. Для этого приходится возвращаться к первому резервуару группы, а затем обходить весь виртуальный список резервуаров для определения длины. Найти первый резервуар в группе не так просто, ведь это единственный элемент группы, на который не ссылается другой указатель. Чтобы найти его, необходимо обойти список в обратном порядке, что требует квадратичного времени.

4.5. Баланс затрат памяти и времени

Начнем с краткой сводки требований по памяти для четырех версий резервуаров из этой главы и сравним их с реализацией Reference из главы 2.

Как видно из табл. 4.10, разумный выбор коллекций и способов кодирования позволяет добиться значительной экономии памяти. Чтобы выйти за рамки, представленные служебными затратами объектов, нам пришлось нарушить API из главы 1 и идентифицировать резервуары целыми числами вместо объектов резервуаров. Все реализации этой главы также жертвуют удобочитаемостью — и, как следствие, удобством сопровождения. Стремление к эффективности использования памяти ведет к использованию низкоуровневых типов (в основном массивов) вместо высокоуровневых коллекций и специальных кодировок, вплоть до применения значений float в качестве индексов массивов в Memory4. Во многих рабочих средах такие приемы считаются нежелательными, но им находится место в узкоспециализированных ситуациях с жесткими ограничениями по памяти, как в некоторых встроенных системах, или с необходимостью хранить огромные объемы данных в основной памяти.


Как упоминалось в главе 1, эффективности по затратам памяти и времени часто вступают в конфликт. В этой и предыдущей главах были приведены как положительные, так и отрицательные примеры такого рода. На рис. 4.10 изображены требования к затратам памяти и времени для семи реализаций из этих глав, а также реализации Reference из главы 2. Вспомните, что в Memory3 и Memory4 заметная экономия памяти достигается за счет изменения API резервуаров.

Самыми сложными реализациями из двух глав являются те, которые максимизируют соответствующее свойство программного кода: Speed3 обеспечивает максимальную скорость выполнения, а Memory4 — максимальную эффективность использования памяти. Кроме того, при сокращении требований к памяти до 4 байт на резервуар в Memory4 временная сложность повышается до квадратичной. Этого следует ожидать — подобные компромиссы типичны при выборе баланса между временем и затратами памяти.

С другой стороны, Speed3 демонстрирует отличную эффективность: затраты памяти близки к Memory2 — минимуму, которого нам удалось добиться без отказа от стандартного API. Следовательно, в большинстве ситуаций при отсутствии жестких ограничений по памяти следует выбирать Speed3.

4.6. А теперь совсем другое

Пришло время применить методы экономии памяти в другом сценарии: работе с мультимножествами. Мультимножеством называется множество, которое может содержать дубликаты. Так, мультимножество {a, a, b} отлично от {a, b}, но неотличимо от {a, b, a}, потому что порядок элементов не важен.

Спроектируем реализацию мультимножества MultiSet, которая эффективно расходует память и поддерживает следующие методы:

• public void add(T elem) — вставляет elem в мультимножество;

• public long count(T elem) — возвращает количество вхождений elem в мультимножество.

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

1. Предположим, вы вставляете n разных объектов c возможностью многократной вставки одного объекта и всего есть m вставок (то есть m по крайней мере не меньше n). Сколько байт потребуется для их хранения?

2. Какова временная сложность операций add и count в вашей реализации?

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

4.6.1. Малое количество дубликатов

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

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

Реализация должна выглядеть примерно так:

public class MultiSet<T> {
   private List<T> data = new ArrayList<>();
   public void add(T elem) {
       data.add(elem);
   }
   public long count(T elem) {
      long count = 0;
      for (T other: data) {
         if (other.equals(elem)) {
             count++;
         }
      }
      return count;
   }
}

С новой библиотекой потоков можно переписать метод count в однострочной реализации:

public long count(T elem) {
   return data.stream().filter(x -> x.equals(elem)).count();
}

Метод add выполняется за постоянное (амортизированное) время (раздел 3.3.5), а count — за линейное время. Затраты памяти после m вставок n разных объектов составят 56 + 4 × m байт (не зависит от n):

• 12 байт — служебная информация объекта MultiSet;

• 4 байта — ссылка на ArrayList;

• 40 байт — минимальная коллекция ArrayList (табл. 4.4);

• 4 × m байт для ссылок на элементы мультимножества.

4.6.2. Большое количество дубликатов

Если дубликаты встречаются часто, лучше использовать два массива: для хранения самих объектов и для хранения количества повторений каждого объекта. Если вы знакомы с библиотекой коллекций, то догадаетесь, что эта задача идеально подходит для Map. Однако обе стандартные реализации Map (HashMap и TreeMap) представляют собой связанные структуры и занимают намного больше памяти, чем две коллекции ArrayList.

В итоге у вас получится нечто такое:

public class MultiSet<T> {
   private List<T> elements = new ArrayList<>();
   private List<Long> repetitions = new ArrayList<>();
   ...

Остаток реализации я оставлю вам для самостоятельной работы. Проследите, чтобы i-й элемент repetitions (который вы получаете от repetitions.get(i)) содержал количество повторений объекта elements.get(i).

Для ускорения выполнения вставка должна проверять первый массив и определять, что вставляется: новый объект или дубликат. В худшем случае оба метода add и count будут выполняться за линейное время.

Затраты памяти после m вставок n разных объектов составят 100 + 28 × n байт (не зависит от m):

• 12 байт — служебная информация объекта MultiSet;

• 2 × 4 байта — ссылки на две коллекции ArrayList;

• 2 × 40 байт — две минимальные коллекции ArrayList;

• 4 × n байт для хранения ссылок на уникальные элементы (первый массив);

• (4 + 20) × n байт для хранения счетчиков Long на уникальные элементы (второй массив). (Каждый объект Long занимает 12 + 8 = 20 байт.)

Решение с двумя массивами наиболее эффективно по памяти, если 100 + 28 × n < 56 + 4 × m, то есть в среднем каждый объект представлен в коллекции не менее 7 раз (m > 11 + 7 × n).

4.7. Реальные сценарии использования

В главах 3 и 4 рассматривались два основных фактора, влияющих на эффективность алгоритма: время и затраты памяти. Было показано, что задача может быть решена разными способами (например, с использованием ArrayList вместо HashSet для хранения групп резервуаров). Выбор того или иного метода обычно приводит к компромиссу между эффективностью по времени и затратам памяти. Лучший выбор зависит от контекста решаемой задачи. Рассмотрим пару сценариев с высокой эффективностью по затратам памяти.

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

• Смартфоны в наши дни оснащаются почти таким же объемом памяти, как стандартные портативные компьютеры. Однако когда компания Google разрабатывала ОС Android в начале 2000-х годов, ситуация была иной. Система Android также должна была работать на устройствах с существенно меньшими объемами памяти, чем у современных телефонов. По этой причине в API Android можно найти следы усилий по экономии памяти.

Например:

— Пакет android.util содержит несколько классов, предоставляющих альтернативы для стандартных коллекций Java с меньшими затратами памяти. Например, SparseArray — эффективная по памяти реализация карты (или ассоциативного массива), связывающей целочисленные ключи с объектами. (В упражнении 2 этой главы вам будет предложено проанализировать этот класс.)

— Все классы Android, относящиеся к работе с графикой, используют для представления координат, углов поворота и т. д. значения float с одинарной точностью вместо значений double. Пример можно найти в классе android. graphics.Camera.

• XML широко используется для обмена данными между разнородными системами. В стандартной схеме взаимодействия приложение разбирает XML, сохраняет контент в реляционной базе данных и, наконец, сохраняет XML в виде BLOB (binary large object). Далее бизнес-логика и запросы выполняются с использованием реляционной схемы, и события загрузки исходной разметки XML происходят редко. То есть лучше проектировать процесс, эффективный по затратам памяти, который сжимает XML-документы перед их сохранением в базе данных.

Об авторе

Марко Фаэлла — преподаватель computer science в Неаполитанском университете имени Фридриха II (Италия). Помимо академических исследований в области computer science Марко увлеченно занимается преподаванием и программированием. Последние 13 лет он ведет курсы про-граммирования повышенной сложности, а также является автором учебника для желающих получить сертификат Java-разработчика и видеокурса по потокам в языке Java.

Более подробно с книгой можно ознакомиться на сайте издательства
» Оглавление
» Отрывок

Для Хаброжителей скидка 25% по купону — Java

По факту оплаты бумажной версии книги на e-mail высылается электронная книга.