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

  1. postwarblues

    24.05.2016 at 15:02

    Эх, побольше бы таких материалов!
    Спасибо!

  2. ScorpioT1000

    24.05.2016 at 16:05

    > никогда, ни при каких обстоятельствах нельзя сравнивать числа с плавающей точкой на равенство.
    да нет, с 0.0 вполне можно сравнить
    кроме того, если над ними не было произведено операций, опять-же, можно сравнивать:
    double a = 0.8 — 0.13;
    double b = a;
    if(a == b) {

    нормальная, адекветная, а, самое главное, эффективная операция в таких случаях.

    Никогда нельзя складывать все правила под одну гребенку.

  3. schoolboy

    24.05.2016 at 21:40

    Жду следующей статьи.

  4. hrapovd

    25.05.2016 at 12:04

    А где можно почитать сборник подобных «правил» программирования:
    «> никогда, ни при каких обстоятельствах нельзя сравнивать числа с плавающей точкой на равенство.» ?

  5. energizer-woolf

    26.05.2016 at 18:42

    > Давай возьмем другой массив:
    >
    > double[] arr1 = {2.0 — 1.1, 3.0 — 2.1, 0.8, 10 — 9.1, 0.7};
    > Вроде бы почти все то же самое, но count(arr1, 0.9) вернет… 0. Почему так?

    Потому что и близко к 0.9 нет ни одного числа в элементах массива, или я чего-то не понял. Как-будто, здесь опечатка?

    • Bill115

      29.05.2016 at 10:53

      Почему близко нет? Первые два элемента == 0.9

      • energizer-woolf

        03.06.2016 at 18:12

        Меня больше напрягла фраза «вроде бы всё тоже самое», потому как неподготовленный ум, за неимением под рукой компилятора с JVM не поймёт, что 2.0 == 0.8999999999999999

  6. assp1r1n3

    27.05.2016 at 00:36

    >рекомендацию для сравнения двух чисел: если Math.abs(x – y) < eps
    дальше даже читать не стал. в лучшем случае можно обойтись (fabs(x-y) < dbl_epsilon * (fabs(x) + fabs(y))), а для других потребуется больше сравнений.

  7. assp1r1n3

    27.05.2016 at 00:45

    Решил прочитать ещё немного, чуть со стула не упал!
    >На практике это означает, что «заведомо положительное» число Math.abs(Integer.MIN_VALUE) равно –2 147 483 648.
    Такое бывает в случае представления целых чисел в виде дополненного кода(two’s complement). Я не знаю гарантируется ли это в стандарте Java, но если система будет использовать что-то другое, результат будет отличаться.
    Sign and mantissa code:
    abs(INT_MIN) == abs(INT_MIN) //true

  8. exlipse

    28.05.2016 at 03:46

    языки программирования в моем понимании это команды и общение с пк и математика тут не причем кроме +-%*. Может быть я не прав.

Оставить мнение

Check Also

WTF is APT? Продвинутые атаки, хитрости и методы защиты

Наверняка ты уже читал о масштабных сетевых атаках, от которых пострадали банки, крупные п…