Bitmap 대량의 데 이 터 를 빠르게 찾 아 재 코드 예제

제목 설명
40 억 개의 정 수 를 포함 하 는 파일 을 드 리 겠 습 니 다.알고리즘 을 써 서 이 파일 에 포함 되 지 않 은 정 수 를 찾 아 보 세 요.1GB 메모리 가 있다 고 가정 하 세 요.
만약 당신 이 10MB 의 메모리 만 있다 면?
문제 풀이 의 사고 방향.
40 억 개의 정수 에 대해 int 배열 로 직접 표시 하려 면 4010^84B=16GB 로 메모리 요 구 를 초과 해 야 합 니 다.
우 리 는 bitmap 로 해결 할 수 있 습 니 다.bitmap 의 기본 사상 은 한 사람 이 정 수 를 표시 하 는 것 입 니 다.예 를 들 어 우 리 는 6 개의 데 이 터 를 가지 고 있 습 니 다.
1
7 3 1 5 6 4
bitmap 용량 이 8 이 라 고 가정 하고 7 을 삽입 할 때 bit[7]=1 로 유추 합 니 다.
bit[3]=1
bit[1]=1
bit[5]=1
……
bit[4]=1
이렇게 해서 우 리 는 5 를 조회 하려 면 bit[5]==1 측 이 존재 하 는 지 확인 해 야 합 니 다.그렇지 않 으 면 존재 하지 않 습 니 다.
이 한 자 리 는 하나의 데 이 터 를 대표 합 니 다.그 40 개의 데 이 터 는 대략 4010^8bit=0.5GB 로 메모리 요 구 를 만족 시 킵 니 다.
디 테 일 구현
우선 int 로 표시 합 니 다.int bmap[1+N/32];/N 은 총수,N=40 억,하나의 int 32bit
그 다음 에 우 리 는 정수 val 을 삽입 합 니 다.먼저 val 이 배열 bmap 에 있 는 색인 을 계산 해 야 합 니 다:index=val/32;
예 를 들 어 정수 33,index=33/32=1,33 번 째 는 배열 에 있 는 index=1 이다.
예 를 들 어 정수 67,index=67/32=2,배열 에 있 는 index=2
그리고 이 index 에 있 는 위 치 를 계산 합 니 다.배열 의 모든 요소 가 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);//xxxxx 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);//이게 더 빨 라?
}　
어떻게 정수 가 존재 하 는 지 검사 합 니까?
예 를 들 어 우 리 는 33 을 검 측 했 습 니 다.마찬가지 로 우 리 는 index 와 index 요소 중의 위 치 를 계산 해 야 합 니 다.
33:index=1,bmap[1]의 위 치 는 1 입 니 다.이 위치 가 1 인지 확인 하기 만 하면 됩 니 다.
bmp[1]&(1<1),이렇게 하면 1 이 true 로 돌아 가 는 지,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;
}

지금 보 자.메모리 요구 가 10MB 라면?
이것 은 당연히 bitmap 로 직접 계산 할 수 없다.40 억 데이터 에서 존재 하지 않 는 데 이 터 를 찾 을 수 있 기 때문에 우 리 는 이렇게 많은 데 이 터 를 여러 조각 으로 나 눌 수 있다.예 를 들 어 각 조각의 크기 가 1000 이면 첫 번 째 조각 은 0 에서 999 의 숫자 이 고 두 번 째 조각 은 1000 에서 1999 의 숫자 이다.
실제로 우 리 는 이 숫자 를 저장 하지 않 고 블록 마다 계수 기 를 설정 합 니 다.이렇게 한 개의 수 를 읽 을 때마다 우 리 는 그것 이 있 는 블록 에 대응 하 는 카운터 에 1 을 추가 합 니 다.
처리 가 끝 난 후에 우 리 는 블록 을 찾 았 습 니 다.카운터 의 값 은 블록 크기(1000)보다 작 습 니 다.이 단락 에 파일 에 포함 되 지 않 은 숫자 가 있 음 을 설명 합 니 다.그리고 우 리 는 이 덩어리 를 단독으로 처리 하면 된다.이제 우 리 는 비트 맵 알고리즘 을 사용 할 수 있다.우 리 는 데 이 터 를 다시 한 번 옮 겨 다 니 며 이 블록 에 떨 어 진 수 를 대응 하 는 위치 1(우 리 는 먼저 이 수 를 0 에서 Blocksize 사이 로 돌려 야 합 니 다).마지막 으로 우 리 는 이 블록 에서 첫 번 째 로 0 인 위 치 를 찾 았 습 니 다.그 에 대응 하 는 수 는 이 파일 에 나타 나 지 않 은 수 입 니 다.)
코드 는 다음 과 같 습 니 다.

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()
{
  //      
  freopen("test.txt", "w", stdout);
  for (int i = 0; i < 1000; ++i)
  {
    if (i == 127) {
      printf("0
");
      continue;
    }
    printf("%d
", i);
  }
  fclose(stdout);
 
  //      
  freopen("test.txt", "r", stdin);
  int Value;
  while (scanf("%d", & Value) != EOF) {
    ++Bucket[Value / BLOCK_SIZE]; //        
  }
  fclose(stdin);
 
  //        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);
 
  //       
  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);
}

이상 이 바로 본 고의 모든 내용 입 니 다.여러분 의 학습 에 도움 이 되 고 저 희 를 많이 응원 해 주 셨 으 면 좋 겠 습 니 다.