IT工程師數位筆記本

topN 算法 以及 逆算法（隨筆）

注解：所謂的 topN 算法指的是 在 海量的數據中進行排序從而活動 前 N 的數據。 這就是所謂的 topN 算法。當然你可以說我就 sort 一下 排序完了直接取 slice(0, n) 不就好咯。 但是這的性能會很差~ 那到底能有多差，這篇文章會給大家一個 直觀的感受。

第一步、造數據

有排序，那么必須先得有數據 才能在這基礎上進行下一步的操作。

    let arr = []
    for (let i = 0; i < 2000; i++) {
        arr.push(i)
    }
    console.log(arr)    // [0, 1, 2, ..., 10000]

第二步、 打亂數據

ok, 現在 數據原料有了，但是呢，現在這個的排序是正常的。我們現在要做的就是打亂這 10000 個數字的順序。 thinking ， emmmmmm。 好像沒什么好的辦法。 思路： 既然是要隨機亂排列。那么隨機數 Math.random() 可以獲取一個 隨機數 通過這個隨機數，我們可以有什么作為呢？

 這個時候，我們想到了 一個 最low 的辦法， sort 排序。 然后再利用 random 隨機數。 好了，我們試一試

    for (var m = 0; m < arr.length; m++) {
        arr.sort( function() {
            return 0.5 - Math.random()
        })
    }
    console.log(arr)

沒錯就是這樣，數據就被隨機打亂了~~~ 但是性能如何呢？
我們專門來測試了一番。

第三步、 打亂數據 性能測試。

我們先從 循環 1000 來逐步加大運算量，看看我們的瀏覽器到哪一步會掛 =。=   --- 代碼如下：

    let arr = []
    let sTime = new Date().getTime()
    console.log('第一步' + sTime)
    for (let i = 0; i < 1000; i++) {
        arr.push(i)
    }
    console.log('第二步' + arr)
    console.log(new Date().getTime() - sTime)
    for (var m = 0; m < arr.length; m++) {
        arr.sort( function() {
            return 0.5 - Math.random()
        })
    }
    console.log('第三步' + arr)
    console.log(new Date().getTime() - sTime)

（1） 1000 循環的結果：

造數據：   4 ms
打亂數據： 600 ms （多次平均值）

（2） 2000 循環的結果：

造數據：   8 ms
打亂數據： 2500 ms （多次平均值）

（3） 5000 循環的結果：

造數據：   8 ms
打亂數據： 18000 ms （多次平均值）

實在是 不想測試 10000 次 數據通過 sort 打亂的過程。 時間 tooooooo loooooooong...

第四步、 再獲得 topN 個數字

我們通過 可以想到的所有方法 對上面的 2000 次計算的數據進行有效的排序。
sort()？
二叉樹？
使用最大堆排序，然后取出前N名？
分成 N * 10 個數組，獲取其中的最大值，再排序 ？

（1） sort() 排序法

代碼如下：

    arr.sort(function(a, b) {
        return a - b
    })
    console.log('第四步' + arr)

結果：

很神奇，在僅僅只有 5000 的數據量的時候 sort 排序 速度居然也還是很快。 平均值在  6ms 左右。

（2） sort() 分成 N * 10 個數組，獲取其中的最大值，再排序

晚上回家繼續寫~~~ 敬請期待