Сложную задачу поставила передо мной редакция журнала: на правах действующего программиста и преподавателя высшей школы, с целью борьбы с веб-программистами и прочими верстальщиками раскрыть тему необходимости изучения математики :). Что ж — вызов принят, хотя это и не так просто. Тем более что в последнее время к вопросу «Должен ли программист знать классическую математику?» добавился еще один: «А должен ли 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, большинство из них, согласно исследованию дампов приложений, все-таки содержат только латинские символы.

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

Вариант 1. Оформи подписку на «Хакер», чтобы читать все статьи на сайте

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

Вариант 2. Купи одну статью

Заинтересовала статья, но нет возможности оплатить подписку? Тогда этот вариант для тебя! Обрати внимание: этот способ покупки доступен только для статей, опубликованных более двух месяцев назад.


11 комментарий

Подпишитесь на ][, чтобы участвовать в обсуждении

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

Check Also

Цифровой паноптикум. Настоящее и будущее тотальной слежки за пользователями

Даже если ты тщательно заботишься о защите своих данных, это не даст тебе желаемой приватн…