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

三種方法：

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

方法概要

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

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

• 分治法（常見思路）

  操作：操作與歸并排序的思想類似，都是分治。

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

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

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

  特點：

• 位圖法（Bitmap）

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

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

  特點：

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

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

  • 對于有符號類型的數(shù)據(jù)，需要用 2 位來表示，比如 第 0 位和第 1 位表示 0 這個數(shù)據(jù)，第 2 位和第 3 位表示 1 這個數(shù)據(jù)......，這會讓位圖能存儲的元素個數(shù)，元素值大小上限減半

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

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

最新評論