本書(shū)第一章提出了一個(gè)看似簡(jiǎn)單的問(wèn)題，有最多1000萬(wàn)條不同的整型數(shù)據(jù)存在于硬盤(pán)的文件中，如何在1M內(nèi)存的情況下對(duì)其進(jìn)行盡可能快的排序。

每個(gè)數(shù)字用4byte，1M即可存儲(chǔ)250 000個(gè)數(shù)據(jù)，顯然，只要每次對(duì)250 000個(gè)數(shù)據(jù)排序，寫(xiě)入到文件中即可，重復(fù)40次。

那么如何選出每次遍歷的二十五萬(wàn)條數(shù)據(jù)呢？有如下兩個(gè)策略：

1、對(duì)一千萬(wàn)條數(shù)據(jù)遍歷40次，第i次遍歷時(shí)，判斷數(shù)是否屬于[i*250000,i*250000+249999），如果是，則讀入內(nèi)存，當(dāng)?shù)趇次遍歷完成時(shí)，內(nèi)

存中有了二十五萬(wàn)條數(shù)據(jù)，這些數(shù)據(jù)比前i-1次遍歷篩選出來(lái)的大，但是比后40-i次遍歷的小。故，將第i次遍歷選入內(nèi)存中的數(shù)排序，輸出到硬盤(pán)文件，

追加到i-1次輸出到那個(gè)文件即可。

特點(diǎn)：簡(jiǎn)單，粗暴，但是遍歷次數(shù)極多，只能串行，對(duì)文件進(jìn)行了40次讀取，本機(jī)運(yùn)行耗時(shí) 2分17秒214毫秒。

2、對(duì)一千萬(wàn)條數(shù)據(jù)遍歷1次，第i組 二十五萬(wàn)條數(shù)據(jù)存入內(nèi)存，排序，輸出到文件i，對(duì)一千萬(wàn)條數(shù)據(jù)完成一次遍歷后，生成40個(gè)內(nèi)容有序的臨時(shí)文件，

在對(duì)這些文件歸并，即可。

特點(diǎn)：對(duì)源文件只需要一次讀入，排序可以采用多線程，IO次數(shù)仍然較高。串行情況下，本機(jī)運(yùn)行耗時(shí)21秒221毫秒

那么如何能達(dá)到10秒以?xún)?nèi)呢？

那么分析一下這個(gè)問(wèn)題的特點(diǎn)：

a、數(shù)據(jù)不超過(guò)最大值

b、所有數(shù)據(jù)不重復(fù)

c、每條數(shù)據(jù)僅是一個(gè)數(shù)

那么可以申請(qǐng)一個(gè)一千萬(wàn)位長(zhǎng)的位向量，下標(biāo)為i的位是1，則代表存在一個(gè)數(shù)i。

3、由此得到了一種針對(duì)此問(wèn)題的位圖排序方法。

申請(qǐng)長(zhǎng)度為一千萬(wàn)位的位向量bit[10000000]，所有位設(shè)置為0，順序讀取待排序文件，每讀入一個(gè)數(shù)i，便將bit[i]置為1。當(dāng)所有數(shù)據(jù)讀入完成，便對(duì)

bit做從頭到尾的遍歷，如果bit[i]=1，則輸出i到文件，當(dāng)遍歷完成，文件則已排好序。本機(jī)運(yùn)行耗時(shí)9秒49毫秒。

?

備注： 無(wú)bit類(lèi)型的編程語(yǔ)言如何實(shí)現(xiàn)位操作

以32位操作系統(tǒng)下的int類(lèi)型為例。設(shè)需要申請(qǐng)N個(gè)位，則需要有a[N/32+1]個(gè)int類(lèi)型方可容得下N位（當(dāng)然，最后一個(gè)int中有些位被浪費(fèi)了）

將第i位置為1的時(shí)候可以用如下操作：

第i位必然在 int型數(shù)組a的第 (i/32)個(gè)數(shù)中，偏移量是 (i%32)，將i位置為1，需要第(i/32)的數(shù)與一個(gè)數(shù)b相 或 即可，b要求是 (i%32)位為1，其他位均

為0，故有如下語(yǔ)句：

a[i/32] | (1 << (i%32));

?

為了保證達(dá)到最快的運(yùn)算速度，上式改寫(xiě)為如下：

a[i >>5] |= (1 << (i & 31));

來(lái)源:http://www.cnblogs.com/tntboom/p/4109458.html

與50位技術(shù)專(zhuān)家面對(duì)面20年技術(shù)見(jiàn)證，附贈(zèng)技術(shù)全景圖

總結(jié)

以上是生活随笔為你收集整理的对一千万条数据进行排序---编程珠玑第二版 第一章的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。