位圖應用

一、背景介紹

       本文主要是對程式設計珠玑中第一章的學習總結。問題背景大緻如下：一個最多包含n個正整數的檔案，每個數都小于n,其中n=10^7，同時所有的正整數不重複出現。現在需要按升序将所有的整數輸出，限制條件是最多有1MB的記憶體空間可用，但磁盤空間充足。

       如果按通常的處理的方法，使用int類型（32位）存儲整數，這樣1MB的空間可存儲10^6B/4B，即約250000個整數，雖然不能同時對所有的資料進行排序。但也可以采取多趟周遊磁盤的方法完成排序工作，但卻IO開銷大耗時多。于是文中便提出了利用位圖（位向量）的方法來解決問題。

二、位圖實作

1、實作介紹

       例如要表示集合{1,2,3,5,8,13}，可采用20位的字元串“01110100100001000000”表示。在問題中每個7位的十進制數表示一個小于1000萬的整數，于是我們可以使用一個具有1000萬個位的字元串來表示這個檔案，其中當且僅當整數i在檔案中存在時，第i位為1。

2、C語言實作

       由于C語言中沒有實作位圖的資料結構(c++中有bitset集合)，需要通過位運算來實作。下面的C語言程式采用了int來實作位圖。

       假設總的位圖位數為N（題設為1000萬），則需要的int數組的位數為(N/32 + 1),是以定義了數組int a[N/32 + 1]。

       對于邏輯上的第i位，其存儲的位置則為第i/32（位運算采用i>>5，即将i右移5位）個int位置，位位置為i%32(位運算采用i&0x1F實作，即i與數31進行“與”運算)。

       是以對邏輯上第i位置1（函數set）為：a[i>>5 ] = a[i>>5] | 1<<(i&0x1F)。即将1左移（i&0x1F）位後再和a[i>>5]進行“或”運算。例如當i等于33時，由33/32及33%32知邏輯位33由a[1]的第1位表示（含第0位）。位運算中，[i>>5]即為a[1],1<<(i&0x1F)結果為2（即0000 0010）,假如此時a[1]為0（即0000 0000）,是以或運算的結果是将a[1]的第1位置1。

c語言實作代碼如下：

#include<stdio.h>
#include<stdlib.h>
#include<time.h>

#define N 10000000

int a[N/ + ];

//将邏輯上第i位置1
void set(int i)
{
    a[i>> ] = a[i>>] | <<(i&);
}

//檢視邏輯上第i位狀态
int test(int i)
{
    return a[i>>] & (<<(i&));
}

//将邏輯上第i位置0
void clear(int i)
{
    a[i>>] = a[i>>] & (~(<<(&)));
}

//清零
void pre()
{
    int i;

    for(i = ; i< N; i++)
        clear(i);
}

int main()
{
    FILE *fp;
    srand((unsigned)time(NULL));
    int count = ;
    int t, i;

    if( (fp = fopen("input.txt", "r")) == NULL )
    {
        printf("can not open the file!\n");
        exit();
    }

    //對位圖清零
    pre();

    //讀入檔案，将讀入資料對應邏輯位置1
    while(fscanf(fp, "%d", &t) != EOF){
        set(t);
    }

    //輸出排序結果
    for(i = ; i < N; i++)
    {
        if(test(i)){
            printf("%d\n", i);
        }
    }
    fclose(fp);
    return ;
}
           

三、其他

       在程式設計珠玑第一章的習題中，包括了将記憶體上限嚴格限制為1MB（習題5），因為上面的實作實際是需要1.25MB的。其實隻要了解了前面的内容也還是很好實作的，最關鍵的兩個思想是位圖和多趟排序。以及習題6中将題目條件改為每個整數最多重複10次，則可以用4位來記錄每個整數的出現次數(好吧 我開始的想法是用10位~)。

       以上。