大數(shù)據(jù)小內(nèi)存排序問(wèn)題，很經(jīng)典，很常見(jiàn)，類(lèi)似的還有比如 “如何對(duì)上百萬(wàn)考試的成績(jī)進(jìn)行排序” 等等。

三種方法：

• 數(shù)據(jù)庫(kù)排序（對(duì)數(shù)據(jù)庫(kù)設(shè)備要求較高）
• 分治法（常見(jiàn)思路）
• 位圖法（Bitmap）

方法概要

• 數(shù)據(jù)庫(kù)排序（對(duì)數(shù)據(jù)庫(kù)設(shè)備要求較高）

  操作：將數(shù)據(jù)全部導(dǎo)入數(shù)據(jù)庫(kù)，建立索引，數(shù)據(jù)庫(kù)對(duì)數(shù)據(jù)進(jìn)行排序，提取出數(shù)據(jù)。
  特點(diǎn)：操作簡(jiǎn)單， 運(yùn)算速度較慢，對(duì)數(shù)據(jù)庫(kù)設(shè)備要求較高。

• 分治法（常見(jiàn)思路）

  操作：操作與歸并排序的思想類(lèi)似，都是分治。

  將數(shù)據(jù)進(jìn)行分塊，然后對(duì)每個(gè)數(shù)據(jù)塊進(jìn)行內(nèi)部的排序（假如是對(duì)int形數(shù)據(jù)升序）。

  和歸并排序類(lèi)似，每個(gè)數(shù)據(jù)塊取第一個(gè)數(shù)據(jù)（當(dāng)前塊的最小數(shù)據(jù)），然后比較取出的數(shù)據(jù)，取其最小加入結(jié)果集。

  重復(fù)2操作，直到取完所有數(shù)據(jù)，此時(shí)排序完畢。

  特點(diǎn)：

• 位圖法（Bitmap）

  操作：基本思想就是利用一位（bit）代表一個(gè)數(shù)字，例如第 3 位上為 1，則說(shuō)明 3 這個(gè)數(shù)字出現(xiàn)過(guò)，若為0，則說(shuō)明 3 這個(gè)數(shù)字沒(méi)有出現(xiàn)過(guò)。很簡(jiǎn)單~

  ? java.util 封裝了 BitSet 這樣一個(gè)類(lèi)，是位圖法的典型實(shí)現(xiàn)。

  特點(diǎn)：

  • 可讀性差（不是一般的差 ??）

  • 位圖存儲(chǔ)的元素個(gè)數(shù)雖然比一般做法多，但是存儲(chǔ)的元素大小受限于存儲(chǔ)空間的大小。要想定義存儲(chǔ)空間大小就需要實(shí)現(xiàn)知道存儲(chǔ)的元素到底有多少

  • 對(duì)于有符號(hào)類(lèi)型的數(shù)據(jù)，需要用 2 位來(lái)表示，比如 第 0 位和第 1 位表示 0 這個(gè)數(shù)據(jù)，第 2 位和第 3 位表示 1 這個(gè)數(shù)據(jù)......，這會(huì)讓位圖能存儲(chǔ)的元素個(gè)數(shù)，元素值大小上限減半

  • 只知道元素是否出現(xiàn)，無(wú)法知道出現(xiàn)的具體次數(shù)

到此這篇關(guān)于大數(shù)據(jù)小內(nèi)存排序問(wèn)題如何巧妙解決的文章就介紹到這了,更多相關(guān)大數(shù)據(jù)小內(nèi)存排序問(wèn)題內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論