ビットマップのソートとその拡張応用--『プログラミング珠玉』読書ノート
一、基本的なビットマップの並べ替え
質問1:n=100万個の正の整数を含むファイルを入力します.各正の整数はN=1000万個未満で、この100万個の正の整数は重複していません.このファイルの数字を並べ替えて、結果をファイルに保存します.できるだけ小さなメモリを消費し、できるだけ速くする必要があります.
解析解決:intで正の整数を1つ保存すると、intは4 Byteで、100万個の数は400万Byteで、約4 Mになります.高速配列を用いると,時間複雑度はO(nlogn)である.
問題の特殊性を考慮すると、すべての数字は正の整数であり、重複しないので、ビットマップで解決できます.各数字はビットマップの1桁に対応し、数字が現れたら1、そうでなければ0に設定します.1つのint 4 Byteは32個の数を保存することができ、すべての数が1000万未満であるため、まず1000万個の大きさのビットマップでこの100万個の数を記録することができ、最後にこのビットマップを最初からスキャンし、1の数字を順番に出力することができる.ビットマップでソートするのに必要な空間は約1.25 Mであり,時間的複雑度はO(N)であり,空間的にも時間的にも速い列よりよい.
疑似コードは次のとおりです.
プログラム実装:まず100万の重複しない正の整数ファイルを生成し、各数は1000万未満で、生成方法は私が前に書いた方法を参考にすることができます.
サンプリング問題——『プログラミング珠玉』読書ノート
この文章.私はFloydの方法を採用して、引き出した後に数字は秩序があって、彼らの順序を乱す必要があって、どのように乱すのは私のトランプのプログラムを参考にすることができます
この文章.重複しない乱数を生成するプログラムは次のとおりです.
データができたら、ビットマップアルゴリズムでデータをソートします.ビットマップをint配列で表し,1000万ビットのビットマップには大きさN=(1000万/32+1)の大きさの配列が必要である(プラス1は1000万/32に余剰がある可能性があるため,残りのデータはintを1つ多く必要とする).
1つの数iを手に入れた後、まずこの数をビットマップのどの位置に置くかを知る.配列をarrayと仮定すると、intは32個の数を表すことができるので、iの配列における位置は(i/32)、すなわちarray[i/32]、具体的には配列array[i/32]のどちらになるのでしょうか.i%32で得ることができる.ビットマップ内の数字の位置を知ったら、ビットマップに数字を入れて、セット、テスト、クリアなどの操作を行うことができます.これらの操作のC++コードは以下のように実現され、ビット操作服を用いて計算されます.
ビットマップ全体のソートのC++コードは以下のように実現される.
二、ビットマップ並べ替え拡張
質問2:入力した正の整数が重複を許容し、最大10回しか重複できない場合、この100万個の数字をどのようにソートすればいいのでしょうか.
解析解決:問題1は重複していない正の整数しか処理できず、入力中の数字が重複している場合、上のビットマップアルゴリズムは適用されません.問題の制限を考慮すると、1つの数字は最大10回しか繰り返しられず、元のビットマップアルゴリズムは1つのビットで1つの数字を表し、1つのビットは2つの状態しかありません:1と0、それぞれこの数字の存在と存在を表し、ビットマップを小さく改善すれば、いくつかのビットで1つの数字を表し、これらのビットの数字はそのビットの数字の出現回数を表します.これによりビットマップでソートできます.最大10回しか繰り返されないため、4ビットで1つの数を表すことができ、このような空間は元の基本ビットマップのソートの4倍であり、約5 Mのメモリ空間が必要であり、時間の複雑さはO(N)である.
プログラム実装:各数値対応配列の位置は、前の解析と同様であり、intは32/4=8の数値を表すことができ、正の整数iに対して、対応する配列の下付き位置:i/8を先に見つけ、その開始ビット:4*(i%8)を見つけることができる.
セット:iが現れるたびにその開始ビットに1を加算する.
試験i出現回数:数字ごとに4ビットを占めるので、0 x 0 Fをシフトして、iに対応する位置に移動し、それに対して、下位に移動してi出現回数を得ることができる.
クリア:テストとは反対に、0 xF 0に対応します.
これらの動作のC++実装コードは以下の通りである.
具体的には、基本的なビットマップと元のビットマップのソートの差は多くありませんが、結果を出力するときは、数値が繰り返される回数に応じて反復出力を行います.
三、ビットマップの拡張応用
ビットマップの利点の1つは省スペースで、通常1つのintは1つの数字しか表すことができなくて、ビットマップで複数の数字を表すことができて、2つは速度が速くて、直接具体的な位置にインデックスすることができます.ソートに加えて、次のように使用できます.
重複する数値を特定:testが実行されるたびに、testがゼロ以外の値を返すと、その数値がすでに存在することを示します.
質問1:n=100万個の正の整数を含むファイルを入力します.各正の整数はN=1000万個未満で、この100万個の正の整数は重複していません.このファイルの数字を並べ替えて、結果をファイルに保存します.できるだけ小さなメモリを消費し、できるだけ速くする必要があります.
解析解決:intで正の整数を1つ保存すると、intは4 Byteで、100万個の数は400万Byteで、約4 Mになります.高速配列を用いると,時間複雑度はO(nlogn)である.
問題の特殊性を考慮すると、すべての数字は正の整数であり、重複しないので、ビットマップで解決できます.各数字はビットマップの1桁に対応し、数字が現れたら1、そうでなければ0に設定します.1つのint 4 Byteは32個の数を保存することができ、すべての数が1000万未満であるため、まず1000万個の大きさのビットマップでこの100万個の数を記録することができ、最後にこのビットマップを最初からスキャンし、1の数字を順番に出力することができる.ビットマップでソートするのに必要な空間は約1.25 Mであり,時間的複雑度はO(N)であり,空間的にも時間的にも速い列よりよい.
疑似コードは次のとおりです.
/* phase 1: initialize set to empty */
for i = [0, N)
bit[i] = 0
/* phase 2: insert present elements into the set */
for each i in the input file
bit[i] = 1
/* phase 3: write the sorted output */
for i = [0, N)
if bit[i] = 1
write i on the output fileプログラム実装:まず100万の重複しない正の整数ファイルを生成し、各数は1000万未満で、生成方法は私が前に書いた方法を参考にすることができます.
サンプリング問題——『プログラミング珠玉』読書ノート
この文章.私はFloydの方法を採用して、引き出した後に数字は秩序があって、彼らの順序を乱す必要があって、どのように乱すのは私のトランプのプログラムを参考にすることができます
この文章.重複しない乱数を生成するプログラムは次のとおりです.
#include <iostream>
#include <cstdlib>
#include <ctime>
#include <set>
#include <vector>
#include <fstream>
using namespace std;
// generate random number between i and j,
// both i and j are inclusive
int randint(int i, int j)
{
if (j < i)
{ int t = i; i = j; j = t; }
int ret = i + rand() % (j - i + 1);
return ret;
}
// floyd sample, take m random number without
// duplicate from n
void floyd_f2(int n, int m, set<int> &S)
{
for (int i = n - m; i < n; ++i)
{
int j = randint(0, i);
if (S.insert(j).second)
continue;
else
S.insert(i);
}
}
// shuffle the data set V
void knuth_shuffle(vector<int> &V)
{
int n = V.size();
for (int i = n - 1; i != 0; --i)
{
int j = randint(0, i);
int t = V[i]; V[i] = V[j]; V[j] = t;
}
}
template<typename T>
void output_file(T beg, T end, char *file)
{
ofstream outfile(file);
if (!outfile)
{
cout << "file \"" << file << "\" not exists" << endl;
return;
}
while (beg != end)
{
outfile << *beg << endl;
++beg;
}
outfile.close();
}
void help()
{
cout << "usage:" << endl;
cout << "./Floyd_F2 n m output_file_name" << endl;
}
int main(int argc, char* argv[])
{
if (argc != 4)
{
help();
return 1;
}
srand(time(NULL));
int n = atoi(argv[1]);
int m = atoi(argv[2]);
set<int> S;
// sample
floyd_f2(n, m, S);
// shuffle
vector<int> V(S.begin(), S.end());
knuth_shuffle(V);
// output
vector<int>::iterator VBeg = V.begin();
vector<int>::iterator VEnd = V.end();
//output(VBeg, VEnd);
output_file(VBeg, VEnd, argv[3]);
return 0;
}データができたら、ビットマップアルゴリズムでデータをソートします.ビットマップをint配列で表し,1000万ビットのビットマップには大きさN=(1000万/32+1)の大きさの配列が必要である(プラス1は1000万/32に余剰がある可能性があるため,残りのデータはintを1つ多く必要とする).
1つの数iを手に入れた後、まずこの数をビットマップのどの位置に置くかを知る.配列をarrayと仮定すると、intは32個の数を表すことができるので、iの配列における位置は(i/32)、すなわちarray[i/32]、具体的には配列array[i/32]のどちらになるのでしょうか.i%32で得ることができる.ビットマップ内の数字の位置を知ったら、ビットマップに数字を入れて、セット、テスト、クリアなどの操作を行うことができます.これらの操作のC++コードは以下のように実現され、ビット操作服を用いて計算されます.
#define BITWORD 32
#define SHIFT 5
#define MARK 0x1F
#define N 10000000
#define COUNT ((N) / (BITWORD))
int ary[COUNT + 1];
void set(int i)
{
ary[i >> SHIFT] |= (1 << (i & MARK));
}
bool test(int i)
{
return (ary[i >> SHIFT] & (1 << (i & MARK)));
}
void clr(int i)
{
ary[i >> SHIFT] &= ~(1 << (i & MARK));
}ビットマップ全体のソートのC++コードは以下のように実現される.
#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <sstream>
using namespace std;
#define BITWORD 32
#define SHIFT 5
#define MARK 0x1F
#define N 10000000
#define COUNT ((N) / (BITWORD))
int ary[COUNT + 1];
void set(int i)
{
ary[i >> SHIFT] |= (1 << (i & MARK));
}
bool test(int i)
{
return (ary[i >> SHIFT] & (1 << (i & MARK)));
}
void clr(int i)
{
ary[i >> SHIFT] &= ~(1 << (i & MARK));
}
void help()
{
cout << "usage:" << endl;
cout << "./BitSort inputfile outputfile" << endl;
}
int main(int argc, char *argv[])
{
if (argc != 3)
{
help();
return 1;
}
ifstream infile(argv[1]);
if (!infile)
{
cout << "file \"" << argv[1] << "\" not exists" << endl;
return 1;
}
time_t t_start, t_end;
t_start = time(NULL);
// read the data and set the data in the bit map
string line;
istringstream istream;
int num = 0;
while (getline(infile, line))
{
istream.str(line);
istream >> num; // read the number
set(num); // set the number
istream.clear();
}
infile.close();
ofstream outfile(argv[2]);
if (!outfile)
{
cout << "create output file \"" << argv[2] << "\" failed" << endl;
return 1;
}
// read the bit map and write to the file
for (int i = 0; i <= N; ++i)
{
if (test(i))
outfile << i << endl;
}
outfile.close();
t_end = time(NULL);
cout << "time collapse: " << difftime(t_end, t_start) << " s" << endl;
cout << "need " << ((double)N / (8 * 1000000)) << " M memory" << endl;
return 0;
}二、ビットマップ並べ替え拡張
質問2:入力した正の整数が重複を許容し、最大10回しか重複できない場合、この100万個の数字をどのようにソートすればいいのでしょうか.
解析解決:問題1は重複していない正の整数しか処理できず、入力中の数字が重複している場合、上のビットマップアルゴリズムは適用されません.問題の制限を考慮すると、1つの数字は最大10回しか繰り返しられず、元のビットマップアルゴリズムは1つのビットで1つの数字を表し、1つのビットは2つの状態しかありません:1と0、それぞれこの数字の存在と存在を表し、ビットマップを小さく改善すれば、いくつかのビットで1つの数字を表し、これらのビットの数字はそのビットの数字の出現回数を表します.これによりビットマップでソートできます.最大10回しか繰り返されないため、4ビットで1つの数を表すことができ、このような空間は元の基本ビットマップのソートの4倍であり、約5 Mのメモリ空間が必要であり、時間の複雑さはO(N)である.
プログラム実装:各数値対応配列の位置は、前の解析と同様であり、intは32/4=8の数値を表すことができ、正の整数iに対して、対応する配列の下付き位置:i/8を先に見つけ、その開始ビット:4*(i%8)を見つけることができる.
セット:iが現れるたびにその開始ビットに1を加算する.
試験i出現回数:数字ごとに4ビットを占めるので、0 x 0 Fをシフトして、iに対応する位置に移動し、それに対して、下位に移動してi出現回数を得ることができる.
クリア:テストとは反対に、0 xF 0に対応します.
これらの動作のC++実装コードは以下の通りである.
#define BITWORD 8
#define SHIFT 3
#define MARK 0x07
#define TEST 0x0F
#define POS ((i & MARK) << 2)
#define N 10000000
#define COUNT ((N) / (BITWORD))
int ary[COUNT + 1];
void set(int i)
{
ary[i >> SHIFT] += 1 << POS;
}
// return the presence count of number i, used for output
int test(int i)
{
return (ary[i >> SHIFT] & (TEST << POS)) >> POS;
}
void clr(int i)
{
ary[i >> SHIFT] &= ~(TEST << ((i & MARK) << 2));
}具体的には、基本的なビットマップと元のビットマップのソートの差は多くありませんが、結果を出力するときは、数値が繰り返される回数に応じて反復出力を行います.
// read the bit map and write to the file
for (int i = 0; i <= N; ++i)
{
int count = test(i); // get the count of number i's presence
for (int j = 0; j != count; ++j)
outfile << i << endl;
}三、ビットマップの拡張応用
ビットマップの利点の1つは省スペースで、通常1つのintは1つの数字しか表すことができなくて、ビットマップで複数の数字を表すことができて、2つは速度が速くて、直接具体的な位置にインデックスすることができます.ソートに加えて、次のように使用できます.
重複する数値を特定:testが実行されるたびに、testがゼロ以外の値を返すと、その数値がすでに存在することを示します.