學會了BitMap的原理，所以我們一定要來好好折騰一下自己，沒有環(huán)境也要創(chuàng)造環(huán)境搞事情

image.png

一、準備數(shù)據(jù)

首先，用世界上最*的語言創(chuàng)建一個大文件

<?php

    set_time_limit(0);
    $max = pow(2, 32) - 1;
    $count = 你喜歡多少就多少;
    while ($count > 0) {
        $arr = array();
        for ($i = 0; $i < 10000; ++$i) {
            $arr[] = mt_rand(0, $max);
        }
        $content = $count > 10000 ? implode(PHP_EOL, $arr) . PHP_EOL : implode(PHP_EOL, $arr);
        file_put_contents('./smalldata.txt', $content, FILE_APPEND);
        $count -= 10000;
        unset($arr);
    }

// 別人高大上的大數(shù)據(jù)，我們這種民間作坊就叫小數(shù)據(jù)

image.png

生成了一個5g多的文件，我忘了當時寫了多少個數(shù)據(jù)，大概5E左右個自然數(shù)吧。

image.png

二、思路以及方案

A、

既然是一行一個數(shù)字，那就要一行一行的讀取文件（應(yīng)該有一次讀取多行的方法，不過我暫時沒找到），然后set bit。空間確定限制在512MB+了，時間復雜度也是O(n)沒跑了，但是一行一行的讀取也確實比較慢，那么就用多線程減少一下時間好了。（實現(xiàn)多線程有幾個方法，我這里用到了實現(xiàn)runnable接口這一種）

B、

首先給多個線程劃分好讀取文件的區(qū)域，第n行 ~ 第n + m行，這樣就需要可以任意讀取文件某一個位置的工具，這里用到了RandomAccessFile，先把文件大小除以線程個數(shù)確定大概范圍，然后遞歸一個一個byte的地讀，遞歸出口是讀取到換行符或者到文件結(jié)尾。

思路和方案大概就是這樣，代碼在我的gayhub上面，拉到最下面就是地址。

C、

其實靠上面兩條就可以做出來了，不過這的要這樣子做的話，效率會非常低，因為性能瓶頸都在IO流上，查了網(wǎng)上優(yōu)化文件讀取的方式，是用MappedByteBuffer。（我開始用了RandomAccessFile，后面查了發(fā)現(xiàn)它是一個一個byte的讀，慢到爆炸）

D、

最后我開了4個線程去排序，花了差不多700s的時間

image.png

這是我用了差不多兩個月的空余時間才做出來的，性能上一定還有很多優(yōu)化的空間的，應(yīng)該主要還是在IO流這塊，不過我所以暫時不去優(yōu)化它了，

代碼的gayhub地址：https://github.com/PHPerKael/BitMap/

看完我的小數(shù)據(jù)，再看看別人家真正的大數(shù)據(jù)處理：

2016年11月10日，具有計算奧運會之稱的Sort Benchmark全球排序競賽公布2016年最終成績，騰訊云大數(shù)據(jù)聯(lián)合團隊用時不到99秒（98.8秒）就完成100TB的數(shù)據(jù)排序，打破了去年329秒的紀錄。在更早前，百度創(chuàng)造的紀錄是716秒，Hadoop的紀錄是4222秒。

image.png