在JavaScript數(shù)組中找到最小元素的位置

注* ?之前有篇文章介紹過數(shù)據(jù)遍歷的性能比較：?for in 比for loop慢至少20倍?，這是另外一篇比較數(shù)組查找性能的例子，通過對手工/indexOf/reduce三者的比較，再次映證，內(nèi)置函數(shù)不一下比手工寫的函數(shù)快。

今天的小程序甚至不是一個程序。這只是一個函數(shù)。

問題陳述如下:給定一個非空的JavaScript數(shù)字數(shù)組,找到最小值的索引。(如果最小值出現(xiàn)不止一次,那么任何此類索引是可以接受的。)

一個解決方案是進行簡單的手動操作,模擬用紙筆如何執(zhí)行操作:首先,你假設第一個元素是贏家,然后你遍歷其他元素。如果你的下一個元素小于第一個元素，那么你聲明這個元素是新的臨時的贏家。function?indexOfSmallest(a)?{

var?lowest?=?0;

for?(var?i?=?1;?i?

if?(a[i]?

}

return?lowest;

}

另一種解決方案是使用reduce內(nèi)聯(lián)函數(shù)本質(zhì)來運行循環(huán),所以你只需要提供初始猜測和if語句的業(yè)務邏輯。function?indexOfSmallest(a)?{

return?a.reduce(function(lowest,?next,?index)?{

return?next?

0);

}

第三個解決方案是使用JavaScript?內(nèi)聯(lián)函數(shù)找到最小的元素,然后將元素轉換為其索引。function?indexOfSmallest(a)?{

return?a.indexOf(Math.min.apply(Math,?a));

}

哪一個最快呢?

好吧,首先,你確定哪一個是最快之前,您需要確保他們都是正確的。你發(fā)現(xiàn)的一件事是,一旦數(shù)組變得很大最小/索引技術會失敗,至少它在IE瀏覽器和Firefox上是這樣的。(在我的例子中,Internet?Explorer和Firefox分別放棄了元素數(shù)量約為250000和500000的數(shù)組)。那是因為你開始觸及引擎的數(shù)量限制參數(shù)，這個參數(shù)你可以傳遞給一個函數(shù)。調(diào)用250000個元素的數(shù)組相當于最少調(diào)用250000個函數(shù)參數(shù)。所以我們會限制自己的數(shù)組長度最多為250000。分享結果之前,我想讓你猜猜哪個算法你認為將是最快和哪個是最慢的。

仍然在等。

我預計手工版本是最后一名,因為,畢竟,這是手工做的一切。我預計使用減少函數(shù)的版本稍快,因為它把一些工作交給了內(nèi)聯(lián)函數(shù)(盡管上面的函數(shù)調(diào)用可能否定了它的改進)。我預計min/?indexOf版本是最快的,因為幾乎所有的工作在內(nèi)聯(lián)函數(shù)中完成,并且兩次數(shù)據(jù)遍歷的開銷將會由內(nèi)聯(lián)函數(shù)的一些改進性能構成。

這里有三個版本在不同大小的數(shù)組上的計時,它是運行在隨機數(shù)據(jù)上。我正常運行了好幾次,所以這個結果與CPU速度是獨立的。

每個數(shù)組元素相對運行時間元素手工reducemin/indexOf

Internet?Explorer?9

100,0001.0002.1552.739

200,0001.0142.3243.099

250,0001.0232.2002.330

Internet?Explorer?10

100,0001.0004.0574.302

200,0001.0284.0574.642

250,0001.0194.0914.068

你感到驚訝嗎?我肯定我很驚訝!

我不僅完全向后又運算了一遍,但手工版本勝利的界限的是超出了我的想象的。

(這表明要知道程序的性能，唯一途徑肯定是坐下來測量它。)

我認為正在發(fā)生的是,JavaScript優(yōu)化器可以很好地優(yōu)化手工代碼,因為它非常簡單。?循環(huán)體沒有函數(shù)調(diào)用,只是一行,在外面沒關系的。使用內(nèi)聯(lián)函數(shù)的版本以從優(yōu)化器隱藏一些信息結束。(畢竟,優(yōu)化器不能提前預測是否有人覆蓋Array.prototype.reduce或者Math.prototype.min的默認實現(xiàn)，所以不能盲目的內(nèi)聯(lián)調(diào)用。)結果是,在IE9瀏覽器上運行手動版本可以快兩倍，在IE10上運行速度超過四倍。

我弄錯了,因為我想起了JavaScript太像一種解釋型語言。在一個純粹的解釋型語言,翻譯的開銷大約與你讓它做的事情的數(shù)量成正比,而不是與做這些事情是多么難成正比。就像一個對每一筆交易固定的服務費,不管交易是100美元50美分。你因此試圖做一筆大的買賣(調(diào)用復雜的內(nèi)聯(lián)函數(shù))而不是大量的小買賣(讀一個數(shù)組元素,比較兩個值,增加一個變量,一個變量復制到另一個)。

福利：我在Firefox上做了這個測試,因為我碰巧比較方便。

每個數(shù)組元素相對運行時間元素手工reducemin/indexOf

Firefox?16

100,0001.00021.5983.958

200,0000.84821.7012.515

250,0000.83921.7882.090

相同的數(shù)據(jù)收集在Firefox?16(這聽起來是可笑的老舊版本，因為到這篇文章到達隊列頭部的時候，Firefox將發(fā)行523版本)展示了一個不同的形象,盡管勝利者是相同的。數(shù)組大小增加的時候手動循環(huán)和min/?indexOf變得更高效。這表明,當你增加數(shù)據(jù)集的大小，固定的開銷逐漸變得不那么重要。

一件比較突出的事是,reduce()方法表現(xiàn)地比其他方法差。我的猜測是,設置函數(shù)調(diào)用(為了內(nèi)聯(lián)函數(shù)和腳本之間的轉換)開銷是很大的,并且JavaScript引擎實現(xiàn)器沒有花任何時間優(yōu)化這種案例,因為reduce在實際代碼中不常使用。

更新：我夸大了我構造一個好的故事敘述的天真。就像我書的序言中指出的那樣,我的故事也許并不完全正確,但他們已經(jīng)足夠真實。我當然知道JavaScript?如今是JITTED(即時解釋執(zhí)行),它改變了計算方式。(同時,是隱藏的數(shù)組副本。)

總結

以上是生活随笔為你收集整理的js数组查找最接近_在JavaScript数组中找到最小元素的位置的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。