今天在一個技術(shù)群里面，有同學(xué)提到了HyperLogLog（數(shù)據(jù)結(jié)構(gòu)），排序方面技術(shù)。所以今天看一下相關(guān)的資料，算作一個總結(jié)。

HyperLogLog（數(shù)據(jù)結(jié)構(gòu)）

HyperLogLog 可以接受多個元素作為輸入，并給出輸入元素的基數(shù)估算值：

• 基數(shù)：集合中不同元素的數(shù)量。比如 {'apple', 'banana', 'cherry', 'banana', 'apple'} 的基數(shù)就是 3 。

• 估算值：算法給出的基數(shù)并不是精確的，可能會比實際稍微多一些或者稍微少一些，但會控制在合

理的范圍之內(nèi)。

HyperLogLog 的優(yōu)點是，即使輸入元素的數(shù)量或者體積非常非常大，計算基數(shù)所需的空間總是固定的、并且是很小的。

一個特定使用場景就是統(tǒng)計某個網(wǎng)站的獨立IP訪問數(shù)量。常規(guī)基于cardinality（基數(shù)）統(tǒng)計已經(jīng)不能滿足空間的存儲要求。有人列出過一個表格，是拿HyperLogLog與常規(guī)統(tǒng)計所占用的空間對比：

HyperLogLog 實現(xiàn)獨立 IP 計算功能

獨立 IP    數(shù)量     一天         一個月        一年一年（使用集合）

一百萬    12 KB  360 KB      4.32 MB      5.4 GB

一千萬    12 KB  360 KB      4.32 MB      54 GB

一億       12 KB  360 KB       4.32 MB     540 GB

結(jié)論：

使用 HyperLogLog 記錄不同數(shù)量的獨立 IP 時，需要耗費的內(nèi)存數(shù)量：

可以看到，要統(tǒng)計相同數(shù)量的獨立 IP ，HyperLogLog 所需的內(nèi)存要比集合少得多。

為 了更好地解決像獨立 IP 地址計算這種問題，Redis 在 2.8.9 版本添加了 HyperLogLog 結(jié)構(gòu)。這樣，我們直接在NOSQL層面調(diào)用相應(yīng)的方法傳入IP，然后就能很快的統(tǒng)計出一個相對的統(tǒng)計結(jié)果。在 Redis 里面，每個HyperLogLog 鍵只需要花費 12 KB 內(nèi)存，就可以計算接近 2^64 個不同元素的基數(shù)。這和計算基數(shù)時，元素越多耗費內(nèi)存就越多的集合形成鮮明對比。但是，因為 HyperLogLog 只會根據(jù)輸入元素來計算基數(shù)，而不會儲存輸入元素本身，所以HyperLogLog 不能像集合那樣，返回輸入的各個元素。redis的PFADD 和 PFCOUNT 的使用示例

redis> PFADD unique::ip::counter '192.168.0.166'

(integer) 1

redis> PFADD unique::ip::counter '127.0.0.1'

(integer) 1

redis> PFADD unique::ip::counter '255.255.255.255'

(integer) 1

redis> PFCOUNT unique::ip::counter

(integer) 3

排序

無意間查看Arrays這個類，發(fā)現(xiàn)它的sort方法有點意思。

看得出來，JDK已經(jīng)準(zhǔn)備主推TimSort算法了。目前只是把老版的實現(xiàn)看懂了。

Timsort 是結(jié)合了合并排序（merge sort）和插入排序（insertion sort）而得出的排序算法，它在現(xiàn)實中有很好的效率。Tim Peters在2002年設(shè)計了該算法并在Python中使用（TimSort 是 Python 中 list.sort 的默認(rèn)實現(xiàn)）。該算法找到數(shù)據(jù)中已經(jīng)排好序的塊-分區(qū)，每一個分區(qū)叫一個run，然后按規(guī)則合并這些run。Pyhton自從2.3版以來一直采用 Timsort算法排序，現(xiàn)在Java SE7和Android也采用Timsort算法對數(shù)組排序。

原理解釋：

       TimSort 算法為了減少對升序部分的回溯和對降序部分的性能倒退，將輸入按其升序和降序特點進(jìn)行了分區(qū)。排序的輸入的單位不是一個個單獨的數(shù)字，而是一個個的塊-分 區(qū)。其中每一個分區(qū)叫一個run。針對這些 run 序列，每次拿一個 run 出來按規(guī)則進(jìn)行合并。每次合并會將兩個 run合并成一個 run。合并的結(jié)果保存到棧中。合并直到消耗掉所有的 run，這時將棧上剩余的 run合并到只剩一個 run 為止。這時這個僅剩的 run 便是排好序的結(jié)果。

綜上述過程，Timsort算法的過程包括

（0）如何數(shù)組長度小于某個值，直接用二分插入排序算法

（1）找到各個run，并入棧

（2）按規(guī)則合并run

TimSort ,wiki地址 

大概意思，就是對任意一段串進(jìn)行拆分，每一個串一定是經(jīng)過排好序的小集合。然后再拿出一個小集合與另外一個集合進(jìn)行比較，組成一個更大的有序集合，直到最后所有的小集合變成一個集合為止。簡要如圖：

排序演示

原理基本就是這樣，再慢慢消化一下，看看源碼。