查找數組中最常見元素的JavaScript函數的速度差異

Question

我正在學習面試，並且一直在練習一些練習題。問題是：

查找數組中最重複的整數。

這是我創建的功能和他們創建的功能。他們被適當命名。

var arr = [3, 6, 6, 1, 5, 8, 9, 6, 6] 
 

 
function mine(arr) { 
 
    arr.sort() 
 
    var count = 0; 
 
    var integer = 0; 
 
    var tempCount = 1; 
 
    var tempInteger = 0; 
 
    var prevInt = null 
 
    for (var i = 0; i < arr.length; i++) { 
 
    tempInteger = arr[i] 
 
    if (i > 0) { 
 
     prevInt = arr[i - 1] 
 
    } 
 
    if (prevInt == arr[i]) { 
 
     tempCount += 1 
 
     if (tempCount > count) { 
 
     count = tempCount 
 
     integer = tempInteger 
 
     } 
 
    } else { 
 
     tempCount = 1 
 
    } 
 
    } 
 
    console.log("most repeated is: " + integer) 
 
} 
 

 
function theirs(a) { 
 
    var count = 1, 
 
    tempCount; 
 
    var popular = a[0]; 
 
    var temp = 0; 
 
    for (var i = 0; i < (a.length - 1); i++) { 
 
    temp = a[i]; 
 
    tempCount = 0; 
 
    for (var j = 1; j < a.length; j++) { 
 
     if (temp == a[j]) 
 
     tempCount++; 
 
    } 
 
    if (tempCount > count) { 
 
     popular = temp; 
 
     count = tempCount; 
 
    } 
 
    } 
 
    console.log("most repeated is: " + popular) 
 
} 
 
console.time("mine") 
 
mine(arr) 
 
console.timeEnd("mine") 
 
console.time("theirs") 
 
theirs(arr) 
 
console.timeEnd("theirs")

這些結果如下：

most repeated is: 6 
mine: 16.929ms 
most repeated is: 6 
theirs: 0.760ms 

是什麼讓我的功能比他們慢？

Answer 1

我的測試結果

我得到下面的結果當我測試（JSFiddle），它隨機陣列50個000個元素：

mine:  28.18 ms 
theirs: 5374.69 ms 

換句話說，你的算法似乎要快很多。這是預料之中的。

爲什麼你的算法更快？

您先對數組進行排序，然後循環一次。 Firefox使用merge sort，Chrome使用quick sort的變體（根據此question）。平均需要O(n*log(n))時間。然後你循環訪問陣列，時間爲O(n)。總共得到O(n*log(n)) + O(n)，可以簡化爲O(n*log(n))。

另一方面，他們的解決方案有一個嵌套循環，外部和內部循環遍歷所有元素。這應該需要O(n^2)。換句話說，它比較慢。

爲什麼你的測試結果不同？

那麼爲什麼你的測試結果與我的不同？我看到一些可能性：

• 您使用了一個小樣本。如果你只是在你的代碼中使用了九個數字，那肯定是這種情況。當你在測試中使用短陣列時，開銷（如Gundy在評論中提到的運行console.log）主宰着它所花費的時間。這可以使結果顯示爲完全隨機的。
• neuronaut表明，它是關係到他們的代碼已經被你的代碼排序的陣列上運行的事實。雖然這是一種不好的測試方式，但我沒有看到它會如何影響結果。
• 某種瀏覽器的差異。

上的.sort的說明（）

進一步的說明：你不應該使用.sort()排序的數字，因爲它字母順序排列的東西。相反，請使用.sort(function(a, b){return a-b})。閱讀更多here。

關於進一步音符進一步指出：在這種特殊情況下，只用.sort()實際上可能是更明智的。既然你不關心排序問題，只關心分組，所以它不會對數字進行排序。它仍然會將具有相同值的元素分組在一起。如果沒有比較功能（我懷疑它是比較快），那麼它是有道理的排序沒有一個。

更快的算法

您在O(n*log(n))解決了這個問題，但你可以在短短O(n)做到這一點。算法很直觀。循環訪問數組，並記錄每個數字出現的次數。然後選擇出現次數最多的號碼。

比方說有數組中m不同的號碼。在陣列中循環需要O(n)，並找到最大需要O(m)。這就給了你O(n) + O(m)，簡化到O(n)因爲m < n。

這是代碼：

function anders(arr) { 

    //Instead of an array we use an object and properties. 
    //It works like a dictionary in other languages. 
    var counts = new Object(); 

    //Count how many of each number there is. 
    for(var i=0; i<arr.length; i++) { 
     //Make sure the property is defined. 
     if(typeof counts[arr[i]] === 'undefined') 
      counts[arr[i]] = 0; 
     //Increase the counter. 
     counts[arr[i]]++; 
    } 

    var max;    //The number with the largest count. 
    var max_count = -1; //The largest count. 

    //Iterate through all of the properties of the counts object 
    //to find the number with the largerst count. 
    for (var num in counts) { 
     if (counts.hasOwnProperty(num)) { 
      if(counts[num] > max_count) { 
       max_count = counts[num]; 
       max = num; 
      } 
     } 
    } 

    //Return the result. 
    return max; 

} 

與0和49之間50個000元件隨機陣列上運行這需要我的電腦上只是3.99毫秒。換句話說，它是最快的。背後是你需要O(m)內存來存儲每個數字出現的時間。

Answer 2

看起來這不是一個公平的測試。當你首先運行你的函數時，它會對數組進行排序。這意味着它們的功能最終會使用已排序的數據，但不會承擔執行排序的時間成本。我試着換在測試運行，並得到了幾乎相同的定時順序：

console.time("theirs") 
theirs(arr) 
console.timeEnd("theirs") 
console.time("mine") 
mine(arr) 
console.timeEnd("mine") 

most repeated is: 6 
theirs: 0.307ms 
most repeated is: 6 
mine: 0.366ms 

另外，如果您使用兩個單獨的數組，你會看到你的函數和他們運行在相同的時間內，大約。最後，請參閱Anders的答案 - 它證明了更大的數據集顯示了您的函數的O（n * log（n））+ O（n）性能與其函數的O（n^2）性能之間的關係。

Answer 3

這裏其他的答案已經做解釋了偉大的工作，爲什麼theirs更快 - 以及如何優化你的。你的大數據集（@Anders）實際上更好。我設法優化了theirs解決方案;也許這裏有一些有用的東西。

---

我可以通過採用一些基本的JS微優化來獲得一致的更快的結果。這些優化也可以應用到您的原始功能，但我將它們應用於theirs。

• Preincrementing是slightly faster比postincrementing，因爲值不需要讀入內存第一
• 反向while循環，也massively faster（我的機器上）比什麼都重要，我試過了，因爲JS是翻譯到操作碼and guaranteeing >= 0 is very fast.對於此測試，我的電腦得分爲514,271,438 ops/sec，而次最快得分198,959,074。
• 緩存length結果 - 對於更大的陣列，這將使better更加明顯快theirs

代碼：

function better(a) { 
    var top = a[0], 
     count = 0, 
     i = len = a.length - 1; 
    while (i--) { 
     var j = len, 
      temp = 0; 
     while (j--) { 
      if (a[j] == a[i]) ++temp; 
     } 
     if (temp > count) { 
      count = temp; 
      top = a[i]; 
     } 
    } 
    console.log("most repeated is " + top); 
} 

[fiddle]

這是非常相似的，如果不同樣，到theirs，但是有了上面的微優化。

下面是運行每個函數500次的結果。該陣列在任何功能運行之前進行了預先排序，並從mine()中刪除了sort。

mine: 44.076ms 
theirs: 35.473ms 
better: 32.016ms