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


Дізнайтесь більше про нові кар'єрні можливості в EchoUA. Цікаві проекти, ринкова оплата, гарний колектив. Надсилайте резюме та приєднуйтеся до нас.

Можливості людського розуму обмежені [.] Наша сила – у використанні технологій, які багаторазово збільшують наші когнітивні здібності, – Дональд Норман

Семплинг

Перш, ніж приступити до пояснення першого алгоритму, слід описати завдання, яке він повинен вирішувати.

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

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

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

На кожній ітерації алгоритм генерує фіксовану кількість кандидатів з рівномірного розподілу, показаных сірим кольором. В даному випадку їх 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 rejectActive (){queue[i]=queue[--queueSize];queue.length=queueSize;sampleActive.classed ("sample--active", false);nextActive ();}function nextActive (){gCandidate.transition ().duration (duration).style ("opacity", 0).selectAll ("circle").remove ();gConnection.transition ().duration (duration).style ("opacity", 0).selectAll ("line").remove ();searchAnnulus.transition ().duration (duration).style ("opacity", 0).each ("end", queueSize?function (){beforeVisible (p.node (),selectActive);}:function (){p.classed ("animation--playing", false);});}})();}})()/*]]>*/

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

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

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

Перемішування - це процес перерозподілу елементів масиву у випадковому порядку. Приміром, ви перемішуєте колоду карт перед роздачею в покері. Хороший алгоритм перемішування незміщений, будь-який отриманий порядок однаково вірогідний.Алгоритм Фишера-Йєтс - відмінний приклад, він не лише незміщений, але і виконується за лінійний час, використовує константну пам'ять і легкий в реалізації.
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?

Київ, Харків, Одеса, Дніпро, Запоріжжя, Кривий Ріг, Вінниця, Херсон, Черкаси, Житомир, Хмельницький, Чернівці, Рівне, Івано-Франківськ, Кременчук, Тернопіль, Луцьк, Ужгород, Кам'янець-Подільський, Стрий - за статистикою саме з цих міст програмісти найбільше переїжджають працювати до Львова. А Ви розглядаєте relocate?


Залишити відповідь

Ваша e-mail адреса не оприлюднюватиметься. Обов’язкові поля позначені *