どのように[0,maxval]の範囲内のm個のランダム整数を生成するか?

ここでは生成すべきデータ構造をInt Setと呼び、インターフェースの定義は以下の通りである.

class IntSetImp

{

public:

    IntSetImp(int maxelements,int maxval);

    void insert(int t);

    int size();

    void report(int *v);//            v 

};

 
一つの使用例は:

void gensets(int m,int maxval)

{

    int *v = new int[m];

    IntSetImp S(m,maxval);

    while(S.size()<m) {

        S.insert(bigrand()%maxval);

    }

    S.report(v);

    for (int i = 0; i < m; ++i)

    {

        cout<<v[i]<<"
";

    }

}

 
この問題をどのように実現するかを検討し、私たちが欲しい機能を各種データ構造で実現し、それらの性能を比較します.
1:強力で一般的なsetテンプレートを使用する

class IntSetSTL

{

private:

    set<int> S;

public:

    IntSetSTL(int maxelements,int maxval){}

    int size(){return S.size();}

    void insert(int t){S.insert(t);}

    void report(int *v)

    {

        int j=0;

        set<int>::iterator i;

        for(i=S.begin();i!=S.end();++i)

        {

            v[j++]=*i;

        }

    }

};

 基本的には標準テンプレートライブラリの該当部分を利用しています.
2:標準テンプレートライブラリを採用しているのに対して、一番簡単な構造で構成できます.

class IntSetArray

{

private:

    int n,*x;//n      ，x    

public:

    IntSetArray(int maxelements,int maxval)

    {

        x=new int[1+maxelements];

        n=0;

        x[0]=maxval;//maxval     ，            

    }

    int size(){return n;}

    void insert(int t)

    {

        int i;//record

        for(i=0;x[i]<t;i++) ;

        if(x[i]==t) return;//already in array

        for(int j=n;j>=i;j--)

            x[j+1]=x[j];

        x[i]=t;

        n++

    }

    void report(int *v)

    {

        for (int i = 0; i < n; ++i)

        {

            v[i]=x[i];

        }

    }

};

 
配列(集合)のサイズを知ることができる場合、配列は秩序化されており、ランダムアクセスをサポートしているので、動作時間はO(logN)の検索関数を二分検索で確立することができる比較的理想的な構造になります.
3:しかし、セットの大きさが分からない場合、チェーンはセットの優先構造を表し、チェーンは挿入時の要素移動のオーバーヘッドを省くことができます.

class IntSetList

{

private:

    int n;

    struct node

    {

        int val;

        node *next;

        node(int v,node *p){val=v;next=p;}

    };

    node *head,*sentinel;

    node *rinsert(node *p,int t)

    {

        if(p->val<t) p->next=rinsert(p->next,t);

        else if(p->val>t)

        {

            p=new node(t,p);

            n++;

        }

        return p;

    }

public:

    IntSetList(int maxelements,int maxval)

    {

        head=sentinel=new node(maxval,0);

        n=0；

    }

    int size(){return n;}

    int insert(int t){head=rinsert(head,t);}

    void report(int *v)

    {

        int j=0;

        for(node *p=head;p!=sentinel;p=p->next) v[j++]=p->val;

    }

};

 4:快速検索と挿入をサポートする構造を以下に考えます.

class IntSetBST

{

private:

    int n,*v,vn;

    struct node

    {

        int val;

        node *left,*right;

        node(int i){val=i;left=right=0;}

    };

    void rinsert(p,t)

    {

        if(p==0)

        {

            p= new node(t);

            n++;

        }

        else if(t<p->val) p->left=rinsert(p->left,t);

        else if(t>p->val) p->right=rinsert(p->right,t);

        return p;

    }

    void traverse(p)

    {

        if(p==0) return;

        traverse(p->left);

        v[vn++]=p->val;

        traverse(p->right);

    }

public:

    IntSetBST(int maxelements,int maxval){root=0;n=0;}

    int size(){return n;}

    void insert(int t) {root=rinsert(root,t);}

    void report(int *x){ v=x;vn=0;traverse(root);}

};

 
 
5:現在、より高級な構造を見て、整数特性を利用した構造--ビットベクトル

class IntSetBitVec

{

private:

    enum { BITSPERWORD=32,SHIFT=5,MASK=0x1F;};//BITSPERWORD  SHIFT     ， 0x1F  31，  11111，     

    int n,*x,hi;

    void set(int i) {          x[i>>SHIFT] |=  (1<<(i & MASK));}//i & MASK   i    ，1<<(i & MASK)=2 （i & MASK）  

    void clr(int i) {          x[i>>SHIFT] &= ~(1<<(i & MASK));}

    void test(int i){ return x[i>>SHIFT] &   (1<<(i & MASK));}

  /*i = 42 --> i&MASK        1<<(i&MASK)     ~(1<<10)      i>>SHIFT

    42=101010  101010        1<<10=2^10     =~10000000000 =101010>>5

              & 11111       =10000000000    = 01111111111 =1

              -------

               001010=10 

    clr(i) --> x[i>>SHIFT]=0

    set(i) --> x[i>>SHIFT]=0|2 （i & MASK）  =2 （i & MASK）    

    test(i) ->     set(i) 2 （i & MASK）   & 2 （i & MASK）  =2 （i & MASK）     True  

                  0 & 。。。=0   False 

    */    

public:

    IntSetBitVec(int maxelements,int maxval)

    {

        hi=maxval;

        x= new int[1+hi/BITSPERWORD];

        for(int i=0;i<hi;i++) clr(i);

        n=0;

    }

    int size() {return n;}

    void insert(int t)

    {

        if(test(i)) return;

        set(t);

        n++;

    }

    void report(int *v)

    {

        int j=0;

        for (int i = 0; i < hi; ++i)

        {

            if(test(i)) v[j++]=i;

        }

    }

};

 
ビットベクトルの不足はnが大きいなら、必要なメモリも比較的大きいです.
6:最後のデータ構造はチェーンとビットベクトルの長所を結合しています.彼女は箱のシーケンスに整数を入れます.

class IntSetBins

{

private:

    int n,bins,maxval;

    struct node

    {

        int val;

        node *next;

        node(int v,node *p) { val=v;next=p;}

    };

    node **bin,*sentinel;

    node *rinsert(node *p,int t)

    {

        if(p->val<t ) p->next=rinsert(p->next,t);

        else if(p->val>t) 

        {

            p = new node(t,p);n++;

        }

        return p;

    }

public:

    IntSetBins(int maxelements,int pmaxval)

    {

        bins = maxelements;

        maxval = pmaxval;

        bin = new node*[bins];

        sentinel = new node(maxval,0);

        for (int i = 0; i < bins; ++i)

            bin[i]=sentinel;

        n=0;

    }

    int size() {return n;}

    void insert(int t)

    {

        int i=t/(1+maxval/bins);

        bin[i] = rinsert(bin[i],t);

    }

    void report(int *v)

    {

        int j=0;

        for (int i = 0; i < bins; ++i)

            for(node *p = bin[i];p!=sentinel;p=p->next)

                v[j++] = p->val;

    }

    ~IntSetBins();

};