我為如此深?yuàn)W的主題而感到歉意，但觀看它們真的很有趣。本位來自：大數(shù)據(jù)文摘，選文 | 吳佳樂 翻譯|黃念 ?校對(duì)|馮琛 姚佳靈，作者 |Mike Bostock 素材來源 | bost.ocks.org

獨(dú)立心靈的力量被高估了……真正的力量源自于外部能提高認(rèn)知能力的幫助。

——唐納德

本文重點(diǎn)研究 算法 。然而，這里討論的技術(shù)適用于更廣泛的問題空間：數(shù)學(xué)公式、動(dòng)態(tài)系統(tǒng)、過程等?；旧?，任何需要理解代碼的地方。

那么，為什么要可視化 算法 呢？甚至為什么要去可視化呢？這篇文章將告訴你，如何利用視覺去思考。

算法是可視化中一種迷人的用例。要將一種算法可視化，我們不只是將數(shù)據(jù)擬合到圖表中，況且也沒有主要的數(shù)據(jù)集。相反的是有描述行為的邏輯規(guī)則。這可能是算法可視化如此不尋常的原因，因?yàn)樵O(shè)計(jì)師可以嘗試這種新奇的形式來更好地溝通。這就是來研究它們的充分的理由。

但是，算法也提醒人們——可視化不僅僅只是一種在數(shù)據(jù)中尋找模式的工具?？梢暬萌祟惖囊曈X系統(tǒng)，以增加人類的智慧。這樣，我們就可以用它來更好地了解這些重要的抽象過程以及其他事情。

采樣

在解釋第一個(gè)算法之前，我首先需要解釋它要解決的問題。

梵高的《星夜》

光 （電磁輻射） ，從這個(gè)屏幕上發(fā)出的光，穿過空氣，由你的晶狀體聚焦，并投射到視網(wǎng)膜上，這是一個(gè)連續(xù)的信號(hào)。要被感知，我們必須通過測量其在空間中的不同點(diǎn)的強(qiáng)度和頻率分布把光信號(hào)降低到離散脈沖。

這種還原過程被稱為采樣，它對(duì)視覺至關(guān)重要。你可以把它理解為——一個(gè)畫家應(yīng)用不同的顏色，采用離散的筆觸形成圖像 （特別是點(diǎn)畫或點(diǎn)彩派） 。采樣其實(shí)是計(jì)算機(jī)圖形學(xué)的核心關(guān)注點(diǎn)，例如，為了通過光線追蹤來柵格化3D場景，我們必須確定在何處拍攝光線。甚至調(diào)整圖像大小也需要采樣。

采樣會(huì)因?yàn)楦鞣N因素的矛盾性而變得困難。一方面要保證采樣點(diǎn)要均勻分布，不要有間隙，另一方面要避免重復(fù)采樣或有規(guī)律地采樣 （否則會(huì)產(chǎn)生混疊） 。這就是為什么你不應(yīng)該在照相時(shí)穿細(xì)條紋襯衫：條紋與相機(jī)傳感器中的像素網(wǎng)格產(chǎn)生共振，從而造成莫爾條紋 （Moiré patterns） 。

圖片來源：retinalmicroscopy.com

這是一張人類視網(wǎng)膜周邊的顯微照片。較大的錐形細(xì)胞檢測顏色，而較小的桿細(xì)胞改善低光視覺。

人類的視網(wǎng)膜有一個(gè)出色的解決方案，在其感光細(xì)胞的位置取樣。細(xì)胞密集和均勻地覆蓋著視網(wǎng)膜 （除了視神經(jīng)上方的盲點(diǎn)） ，然而細(xì)胞的相對(duì)位置是不規(guī)則的。這被稱為泊松盤分布，因?yàn)樗３至思?xì)胞之間的最小距離，避免遮擋而浪費(fèi)光感受器。

但是構(gòu)造一個(gè)泊松盤分布是困難的，因此有一個(gè)簡單的叫做 Mitchel的近似算法，它是最佳候選算法。

從這些點(diǎn)可以看出，最佳候選采樣產(chǎn)生了讓人愉快的隨機(jī)分布。這不是沒有缺陷：在一些地區(qū)有太多的樣本 （過采樣） ，而在其他地區(qū)是不夠的 （欠采樣） 。但它相當(dāng)好，同樣重要的是容易實(shí)施。

以下是它的工作原理：

對(duì)于每個(gè)新樣本，最佳候選算法生成固定數(shù)量的候選采樣點(diǎn)，用灰色表示 （在這里，這個(gè)數(shù)為10） 。從采樣區(qū)域均勻地選擇每個(gè)候選采樣點(diǎn)。

最佳候選者，以紅色顯示，是離所有先前樣本 （以黑色顯示） 最遠(yuǎn)的一個(gè)。從每個(gè)候選采樣點(diǎn)到最接近的樣本的距離由相關(guān)聯(lián)的線和圓圈表示：注意在灰色或紅色圓圈內(nèi)部沒有其他樣本。在創(chuàng)建所有候選采樣點(diǎn)并測量距離之后，最佳候選采樣點(diǎn)成為新樣本，并且丟棄剩余候選采樣點(diǎn)。

▼代碼如下所示：

function sample() {

varbestCandidate, 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;

}

正如我解釋了上面的算法，我會(huì)讓代碼獨(dú)立出來 （另外，這篇文章的目的是讓你通過可視化學(xué)習(xí)代碼） 。但我會(huì)明確一些細(xì)節(jié)：

其中numCandidates表示一次生成的候選采樣點(diǎn)個(gè)數(shù)。這個(gè)參數(shù)讓你以質(zhì)量換取速度。numCandidates越小，算法運(yùn)行速度越快。相反，numCandidates越大，算法運(yùn)行速度越慢，但是采樣質(zhì)量越高。

▼distance函數(shù)是簡單幾何：

function distance(a, b) {

vardx = a[0] – b[0],

dy = a[1] – b[1];

return Math.sqrt(dx * dx + dy * dy);

}

如果你想的話，在這里可以忽略開平方 （sqrt） ，因?yàn)樗且粋€(gè)單調(diào)函數(shù)，并且，它不改變最佳候選采樣點(diǎn)的結(jié)果。

findClosest函數(shù)返回距離當(dāng)前候選采樣點(diǎn)最近的采樣點(diǎn)。我們可以使用暴力搜索來實(shí)現(xiàn)，即對(duì)每一個(gè)現(xiàn)有的采樣點(diǎn)進(jìn)行迭代?；蛘?，可以讓搜索加速，如利用四叉樹搜索算法。暴力搜索實(shí)現(xiàn)簡單，但非常慢 （時(shí)間復(fù)雜度太高） 。而加速方式要快得多，但需要做更多的工作來實(shí)現(xiàn)。

談到權(quán)衡——在決定是否使用一個(gè)算法，我們不是憑空評(píng)估它，而是將其與其他方法進(jìn)行比較。作為一個(gè)實(shí)際問題，權(quán)衡實(shí)施的復(fù)雜性：需要多久來實(shí)現(xiàn)、維護(hù)難度，對(duì)于衡量它的性能和質(zhì)量是十分有用的。

▼最簡單的替代方法是均勻隨機(jī)采樣：

function sample() {

return [random() * width, random() * height];

}

它看起來是這樣的：

統(tǒng)一隨機(jī)是相當(dāng)糟糕的。存在嚴(yán)重的欠采樣和過采樣：許多樣本點(diǎn)擁擠在一起，甚至重疊，導(dǎo)致大的空區(qū)域 （當(dāng)每次采樣的候選采樣點(diǎn)的數(shù)量被設(shè)置為1時(shí)，均勻隨機(jī)采樣也代表最佳候選算法的質(zhì)量的下限） 。

除了通過采樣點(diǎn)的分布規(guī)律來鑒別采樣質(zhì)量，我們還可以嘗試通過根據(jù)最接近的樣本的顏色對(duì)圖像著色來在不同的采樣策略下模擬視覺。這實(shí)際上是采樣點(diǎn)的Voronoi圖，其中每個(gè)單元由相關(guān)樣品著色。

通過6667個(gè)均勻隨機(jī)采樣后的《星夜》看起來是怎樣的？

這種方法的弊端也很明顯。采樣點(diǎn)分布不均導(dǎo)致每個(gè)單位在尺寸大小上變化很大，和預(yù)期的不均勻采樣點(diǎn)分布一樣。細(xì)節(jié)丟失嚴(yán)重是因?yàn)槊芗蓸狱c(diǎn) （小單元） 沒有充分利用起來。同時(shí)，稀疏采樣點(diǎn) （大單元） 通過夸大稀有色彩 （例如左下角的粉紅色） 引入了噪音。

現(xiàn)在來看看最佳候選采樣：

好多了！雖然仍然隨機(jī)放置，但單元的大小更一致。盡管樣品的數(shù)量 （6667） 保持不變，但由于它們均勻分布，保留了更多的細(xì)節(jié)和引入了更少的噪聲。如果你瞇著眼睛，幾乎可以弄清楚原來的筆觸。

我們可以使用Voronoi圖來更直觀地研究樣本分布，通過根據(jù)其面積給每個(gè)單元上色。較暗的單元較大，表示稀疏采樣; 較淺的單元較小，表明密集采樣。最佳圖案具有幾乎均勻的顏色，同時(shí)保持不規(guī)則的采樣位置 （顯示單元面積分布的直方圖也是很好的，但是Voronoi具有同時(shí)顯示采樣位置的優(yōu)點(diǎn)） 。

這是同樣的6667個(gè)采樣點(diǎn)的不均勻隨機(jī)采樣：

黑點(diǎn)是采樣點(diǎn)之間的大空隙，可能是由于欠采樣導(dǎo)致的視覺局部缺陷。相同數(shù)量的最佳候選樣品在單元面積中表現(xiàn)出小得多的變化，并且因此著色更一致：

我們能做得比最佳候選算法更好嗎？是的! 我們不僅可以用不同的算法產(chǎn)生更好的樣本分布，而且這種算法更快 （線性時(shí)間） 。它至少像最佳候選算法一樣容易實(shí)現(xiàn)。這種算法甚至可以擴(kuò)展到任意維度。

這個(gè)奇跡叫做Bridson的泊松盤采樣算法，它看起來像這樣：

該算法的功能明顯不同于其他兩個(gè)——它充分利用現(xiàn)有采樣點(diǎn)逐步生成新的采樣點(diǎn)，而不是在整個(gè)采樣區(qū)域隨機(jī)生成新的采樣點(diǎn)。這使其進(jìn)展具有準(zhǔn)生物學(xué)外觀，如在培養(yǎng)皿中分裂的細(xì)胞。注意，也沒有采樣點(diǎn)彼此太接近；這是定義由算法實(shí)施的泊松盤分布的最小距離約束。

這就是它的工作原理：

紅點(diǎn)表示“活躍”采樣點(diǎn)。在每次迭代中，從所有活躍采樣點(diǎn)的集合中隨機(jī)選擇一個(gè)。然后，在圍繞所選采樣點(diǎn)的環(huán)內(nèi)隨機(jī)生成一些數(shù)量的候選采樣點(diǎn) （用空心黑點(diǎn)表示） 。環(huán)從半徑r延伸到2r，其中r是樣本之間的最小允許距離。

來自現(xiàn)有采樣點(diǎn)的距離r內(nèi)的候選采樣點(diǎn)被拒絕；這個(gè)“禁止區(qū)”以灰色顯示，用黑線連接將被拒絕的候選采樣點(diǎn)和附近的現(xiàn)有采樣點(diǎn)。網(wǎng)格加速每個(gè)候選采樣點(diǎn)的距離檢查。網(wǎng)格尺寸r /√2確保每個(gè)單元可以包含至多一個(gè)采樣點(diǎn)，并且僅需要檢查固定數(shù)量的相鄰單元。

如果候選采樣點(diǎn)是可以接受的，它被添加作為一個(gè)新的采樣點(diǎn)，然后隨機(jī)選擇一個(gè)新的活躍采樣點(diǎn)。如果沒有一個(gè)候選采樣點(diǎn)是可以接受的，所選擇的活躍采樣點(diǎn)被標(biāo)記為無效 （顏色從紅色變?yōu)楹谏?/span> 。當(dāng)沒有采樣點(diǎn)保持活躍時(shí)，該算法終止。

面積用著色表示的Voronoi圖顯示了泊松盤采樣算法相對(duì)于最佳候選算法的改進(jìn)，沒有深藍(lán)色或淺黃色細(xì)胞：

泊松盤采樣下的《星夜》最大地保留了細(xì)節(jié)和引入了最少的噪音。它讓人想起美麗的羅馬馬賽克：

現(xiàn)在，你已經(jīng)看到了一些例子，讓我們簡要地思考一下為什么要把算法可視化。

娛樂

我發(fā)現(xiàn)可視化的算法有無窮的魅力，甚至令人著迷。特別是在涉及隨機(jī)性時(shí)。雖然這看似是一個(gè)牽強(qiáng)的理由，但不要低估了快樂的價(jià)值！此外，盡管這些可視化甚至在不理解基礎(chǔ)算法的情況下也可以參與，但是掌握算法的重要性可以給出更深的理解。

教學(xué)

你發(fā)現(xiàn)代碼或動(dòng)畫更有幫助嗎？偽代碼 （ 不能編譯的代碼的委婉語） 怎么樣？ 雖然形式描述在明確的文檔中有它的位置，可視化可以使直觀的理解更容易。

調(diào)試

你有沒有實(shí)現(xiàn)基于形式描述的算法？ 可能很難！ 能夠看到你的代碼在做什么可以提高生產(chǎn)力。 可視化不能取代測試需求，但測試主要用于檢測故障而不是解釋它。即使輸出看起來正確，可視化還可以在實(shí)現(xiàn)過程中發(fā)現(xiàn)意外的表現(xiàn) （參看Bret Victor的《可學(xué)習(xí)的編程》和為了優(yōu)秀的相關(guān)工作的《發(fā)明原理》） 。

學(xué)習(xí)

即使你只是想為自己學(xué)習(xí)，可視化會(huì)是一個(gè)很好的方式來得到深刻的理解。教學(xué)是最有效的學(xué)習(xí)方法之一，實(shí)現(xiàn)可視化就像教自己。我發(fā)現(xiàn)看到它，而不是熟記小而容易忘記細(xì)節(jié)的代碼，更容易直觀地記住一個(gè)算法。

洗牌

洗牌是隨機(jī)重新排列一組元素的過程。例如，你可以在打牌之前洗牌。一個(gè)好的洗牌算法是無偏的，其中每個(gè)排序都有相同的可能性。

Fisher-Yates shuffle是一個(gè)最佳的洗牌算法。 它不僅是無偏的，而且在線性時(shí)間內(nèi)運(yùn)行，使用恒定的空間，并且易于實(shí)現(xiàn)。

▼代碼如下：

function shuffle(array) {

varn = 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;

}

以上是代碼，下面是一個(gè)可視化的解釋：

每一條線代表一個(gè)數(shù)字，數(shù)字小向左傾斜，數(shù)字大就向右傾斜。

請(qǐng)注意，你可以對(duì)一組任何東西進(jìn)行洗牌，不只是數(shù)字，但這種可視化編碼對(duì)于顯示元素的順序很管用。它的靈感來自于Robert Sedgwick的《用C語言實(shí)現(xiàn)的算法》中的排序可視化。

該算法把數(shù)組劃分為兩個(gè)部分，右半邊是已洗牌區(qū)域 （用黑色表示） ，左半邊是待洗牌區(qū)域 （用灰色表示） 。每一步從左邊的待洗牌區(qū)域隨機(jī)選擇一個(gè)元素并將其移動(dòng)到右側(cè)，已洗牌區(qū)域元素?cái)?shù)量擴(kuò)大了1個(gè)。左半邊的初始順序不必保留，這樣給已洗牌區(qū)域的新元素提供了空間，該算法可以簡單地講元素交換到位。最終所有的元素都被洗牌，算法終止。

如果Fisher–Yates是一個(gè)很好的算法，那么一個(gè)不好的算法是什么樣的？

▼這是一個(gè)：

//不要這么做！

function shuffle(array) {

return array.sort(function(a, b) {

return Math.random() – .5; // ?_?

});

}

這種方法利用排序通過指定隨機(jī)比較器函數(shù)來洗牌。比較器定義元素的順序。它使用參數(shù)a和b （要比較的數(shù)組中的兩個(gè)元素） ，如果a小于b，則返回小于零的值，如果a大于b，則返回大于零的值，如果a和b相等，則返回0。比較器在排序期間重復(fù)調(diào)用。

如果不給array.sort指定一個(gè)比較器，元素按照字典序列排序。

在這里，比較器返回一個(gè)在-0.5和+0.5之間的隨機(jī)數(shù)。假設(shè)這定義了一個(gè)隨機(jī)順序，那么排序會(huì)隨機(jī)地混雜元素并實(shí)施好的洗牌。

不幸的是，這個(gè)假設(shè)是有缺陷的。隨機(jī)成對(duì)順序 （對(duì)于任何兩個(gè)元素） 不會(huì)為一組元素建立隨機(jī)順序。比較器必須遵守傳遞性：如果a> b和b> c，則a> c。但隨機(jī)比較器返回一個(gè)隨機(jī)值，違反了傳遞性，并導(dǎo)致array.sort的行為是未定義的！可能你會(huì)有運(yùn)氣，也可能沒有。

它怎么不好呢？我們可以通過可視化輸出來試著回答這個(gè)問題：

該算法不好的另一個(gè)原因是排序需要O（n lg n）時(shí)間，使得它顯著地慢于只需要O（n）時(shí)間的Fisher-Yates算法。但是速度缺陷比偏差缺陷小。

這可能看起來是隨機(jī)的，因此你可能會(huì)得出結(jié)論，隨機(jī)比較器洗牌足夠好了，并不再關(guān)注偏差，看作是迂腐的。但看起來可能會(huì)誤導(dǎo)！有許多對(duì)人眼來說看起來是隨機(jī)的，但實(shí)際上是非隨機(jī)的。

這種欺騙表明可視化不是一個(gè)魔術(shù)棒。 算法的單次運(yùn)行顯示不能有效地評(píng)估其隨機(jī)性的質(zhì)量。我們必須仔細(xì)設(shè)計(jì)一個(gè)可視化來解決手頭的具體問題： 算法的偏差是什么？

為了顯示偏差，我們必須首先定義它。一個(gè)定義是基于在洗牌之后索引i處的數(shù)組元素將在洗牌之后處于索引j的概率。如果算法是無偏的，則每個(gè)元素在洗牌結(jié)束后出現(xiàn)在每個(gè)索引處的概率相等，因此所有i和j的概率相同：1 / n，其中n是元素的數(shù)量。

分析計(jì)算這些概率是困難的，因?yàn)樗Q于知道使用的確切排序算法。但是根據(jù)經(jīng)驗(yàn)計(jì)算是很容易的：我們簡單地洗牌數(shù)千次，并計(jì)數(shù)索引j處元素i的出現(xiàn)次數(shù)。該概率矩陣的有效顯示是矩陣圖：

矩陣的列 （水平位置） 表示在洗牌之前的元素的索引，而行 （垂直位置） 表示洗牌之后的元素的索引。概率用顏色編碼：綠色單元表示正偏差，其中元素出現(xiàn)地比我們對(duì)無偏差算法的預(yù)期更頻繁；同樣紅色單元表示負(fù)偏差，其發(fā)生頻率低于預(yù)期。

如上所示，Chrome中的隨機(jī)比較器洗牌結(jié)果是令人驚訝的是平庸。部分陣列僅弱偏置。然而，它在對(duì)角線下方表現(xiàn)出強(qiáng)的正偏置，這表示將元素從索引i推到i + 1或i + 2的趨勢。第一行、中間行和最后一行也有奇怪的行為，這可能是Chrome使用“三中值”的快速排序的結(jié)果。

無偏的Fisher–Yates算法看上去是這樣的：

除了由于經(jīng)驗(yàn)測量的少量噪聲之外，在該矩陣中沒有可見的規(guī)律。 （如果需要，可以通過進(jìn)行額外的測量來降低噪聲。）

隨機(jī)比較器洗牌的行為在很大程度上取決于瀏覽器。不同的瀏覽器使用不同的排序算法，并且不同的排序算法與 （破壞了的） 隨機(jī)比較器表現(xiàn)非常不同。這里是隨機(jī)比較器在Firefox上洗牌的結(jié)果：

這是非常失偏的！所得到的數(shù)組通常幾乎沒有洗過牌，如該矩陣中的強(qiáng)綠色對(duì)角線所示。這并不意味著Chrome的排序是比Firefox的“更好”，它只是意味著不應(yīng)該使用隨機(jī)比較器洗牌。隨機(jī)比較器從根本上被破壞了。

排序

排序是洗牌的逆過程——它從無序創(chuàng)建順序，反之亦然。這使得排序成為更困難的問題，要為不同的權(quán)衡和約束設(shè)計(jì)各種解決方案。

最知名的排序算法之一是快速排序。

Quicksort首先通過選擇一個(gè)基準(zhǔn)將數(shù)組分成兩個(gè)部分。 左半部包含所有小于基準(zhǔn)的元素，而右半部包含大于基準(zhǔn)的所有元素。在數(shù)組分區(qū)后，快速排序在左右兩部分內(nèi)遞歸。當(dāng)每個(gè)部分只包含一個(gè)元素時(shí)，遞歸停止。

分區(qū)操作使得只在數(shù)組的活動(dòng)部分上進(jìn)行單一操作。類似于Fisher-Yates通過交換元素遞增地建立洗牌區(qū)，分區(qū)操作遞增地構(gòu)建子陣列的較小 （左） 和較大 （右） 部分。當(dāng)每個(gè)元素被訪問時(shí)，如果它小于基準(zhǔn)，它被交換到較小部分; 如果它大于基準(zhǔn)，則分區(qū)操作移動(dòng)到下一個(gè)元素。

▼代碼如下所示：

function quicksort(array, left, right) {

if(left < right – 1) {

var pivot = left + right >> 1;

pivot = partition(array, left, right, pivot);

quicksort(array, left, pivot);

quicksort(array, pivot + 1, right);

}

}

?

function partition(array, left, right,pivot) {

varpivotValue = array[pivot];

swap(array, pivot, –right);

for(var i = left; i < right; ++i) {

if (array[i] < pivotValue) {

swap(array, i, left++);

}

}

swap(array, left, right);

return left;

}

快速排序有很多版本。上面顯示的是最簡單也是速度最慢的一個(gè)。這種變化對(duì)于教學(xué)是有用的，但是在實(shí)踐中，為了得到更好的性能應(yīng)用了更復(fù)雜的實(shí)現(xiàn)方法。

常見的改進(jìn)是“三中值”樞軸選擇，其中第一，中間和最后元素的中值被用作基準(zhǔn)。這傾向于選擇更接近真實(shí)中值的基準(zhǔn)，導(dǎo)致類似大小的左半部分和右半部分以及遞歸層數(shù)更少。另一個(gè)優(yōu)化是對(duì)于數(shù)組的小部分來說，從快速排序切換到插入排序，由于函數(shù)調(diào)用的開銷問題這可以更快。

一個(gè)特別聰明的變化是Yaroslavskiy的雙基準(zhǔn)快速排序，它將數(shù)組分為三個(gè)部分，而不是兩個(gè)。這是Java和Dart中的默認(rèn)排序算法。

上面的排序和洗牌動(dòng)畫有不錯(cuò)的屬性，那就是時(shí)間映射到時(shí)間：我們可以簡單地觀察算法如何進(jìn)行。但是雖然直觀，動(dòng)畫也可以讓人在看的時(shí)候感到沮喪，特別是如果我們想關(guān)注偶然的、奇怪的算法的行為。動(dòng)畫也嚴(yán)重依賴我們的記憶來觀察行為模式。雖然通過控制以暫停和擦洗時(shí)間來改進(jìn)動(dòng)畫，但是同時(shí)展示一切的靜態(tài)顯示甚至可以更有效。眼睛掃描比手動(dòng)要快。

將動(dòng)畫轉(zhuǎn)換為靜態(tài)顯示的一種簡單方法是從動(dòng)畫中選擇關(guān)鍵幀，并按順序顯示，如同漫畫一樣。如果我們在關(guān)鍵幀之間刪除冗余信息，我們會(huì)更有效地使用空間。更密集的顯示可能需要更多的研究來理解，但是可以更快地掃描，因?yàn)檠劬σ苿?dòng)較少。

下面，每一行顯示遞歸之前的數(shù)組的狀態(tài)。第一行是數(shù)組的初始狀態(tài)，第二行是第一次分區(qū)操作之后的數(shù)組，第三行是第一個(gè)分區(qū)的左右部分再次被分區(qū)之后的數(shù)組等等。實(shí)際上，這是廣度優(yōu)先快速排序，其中左右兩側(cè)的分區(qū)操作并行進(jìn)行。

與之前一樣，每個(gè)分區(qū)操作的基準(zhǔn)以紅色突出顯示。請(qǐng)注意，在下一級(jí)遞歸處，基準(zhǔn)將變?yōu)榛疑悍謪^(qū)操作完成后，關(guān)聯(lián)的基準(zhǔn)處于其最終的排序位置。顯示的總深度是遞歸的最大深度，給出了快速排序執(zhí)行如何有效的感覺。它在很大程度上取決于輸入和基準(zhǔn)選擇。

快速排序的另一個(gè)靜態(tài)顯示，密度較小但可能更容易讀，將每個(gè)元素表示為彩色線，并顯示每個(gè)順序交換。 （這種形式是受到Aldo Cortesi的排序可視化的啟發(fā)。） 更小的值顏色更輕，更大的值顏色更深。

現(xiàn)在已經(jīng)看到了同一算法的三種不同的視覺展示：動(dòng)畫、稠密靜態(tài)展示和稀疏靜態(tài)展示。每種形式都有各自的優(yōu)缺點(diǎn)。動(dòng)畫看起來有趣，但靜態(tài)的可視化允許仔細(xì)檢查，而不用著急。稀疏展示可能更容易理解，但密集展示除了顯示細(xì)節(jié)之外，還顯示算法行為的“宏觀”視圖。

在我們繼續(xù)下去之前，讓我們將快速排序與另一個(gè)眾所周知的排序算法——?dú)w并排序進(jìn)行對(duì)比。

▼下列為歸并排序的代碼：

function mergesort(array) {

varn = array.length, a0 = array, a1 = new Array(n);

for(var m = 1; m < n; m <<= 1) {

for (var i = 0; i < n; i += m << 1) {

var left = i,

right = Math.min(i + m, n),

end = Math.min(i + (m << 1), n);

merge(a0, a1, left, right, end);

}

i= a0, a0 = a1, a1 = i;

}

if(array === a1) {

for (var i = 0; i < n; ++i) {

array[i] = a0[i];

}

}

}

function merge(a0, a1, left, right, end) {

for(var i0 = left, i1 = right; left < end; ++left) {

if (i0 < right && (i1 >= end || a0[i0] <= a0[i1])) {

a1[left] = a0[i0++];

}else {

a1[left] = a0[i1++];

}

}

}

下面是相關(guān)的動(dòng)畫展示：

正如你可能從代碼或動(dòng)畫中推測的，歸并排序采用了一種與快速排序非常不同的排序方法?？焖倥判蛲ㄟ^執(zhí)行交換就地運(yùn)行，與快速排序不同，歸并排序需要額外的數(shù)組副本。這個(gè)額外的空間用于歸并排序的子數(shù)組，把來自子數(shù)組的每對(duì)元素組合在一起，同時(shí)保持順序。由于歸并排序運(yùn)行副本而不是交換，因此我們必須相應(yīng)地修改動(dòng)畫 （或有誤導(dǎo)讀者的風(fēng)險(xiǎn)） 。

歸并排序自下而上進(jìn)行。最初，它合并大小為1的子數(shù)組，因?yàn)樗鼈兘?jīng)過了排序。每個(gè)相鄰的子數(shù)組：首先，只是一對(duì)元素，使用額外的數(shù)組合并為大小為2的排序子數(shù)組。然后，將大小為2的每個(gè)相鄰排序子數(shù)組合并成大小為4的排序子數(shù)組。每次遍歷整個(gè)數(shù)組后，歸并排序?qū)⑴判蜃訑?shù)組的大小加倍：8，16，等等。最終，這個(gè)加倍合并了整個(gè)數(shù)組，算法終止。

因?yàn)闅w并排序在數(shù)組上執(zhí)行重復(fù)遍歷而不是像快速排序那樣遞歸，并且因?yàn)槊看伪闅v使排序的子數(shù)組的大小加倍，而不考慮輸入，所以更容易設(shè)計(jì)成靜態(tài)展示。我們只需在每次合并后顯示數(shù)組的狀態(tài)。

讓我們再花一點(diǎn)時(shí)間來想想我們所看到的。這里的目標(biāo)是研究算法的行為而不是特定的數(shù)據(jù)集。但仍然有數(shù)據(jù)，這是必然的，因?yàn)閿?shù)據(jù)是從算法的執(zhí)行而導(dǎo)出的。這意味著我們可以使用派生數(shù)據(jù)的類型來將算法可視化分類。

▼第0級(jí)/黑盒

最簡單的類，只顯示輸出。不解釋算法的操作，但它仍然可以驗(yàn)證正確性。通過將算法視為黑盒，可以更容易地比較不同算法的輸出。黑盒可視化還可以與更深入的輸出分析結(jié)合，例如上面顯示的隨機(jī)偏移矩陣圖。

▼第1級(jí)/灰盒

許多算法 （雖然不是全部） 增量地構(gòu)建輸出。隨著它的進(jìn)程，通過可視化過程中間的輸出，開始看到算法是如何工作的。這解釋了更多而不必引入新的抽象概念，因?yàn)檫^程中間和最終輸出共享相同的結(jié)構(gòu)。然而，這種類型的可視化會(huì)產(chǎn)生比它可以回答的更多的問題，因?yàn)樗鼪]有解釋為什么算法做它要做的事。

▼第2級(jí)/白盒

為了回答“為什么”這個(gè)問題，白盒可視化暴露算法的內(nèi)部狀態(tài)以及其中間過程輸出。這種類型有最大的潛力來解釋，但也對(duì)讀者是最大的負(fù)擔(dān)，因?yàn)閮?nèi)部狀態(tài)的意義和目的必須清楚地描述。這里有一個(gè)風(fēng)險(xiǎn)，額外的復(fù)雜性會(huì)壓垮讀者；分層信息可以使圖形更容易獲得。最后，由于內(nèi)部狀態(tài)高度依賴于特定算法，這種類型的可視化通常不適合于比較算法。

還有實(shí)現(xiàn)算法可視化的實(shí)際問題。通常不能只是運(yùn)行代碼；必須有辦法捕獲它以便可視化 （查看本文的源代碼示例） 。甚至可能需要與可視化交叉執(zhí)行，這對(duì)于捕獲遞歸算法的堆棧狀態(tài)尤其具有挑戰(zhàn)性。語言解析器如Esprima可以通過代碼檢測方便地實(shí)現(xiàn)算法可視化，將執(zhí)行代碼與可視化代碼完全分離。

迷宮的生成

最后一個(gè)問題，我們會(huì)看下的是迷宮生成。本節(jié)中的所有算法生成二維矩形網(wǎng)格的生成樹。這意味著沒有循環(huán)，并且存在從左下角的根到迷宮中的每個(gè)其他單元的唯一路徑。

我為如此深?yuàn)W的主題而感到歉意。 我不知道為什么這些算法是有用的，除了簡單的游戲，可能是關(guān)于電氣網(wǎng)絡(luò)。但即使如此，它們從可視化視角看也很迷人，因?yàn)樗鼈円苑浅２煌姆绞浇鉀Q了同樣的有高度約束的問題。

觀看它們真有趣。

隨機(jī)遍歷算法初始化左下角的迷宮的第一個(gè)單元。該算法然后跟蹤迷宮可以擴(kuò)展的所有可能的方式 （以紅色標(biāo)示） 。在每個(gè)步驟，隨機(jī)挑選這些可能的擴(kuò)展中的一個(gè)，只要這不重新連接它與另一個(gè)部分的迷宮，該迷宮就會(huì)延伸擴(kuò)展。

像Bridon的泊松盤采樣算法一樣，隨機(jī)遍歷保持前沿，并從邊界中隨機(jī)選擇進(jìn)行擴(kuò)展。因此，兩種算法似乎都像真菌一樣有機(jī)地生長。

隨機(jī)深度優(yōu)先遍歷遵循一個(gè)非常不同的模式：

不是每次都選擇一個(gè)新的隨機(jī)通道，該算法總是在隨機(jī)方向上延伸最深的通道，一個(gè)最長的回到根的通道。因此，隨機(jī)深度優(yōu)先遍歷分支，僅當(dāng)當(dāng)前路徑是個(gè)死結(jié)時(shí)，進(jìn)入迷宮的較早時(shí)的分支。要繼續(xù)，它會(huì)回溯，直到它可以開始一個(gè)新的分支。這種蛇狀的探索導(dǎo)致迷宮帶有明顯更少的分支和更長的蜿蜒通道。

Prim的算法構(gòu)造最小生成樹，具有加權(quán)邊緣的圖的生成樹具有最低的總權(quán)重。 該算法可以用于通過隨機(jī)初始化邊緣權(quán)重來構(gòu)建隨機(jī)生成樹：

在每個(gè)步驟中，Prim的算法使用連接到現(xiàn)有迷宮的最低加權(quán)邊緣 （潛在方向） 擴(kuò)展迷宮。如果該邊緣將形成環(huán)路，則其被丟棄，然后考慮次最低加權(quán)邊緣。

Prim的算法通常使用堆來實(shí)現(xiàn)，這是用于對(duì)元素進(jìn)行優(yōu)先級(jí)排序的有效數(shù)據(jù)結(jié)構(gòu)。 當(dāng)一個(gè)新的單元格加入迷宮時(shí)，連接的邊緣 （以紅色標(biāo)示） 被添加到堆。盡管邊以任意順序添加，堆允許快速除去最低加權(quán)邊。

最后，這是一個(gè)最不尋常的例子：

Wilson的算法使用循環(huán)擦除隨機(jī)游走來生成統(tǒng)一的生成樹，是所有可能的生成樹的無偏差樣本。我們看到的其他迷宮生成算法缺乏這個(gè)美麗的數(shù)學(xué)屬性。

該算法用任意起始單元初始化迷宮。然后，新的單元格被加入迷宮，啟動(dòng)隨機(jī)游走 （用紅色標(biāo)示） 。繼續(xù)隨機(jī)游走，直到它重新連接到現(xiàn)有的迷宮 （用白色標(biāo)示） 。然而，如果隨機(jī)游走本身相交，則在隨機(jī)游走繼續(xù)之前擦除所得到的循環(huán)。

最初，算法看著可能令人沮喪地慢，因?yàn)樵缙陔S機(jī)游走不可能與小的現(xiàn)有迷宮重新連接。隨著迷宮增長，隨機(jī)游走變得更可能與迷宮碰撞，并且算法加速顯著。

這四種迷宮生成算法的工作方式截然不同。然而，當(dāng)動(dòng)畫結(jié)束時(shí)，所得到的迷宮彼此件難以區(qū)分。動(dòng)畫可用于顯示算法如何工作，但無法顯示生成的樹結(jié)構(gòu)。

一種顯示結(jié)構(gòu)，而不是過程的方法是用顏色填充迷宮：

顏色編碼樹深度——回到在左下角的根的路徑的長度。隨著越深入樹，顏色標(biāo)度循環(huán)；當(dāng)一個(gè)深路徑循環(huán)回鄰近一個(gè)淺路徑時(shí)，這偶爾會(huì)誤導(dǎo)，但更高的對(duì)比度允許更好的局部結(jié)構(gòu)的分化。 （這不是一個(gè)傳統(tǒng)的彩虹色標(biāo)，名義上被認(rèn)為有害，但立方體的彩虹具有改善的感知性能的能力。）

我們可以通過減去墻，進(jìn)一步強(qiáng)調(diào)迷宮的結(jié)構(gòu)，減少視覺噪聲。下面的圖中，每個(gè)像素表示通過迷宮的路徑。如上所述，路徑通過深度著色，隨著時(shí)間的推移，顏色像潮水一樣更深入迷宮。

顏色的同心圓，像領(lǐng)帶染色襯衫，揭示隨機(jī)遍歷產(chǎn)生許多分支路徑。然而，每條路徑的形狀不是特別有趣，因?yàn)樗灾本€回到根。因?yàn)殡S機(jī)遍歷通過從邊界隨機(jī)采集來擴(kuò)展迷宮，路徑從來沒有被給予很多蜿蜒的自由 – 它們最終與增長的邊界碰撞并且由于對(duì)循環(huán)的限制而終止。

另一方面，隨機(jī)深度優(yōu)先遍歷都是關(guān)于蜿蜒的：

這個(gè)動(dòng)畫以之前那個(gè)50倍的速度進(jìn)行。這種加速是必要的，因?yàn)橛捎诜种в邢?，隨機(jī)深度優(yōu)先遍歷迷宮比隨機(jī)遍歷迷宮深得多。可以看到，在任何特定深度的活動(dòng)分支通常只有一個(gè)，很少有多個(gè)。

下面，用隨機(jī)圖演示Prim的算法：

這更有趣！同時(shí)擴(kuò)展的小花的顏色顯示基本的分支，并且有比隨機(jī)遍歷更復(fù)雜的全局結(jié)構(gòu)。

Wilson的算法盡管操作很不同，卻似乎產(chǎn)生了非常相似的結(jié)果：

只是因?yàn)樗鼈兛雌饋硐嗤⒉灰馕吨鼈兿嗤?。盡管外觀上一樣，Prim的算法在隨機(jī)加權(quán)圖不生成統(tǒng)一的生成樹 （據(jù)我所知，證明這是我的專業(yè)領(lǐng)域之外） 。可視化有時(shí)會(huì)由于人為錯(cuò)誤而會(huì)誤導(dǎo)。早期版本的Prim的顏色洪水有一個(gè)錯(cuò)誤，顏色標(biāo)度旋轉(zhuǎn)的速度是預(yù)期的兩倍；這表明Prim和Wilson的算法產(chǎn)生了非常不同的樹，而事實(shí)上它們看起來相似多于差異。

由于這些迷宮是生成樹，也可以使用專門的樹來可視化地顯示結(jié)構(gòu)。為了說明迷宮和樹之間的對(duì)偶性，這里由Wilson的算法生成的迷宮的通道 （以白色標(biāo)示） 逐漸變換成整潔的樹布局。與其他動(dòng)畫一樣，它從深度開始，從根開始進(jìn)一步擴(kuò)展到葉子：

為了進(jìn)行比較，我們再來看看隨機(jī)深度優(yōu)先遍歷產(chǎn)生的擁有長通道和小分枝的樹。

兩棵樹具有相同數(shù)量的節(jié)點(diǎn) （3239） 并且被縮放以適合相同區(qū)域 （960×500個(gè)像素） 。這隱藏了一個(gè)重要的區(qū)別：在這個(gè)尺寸上，隨機(jī)深度優(yōu)先遍歷通常產(chǎn)生比Wilson的算法深兩到五倍的樹。上面的樹的深度分別為315和1338。在用于顏色洪水的更大的480000節(jié)點(diǎn)的迷宮中，隨機(jī)深度優(yōu)先遍歷產(chǎn)生的樹深10到20倍！

利用視覺來思考

本文重點(diǎn)研究算法。然而，這里討論的技術(shù)適用于更廣泛的問題空間： 數(shù)學(xué)公式、動(dòng)態(tài)系統(tǒng)、過程等?；旧?，任何需要理解代碼的地方。

那么：

——為什么要可視化算法呢？為什么要可視化一些東西？

——利用人的視覺系統(tǒng)，可以提高理解?；蛘吒唵蔚卣f，利用視覺去思考。

來源：https://bost.ocks.org/mike/algorithms/