Нариси з математики
Зміст статті
Складне завдання поставила переді мною редакція журналу: на правах чинного програміста та викладача вищої школи з метою боротьби з веб-програмістами та іншими верстальниками розкрити тему необхідності вивчення математики :). Що ж, виклик прийнятий, хоча це й не так просто. Тим більше що останнім часом до питання «Чи програміст повинен знати класичну математику?». додався ще один: «А чи має data scientist вміти програмувати?»
У цьому є якась іронія — виявляється, люди, які добре знають математику, далеко не завжди добре програмують. У цій статті я не воскрешатиму міфи на кшталт того, що, щоб стати гуру програмування, потрібно прочитати відому чотиритомну працю Кнута. У Радянському Союзі теж була книга, яка у всіх була і яку ніхто не читав, - "Капітал" Маркса. Все просто: Батіг не для всіх, і, мабуть, найважливіше, що можна витягти з першого тому, — у байті не завжди було вісім біт.
Насамперед є різні завдання, які вимагають різного рівня підготовки. Знання геометрії алгебри навряд чи допоможе у вирішенні щоденних завдань, якщо ти займаєшся веб-розробкою. Строго кажучи, існує тільки дві по-справжньому необхідні математичні навички для програміста - цевміння вважати і вмінняпрацювати з логічними виразами.
Зрозуміло, існують ємні з погляду математики області програмування, наприклад, криптографія і комп'ютерна графіка. Але одна тема виникає у всіх розділах програмування, нехай навіть різною мірою, — це складність. У якомусь сенсі, що б ми не програмували, ми постійно стикаємося із завданням контролю складності.Це може бути обчислювальна складність, коли ти маєш вміти реалізовувати ефективні алгоритми, або ж складність коду, і тоді потрібен рефакторинг, і таке інше. Тому більшість математики, яка застосовується більш-менш повсюдно, — це математика, необхідна алгоритмів і аналізу коду загалом.
Тут, перед тим як говорити про алгоритми, я наведу кілька прикладів на абсолютно абстрактну тему.
Дещо про числа
Якщо бути дуже чесним, то слід зазначити, що знання математики далеко не завжди допомагає програмісту, тому що математика, пов'язана безпосередньо з числами, часто працює інакше, ніж здається, через особливості представлення чисел у комп'ютері.
Почнемо з чогось дуже простого, але дуже примітного — траплялося, що на таке запитання на співбесіді досвідчені розробники, які закінчили математичний факультет, відповідали неправильно (людей, які пишуть таке в коді, значно більше, ніж може здатися на перший погляд). Ось, наприклад, тобі потрібно знайти всі числа в масиві, що дорівнює 0.9, або порахувати їх кількість. Що може бути простішим?
Взагалі клас, пишемо блоковий тест за допомогою JUnit для масиву:
Все працює, count (arr, 0.9) дасть 3, все як годиться - давай у продакшен. За таке реально можна втратити роботу. Є щось, чого я досі не можу зрозуміти. Чому розробники компілятора дозволяють компілювати цей код без помилок та попереджень? Давай візьмемо інший масив:
Начебто майже все те саме, але count(arr1, 0.9) поверне. 0. Чому так? Давай просто виведемо масив на екран:
Одна з перших речей, які повинен знати будь-який програміст: ніколи, за жодних обставин не можна порівнювати числа з плаваючою точкою на рівність. Чому взагалі таквідбувається? Тому що так влаштовано двійкове уявлення чисел із плаваючою точкою :). Тільки з цієї теми можна написати не одну, а кілька статей. Тут я не наводитиму зайвих розумних слів, таких як «машинний епсілон», а просто дам рекомендацію для порівняння двох чисел: якщо Math.abs(x – y) , то можна вважати їх рівними. Величину eps можна підібрати виходячи із завдання (це просто досить мале число). Взагалі, з числами в комп'ютері пов'язано багато цікавого, а з числами з точкою, що плаває особливо, тому що далеко не всі розуміють, як це насправді працює. Ось чудовий приклад (теж із Java): вираз 0.0 > Double.MIN_VALUE поверне false!
Багато читачів знають слова «мантіса» та «експонента», а докладний опис подібних ефектів явно виходить за рамки статті, так що я лише дам корисні посилання для початку:
Тут же просто відзначу деякі корисні факти. Числа з плаваючою точкою і цілі числа поводяться по-різному в тих самих ситуаціях. Наприклад, розподіл на 0 у разі цілих чисел призводить до виникнення виключення, тоді як у разі чисел з плаваючою точкою — до появи значень Double.POSITIVE_INFINITY , Double.NEGATIVE_INFINITY і NaN (якщо 0,0 розділити на 0). Переповнення також працює по-різному:
У попередньому прикладі ми мали функцію 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, більшість із них, згідно з дослідженням дампів додатків, все-таки містять лише латинські символи.