今天在一個技術群里面，有同學提到了HyperLogLog（數據結構），排序方面技術。所以今天看一下相關的資料，算作一個總結。

HyperLogLog（數據結構）

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

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

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

理的范圍之內。

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

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

HyperLogLog 實現獨立 IP 計算功能

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

一百萬    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

結論：

使用 HyperLogLog 記錄不同數量的獨立 IP 時，需要耗費的內存數量：

可以看到，要統計相同數量的獨立 IP ，HyperLogLog 所需的內存要比集合少得多。

為 了更好地解決像獨立 IP 地址計算這種問題，Redis 在 2.8.9 版本添加了 HyperLogLog 結構。這樣，我們直接在NOSQL層面調用相應的方法傳入IP，然后就能很快的統計出一個相對的統計結果。在 Redis 里面，每個HyperLogLog 鍵只需要花費 12 KB 內存，就可以計算接近 2^64 個不同元素的基數。這和計算基數時，元素越多耗費內存就越多的集合形成鮮明對比。但是，因為 HyperLogLog 只會根據輸入元素來計算基數，而不會儲存輸入元素本身，所以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這個類，發現它的sort方法有點意思。

看得出來，JDK已經準備主推TimSort算法了。目前只是把老版的實現看懂了。

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

原理解釋：

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

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

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

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

（2）按規則合并run

TimSort ,wiki地址 

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

排序演示

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