[Java, Профессиональная литература] Книга «Стильный Java. Код, который работает всегда и везде»
Автор
Сообщение
news_bot ®
Стаж: 6 лет 9 месяцев
Сообщений: 27286
оригинал
Привет, Хаброжители! В современном мире разработки успешность приложения уже не определяется параметром «просто работает». Хороший программист должен знать возможности языка, практические приемы проектирования и платформенные средства для достижения максимальной производительности и жизнеспособности программ. Эта книга написана для разработчиков, которые хотят создавать качественный софт. Затронуты все ключевые показатели ПО: скорость, затраты памяти, надежность, удобочитаемость, потоковая безопасность, универсальность и элегантность. Реальные задачи и прикладные примеры кода на Java помогут надежно усвоить концепции. Пройдя все этапы создания центрального проекта книги, вы сможете уверенно выбрать правильный путь оптимизации собственного приложения.
О книге
SPL
Главная идея этой книги — показать мышление опытного разработчика с помощью сравнения свойств программного кода (или нефункциональных требований).
Схема на с. 12 связывает содержимое книги с широким спектром знаний, необходимых профессиональному разработчику. Изучение Java требует знакомства с классами, методами, полями и т.д. (здесь база не рассматривается). Далее освоение языка идет по трем путям:
- Путь языка программирования — изучение расширенных возможностей языка (таких, как обобщения и многопоточность).
- Путь алгоритмов — изучение базовых теоретических принципов, стандартных алгоритмов и структур данных.
- Путь технологии программирования — изучение принципов проектирования и передовых методов, упрощающих управление сложностью, особенно в крупных проектах.
В книге рассмотрены все эти области, но в несколько нетрадиционном виде. Вместо того чтобы освещать разные аспекты по отдельности, я смешал их в соответствии с потребностями определенной главы.
Каждая глава посвящена одному свойству программного кода, такому как скорость выполнения или удобочитаемость. Они не только важны и распространены, но и могут осмысленно применяться к малым кодовым единицам (например, к отдельному классу). Я постарался сосредоточиться на общих принципах и приемах программирования, а не на конкретных инструментах. В ряде случаев я ссылался на инструменты и библиотеки, которые помогут оценить и оптимизировать рассматриваемые свойства.
Структура книги
SPL
Ниже приведен краткий список глав и свойств кода, которые в них рассматриваются. Не пренебрегайте упражнениями в конце каждой главы. Они сопровождаются подробными решениями и завершают материал главы применением описанных методов в разных контекстах.
Глава 1. В первой главе описана задача программирования, которую мы будем решать (класс для представления резервуаров с водой). Здесь приведена наивная реализация, которая демонстрирует типичные заблуждения неопытных программистов.
Глава 2. Подробное описание эталонной реализации, обеспечивающей хороший баланс разных свойств.
Глава 3. Сосредоточившись на эффективности по времени, мы улучшим время выполнения эталонной реализации более чем на два порядка (в 500 раз) и увидим, что разные сценарии практического использования вынуждают нас идти на разные компромиссы.
Глава 4. Проведем эксперименты с эффективностью по затратам памяти и увидим, что по сравнению с эталонной реализацией затраты памяти сокращаются более чем на 50 % при использовании объектов и на 90 % — при отказе от использования отдельного объекта для каждого резервуара.
Глава 5. Постараемся достичь надежности за счет контрактного проектирования и усиления эталонного класса проверками во время выполнения, а также с помощью тестовых условий, основанных на контрактах методов и инвариантах классов.
Глава 6. Постараемся достичь надежности за счет модульного тестирования с помощью методов проектирования и выполнения набора тестов, а также рассмотрим метрики и средства тестового покрытия кода.
Глава 7. Произведем рефакторинг эталонной реализации для применения рекомендуемых методов создания чистого самодокументируемого кода.
Глава 8. В контексте конкурентности и потокобезопасности вспомним основные понятия синхронизации потоков и выясним, почему в нашем текущем примере необходимо применять нетривиальные механизмы для предотвращения взаимных блокировок и состояния гонки.
Глава 9. Рассмотрим возможность повторного использования: обобщим эталонный класс, чтобы он мог применяться в других приложениях с аналогичной общей структурой.
Приложение А. При обсуждении лаконичности кода я представлю компактную реализацию примера, объем исходного кода которого составит всего 15 % от эталонной версии. Конечно, получится заумный код, за который вас запинают на любом сеансе рецензирования кода.
Приложение Б. Наконец, мы соберем воедино все свойства и построим финальную версию класса, представляющего резервуары.
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 высылается электронная книга.
===========
Источник:
habr.com
===========
Похожие новости:
- [Open source, *nix, Виртуализация, Карьера в IT-индустрии] Edge-сервера, терминальные сеансы с помощью Linux-команды script и 5 подходов к облачной автоматизации
- [Разработка веб-сайтов, JavaScript, SvelteJS] Переиспользуемый компонент Svelte: чтобы никому не было больно
- [Программирование, Java] Вы часто используете null? А он у нас в спецификации
- [] IntelliJ IDEA Conf: отмечаем два десятилетия продуктивной разработки
- [Тестирование IT-систем, JavaScript] Перестаньте использовать Page Objects (РО) и начните использовать App Actions (перевод)
- [JavaScript, Искусственный интеллект, Логические игры] Пишем ИИ для игры Гомоку (5 в ряд)
- [JavaScript, Программирование, Учебный процесс в IT] Решение забавной задачки на JavaScript (перевод)
- [Разработка веб-сайтов, JavaScript, Программирование, .NET] Рабочий прототип секретного мессенджера
- [Алгоритмы, Профессиональная литература] Книга «Совершенный алгоритм. Алгоритмы для NP-трудных задач »
- [JavaScript, C++, Kotlin, TypeScript] Сага о типизации и тайпчекинге для JavaScript
Теги для поиска: #_java, #_professionalnaja_literatura (Профессиональная литература), #_java, [url=https://torrents-local.xyz/search.php?nm=%23_blog_kompanii_izdatelskij_dom_«piter»&to=0&allw=0&o=1&s=0&f%5B%5D=820&f%5B%5D=959&f%5B%5D=958&f%5B%5D=872&f%5B%5D=967&f%5B%5D=954&f%5B%5D=885&f%5B%5D=882&f%5B%5D=863&f%5B%5D=881&f%5B%5D=860&f%5B%5D=884&f%5B%5D=865&f%5B%5D=873&f%5B%5D=861&f%5B%5D=864&f%5B%5D=883&f%5B%5D=957&f%5B%5D=859&f%5B%5D=966&f%5B%5D=956&f%5B%5D=955]#_blog_kompanii_izdatelskij_dom_«piter» (
Блог компании Издательский дом «Питер»
)[/url], #_java, #_professionalnaja_literatura (
Профессиональная литература
)
Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете голосовать в опросах
Вы не можете прикреплять файлы к сообщениям
Вы не можете скачивать файлы
Текущее время: 25-Ноя 07:21
Часовой пояс: UTC + 5
| Автор | Сообщение |
|---|---|
|
news_bot ®
Стаж: 6 лет 9 месяцев |
|
 оригинал Привет, Хаброжители! В современном мире разработки успешность приложения уже не определяется параметром «просто работает». Хороший программист должен знать возможности языка, практические приемы проектирования и платформенные средства для достижения максимальной производительности и жизнеспособности программ. Эта книга написана для разработчиков, которые хотят создавать качественный софт. Затронуты все ключевые показатели ПО: скорость, затраты памяти, надежность, удобочитаемость, потоковая безопасность, универсальность и элегантность. Реальные задачи и прикладные примеры кода на Java помогут надежно усвоить концепции. Пройдя все этапы создания центрального проекта книги, вы сможете уверенно выбрать правильный путь оптимизации собственного приложения. О книгеSPLГлавная идея этой книги — показать мышление опытного разработчика с помощью сравнения свойств программного кода (или нефункциональных требований).
Схема на с. 12 связывает содержимое книги с широким спектром знаний, необходимых профессиональному разработчику. Изучение Java требует знакомства с классами, методами, полями и т.д. (здесь база не рассматривается). Далее освоение языка идет по трем путям:
В книге рассмотрены все эти области, но в несколько нетрадиционном виде. Вместо того чтобы освещать разные аспекты по отдельности, я смешал их в соответствии с потребностями определенной главы. Каждая глава посвящена одному свойству программного кода, такому как скорость выполнения или удобочитаемость. Они не только важны и распространены, но и могут осмысленно применяться к малым кодовым единицам (например, к отдельному классу). Я постарался сосредоточиться на общих принципах и приемах программирования, а не на конкретных инструментах. В ряде случаев я ссылался на инструменты и библиотеки, которые помогут оценить и оптимизировать рассматриваемые свойства. Структура книгиSPLНиже приведен краткий список глав и свойств кода, которые в них рассматриваются. Не пренебрегайте упражнениями в конце каждой главы. Они сопровождаются подробными решениями и завершают материал главы применением описанных методов в разных контекстах.
Глава 1. В первой главе описана задача программирования, которую мы будем решать (класс для представления резервуаров с водой). Здесь приведена наивная реализация, которая демонстрирует типичные заблуждения неопытных программистов. Глава 2. Подробное описание эталонной реализации, обеспечивающей хороший баланс разных свойств. Глава 3. Сосредоточившись на эффективности по времени, мы улучшим время выполнения эталонной реализации более чем на два порядка (в 500 раз) и увидим, что разные сценарии практического использования вынуждают нас идти на разные компромиссы. Глава 4. Проведем эксперименты с эффективностью по затратам памяти и увидим, что по сравнению с эталонной реализацией затраты памяти сокращаются более чем на 50 % при использовании объектов и на 90 % — при отказе от использования отдельного объекта для каждого резервуара. Глава 5. Постараемся достичь надежности за счет контрактного проектирования и усиления эталонного класса проверками во время выполнения, а также с помощью тестовых условий, основанных на контрактах методов и инвариантах классов. Глава 6. Постараемся достичь надежности за счет модульного тестирования с помощью методов проектирования и выполнения набора тестов, а также рассмотрим метрики и средства тестового покрытия кода. Глава 7. Произведем рефакторинг эталонной реализации для применения рекомендуемых методов создания чистого самодокументируемого кода. Глава 8. В контексте конкурентности и потокобезопасности вспомним основные понятия синхронизации потоков и выясним, почему в нашем текущем примере необходимо применять нетривиальные механизмы для предотвращения взаимных блокировок и состояния гонки. Глава 9. Рассмотрим возможность повторного использования: обобщим эталонный класс, чтобы он мог применяться в других приложениях с аналогичной общей структурой. Приложение А. При обсуждении лаконичности кода я представлю компактную реализацию примера, объем исходного кода которого составит всего 15 % от эталонной версии. Конечно, получится заумный код, за который вас запинают на любом сеансе рецензирования кода. Приложение Б. Наконец, мы соберем воедино все свойства и построим финальную версию класса, представляющего резервуары. 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, которая эффективно расходует память и поддерживает следующие методы:
Для сравнения и выбора между разными реализациями можно руководствоваться следующими вопросами: 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):
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):
Решение с двумя массивами наиболее эффективно по памяти, если 100 + 28 × n < 56 + 4 × m, то есть в среднем каждый объект представлен в коллекции не менее 7 раз (m > 11 + 7 × n). 4.7. Реальные сценарии использования В главах 3 и 4 рассматривались два основных фактора, влияющих на эффективность алгоритма: время и затраты памяти. Было показано, что задача может быть решена разными способами (например, с использованием ArrayList вместо HashSet для хранения групп резервуаров). Выбор того или иного метода обычно приводит к компромиссу между эффективностью по времени и затратам памяти. Лучший выбор зависит от контекста решаемой задачи. Рассмотрим пару сценариев с высокой эффективностью по затратам памяти.
Например: — Пакет android.util содержит несколько классов, предоставляющих альтернативы для стандартных коллекций Java с меньшими затратами памяти. Например, SparseArray — эффективная по памяти реализация карты (или ассоциативного массива), связывающей целочисленные ключи с объектами. (В упражнении 2 этой главы вам будет предложено проанализировать этот класс.) — Все классы Android, относящиеся к работе с графикой, используют для представления координат, углов поворота и т. д. значения float с одинарной точностью вместо значений double. Пример можно найти в классе android. graphics.Camera.
Об авторе Марко Фаэлла — преподаватель computer science в Неаполитанском университете имени Фридриха II (Италия). Помимо академических исследований в области computer science Марко увлеченно занимается преподаванием и программированием. Последние 13 лет он ведет курсы про-граммирования повышенной сложности, а также является автором учебника для желающих получить сертификат Java-разработчика и видеокурса по потокам в языке Java. Более подробно с книгой можно ознакомиться на сайте издательства » Оглавление » Отрывок Для Хаброжителей скидка 25% по купону — Java По факту оплаты бумажной версии книги на e-mail высылается электронная книга. =========== Источник: habr.com =========== Похожие новости:
Блог компании Издательский дом «Питер» )[/url], #_java, #_professionalnaja_literatura ( Профессиональная литература ) |
|
Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете голосовать в опросах
Вы не можете прикреплять файлы к сообщениям
Вы не можете скачивать файлы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете голосовать в опросах
Вы не можете прикреплять файлы к сообщениям
Вы не можете скачивать файлы
Текущее время: 25-Ноя 07:21
Часовой пояс: UTC + 5