99热在线精品一区二区三区_国产伦精品一区二区三区女破破_亚洲一区二区三区无码_精品国产欧美日韩另类一区

今天就跟大家聊聊有關(guān)使用BitMap怎么實(shí)現(xiàn)大數(shù)據(jù)排序去重，可能很多人都不太了解，為了讓大家更加了解，小編給大家總結(jié)了以下內(nèi)容，希望大家根據(jù)這篇文章可以有所收獲。

武定網(wǎng)站制作公司哪家好，找成都創(chuàng)新互聯(lián)公司！從網(wǎng)頁(yè)設(shè)計(jì)、網(wǎng)站建設(shè)、微信開(kāi)發(fā)、APP開(kāi)發(fā)、響應(yīng)式網(wǎng)站設(shè)計(jì)等網(wǎng)站項(xiàng)目制作，到程序開(kāi)發(fā)，運(yùn)營(yíng)維護(hù)。成都創(chuàng)新互聯(lián)公司于2013年開(kāi)始到現(xiàn)在10年的時(shí)間，我們擁有了豐富的建站經(jīng)驗(yàn)和運(yùn)維經(jīng)驗(yàn)，來(lái)保證我們的工作的順利進(jìn)行。專注于網(wǎng)站建設(shè)就選成都創(chuàng)新互聯(lián)公司。

1、問(wèn)題 問(wèn)題提出：

M（如10億）個(gè)int整數(shù)，只有其中N個(gè)數(shù)重復(fù)出現(xiàn)過(guò)，讀取到內(nèi)存中并將重復(fù)的整數(shù)刪除。

2、解決方案 問(wèn)題分析：

我們肯定會(huì)先想到在計(jì)算機(jī)內(nèi)存中開(kāi)辟M(fèi)個(gè)int整型數(shù)據(jù)數(shù)組，來(lái)one bye one讀取M個(gè)int類型數(shù)組， 然后在一一比對(duì)數(shù)值，最后將重復(fù)數(shù)據(jù)的去掉。當(dāng)然這在處理小規(guī)模數(shù)據(jù)是可行的。

我們考慮大數(shù)據(jù)的情況：例如在java語(yǔ)言下，對(duì)10億個(gè)int類型數(shù)據(jù)排重。

java中一個(gè)int類型在內(nèi)存中占4byte。那么10億個(gè)int類型數(shù)據(jù)共需要開(kāi)辟10^9次方*4byte≈4GB的連續(xù)內(nèi)存空間。以32位操作系統(tǒng)電腦為例，最大支持內(nèi)存為4G，可用內(nèi)存更是小于4G。所以上述方法在處理大數(shù)據(jù)時(shí)根本行不通。

思維轉(zhuǎn)化：

既然我們不能為所有 int 類型的數(shù)據(jù)開(kāi)辟 int 類型數(shù)組，那么可以采取更小的數(shù)據(jù)類型來(lái)讀取緩存 int 類型數(shù)據(jù)。考慮到計(jì)算機(jī)內(nèi)部處理的數(shù)據(jù)都是 01 序列的bit，那么我們是否可以用 1bit 來(lái)表示一個(gè) int 類型數(shù)據(jù)。

位映射的引出：

使用較小的數(shù)據(jù)類型指代較大的數(shù)據(jù)類型。如上所說(shuō)的問(wèn)題，我們可以用1個(gè) bit 來(lái)對(duì)應(yīng)一個(gè)int 整數(shù)。假如對(duì)應(yīng)的 int 類型的數(shù)據(jù)存在，就將其對(duì)應(yīng)的 bit 賦值為1，否則，賦值為0（boolean類型）。java中 int 范圍為 -2^31 到 2^31-1. 那么所有可能的數(shù)值組成的長(zhǎng)度為2^32. 對(duì)應(yīng)的 bit 長(zhǎng)度也為 2^32. 那么可以用這樣處理之后只需要開(kāi)辟2^32 bit = 2^29 byte = 512M 大小的 內(nèi)存空間 。顯然，這樣處理就能滿足要求了，雖然對(duì)內(nèi)存的消耗也不太小。

問(wèn)題解決方案：

首先定義如下圖的int - byte 映射關(guān)系，當(dāng)然，映射關(guān)系可以自定義。但前提要保證你的數(shù)組上下標(biāo)不能越界。

但如上定義的bit[]數(shù)組顯然在計(jì)算機(jī)中是不存在的，所我們需要將其轉(zhuǎn)化為 java 中的一個(gè)基本數(shù)據(jù)類型存儲(chǔ)。顯然，byte[] 是最好的選擇。

將其轉(zhuǎn)化為byte[] 數(shù)組方案：

自定義的映射關(guān)系表，每個(gè)bit對(duì)應(yīng)一個(gè) int 數(shù)值，將 int 的最大值，最小值與數(shù)組的最大最小索引相對(duì)應(yīng)。從上圖可以看出來(lái) int 數(shù)值與bit索引相差 2^31次方。當(dāng)然，你也可以定義其他的映射關(guān)系，只是注意不要發(fā)生數(shù)組越界的情況。

bit[]索引：由于最大值可能是2^32,故用long接收: long bitIndex = num + (1l << 31);

byte[]索引: int index = (int) (bitIndex / 8); ，在字節(jié)byte[index]中的具體位置： int innerIndex = (int) (bitIndex % 8);

更新值： dataBytes[index] = (byte) (dataBytes[index] | (1 << innerIndex));

` import java.util.Random;

/**

• 問(wèn)題：M（如10億）個(gè)int整數(shù)，只有其中N個(gè)數(shù)重復(fù)出現(xiàn)過(guò)，讀取到內(nèi)存中并將重復(fù)的整數(shù)刪除。
  

• 使用位映射來(lái)進(jìn)行海量數(shù)據(jù)的去重排序，原先一個(gè)元素用一個(gè)int現(xiàn)在只用一個(gè)bit， 內(nèi)存占比4*8bit:1bit=32:1
  

• 亦可用java語(yǔ)言提供的BitSet，不過(guò)其指定bit index的參數(shù)為int類型，因此在此例中將輸入數(shù)轉(zhuǎn)為bit index時(shí)對(duì)于較大的數(shù)會(huì)越界
  
  */ public class BigDataSort {

  private static final int CAPACITY = 1_000_000;// 數(shù)據(jù)容量

  public static void main(String[] args) {

   testMyFullBitMap();

  }

  public static void testMyFullBitMap() { MyFullBitMap ms = new MyFullBitMap();

   byte[] bytes = null;
  
   Random random = new Random();
   long startTime = System.currentTimeMillis();
   for (int i = 0; i < CAPACITY; i++) {
       int num = random.nextInt();
       // System.out.println("讀取了第 " + (i + 1) + "\t個(gè)數(shù): " + num);
       bytes = ms.setBit(num);
   }
   long endTime = System.currentTimeMillis();
   System.out.printf("存入%d個(gè)數(shù)，用時(shí)%dms\n", CAPACITY, endTime - startTime);
  
   startTime = System.currentTimeMillis();
   ms.output(bytes);
   endTime = System.currentTimeMillis();
   System.out.printf("取出%d個(gè)數(shù)，用時(shí)%dms\n", CAPACITY, endTime - startTime);

  } }

class MyFullBitMap { // 定義一個(gè)byte數(shù)組表示所有的int數(shù)據(jù)，一bit對(duì)應(yīng)一個(gè)，共2^32b=2^29B=512MB private byte[] dataBytes = new byte[1 << 29];

/**
 * 讀取數(shù)據(jù)，并將對(duì)應(yīng)數(shù)數(shù)據(jù)的 到對(duì)應(yīng)的bit中，并返回byte數(shù)組
 * 
 * [@param](https://my.oschina.net/u/2303379) num
 *            讀取的數(shù)據(jù)
 * [@return](https://my.oschina.net/u/556800) byte數(shù)組 dataBytes
 */
public byte[] setBit(int num) {

    long bitIndex = num + (1l << 31); // 獲取num數(shù)據(jù)對(duì)應(yīng)bit數(shù)組（虛擬）的索引
    int index = (int) (bitIndex / 8); // bit數(shù)組（虛擬）在byte數(shù)組中的索引
    int innerIndex = (int) (bitIndex % 8); // bitIndex 在byte[]數(shù)組索引index 中的具體位置

    // System.out.println("byte[" + index + "] 中的索引：" + innerIndex);

    dataBytes[index] = (byte) (dataBytes[index] | (1 << innerIndex));
    return dataBytes;
}

/**
 * 輸出數(shù)組中的數(shù)據(jù)
 * 
 * [@param](https://my.oschina.net/u/2303379) bytes
 *            byte數(shù)組
 */
public void output(byte[] bytes) {
    int count = 0;
    for (int i = 0; i < bytes.length; i++) {
        for (int j = 0; j < 8; j++) {
            if (((bytes[i]) & (1 << j)) != 0) {
                count++;
                int number = (int) ((((long) i * 8 + j) - (1l << 31)));
                // System.out.println("取出的第 " + count + "\t個(gè)數(shù): " + number);
            }
        }
    }
}

}`

3. Bit-map應(yīng)用之快速去重 　　2.5億個(gè)整數(shù)中找出不重復(fù)的整數(shù)的個(gè)數(shù)，內(nèi)存空間不足以容納這2.5億個(gè)整數(shù)。 　　首先，根據(jù)“內(nèi)存空間不足以容納這2.5億個(gè)整數(shù)”我們可以快速的聯(lián)想到Bit-map。下邊關(guān)鍵的問(wèn)題就是怎么設(shè)計(jì)我們的Bit-map來(lái)表示這2.5億個(gè)數(shù)字的狀態(tài)了。其實(shí)這個(gè)問(wèn)題很簡(jiǎn)單，一個(gè)數(shù)字的狀態(tài)只有三種，分別為不存在，只有一個(gè)，有重復(fù)。因此，我們只需要2bits就可以對(duì)一個(gè)數(shù)字的狀態(tài)進(jìn)行存儲(chǔ)了，假設(shè)我們?cè)O(shè)定一個(gè)數(shù)字不存在為00，存在一次01，存在兩次及其以上為11。那我們大概需要存儲(chǔ)空間幾十兆左右。 　　接下來(lái)的任務(wù)就是遍歷一次這2.5億個(gè)數(shù)字，如果對(duì)應(yīng)的狀態(tài)位為00，則將其變?yōu)?1；如果對(duì)應(yīng)的狀態(tài)位為01，則將其變?yōu)?1；如果為11，,對(duì)應(yīng)的轉(zhuǎn)態(tài)位保持不變。 　　最后，我們將狀態(tài)位為01的進(jìn)行統(tǒng)計(jì)，就得到了不重復(fù)的數(shù)字個(gè)數(shù)，時(shí)間復(fù)雜度為O(n)。 轉(zhuǎn)自：https://www.cnblogs.com/yale/p/9307363.html

看完上述內(nèi)容，你們對(duì)使用BitMap怎么實(shí)現(xiàn)大數(shù)據(jù)排序去重有進(jìn)一步的了解嗎？如果還想了解更多知識(shí)或者相關(guān)內(nèi)容，請(qǐng)關(guān)注創(chuàng)新互聯(lián)行業(yè)資訊頻道，感謝大家的支持。

分享文章：使用BitMap怎么實(shí)現(xiàn)大數(shù)據(jù)排序去重
轉(zhuǎn)載來(lái)于：http://www.ef60e0e.cn/article/gshepo.html