Сложную задачу поставила передо мной редакция журнала: на правах действующего программиста и преподавателя высшей школы, с целью борьбы с веб-программистами и прочими верстальщиками раскрыть тему необходимости изучения математики :). Что ж — вызов принят, хотя это и не так просто. Тем более что в последнее время к вопросу «Должен ли программист знать классическую математику?» добавился еще один: «А должен ли data scientist уметь программировать?»
В этом есть какая-то ирония — оказывается, люди, хорошо знающие математику, далеко не всегда хорошо программируют. В этой статье я не буду воскрешать мифы вроде того, что, чтобы стать гуру программирования, нужно прочесть известный четырехтомный труд Кнута. В Советском Союзе тоже имелась книга, которая у всех была и которую никто не читал, — «Капитал» Маркса. Все просто: Кнут не для всех, и, наверное, самое важное, что можно извлечь из первого тома, — в байте не всегда было восемь бит.
...все просто: Кнут не для всех, и, наверное, самое важное, что можно извлечь из первого тома, — в байте не всегда было восемь бит
Прежде всего, есть разные задачи, которые требуют разного уровня подготовки. Знание алгебраической геометрии вряд ли поможет в решении каждодневных задач, если ты занимаешься веб-разработкой. Строго говоря, существует только два по-настоящему необходимых
математических навыка для программиста — это умение считать и умение работать с логическими выражениями.
Разумеется, существуют емкие с точки зрения математики области программирования, например криптография и компьютерная графика. Но одна тема возникает во всех разделах программирования, пусть даже в разной степени, — это сложность. В каком-то смысле, что бы мы ни программировали, мы постоянно сталкиваемся с задачей контроля сложности. Это может быть вычислительная сложность, когда ты должен уметь реализовывать эффективные алгоритмы, или же сложность кода, и тогда нужен рефакторинг, и так далее. Поэтому большая часть математики, которая применяется более или менее повсеместно, — это математика, нужная для алгоритмов и анализа кода в целом.
Здесь, перед тем как говорить об алгоритмах, я приведу несколько примеров на совершенно отвлеченную тему.
Кое-что о числах
Если быть совсем честным, то стоит отметить, что знание математики далеко не всегда помогает программисту, потому что математика, связанная непосредственно с числами, часто работает иначе, чем кажется, из-за особенностей представления чисел в компьютере.
Начнем с чего-нибудь совсем простого, но очень примечательного — случалось, что на такой вопрос на собеседовании опытные разработчики, окончившие математический факультет, отвечали неправильно (людей, которые пишут такое в коде, существенно больше, чем может показаться на первый взгляд). Вот, к примеру, тебе нужно найти все числа в массиве, равные 0.9, или сосчитать их количество. Что может быть проще?
static int count(double[] arr, double v) {
int c = 0;
for(int i = 0; i < arr.length; i++)
if (arr[i] == v) c++;
return c;
}Вообще класс, пишем блочный тест с помощью JUnit для массива:
@Test
void testCount() throws Exception {
double[] arr = {0.9, 0.9, 0.8, 0.9, 0.7};
assertEquals(3, count(arr, 0.9));
}Все работает, count(arr, 0.9) даст 3, все как положено — давай в продакшен. За такое реально можно лишиться работы... Есть нечто, чего я до сих пор не могу понять. Почему разработчики компилятора разрешают компилировать этот код без ошибок и предупреждений? Давай возьмем другой массив:
double[] arr1 = {2.0 - 1.1, 3.0 - 2.1, 0.8, 10 - 9.1, 0.7};Вроде бы почти все то же самое, но count(arr1, 0.9) вернет... 0. Почему так? Давай просто выведем массив на экран:
0.8999999999999999
0.8999999999999999
0.8
0.9000000000000004
0.7Одна из первых вещей, которые должен знать любой программист: никогда, ни при каких обстоятельствах нельзя сравнивать числа с плавающей точкой на равенство. Почему вообще так происходит? Потому что так устроено двоичное представление чисел с плавающей точкой :). Только на эту тему можно написать не одну, а несколько статей. Здесь я не буду приводить лишних умных слов, таких как «машинный эпсилон», а просто дам рекомендацию для сравнения двух чисел: если Math.abs(x – y) < eps, то можно считать их равными. Величину eps можно подобрать исходя из задачи (это просто достаточно малое число). Вообще, с числами в компьютере связано много интересного, а с числами с плавающей точкой особенно, потому что далеко не все понимают, как это на самом деле работает. Вот прекрасный пример (тоже из Java): выражение 0.0 > Double.MIN_VALUE вернет false!
Многие читатели знают слова «мантисса» и «экспонента», а подробное описание подобных эффектов явно выходит за рамки статьи, так что я всего лишь дам полезные ссылки для начала:
Здесь же просто отмечу кое-какие полезные факты. Числа с плавающей точкой и целые числа ведут себя по-разному в одних и тех же ситуациях. К примеру, деление на 0 в случае целых чисел приводит к возникновению исключения, а вот в случае чисел с плавающей точкой — к появлению значений Double.POSITIVE_INFINITY, Double.NEGATIVE_INFINITY и NaN (если 0,0 разделить на 0). Переполнение также работает по-разному:
Double.MAX_VALUE + 10000 == Double.MAX_VALUE // true
Integer.MAX_VALUE + 10000 == Integer.MAX_VALUE // falseВ предыдущем примере у нас была функция Math.abs(). Кстати, функция вычисления абсолютного значения интересна сама по себе, особенно для целых чисел (для разных типов используются разные функции), и может создать тебе очень большие проблемы (особенно в больших проектах). Предлагаю подумать о том, всегда ли модуль возвращает корректный результат, то есть можем ли мы вообще полагаться на то, что результат модуля всегда больше либо равен 0? Ведь этому нас учат в школе и в университете. Проблема в том, что даже целые числа хранятся в памяти так, что что-нибудь не работает. Подумаем в этом направлении, возьмем любое целое со знаком: пусть 32 бита, диапазон значений такого числа от –2^31 до 2^31 – 1.
Кто-нибудь видит проблемное место? Отрицательная часть длиннее положительной! На практике это означает, что «заведомо положительное» число Math.abs(Integer.MIN_VALUE) равно –2 147 483 648.
Сложность, алгоритмы и структуры данных
Теперь перейдем к примерам другого рода. Недавно я был на последней конференции JPoint. Алексей Шипилев (@shipilev) рассказывал про компактификацию строк в Java 9. Несмотря на то что строки в Java в кодировке UTF-16, большинство из них, согласно исследованию дампов приложений, все-таки содержат только латинские символы. Таким образом они могут хорошо помещаться в строки, где на символ отводится один байт, что уменьшит занимаемую память и увеличит пропускную способность. Однако вопрос в том, как это правильно реализовать. Интересно, например, почему бы не использовать просто UTF-8 вместо UTF-16? Основное достоинство UTF-8 состоит в том, что это кодировка с переменным количеством байтов на символ и латинские символы всегда представимы одним байтом. Это, безусловно, дает выигрыш по сравнению с UTF-16 строками и, как может показаться, как раз решает нашу проблему.
Как бы не так. Оказывается, что одним из самых часто вызываемых методов класса String в Java является метод charAt(). Причем типичный контекст его использования следующий:
for (int i = 0; i < s.length(); i++) {
char ch = s.charAt(i);
...
}Если наша строка хранится в кодировке с переменными числом байтов, то операция charAt() будет выполняться за линейное от длины строки время, а не за O(1), что приведет к регрессии таких циклов до квадратичной сложности.
Так, стоп! Это вполне обычный кейс для знания алгоритмов. Строго говоря, никаких алгоритмов тут помнить не надо, Кнута с Корменом читать не обязательно. Однако знать O-нотацию (и вообще матан на уровне первого курса) получается полезно.
Для тех, кто еще не в курсе, но кому компилятор (совершенно зря) разрешает компилировать такие программы: здесь написано, что доступ к символу в строке происходит за постоянное время, которое не зависит от длины строки. Это все потому, что строки, как это часто (но не всегда) бывает, реализованы через массивы. Тут можно было бы закончить с примером, но нет. Дело в том, что есть люди, которые слышали про O-нотацию, но пользуются ей слишком буквально. Наверное, ты в курсе, что есть такие языки программирования, в которых все массивы ассоциативные (то есть словари) или в которых просто нет массивов (такие тоже есть, и их все любят). И ты, наверное, слышал, что доступ к словарю тоже O(1).
И вот я сам видел, как многие люди смело используют словари везде, даже там, где можно было бы использовать массивы.
Дело в том, что O(1) — это абстракция, которая нам говорит, что это константа, но не говорит какая. В случае словарей она много больше, чем в случае массивов. Так, этот пример просто про умение считать и понимание O-нотации, здесь ничего не написано про то, с чем имеют дело инженеры по производительности (кеш-промахи, предвыборка и так далее), там нужно не только уметь считать, но и еще много чего знать.
Раз уж мы коснулись довольно болезненной темы про алгоритмы. Я сам много раз слышал, что знать алгоритмы вообще не нужно, потому что все написали за нас. Последнее почти всегда правда. Если даже и так, то знание помогает понять, какую структуру данных или алгоритм нужно использовать в каждом конкретном случае. Почему «почти» — потому что иногда это все-таки случается.
Когда я был молод, памяти в хорошем компьютере было 4 Мбайт, то есть в 1024 раза меньше, чем сейчас в плохом. И чтобы получить доступ ко всей этой памяти, нужно было писать на Watcom C и использовать защищенный режим с помощью DOS/4G, потому что в реальном режиме процессора x86 не было плоской модели памяти, а была модель сегмент-смещение и столько адресовать нормальным образом было просто нельзя. Как ты думаешь, что изменилось с тех пор? Правильный ответ: ничего.
Все те же проблемы. Очень много людей пишут на Java сейчас так, как тогда писали на C. Но у языка Java есть одно ограничение, которое порождает очень специальный кейс, где нужно брать и кодить алгоритмы и структуры данных самому, даже при такой инфраструктуре, которая выстроена вокруг языка. Речь идет о том, что адресация массивов — это 32-битное знаковое целое. А что делать, если ты хочешь сделать бит-сет на > 2 миллиарда бит? Если у тебя есть необходимость в структуре данных, в которой больше двух миллиардов элементов, то у тебя серьезные проблемы — тебе, скорее всего, придется реализовывать это самому. Даже если это массив. Вот тут от того, с чем именно тебе нужно иметь дело, зависит масштаб проблемы.
Ладно, здесь нам повезло, битовый сет — это довольно просто. Для его реализации нужно знать, как работать с битовыми масками, и просто уметь считать. Для того чтобы реализовать битовый сет, достаточно научиться имитировать массивы большей длины. Помимо алгоритмических и математических тонкостей, здесь есть еще и чисто инженерные проблемы. Если нам нужно создать массив из целых чисел, скажем, на 4 миллиарда элементов, то может показаться, что для этого достаточно создать два массива по 2 миллиарда. На самом деле лучше так не делать, особенно в Java, — потому что там существует сборка мусора, а дефрагментация памяти есть всегда, и найти два раза по 8 Гбайт пустоты в памяти, даже если у тебя сервер с 64 Гбайт памяти, может оказаться непосильной задачей. Лучше, конечно, сделать десяток-другой массивов поменьше.
Математика О-нотаций нам говорит, что нет никакой разницы в сложности алгоритма независимо от количества массивов, однако наилучшим вариантом будет использовать количество массивов, равное степени двойки. Например, 64. Дело в том, что операция вычисления остатка от деления в произвольном случае — это довольно дорого, особенно если у тебя высоконагруженный цикл, тогда как в случае степени двойки остаток отделения на 64 совпадает с битовым «и» с числом 63 (немного математики, но не все знают), что значительно быстрее.
Вместо заключения
Я не просто так вспомнил про битовый сет, потому что он лежит в основе очень интересной, а главное, полезной структуры данных, которая называется фильтр Блума (Bloom Filter). Это вероятностная структура данных, а потому даже для того, чтобы просто с ней работать, нужно немного знать математику и как минимум основы теории вероятностей.
Фильтр Блума — это компактное представление множества, которое обеспечивает проверку на вхождение с некоторой вероятностью ложноположительного результата (false positive), то есть если операция get для фильтра Блума говорит нам, что элемента во множестве нет, то его действительно нет, а вот в положительном случае можно гарантировать корректность результата только с какой-то вероятностью. Интересный момент в работе с такой структурой данных заключается в том, что ты можешь всегда выбирать баланс между достоверностью положительного результата и экономией места. Часто фильтр Блума используется для первичной проверки принадлежности элемента множеству, если точная проверка слишком дорога.
Как это работает? Об этом я очень подробно напишу в следующей статье, а здесь сделаю только небольшой спойлер. На самом деле все довольно просто: при добавлении элемента вычисляется несколько различных хешей (их число варьируется параметрами, обычно около шести) для данного объекта, потом берется остаток от деления на длину битового сета и устанавливаются соответствующие биты.
Для проверки используется тот же процесс: если хотя бы один бит из необходимых отсутствует, то данного элемента во множестве точно нет (хотя возможны коллизии). В общем, жди продолжения с анализом и реализацией вероятностной структуры данных с long-адресацией в следующей статье :).
