1. Серія контенту:
2. Цей контент є частиною серії: Коментар
3. Написання коду з оптимальною продуктивністю
4. рекурсія
5. Лістинг 1. Лістинг 1
6. Лістинг 2. Лістинг 2
7. Лістинг 3. Лістинг 3
8. цикл
9. Що краще?
10. контрольні приклади
11. обчислення суми
12. Малюнок 1. Малюнок 1. Обчислення суми
13. Малюнок 2. Малюнок 2. Обчислення факторіала
14. Лістинг 4. Лістинг 4
15. Лістинг 5. Лістинг 5
16. Лістинг 6. Лістинг 6
17. висновок
18. Ресурси для скачування

коментар

Серія контенту:

Цей контент є частиною # з серії # статей: Коментар

https://www.ibm.com/developerworks/ru/library/?series_title_by=**auto**

Слідкуйте за виходом нових статей цієї серії.

Цей контент є частиною серії: Коментар

Слідкуйте за виходом нових статей цієї серії.

Написання коду з оптимальною продуктивністю

Програмісти знаходяться в постійному пошуку найбільш продуктивних способів підвищення продуктивності додатків. І хоча більшості програмістів відомі концепції циклів і рекурсії, багато хто використовує лише один з цих методів, не замислюючись про те, наскільки можна підвищити продуктивність, вибравши оптимальний підхід. Насправді навіть невелика зміна може мати значний вплив на продуктивність додатків.

рекурсія

Рекурсією в програмуванні називається метод, що викликає сам себе. Незважаючи на простоту визначення, цей підхід досить складний для розуміння, оскільки людині не властивий подібний стиль мислення. Більш того, існують рекурсії різних типів, що вносить ще більшу плутанину. Найчастіше застосовуються рекурсії наступних двох типів:

• Головний рекурсія - рекурсивний виклик виконується ближче до початку методу і є одним з перших оброблюваних об'єктів. Оскільки він викликає сам себе, йому доводиться покладатися на результати попередньої операції, вміщеній в стек викликів. Через використання стека викликів існує ймовірність переповнення стека, якщо стек викликів недостатньо великий.
• Кінцева рекурсія - рекурсивний виклик виконується в кінці і є останнім рядком оброблюваного коду. Цей метод не використовує стек викликів незалежно від глибини рекурсії.

В математиці рекурсія поширена досить широко, тому простіше буде пояснити її на прикладі рекурсивного виклику. Вираз 5! (Факторіал числа 5) можна записати в такий спосіб:

5!
5 * 4!
5 * 4 * 3!
5 * 4 * 3 * 2!
5 * 4 * 3 * 2 * 1!
5 * 4 * 3 * 2 * 1

У лістингу 1 наведено приклад обчислення 5! за допомогою головного рекурсії.

5!
5 * 4!
5 * 4 * 3!
5 * 4 * 3 * 2!
5 * 4 * 3 * 2 * 1!
5 * 4 * 3 * 2 * 1

У лістингу 1 наведено приклад обчислення 5! за допомогою головного рекурсії.

Лістинг 1. Лістинг 1

public long getFactorial (long currNum) {if (currNum == 1) return 1; return currNum * getFactorial (currNum - 1); }

Кожен рекурсивний виклик повинен бути завершений і поміщений в стек викликів до розрахунку факторіала. Java ™ буде інтерпретувати кожен виклик методу getFactorial наступним чином (кожен рядок являє об'єкт, що знаходиться в стеку викликів):

5 * getFactorial (4)
5 * (4 * getFactorial (3))
5 * (4 * (3 * getFactorial (2)))
5 * (4 * (3 * (2 * getFactorial (1))))
5 * (4 * (3 * (2 * 1)))
120

У лістингу 2 наведено приклад обчислення 5! за допомогою кінцевої рекурсії.

Лістинг 2. Лістинг 2

public long getFactorial (long currNum, long sum) {if (currNum == 0) return sum; return getFactorial (currNum - 1, sum * = currNum); }

В цьому випадку рекурсивні виклики не використовують стек викликів для зберігання інформації, необхідної для розрахунку факторіала. Замість цього вони передають результат попереднього виклику.

Лістинг 3. Лістинг 3

getFactorial (5,0) getFactorial (4,5) getFactorial (3,20) getFactorial (2,60) getFactorial (1,120) getFactorial (0,120) 120

цикл

Мови програмування надають цикли кількох різних типів, дуже добре знайомих більшості програмістів. У мові програмування Java є цикли for, do і while. Цикл - це багатократне виконання декількох операторів. Цикли неможливо заносять дані в стек викликів незалежно від числа виконань циклу. Важливою відмінністю циклів від рекурсивних функцій є той факт, що цикли використовують для підрахунку числа виконань итератор, а рекурсивні функції для визначення моменту виходу повинні виконувати порівняння результатів. Іншою важливою відмінністю є можливість застосування в циклах фільтрів і інших селекторів. Прикладом такої ситуації може служити цикл foreach.

Що краще?

На це питання відповісти непросто. Найчастіше цикли дають кращу продуктивність, ніж рекурсивні виклики, оскільки виклики методів споживають більше ресурсів, ніж виконання звичайних операторів. У разі головного рекурсії стек викликів розростається, і його необхідно переглядати для отримання кінцевої відповіді. Проте це твердження справедливе не завжди і залежить від типу розв'язуваної задачі.

контрольні приклади

Наведені нижче контрольні приклади запускалися в 64-розрядної середовищі виконання IBM Java Runtime Environment (JRE) 7.0.4.0 (з аргументом командного рядка -Xms256m -Xmx256m -Dcom.ibm.tools.attach.enable = no). Щоб середовище виконання не витрачала час на розширення і стиснення купи, JRE запускалася з фіксованим розміром купи 256 МБ. Відключення API Attach не дозволяє JRE запускати додатки-агенти (зазвичай використовуються для моніторингу), що нормалізує продуктивність в кожному тесті. При збільшенні стека викликів для ініціалізації стека і підтримки його на рівні 3 МБ використовувався аргумент командного рядка -Xss3m -Xssi3m.

обчислення суми

При підсумовуванні чисел цикл показав значно більш високу продуктивність, а кінцева рекурсія виявилася швидше головний. При збільшенні стека викликів Java до 3 МБ головний рекурсія зрівнялася за швидкістю з кінцевими, але все ж не змогла наздогнати цикл.

Малюнок 1. Малюнок 1. Обчислення суми

обчислення факторіала

Цей примітний приклад ілюструє залежність результатів від використовуваних операторів. При використанні простого типу даних int кращі результати у всіх випадках вийшли для циклу. Застосування типу int обмежує величину результату до 32-розрядної цілого числа зі знаком. Для великих факториалов можна використовувати тип даних BigInteger, але така конструкція буде більш витратною. Результати застосування BigInteger показали, що використання головного рекурсії в парі з кінцевими забезпечує кращу швидкодію, ніж чисто кінцева рекурсія або цикл.

Малюнок 2. Малюнок 2. Обчислення факторіала

Області застосування рекурсії

Рекурсія є дуже потужним інструментом програмування. Її можна використовувати для вирішення завдань, які більш ефективно представляються рекурсією і можуть використовувати стек викликів. Як правило, це відноситься до завдань сортування, які ефективно вирішуються за допомогою рекурсії, що забезпечує більш високу швидкість, ніж цикли.

У задачі, що отримала назву Ханойська вежа , Дані три стрижня і диски різного розміру, які в початковому стані надіті на перший стрижень у вигляді вежі. Завдання полягає в тому, щоб перенести вежу на інший стрижень, при цьому забороняється класти великий диск на маленький. Цю чудову завдання можна легко вирішити за допомогою рекурсії за 2n - 1 ходів, де n - число дисків.

Наприклад, візьмемо чотири диска і спробуємо перенести їх з стрижня A на стрижень C, використовуючи стрижень B для тимчасового зберігання. За допомогою описаної нижче рекурсивної функції це може бути виконано за 15 ходів. Процес рішення можна візуалізувати цим апплетом . Функція викликається (2n * 2) - 1, або 31 разів. Причина, по якій число викликів функції не дорівнює числу ходів, криється в тому, що для обробки ходів необхідно встановити стек викликів. У цьому прикладі використовується головний рекурсія (лістинг 4).

Лістинг 4. Лістинг 4

private static void solveTower (int num, int fromPeg, int toPeg, int tempPeg) {if (num> 0) {// move a disc from the fromPeg to the tempPeg solveTower (num - 1, fromPeg, tempPeg, toPeg); System.out.println ( "Disc moved from" + fromPeg + "to" + toPeg); // move disc from the tempPeg to the toPeg solveTower (num - 1, tempPeg, toPeg, fromPeg); }}

Результат для чотирьох дисків показаний в лістингу 5.

Лістинг 5. Лістинг 5

1. Диск перенесений з 1 на 2 2. Диск перенесений з 1 на 3 3. Диск перенесений з 2 на 3 4. Диск перенесений з 1 на 2 5. Диск перенесений з 3 на 1 6. Диск перенесений з 3 на 2 7. Диск перенесений з 1 на 2 8. Диск перенесений з 1 на 3 9. Диск перенесений з 2 на 3 10. Диск перенесений з 2 на 1 11. Диск перенесений з 3 на 1 12. Диск перенесений з 2 на 3 13. Диск перенесений з 1 на 2 14. Диск перенесений з 1 на 3 15. Диск перенесений з 2 на 3

Ханойська вежа - широко поширена завдання, яке можна вирішити за допомогою рекурсії. Однак не всі завдання настільки очевидні, багато хто з них вимагають часу на аналіз і рішення. Ханойську вежу можна вирішити і за допомогою циклів, однак це потребує використання кількох різних циклів і ітераторів. Це рішення буде працювати довше і зажадає більшого обсягу коду.

Нижче показаний ітераційний спосіб вирішення Ханойська вежі. У цьому прикладі використані операції з битами, які працюють швидше математичних операцій. За основу була взята ця програма на мові C .

Лістинг 6. Лістинг 6

int numMoves = (1 << numDiscs) - 1; int [] pegs = {1, 2, 3, 1, 3, 2}; int count = 0; for (int currMove = 1; currMove <= numMoves; currMove ++) {int disc = 0; while ((currMove >> disc & 1) == 0) {disc ++; } Int level = (numDiscs - disc) & 1; int fromPeg = (currMove >> ++ disc)% 3; fromPeg = pegs [fromPeg + (level * 3)]; int toPeg = (fromPeg + level)% 3 + 1; System.out.println (++ count + ". Disc moved from" + fromPeg + "to" + toPeg); }

висновок

Хоча багатьом програмістам звичніше працювати з циклами, рекурсию також не можна скидати з рахунків, особливо якщо вона дає приріст продуктивності або дозволяє вигідно використовувати стек викликів. Не завжди легко передбачити, який метод дасть кращі результати, тому обов'язково потрібно проводити тести продуктивності. При використанні головного рекурсії також необхідно брати до уваги розмір стека.

Ресурси для скачування

Схожі теми

Підпишіть мене на повідомлення до коментарів