題目描述

給你一個文件，里面包含40億個整數(shù)，寫一個算法找出該文件中不包含的一個整數(shù)， 假設(shè)你有1GB內(nèi)存可用。

如果你只有10MB的內(nèi)存呢？

解題思路

對于40億個整數(shù)，如果直接用int數(shù)組來表示的大約要用4010^84B=16GB,超出了內(nèi)存要求，這里

我們可以用bitmap來解決，bitmap基本思想是一位表示一個整數(shù)，比如我們有6個數(shù)據(jù)：

1
7 3 1 5 6 4

假設(shè)bitmap容量為8，當插入7時 bit[7]=1，以此類推

bit[3]=1

bit[1]=1

bit[5]=1

……

bit[4]=1

這樣我們查詢5，只需要查看bit[5]==1側(cè)存在，否則不存在。

這樣一個位代表一個數(shù)據(jù)，那40一個數(shù)據(jù)大概要4010^8bit = 0.5GB,滿足內(nèi)存要求。

實現(xiàn)細節(jié)

首先我們用int來表示：int bmap[1+N/32]; //N是總數(shù)，N=40億，一個int32bit

然后我們插入一個整數(shù)val，要先計算val位于數(shù)組bmap中的索引:index = val/32;

比如整數(shù)33，index=33/32=1,第33位于數(shù)組中的index=1

比如整數(shù)67，index=67/32=2,位于數(shù)組中index=2

然后在計算在這個index中的位置，因為數(shù)組中的每個元素有32位

33，index=1，在1中的位置為33%32=1

67，index=2，在2中的位置為67%32=3

然后就是標識這個位置為1：

bmap[val/32] |= (1<<(val%32));

33: bmap[1] != (1<<1);//xxxxxx 1 x,紅絲位置被置為1

67: bmap[2] != (1<<3);//xxxx 1 xxx

代碼

void setVal(int val)
{
bmap[val / 32] |= (1 << (val % 32));
//bmap[val>>5] != (val&0x1F);//這個更快？
}　

怎樣檢測整數(shù)是否存在？

比如我們檢測33，同樣我們需要計算index，以及在index元素中的位置

33: index = 1, 在bmap[1]中的位置為 1，只需要檢測這個位置是否為1

bmp[1] &(1<<1),這樣是1返回true，否側(cè)返回false

67:bmp[2]&(1<<3)

127:bmp[3]&(1<<31)

代碼：

bool testVal(int val)
{
return bmap[val / 32] & (1 << (val % 32));
//return bmap[val>>5] & (val&0x1F);
}　

下面是完整測試代碼：

const int N = MaxN;
const int BitLen = 32;
int bmap[1 + N / BitLen];
 
void setVal(int val)
{
  bmap[val / BitLen] |= (1 << (val % BitLen));
}
 
bool testVal(int val)
{
  return bmap[val / BitLen] & (1 << (val % BitLen));
}
 
void funTest()
{
  int a[] = { 1, 2, 3, 4, 6, 7};
 
  for (int i = 0; i < 6; ++i)
  {
    setVal(a[i]);
  }
 
  std:: cout << testVal(5) << std:: endl;
  return 0;
}

現(xiàn)在我們來看如果內(nèi)存要求是10MB呢？

這當然不能用bitmap來直接計算。因為從40億數(shù)據(jù)找出一個不存在的數(shù)據(jù)，我們可以將這么多的數(shù)據(jù)分成許多塊， 比如每一個塊的大小是1000，那么第一塊保存的就是0到999的數(shù)，第2塊保存的就是1000 到1999的數(shù)……

實際上我們并不保存這些數(shù)，而是給每一個塊設(shè)置一個計數(shù)器。 這樣每讀入一個數(shù)，我們就在它所在的塊對應(yīng)的計數(shù)器加1。

處理結(jié)束之后， 我們找到一個塊，它的計數(shù)器值小于塊大小(1000)， 說明了這一段里面一定有數(shù)字是文件中所不包含的。然后我們單獨處理這個塊即可。接下來我們就可以用Bit Map算法了。我們再遍歷一遍數(shù)據(jù)， 把落在這個塊的數(shù)對應(yīng)的位置1(我們要先把這個數(shù)歸約到0到blocksize之間)。 最后我們找到這個塊中第一個為0的位，其對應(yīng)的數(shù)就是一個沒有出現(xiàn)在該文件中的數(shù)。)

代碼如下（一個測試的代碼）：

const int N = 1000;
const int BITLEN = 32;
const int BLOCK_SIZE = 100;
 
int Bucket[1 + N / BLOCK_SIZE] = { 0};
int BitMap[1 + BLOCK_SIZE / BITLEN] = { 0};
 
void test()
{
  //生成測試數(shù)據(jù)
  freopen("test.txt", "w", stdout);
  for (int i = 0; i < 1000; ++i)
  {
    if (i == 127) {
      printf("0\n");
      continue;
    }
    printf("%d\n", i);
  }
  fclose(stdout);
 
  //讀入測試數(shù)據(jù)
  freopen("test.txt", "r", stdin);
  int Value;
  while (scanf("%d", & Value) != EOF) {
    ++Bucket[Value / BLOCK_SIZE]; //測試數(shù)據(jù)分段累計
  }
  fclose(stdin);
 
  //找出累計計數(shù)小于BLOCK_SIZE的
  int Start = -1, i;
  for (i = 0; i < 1 + N / BLOCK_SIZE; ++i) {
    if (Bucket[i] < BLOCK_SIZE) {
      Start = i * BLOCK_SIZE;
      break;
    }
  }
  if (i == 1 + N / BLOCK_SIZE || Bucket[N / BLOCK_SIZE] == 0 && i == N / BLOCK_SIZE) return;
  int End = Start + BLOCK_SIZE - 1;
 
  //在不滿足的那段用bitmap來檢測
  freopen("test.txt", "r", stdin);
  while (scanf("%d", & Value) != EOF) {
    if (Value >= Start && Value <= End)//Value必須滿足在那段
    {
      int Temp = Value - Start;
      BitMap[Temp / BITLEN] |= (1 << (Temp % BITLEN));
    }
  }
  fclose(stdin);
 
  //找出不存在的數(shù)
  freopen("re.txt", "w", stdout);
  bool Found = false;
  for (int i = 0; i < 1 + BLOCK_SIZE / BITLEN; ++i)
  {
    for (int k = 0; k < BITLEN; ++k)
    {
      if ((BitMap[i] & (1 << k)) == 0) {
        printf("%d ", i * BITLEN + k + Start);
        Found = true;
        break;
      }
    }
    if (Found) break;
  }
  fclose(stdout);
}

以上就是本文的全部內(nèi)容，希望對大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。

最新評論