題目描述

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

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

解題思路

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

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

1
7 3 1 5 6 4

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

bit[3]=1

bit[1]=1

bit[5]=1

……

bit[4]=1

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

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

實(shí)現(xiàn)細(xì)節(jié)

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

然后我們插入一個(gè)整數(shù)val，要先計(jì)算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

然后在計(jì)算在這個(gè)index中的位置，因?yàn)閿?shù)組中的每個(gè)元素有32位

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

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

然后就是標(biāo)識(shí)這個(gè)位置為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);//這個(gè)更快？
}　

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

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

33: index = 1, 在bmap[1]中的位置為 1，只需要檢測(cè)這個(gè)位置是否為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);
}　

下面是完整測(cè)試代碼：

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呢？

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

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

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

代碼如下（一個(gè)測(cè)試的代碼）：

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()
{
  //生成測(cè)試數(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);
 
  //讀入測(cè)試數(shù)據(jù)
  freopen("test.txt", "r", stdin);
  int Value;
  while (scanf("%d", & Value) != EOF) {
    ++Bucket[Value / BLOCK_SIZE]; //測(cè)試數(shù)據(jù)分段累計(jì)
  }
  fclose(stdin);
 
  //找出累計(jì)計(jì)數(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來檢測(cè)
  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)容，希望對(duì)大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。

最新評(píng)論