1. Реалізація та емпіричний аналіз

Розглянуто основні методи отримання інформації про кількісні показники продуктивності алгоритмів.

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

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

приклад в "Вступ" демонструє багато з базових концепцій аналізу алгоритмів, тому для конкретизації певних моментів ми будемо часто посилатися на продуктивність алгоритмів об'едіненіе- пошук. Кілька нових прикладів будуть детально розглянуті в розділі 2.6.

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

Повне охоплення методів аналізу алгоритмів сам по собі є предметом книги (див. Розділ посилань), і тут ми розглянемо лише основи, які дозволять

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

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

Реалізація та емпіричний аналіз

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

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

Ми висловлюємо алгоритми на С ++, але ця книга про алгоритми, а не про програмування на С ++. Звичайно ж, ми будемо розглядати реалізації на С ++ багатьох важливих завдань, і коли існує зручний і ефективний спосіб вирішити задачу саме засобами С ++, ми скористаємося цією перевагою. Однак переважна більшість висновків про реалізацію алгоритмів може бути застосовано до будь-якої сучасної середовищі програмування. Переклад програм з "Вступ" і майже всіх інших програм з даної книги на інший сучасну мову програмування - це досить просте завдання. Якщо в деяких випадках будь-якої іншої мови забезпечує більш ефективний механізм вирішення певних завдань, ми будемо вказувати на це. Наша мета - використати С ++ як засіб вираження алгоритмів, а не затримуватися на питаннях, специфічних для мови.

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

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

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

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

Один з перших кроків в розумінні продуктивності алгоритмів - це емпіричний аналіз. Якщо є два алгоритму для вирішення однієї задачі, то все природно: ми запустимо обидва і побачимо, який з них виконується довше! Це концепція може здатися занадто очевидною, щоб про неї варто було говорити, але її часто не беруть до уваги при порівняльному аналізі алгоритмів. Важко не помітити, що один алгоритм в 10 разів швидше за інше, якщо один виконується 3 секунди, а інший 30 секунд, проте при математичному аналізі цю різницю легко випустити з уваги як невеликий постійний множник. При вимірах продуктивності ретельних реалізацій алгоритмів для типових даних ми отримуємо результати, які не тільки є прямим показником ефективності, але і містять інформацію, необхідну для порівняння алгоритмів і обгрунтування додаються математичних результатів (див., Наприклад, таблиця 1.1 ). Якщо емпіричне вивчення починає поглинати значну кількість часу, на допомогу приходить математичний аналіз. Навряд чи варто очікувати завершення програми протягом години або цілого дня, щоб переконатися, що вона працює повільно - особливо якщо той же результат може дати нескладний аналіз.

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

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

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

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

Можливо, найбільш поширеною помилкою при виборі алгоритму є ігнорування характеристик продуктивності. Більш швидкі алгоритми, як правило, складніше, ніж прямі рішення, і розробники часто віддають перевагу більш повільні алгоритми, щоб уникнути зайвих складнощів. Однак, як було показано на прикладі алгоритмів об'єднання-пошук, можна домогтися значних поліпшень за допомогою навіть кількох рядків коду. Користувачі дивно великого числа комп'ютерних систем втрачають багато часу в очікуванні рішення задачі простими квадратичними алгоритмами, в той час як доступні алгоритми складності або лінійні алгоритми ненабагато складніше, але можуть вирішити задачу значно швидше. Але коли ми маємо справу з великими завданнями, доводиться шукати найкращий алгоритм, що і буде показано далі.

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

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

вправи

2.1. Переведіть програму з "Вступ" на іншу мову програмування і дайте відповідь на питання вправи 1.22 для вашої реалізації.

2.2. Скільки часу займе порахувати до 1 мільярда (не враховуючи переповнення)? Визначте кількість часу, необхідне програмою

int i, j, k, count = 0; for (i = 0; i <N; i ++) for (j = 0; j <N; j ++) for (k = 0; k <N; k ++) count ++;

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