Велика збірка заворожливої візуалізації відомих алгоритмів

“Зоряна ніч”, Ван Гог

Мікрофотографія сітківки

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

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

function sample () {
var bestCandidate, bestDistance = 0; for (var i = 0; i < numCandidates; ++i) { var c =[Math.random () * width, Math.random () * height], d = distance (findClosest (samples, c), c); if (d > bestDistance) { bestDistance = d; bestCandidate = c; } } return bestCandidate;}

Оскільки я пояснив роботу алгоритму вище, я залишу код без коментарів. (Все-таки мета цієї статті – візуалізація). Проте я уточню деякі детали:Внешняя змінна numCandidates визначає кількість кандидатів, генерованих на кожній ітерації. Зміна цього параметра дозволяє регулювати співвідношення швидкості і якості генерації. Чим менше кількості кандидатів, тим швидше працює алгоритм, але якість генерації при цьому падає.Функція distance – проста геометрія:

function distance (a, b) { var dx = a[0] - b[0],
dy = a[1] - b[1]; return Math.sqrt (dx * dx + dy * dy);}

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

Функція findClosest повертає найближчу до кандидата точку. Це можна зробити простим перебором або швидше, наприклад, використовуючи quadtree. Перебір просто реалізувати, але працює він повільно, за квадратичний час. Другий варіант помітно швидше, але вимагає більше зусиль для реалізації.Говорячи про компроміси: при ухваленні рішення про використання того або іншого алгоритму ми розглядаємо його порівняно з іншими варіантами. На одній чаші вагів знаходиться складність реалізації і підтримки, на іншій – якість і швидкість роботи.Найпростіша альтернатива – використати рівномірний розподіл:

function sample (){ return [random () * width, random () * height];
"Зоряна ніч" через рівномірно розподілені осередки

"Зоряна ніч" через осередки, згенеровані по алгоритму пошуку найкращого кандидата

Діаграма Вороного для рівномірного розподілу

Діаграма Вороного для осередків, згенерованих по алгоритму пошуку найкращого кандидата

Діаграма Вороного для осередків, розподілених по Пуассону

"Зоряна ніч" через осередки, розподілені по Пуассону

function shuffle (array) { var n = array.length, t, i; while (n) { i = Math.random () * n-- | 0; // 0 ≤ i < n t = array[n]; array[n] = array[i]; array[i] = t; } return array;
function transform (d){return" translate ("+x (d.index) +","+height+") rotate ("+a (d.value)+") ";}function shuffle (array){var swaps=[],m=array.length, t, i;while (m){i=Math.floor (Math.random ()*m--);t=array[m];array[m]=array[i];array[i]=t;swaps.push ([m, i]);}return swaps;}})()/*]]>*/
Для детальнішого пояснення роботи алгоритму см мою статтю.
function shuffle (array) { return array.sort (function (a, b) { return Math.random () - .5; // ಠ_ಠ});
}

Тут ми використовуємо сортування з довільним компаратором для перемішування. Компаратор визначає порядок елементів. Він приймає два елементи масиву - a і b і повертає число менше нуля, якщо a менше b, число більше нуля, якщо a більше b, чи нуль, якщо вони рівні. Компаратор викликається кілька разів при проході по масиву.

Якщо ви не вкажете компаратор для array.sort, елементи будуть впорядковані лексикографічно.

function transform (d, i){return" translate ("+x (i) +","+height+") rotate ("+a (d)+") ";}
function shuffle (array){return array.sort (function (){return Math.random () -.5;});}})()/*]]>*/

Інша проблема з цим алгоритмом - час роботи. Він виконується за O (n*log n), що робить його помітно повільніше, ніж алгоритм Фишера-Йєтс, який виконується за лінійний час. Але швидкість - проблема менша, ніж упередженість.

Зміщення видно неозброєним оком - діагональна зелена лінія показує, що первинний масив майже не перемішаний. Це не означає, що в Chrome сортування " краще", ніж в Firefox. Це говорить лише про те, що не слід використати компаратор на випадкових числах. Такі компаратори не здатні правильно функціонувати.

_{Переклад статті "Visualizing Algorithms"}

робить ще і розташування точок.)Ось ті ж 6667 точок з рівномірного розподілу:

Чи можемо ми зробити ще краще? Так! Причому, ми не лише отримаємо кращий результат, але і отримаємо його швидше - за лінійний час. Крім того, цей алгоритм майже також просто реалізувати, як і пошук найкращого кандитата, і він прекрасно масштабується.Цей чудовий алгоритм - алгоритм Бридсона для розподілу Пуассона :

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

-> ;var p=d3.select ("#random - comparator - firefox - shuffle - bias");var svg=p.append ("svg").attr ("width", width+margin.left+margin.right).attr ("height", height+margin.top+margin.bottom).style ("margin-left", - margin.left+" px").append ("g").attr ("transform", "translate ("+margin.left+","+margin.top+")");queue (1).defer (beforeVisible, p.node()).defer (d3.json, "random - comparator - firefox - shuffle - bias.json").await (ready);function ready (error, _, matrix){if (error) return console.error (error);var row=svg.selectAll (".row").data (matrix).enter ().append ("g").attr ("class"," row").attr ("transform", function (d, i){return" translate (0,"+x (i)+") ";});row.selectAll (".cell").data (function (d){return d;}).enter ().append ("rect").style ("shape-rendering"," crispEdges").attr ("class"," cell").attr ("x", function (d, i){return x (i);}).attr ("width", x.rangeBand()).attr ("height", x.rangeBand()).style ("fill", z);row.append ("line").attr ("x2", width);ro w.append ("text").attr ("x", x (0) - 6).attr ("y", x.rangeBand ()/2).attr ("dy"".32em").text (function (d, i){return i;});var column=svg.selectAll (".column").data (matrix).enter ().append ("g").attr ("class"," column").attr ("transform", function (d, i){return" translate ("+x (i) +",0) ";});column.append ("line").attr ("x1", - width);column.append ("text").attr ("x", 6 - x (0)).attr ("y", x.rangeBand ()/2).attr ("dy"".32em").attr ("transform", "rotate (- 90)").text (function (d, i){return i;});}})() ->

Інтерактивну версію цієї матриці для дослідження різних алгоритмів перемішування можна узяти тут: Will It Shuffle?