Рандомізація функції

В інформатиці, функція рандомізації або рандомізація функції — це алгоритм або процедура, яка реалізує функцію, випадково обираючи між двома конкретними наборами, придатними для використання в увипадковленому алгоритмі.

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

Використання

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

Розглянемо, наприклад, такий алгоритм сортування, як швидке сортування, яке має невеликий передбачуваний час виконання для довільного набору вхідних даних, коли вхідні елементи представлені у випадковому порядку, але працює дуже повільно, в окремих ситуаціях, коли вхідні данні упорядковані "незручно" для алгоритму. Рандомізація функції цілих чисел від 1 до n в набір цілих чисел від 1 до n може бути використана для зміни порядку n вхідних елементів у «випадковому» порядку, перед викликом алгоритму. Цей модифікований (випадковим чином) алгоритм буде мати невеликий передбачуваний час виконання, незалежно від порядку введення даних.

Вимоги

Хаотичність

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

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

Однорідність

Вимоги однорідності для функції рандомізації, як правило, набагато слабші, ніж для хеш-функцій і псевдовипадкових генераторів. Мінімальна вимога, що відображає будь-який вхід детермінований алгоритм у «гарній» вхід з досить високою ймовірністю. (Тим не менш, аналіз, як правило, простіший, якщо функція рандомізації реалізує кожне можливе відображення з рівною ймовірністю.)

Джерело