Сила кожного програміста – у його знаннях. Так, здатність добре гуглити теж стоїть не на останньому місці, але, однак, має бути певний запас знань, на основі якого формується спосіб мислення розробника. Чим глибші ці знання, тим цікавіші рішення може придумати програміст.
Однією з частин такої "бази" є структури даних і алгоритми. Як же можна розширювати свої знання у цьому напрямі? Як варіант — знайти книгу, знання з якої стануть вогнетривким запасом і фундаментом для подальшого вивчення. Для мене такою книгою і стала «Структури даних та алгоритми Java» Роберта Лафоре.
Для кого
Аудиторією для цієї книги може послужити дуже широкий спектр людей, адже вона буде корисна і для тих, хто тільки збагнув синтаксис мови Java, і для практикуючих програмістів, для більш глибокого розуміння особливостей структур даних та алгоритмів.
Про що
Ця книга присвячена вивченню та використанню структур даних та алгоритмів у програмуванні. Вона розповість читачеві, як структури даних визначають спосіб організації даних у пам'яті, і навіть як алгоритми забезпечують виконання різних операцій із цими структурами. Давайте копні трохи глибше і подивимося, про що саме розповідає ця книга:
Масиви. Докладно розглядається операції вставки, пошуку та видалення в масивах та впорядкованих масивах. Демонструється робота лінійного та двійкового пошуку для впорядкованих та невпорядкованих масивів. Також ви дізнаєтесь, що таке O-синтаксис.
Сортування. Розглядаються три прості методи сортування — "бульбашкове сортування", "сортування методом вибору", "сортування методом вставки". З книги ви дізнаєтеся, яка з них найповільніша, а яка найпростіша.
Стеки та черги. Розглядаються такі структури даних як стек, черга та пріоритетна черга, їх ефективність, реалізація на Java.
Зв'язкові списки. Книга розповідає про двозв'язкові та двосторонні списки, про їх ефективність та те, яким чином виконуються операції вставки, пошуку та видалення. Також розглядаються ітератори і те, які їм потрібні методи.
Рекурсії. Розглядаються рекурсії у різних ситуаціях, таких як: обчислення трикутних чисел та факторіалів, побудова анаграм, виконання рекурсивного двійкового пошуку, розв'язання головоломки “Ханойська вежа”, реалізація сортування злиттям, розв'язання задачі про рюкзак.
Нетривіальні сортування. Розглядаються більш досконалі методи: сортування Шелла, швидке сортування та порозрядне, їх алгоритми, ефективність.
Двійкові дерева. Розглядаються збалансовані дерева двійкового пошуку, як вони працюють, їх операції вставки, видалення, різні види обходу, пошук мінімуму та максимуму, пошук наступника. Також буде розглянуто Код Хаффмана.
Червоно-чорні дерева. Розглядається один із найефективніших різновидів збалансованих дерев, їх операції повороту та перемикання кольорів, необхідні для балансування.
Дерева 2-3-4. Описуються дерева цього виду як приклад багатоколійних дерев, розглядається їхня робота, відношення з В-деревами, які використовуються для зовнішнього зберігання даних.
Хеш-таблиці. Розглядається хешування та його різні методи, такі як лінійне та квадратичне пробування, подвійне хешування та метод ланцюжків. Також ви зможете дізнатися, як можна застосувати хешування для організації зовнішнього зберігання файлів.
Піраміди. Це особливий тип дерева, що використовується для ефективної реалізації пріоритетних черг. У книзі розглядаються механізми операції вставки, видалення, перестановки. Також ви дізнаєтеся, що таке пірамідальна перестановка і як її можна реалізувати Java.
Графи. Наводяться зважені та незважені графи, алгоритми для пошуку за ними, алгоритми, що застосовуються для знаходження найкоротших шляхів обходу.
Для більшої наочності у кожному розділі наводиться власна реалізація аналізованої структури даних. Наприклад, якщо це список, буде наведено приклад класу, що реалізує описаний функціонал. Останній розділ книги, відштовхуючись від знань, отриманих із попередніх розділів, починає збирати всі знання в єдину картину. Наприклад, ви зможете чітко сформувати уявлення про те, яку структуру даних у якій ситуації використовувати.
Також наприкінці кожного розділу є невеликі вправи. Деякі з них пов'язані з виконанням операцій з програмою Workshop, а інші дають вам невеликі завдання безпосередньо в коді.
Що таке програми Workshop
Для демонстрації даних структур та алгоритмів використовуються програми Workshop. Програми оформлені у вигляді аплетів Java, які можна запускати у браузері. Програми Workshop будують графічні схеми, які показують, як працює алгоритм чи структура даних.
Наприклад, в одному з додатків, призначеному для відображення сортування стовпців за зростанням, при кожному натисканні кнопки на гістограмі виконуватиметься наступний крок. При цьому виводитимуться значення змінних, задіяних у даному алгоритмі, щоб було видно, як відбувається виконання коду (нагадує опис дебагера, чи не так?).
дуже легко читається, багато прикладів пояснюються майже "на пальцях";
відкриває очі на багато класичних речей без застосування складних математичних формул. Ну, майже без них:)
незважаючи на те, що приклади наведені мовою Java, дії, що відбуваються в коді, досить докладно пояснюються текстом після і коментарями в коді. Тому її може читати користувач будь-якої мови програмування, оскільки приклади коду досить прості: вони читаються майже псевдокод.
Мінуси книги
попри пояснення "на пальцях", у ньому бувають прогалини. Для пояснення сортування масивів автор малює футбольну команду, а сортування Шелла там практично не описано: я не зміг її зрозуміти та читав про неї в інтернеті;
можливі друкарські помилки, як правило у зображеннях або таблицях;
деякий код дуже застарілий.
Аналоги
Аналогами цієї книги або наступними за нею (для тих, хто хоче продовжувати вивчення) я раджу:
"Алгоритми на Java" Роберта Седжвіка;
"Алгоритми: побудова та аналіз" Томаса Кормена.
Підсумок
Мінусів у книги небагато, тож вона дійсно варта прочитання. У ній доступно пояснюється безліч базових, основних тем, таких як різні сортування, масиви, дерева, колекції, графи і так далі. Так як книга не дуже прив'язується до Java, база знань, отриманих від її вивчення, буде корисною і в інших мовах програмування. Must have, must read – якщо ви розробник.
Однією з частин такої "бази" є структури даних і алгоритми. Як же можна розширювати свої знання у цьому напрямі? Як варіант — знайти книгу, знання з якої стануть вогнетривким запасом і фундаментом для подальшого вивчення. Для мене такою книгою і стала «Структури даних та алгоритми Java» Роберта Лафоре.
