程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> 微軟筆試題給一個包含10^7個整數的大文件排序

微軟筆試題給一個包含10^7個整數的大文件排序

編輯：C++入門知識

這個題目有一個前提條件，大文件的中的數據有有一個特點，那就是不存在重復的數據。就算是重復的數據，也只讓你求出去除重復之後的那些數據的排序結果。

如果題目變成了這樣，我們就可以考慮創建一個大的數組。數組的下表表示一個整數，數組的內容在我遍歷文件的時候再賦值。如果數組下標代表的那個整數存在，我們就把數組的這個元素賦值為1，否則賦值為0.這樣我們就可以再次遍歷數組，把元素的值為1的那些下標輸出到另一個文件，這樣另一個文件中就存放了排好序的數據了。

上面的那個數組，其實我們可以用vector<bool>,或者bitset<n>;來實現，這就是所謂的位圖算法，實現如下：

[cpp]
//對10^7個整數的文件進行排序，整數無重復，將排序的結果寫到sorted_data.txt文件中。
//用位圖的方法。
void sort_big_file_with_single_data()
{
    timer t;
    //生成一個大數集合，隨機排列
    const int n=5000000;
    vector<int> a;
    for (int i=0;i<n;i++)
        a.push_back(i);

    variate_generator<mt19937, uniform_int<> > myrandom (mt19937(), uniform_int<>(0,n-1));
    for (int i=0; i<n; ++i)
        swap(a[myrandom()],a[myrandom()]);

    //寫數據到文件
    ofstream fout("data.txt",ios::binary);
    if (!fout)
    {
        cout<<"can not open file to write"<<endl;
    }
    for (int i=0;i<n;i++)
    {
        fout.write(reinterpret_cast<const char*>(&a[i]),sizeof(int));
    }
    fout.close();

    //從文件中讀取前100個數據並顯示
    ifstream fin;
    fin.open("data.txt",ios::binary);
    for (int i=0,num=0;i<100;i++)
    {
        fin.read(reinterpret_cast<char*>(&num),sizeof(int));
        if (fin.eof())
        {
            break;
        }
        cout<<num<<" ";
    }
    fin.close();

    //對文件排序
    bitset<n> bit;
    bit.reset();
    //ifstream fin;
    fin.open("data.txt",ios::binary);
    int i=0;
    while (true)
    {
        fin.read(reinterpret_cast<char*>(&i),sizeof(int));
        if (fin.eof())
        {
            break;
        }
        bit[i]=true;
    }
    fin.close();
    //將排序的文件輸出到sorted_data.txt
    //ofstream fout;
    fout.open("sorted_data.txt",ios::binary);
    for (int i=0;i<n;i++)
    {
        if (bit[i]==true)
        {
            fout.write(reinterpret_cast<const char*>(&i),sizeof(int));
        }
    }
    fout.close();
    cout<<"sort data "<<t.elapsed()<<" seconds needed"<<endl;

    //讀取已經排序的文件並顯示前100個數據
    fin.open("sorted_data.txt",ios::binary);
    for (int i=0,num=0;i<100;i++)
    {
        fin.read(reinterpret_cast<char*>(&num),sizeof(int));
        if (fin.eof())
        {
            break;
        }
        cout<<num<<" ";
    }
    fin.close();
}

//對10^7個整數的文件進行排序，整數無重復，將排序的結果寫到sorted_data.txt文件中。
//用位圖的方法。
void sort_big_file_with_single_data()
{
timer t;
//生成一個大數集合，隨機排列
const int n=5000000;
vector<int> a;
for (int i=0;i<n;i++)
a.push_back(i);

variate_generator<mt19937, uniform_int<> > myrandom (mt19937(), uniform_int<>(0,n-1));
for (int i=0; i<n; ++i)
swap(a[myrandom()],a[myrandom()]);

//寫數據到文件
ofstream fout("data.txt",ios::binary);
if (!fout)
{
cout<<"can not open file to write"<<endl;
}
for (int i=0;i<n;i++)
{
fout.write(reinterpret_cast<const char*>(&a[i]),sizeof(int));
}
fout.close();

//從文件中讀取前100個數據並顯示
ifstream fin;
fin.open("data.txt",ios::binary);
for (int i=0,num=0;i<100;i++)
{
  fin.read(reinterpret_cast<char*>(&num),sizeof(int));
  if (fin.eof())
  {
   break;
  }
  cout<<num<<" ";
}
fin.close();

//對文件排序
bitset<n> bit;
bit.reset();
//ifstream fin;
fin.open("data.txt",ios::binary);
int i=0;
while (true)
{
  fin.read(reinterpret_cast<char*>(&i),sizeof(int));
  if (fin.eof())
  {
   break;
  }
  bit[i]=true;
}
fin.close();
//將排序的文件輸出到sorted_data.txt
//ofstream fout;
fout.open("sorted_data.txt",ios::binary);
for (int i=0;i<n;i++)
{
  if (bit[i]==true)
  {
   fout.write(reinterpret_cast<const char*>(&i),sizeof(int));
  }
}
fout.close();
cout<<"sort data "<<t.elapsed()<<" seconds needed"<<endl;

//讀取已經排序的文件並顯示前100個數據
fin.open("sorted_data.txt",ios::binary);
for (int i=0,num=0;i<100;i++)
{
  fin.read(reinterpret_cast<char*>(&num),sizeof(int));
  if (fin.eof())
  {
   break;
  }
  cout<<num<<" ";
}
fin.close();
}
上面對5百萬個整數的文件進行排序，將結果輸出到另外一個文件中，並顯示輸出文件的一部分作為測試結果。