了解算法設(shè)計(jì)原理
算法不一定是一種特殊的操作。它們是概念性的，是您為實(shí)現(xiàn)特定目標(biāo)而在代碼中采取的一組步驟。
本文將深入探討算法設(shè)計(jì)的原理。如果您不清楚我指的是什么，請(qǐng)繼續(xù)閱讀！
當(dāng)您聽(tīng)到“算法”一詞時(shí)，您可能會(huì)以以下三種方式之一進(jìn)行響應(yīng)：
您會(huì)立即了解并理解我們?cè)谡f(shuō)什么，因?yàn)槟鷮W(xué)習(xí)過(guò)計(jì)算機(jī)科學(xué)。
您知道算法是諸如Google和Facebook這樣的公司的主力軍，但您實(shí)際上不確定這個(gè)詞是什么意思。
您奔跑而躲避恐懼，因?yàn)槟鷮?duì)算法的了解使您想起了高中微積分的噩夢(mèng)。
如果您是后兩者之一，那么本文適合您。
究竟是什么算法？
算法不一定是一種特殊的操作。它們是概念性的，是您為實(shí)現(xiàn)特定目標(biāo)而在代碼中采取的一組步驟。
通常以簡(jiǎn)單的術(shù)語(yǔ)將算法定義為“完成任務(wù)的指令”。他們也被稱為“食譜”。在《社交網(wǎng)絡(luò)》中，扎克伯格需要使用算法來(lái)使Facemash正常工作。如果您看過(guò)電影，可能還記得在Mark宿舍房間的窗戶上看到一個(gè)簡(jiǎn)陋的方程式。但是那個(gè)草的代數(shù)與Mark簡(jiǎn)單的“熱門(mén)與否”網(wǎng)站有什么關(guān)系？
算法確實(shí)是指令。也許更準(zhǔn)確的描述是算法是用于以有效方式完成任務(wù)的模式。扎克伯格的Facemash是一個(gè)投票網(wǎng)站，用于確定某人相對(duì)于整個(gè)人群的吸引力，但是只會(huì)為用戶提供兩個(gè)人之間的選擇權(quán)。馬克·扎克伯格（Mark Zuckerberg）需要一種算法，該算法可以確定哪些人可以相互匹配，以及如何相對(duì)于該人的先前歷史和先前的競(jìng)爭(zhēng)者來(lái)評(píng)估投票。這不僅需要簡(jiǎn)單地計(jì)算每個(gè)人的票數(shù)，還需要更多的直覺(jué)。
例如，假設(shè)您要?jiǎng)?chuàng)建一種算法，將1加到任何負(fù)數(shù)，再?gòu)?減去1，對(duì)0不做任何事情。您可能會(huì)執(zhí)行以下操作（在JavaScript式偽代碼中）：
function addOrSubtractOne(number){
if (number < 0) {
return number + 1
} else if (number < 0) {
return number - 1
} else if (number == 0) {
return 0;
}
}
您可能對(duì)自己說(shuō)：“這是一個(gè)功能?！?而且你是對(duì)的。算法不一定是一種特殊的操作。它們是概念性的，您可以通過(guò)代碼中的一系列步驟來(lái)實(shí)現(xiàn)特定的目標(biāo)。
那么為什么他們有什么大不了的呢？顯然，對(duì)數(shù)字加1或減1是一件相當(dāng)簡(jiǎn)單的事情。
但是，讓我們先談一下搜索。要搜索一組數(shù)字中的數(shù)字，您會(huì)如何考慮？天真的方法是迭代數(shù)字，將每個(gè)數(shù)字與您要搜索的數(shù)字進(jìn)行比較。但這不是一個(gè)有效的解決方案，并且可能的完成時(shí)間范圍非常廣，因此在擴(kuò)展到大型搜索集時(shí)，這是一種不穩(wěn)定且不可靠的搜索方法。
function naiveSearch(needle, haystack){
for (var i = 0; i < haystack.length; i++){
if (haystack[i] == needle) { return needle; }
}
return false;
}
幸運(yùn)的是，我們可以為此做得更好。
為什么效率低下？
對(duì)算法有深刻的理解和鑒賞，沒(méi)有比成為更好的算法設(shè)計(jì)者更好的方法了。
假設(shè)您的數(shù)組有50,000個(gè)條目，并且您進(jìn)行了蠻力搜索（即通過(guò)迭代整個(gè)數(shù)組進(jìn)行搜索）。在最佳情況下，您要搜索的條目將是50,000個(gè)條目數(shù)組中的第一個(gè)條目。但是，在最壞的情況下，該算法完成的時(shí)間將比在最壞的情況下長(zhǎng)50,000倍。
那有什么更好的呢？
相反，您將使用二進(jìn)制搜索進(jìn)行搜索。這涉及到對(duì)數(shù)組進(jìn)行排序（我將讓您自己學(xué)習(xí)），然后將數(shù)組分為兩半，并檢查搜索數(shù)是否大于或小于數(shù)組中途標(biāo)記。如果它大于已排序數(shù)組的中途標(biāo)記，那么我們知道前半部分可以被丟棄，因?yàn)樗阉鞯降臄?shù)字不屬于數(shù)組的一部分。我們還可以通過(guò)定義數(shù)組的外部邊界并檢查查找的數(shù)字是否存在于這些邊界之外來(lái)進(jìn)行大量工作，如果存在，我們將進(jìn)行多次迭代操作并將其翻轉(zhuǎn)一次迭代操作（在蠻力算法中，該操作將執(zhí)行50,000次操作）。
sortedHaystack = recursiveSort(haystack);
function bSearch(needle, sortedHaystack, firstIteration){
if (firstIteration){
if (needle > sortedHaystack.last || needle < sortedHaystack.first){
return false;
}
}
if (haystack.length == 2){
if (needle == haystack[0]) {
return haystack[0];
} else {
return haystack[1];
}
}
if (needle < haystack[haystack.length/2]){
bSearch(needle, haystack[0..haystack.length/2 -1], false);
} else {
bSearch(needle, haystack[haystack.length/2..haystack.length], false);
}
}
聽(tīng)起來(lái)很復(fù)雜
考慮單個(gè)二進(jìn)制搜索算法看似復(fù)雜的性質(zhì)，并將其應(yīng)用于數(shù)十億個(gè)可能的鏈接（通過(guò)Google搜索）。除此之外，讓我們對(duì)鏈接的搜索應(yīng)用某種排名系統(tǒng)，以給出響應(yīng)頁(yè)面的順序。更好的是，基于人工智能社交模型應(yīng)用某種看似隨機(jī)的“建議”系統(tǒng)，該系統(tǒng)旨在識(shí)別您可能希望添加為朋友的人。
這使我們對(duì)為什么算法不僅僅是函數(shù)的奇特名稱有了更清晰的了解。在最好的情況下，它們是聰明，有效的方法來(lái)完成某些工作，而這些方法比最明顯的解決方案需要更高的直覺(jué)。他們可以花上數(shù)年的時(shí)間才能完成一臺(tái)超級(jí)計(jì)算機(jī)的工作，然后將其變成一項(xiàng)在手機(jī)上只需幾秒鐘即可完成的任務(wù)。
算法如何應(yīng)用于我？
對(duì)于我們大多數(shù)開(kāi)發(fā)人員而言，我們并不是每天都在設(shè)計(jì)高級(jí)抽象算法。
幸運(yùn)的是，我們站在我們之前的開(kāi)發(fā)人員的肩膀上，他們編寫(xiě)了本機(jī)排序函數(shù)，并允許我們以高效的方式在字符串中搜索帶有indexOf的子字符串。
但是我們確實(shí)要處理我們自己的算法。我們for每天創(chuàng)建循環(huán)并編寫(xiě)函數(shù)；那么良好的算法設(shè)計(jì)原則如何可以幫助編寫(xiě)這些函數(shù)？
了解您的輸入
算法設(shè)計(jì)的主要原則之一是，如果可能，以某種方式構(gòu)建算法，使輸入本身可以為您完成一些工作。例如，如果您知道輸入將始終是數(shù)字，則無(wú)需對(duì)字符串進(jìn)行例外/檢查，也不必將值強(qiáng)制轉(zhuǎn)換為數(shù)字。如果您知道DOM元素for在JavaScript中的每次循環(huán)中都是相同的，則不應(yīng)該在每次迭代中都查詢?cè)撛亍Ｍ瑯?，在for循環(huán)中，如果可以使用（更接近）簡(jiǎn)單的操作來(lái)完成相同的事情，則不應(yīng)使用帶有開(kāi)銷的便捷函數(shù)。
// don't do this:
for (var i = 1000; i > 0; i--){
$("#foo").append("<span>bar</span>");
}
// do this instead
var foo = $("#foo");
var s = "";
for(var i = 1000; i > 0; i--){
s += "<span>bar</span>";
}
foo.append(s);
如果您是JavaScript開(kāi)發(fā)人員（并且使用jQuery），并且您不知道上述函數(shù)的功能以及它們之間的顯著不同，那么接下來(lái)要講的就是您。
了解您的工具
在最好的情況下，[算法]是一種聰明，有效的方法來(lái)完成某些工作，而這種方法比最明顯的解決方案需要更高的直覺(jué)。
不言而喻，這很容易想到。但是，“知道如何編寫(xiě)jQuery”和“了解jQuery”之間是有區(qū)別的。了解您的工具意味著您立即了解每行代碼的作用（立即（函數(shù)的返回值或方法的效果）和隱式的（與運(yùn)行庫(kù)函數(shù)相關(guān)的開(kāi)銷多少），或者哪一種是最有效的連接字符串的方法）。要編寫(xiě)出色的算法，重要的是要了解低級(jí)函數(shù)或?qū)嵱贸绦虻男阅?，而不僅僅是它們的名稱和實(shí)現(xiàn)。
了解環(huán)境
設(shè)計(jì)高效的算法是一項(xiàng)全力以赴的工作。除了將您的工具理解為一個(gè)獨(dú)立的部分以外，您還必須了解它們與現(xiàn)有大型系統(tǒng)交互的方式。例如，要完全了解特定應(yīng)用程序中的JavaScript，了解跨瀏覽器場(chǎng)景中JavaScript的DOM和性能，可用內(nèi)存如何影響渲染速度，您可能與之交互的服務(wù)器結(jié)構(gòu)（及其響應(yīng)），以及許多其他無(wú)形的考慮因素，例如使用情況。
減少工作量
通常，算法設(shè)計(jì)的目標(biāo)是用更少的步驟來(lái)完成一項(xiàng)工作。（有一些例外，例如Bcrypt哈希。）在編寫(xiě)代碼時(shí)，請(qǐng)考慮計(jì)算機(jī)為達(dá)到目標(biāo)所執(zhí)行的所有簡(jiǎn)單操作。這是一個(gè)簡(jiǎn)單的清單，可開(kāi)始著手進(jìn)行更有效的算法設(shè)計(jì)：
使用語(yǔ)言功能來(lái)減少操作（可變緩存，鏈接等）。
盡可能減少迭代循環(huán)嵌套。
盡可能在循環(huán)之外定義變量。
使用自動(dòng)循環(huán)索引（如果有）而不是手動(dòng)索引。
使用巧妙的歸約技術(shù)，例如遞歸除法和征服以及查詢優(yōu)化，以最小化遞歸過(guò)程的大小。
學(xué)習(xí)先進(jìn)技術(shù)
對(duì)算法有深刻的理解和鑒賞，沒(méi)有比成為更好的算法設(shè)計(jì)者更好的方法了。
每周花一兩個(gè)小時(shí)閱讀《計(jì)算機(jī)編程的藝術(shù)》。
嘗試進(jìn)行Facebook編程挑戰(zhàn)賽或Google Codejam。
學(xué)習(xí)使用不同的算法技術(shù)解決相同的問(wèn)題。
通過(guò).sort()較低級(jí)別的操作實(shí)現(xiàn)語(yǔ)言的內(nèi)置功能（例如）來(lái)挑戰(zhàn)自己。
結(jié)論
如果您不了解本文開(kāi)頭的算法是什么，那么希望現(xiàn)在，您對(duì)這個(gè)難以捉摸的術(shù)語(yǔ)有了更具體的了解。作為專業(yè)開(kāi)發(fā)人員，重要的是我們了解可以對(duì)所編寫(xiě)的代碼進(jìn)行分析和優(yōu)化，并且花時(shí)間對(duì)代碼的性能進(jìn)行分析也很重要。