sort big data
或许是巧合，sorting是我们队名，下午的题目也是sorting题目，但是我们当时做的并不好，个人觉得。
首先思路比较有限，没有开阔，尽管分治在理论上和直接sort似乎没有太多的差别
直接排序nlogn
分治排序(假设刚好整分) n/m log n/m m +n= n(1+logn/m)
正如胡瀚森大神所说，log 50W~=19 和log 5W +1~=17 差别几乎是可以忽略的， 所以用分支并不会带来较明显的性能优势，自己实践发现的确也是如此。
这里实现了几个版本
直接sort，快排，也是较快的
unique可以调用系统的，不一定是unique_copy，或者自己写一个one-pass的，自己写了一个双while，后来发现其实是可以缩掉一个while，正如fawkes大神所说，他习惯判断是否和前一个元素
相等，我的是和之前已经处理过的最后一个元素是否相等。华师软院likexi同学组提到的分治我自己写了一下，结果发现了自己对于pop_heap api使用的一个严重错误。其实本不需要用heap，但是这样也好，多暴露一些问题。
因为分别是按照极短排序直接append就可以了，不用merge。
pop_heap 我以为是: swap(a[0],a[size-1]), size—; Filterdown(0), 但是发现不是的，a[0]也要参与比较，这样我已开始a[0] 越界了调用pop_heap 就会出bug.
pop_heap 的 Preconditions 是三个条件，[first, last)至少一个元素，也即last>first, 并且[first, last] is a heap, 所以我的做法是错误的。因为first已经越界了。
所以我目前想到的做法就是 手动swap size— 然后make_heap。 群里某童鞋发给我STL源码，之前一直以为这种自己是接触不到的，现在也要逐渐开始懂源码了。
但是后来看了下，发现其实还是要照原来的思路来理解，遇到问题不是pop_heap的问题，而是MSVC那个蛋疼的STL，那个蛋疼的algorithm里面的pop_heap, 管他怎么实现，反正和SGI STL不一样就对了。但是SGI STL里面要求原始的[first, last)是heap，这里也有异或
- 如果直接merge 复杂度一般是比heap要高的。
附上搞的代码，不要用MSVC编译。。。。
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <ctime>
#include <vector>
using namespace std;
typedef unsigned int ui;
const ui MAXNUM=5e5;
// 实现基本的，分支的，首先unique_copy, 计时，还有多线程，Java Bigint，处理不止10位的整数，string char*, bitset， bitmap, 位率
ui a[MAXNUM];
ui b[MAXNUM];
ui n;
ui bucket_num=32;
ui MAXUINT=0xFFFFFFFF;
clock_t start;
clock_t endc;
vector<ui> bucket[MAXNUM];
vector<ui> veca;
vector<pair<int,int> > bucketpos;
void removerepeated_fawks(vector<ui>& a)
{
int save = 0;
int n = a.size();
for (int i = 0; i < n; i++)
{
if (!i || a[i] != a[i - 1]) a[save++] = a[i];
}
a.resize(save);
}
void removerepeated(vector<ui>& a)
{
if(a.size()==0) return ;
ui bucketn = a.size();
ui i=1,curi=0;
while(i<bucketn)
{
while(i<bucketn && a[i]==a[curi])
i++;
if(i==bucketn) break;
a[++curi]=a[i++];
}
a.resize(curi+1);
}
void removerepeated_onewhile(vector<ui>& a)
{
if(a.size()==0) return;
ui i=1,curi=0;
while(i<a.size())
{
if(a[curi]!=a[i])
{
a[++curi]=a[i++];
}
else
i++;
}
a.resize(curi+1);
}
void sort_unique_copy()
{
sort(a,a+n);
//ui* end_b=unique_copy(a,a+n,b);
ui* aend=unique(a,a+n);
//printf("%d\n",end_b-b);
printf("%d\n",aend-a);
for(ui* i=a;i!=aend;i++)
printf("%u\n",*i);
/*
for(size_t i=0;i<n;i++)
printf("%d ",b[i]);
*/
puts("");
}
void sort_one_pass()
{
//start=clock();
sort(veca.begin(),veca.end());
//endc=clock();
//printf("STL Sorting Time: %f\n",(double)(endc - start) / CLOCKS_PER_SEC);
removerepeated_fawks(veca);
/*
ui i=1,curi=0;
while(i<n)
{
while(i<n && a[i]==a[curi])
i++;
if(i==n) break;
a[++curi]=a[i++];
}*/
//start=clock();
printf("%d\n",veca.size());
for(ui i=0;i<veca.size();i++)
printf("%u\n",veca[i]);
//endc=clock();
//printf("Writing Time: %f\n",(double)(endc - start) / CLOCKS_PER_SEC);
}
bool AtLeastTwoArray()
{
if(bucketpos.size()>=2)
return true;
else
return false;
}
bool comp(const pair<int,int> i, const pair<int,int> j)
{
return bucket[i.first][i.second]>bucket[j.first][j.second];
}
void sort_m_bucket_append()
{
bucketpos.clear();
//ui threshold[bucket_num];
//for(ui i=0;i<bucket_num;i++)
// threshold[i]=n/4*i;
//ui merge[n];
for(ui i=0;i<bucket_num;i++)
bucket[i].clear();
ui bucket_cap=MAXUINT/bucket_num+1;
for(ui i=0;i<n;i++)
{
bucket[veca[i]/bucket_cap].push_back(veca[i]);
}
for(ui i=0;i<bucket_num;i++)
{
sort(bucket[i].begin(),bucket[i].end());
removerepeated(bucket[i]);
}
ui ai=0;
for(ui i=0;i<bucket_num;i++)
{
for(ui j=0;j<bucket[i].size();j++)
a[ai++]=bucket[i][j];
}
printf("%u\n",ai);
for(ui i=0;i<ai;i++)
printf("%u\n",a[i]);
}
void sort_m_bucket()
{
bucketpos.clear();
//ui threshold[bucket_num];
//for(ui i=0;i<bucket_num;i++)
// threshold[i]=n/4*i;
//ui merge[n];
for(ui i=0;i<bucket_num;i++)
bucket[i].clear();
ui bucket_cap=MAXUINT/bucket_num+1;
for(ui i=0;i<n;i++)
{
bucket[veca[i]/bucket_cap].push_back(veca[i]);
}
for(ui i=0;i<bucket_num;i++)
{
sort(bucket[i].begin(),bucket[i].end());
removerepeated(bucket[i]);
}
//vector<ui> pos(bucket_num,0);
for(ui i=0;i<bucket_num;i++)
{
if(bucket[i].size()>=1)
bucketpos.push_back(make_pair(i,0));
}
make_heap(bucketpos.begin(),bucketpos.end(),comp);
ui min,ai=0;
ui mini;
while(AtLeastTwoArray())
{
a[ai++]=bucket[bucketpos.front().first][bucketpos.front().second];
bucketpos.front().second=bucketpos.front().second+1;
if(bucketpos.front().second>=bucket[bucketpos.front().first].size())
{
pop_heap(bucketpos.begin(),bucketpos.end(),comp);
bucketpos.pop_back();
}
else
{
pop_heap(bucketpos.begin(),bucketpos.end(),comp);
push_heap(bucketpos.begin(),bucketpos.end(),comp);
}
/*
if(bucketpos.front().second+1<bucket[bucketpos.front().first].size())
{
bucketpos.front().second=bucketpos.front().second+1;
pop_heap(bucketpos.begin(),bucketpos.end(),comp);
push_heap(bucketpos.begin(),bucketpos.end(),comp);
}
else
{
swap(bucketpos.front(),bucketpos.back());
bucketpos.pop_back();
make_heap(bucketpos.begin(),bucketpos.end(),comp);
}
*/
/*
min=0xFFFFFFFF;
for(ui i=0;i<bucket_num;i++)
{
if(pos[i]>=bucket[i].size())
continue;
if(min>bucket[i][pos[i]])
min=bucket[i][pos[i]],mini=i;
}
a[ai++]=min;
pos[mini]++;*/
}
if(bucketpos.size()==1)
{
for(ui j=bucketpos[0].second;j<bucket[bucketpos[0].first].size();j++)
a[ai++]=bucket[bucketpos[0].first][j];
}
//merged ai number of type ui into a[]
printf("%u\n",ai);
for(ui i=0;i<ai;i++)
printf("%u\n",a[i]);
/*
for(ui i=0;i<bucket_num;i++)
{
if(i!=0)
sort(a+(n/bucket_num)*i+1,(n/bucket_num)*(i+1)+2)
else
sort(a,a+n/bucket_num+1);
}*/
//sort(a,a+n/bucket_num+1);
//sort(a+n/bucket_num+1,a+n/bucket_num)
}
int main()
{
freopen("in.txt","r",stdin);
freopen("out_unique_copy.txt","w",stdout);
/*
srand(time(NULL));
printf("%d\n",MAXNUM);
for(ui i=0;i<MAXNUM;i++)
printf("%u\n",ui((double)rand()/RAND_MAX * MAXUINT));
*/
start=clock();
scanf("%d", &n);
ui x;
for(ui i=0;i<n;i++)
scanf("%u", &x),veca.push_back(x);
endc=clock();
printf("Reading Time: %f\n",(double)(endc - start)/CLOCKS_PER_SEC);
start=clock();
sort_m_bucket();
endc=clock();
printf("STL Sorting Time: %f\n",(double)(endc - start) / CLOCKS_PER_SEC);
//duration = (double)(finish - start) / CLOCKS_PER_SEC
//printf("Reading Time: %f\n",(double)(end - start) / CLOCKS_PER_SEC);
return 0;
}