学步园

前面发了两篇内排序的文章。（一）中当时归并排序并没有写出，（二）中今天发现在非递归quickSort中stack<node*> 存在内存泄露，并且主程序选项功能支持不是很好，所以今天又练习写了一遍。

大规模排序时，发现1million整形数据大小为6.8M，int在当前平台占4B

1million = 1000000 = 10⁶ ≈2²⁰  总容量=4B*2²⁰ =4M≈6.8M，因为这里面还有空格、回车还有文件自身的一些信息占容量。100million数据大小为673M，1billion数据大小为6.6G。各种文件系统大小限制在下有说明。当前系统最大申请内存可达400G。

C/C++源码:sort.cpp

功能：七种常见内排序算法

#include <iostream><br /> #include <stack><br /> #include <cassert><br /> #include <cstring><br /> #include <cstdio><br /> using namespace std;</p> <p>void bubble(int A[],int n);<br /> void select(int A[],int n);<br /> void insert(int A[],int n);<br /> void shell(int A[],int n);<br /> void merge(int A[],int n);<br /> void heap(int A[],int n);<br /> void quick(int A[],int n);</p> <p>//return 0 success 1 fail<br /> int deal_opt(string& in, string& out, int& n, int& times, int argc, char *argv[]);<br /> int deal_in(int*& A,int& n,int N, string file);<br /> int deal_out(int A[],int n,string file);</p> <p>typedef void (*FUNC)(int A[],int n);<br /> FUNC sort_func[]={bubble,select,insert,shell,merge,heap,quick};<br /> string sort_name[]={"bubble","select","insert","shell","merge","heap","quick"};<br /> const int sort_num=sizeof(sort_func)/sizeof(FUNC);<br /> const int num_per_line = 10;</p> <p>int main(int argc, char *argv[])<br /> {<br /> string infile("din.txt"), outfile("dout_");<br /> string help("command [-i infile] [-o outfile] [-n arrNum] [-t sortTimes]");<br /> int num = 0, *arr = NULL,*arr1=NULL;<br /> int N = 1024*1024*1024;<br /> int sort_times=1;</p> <p> if(0==deal_opt(infile,outfile,N,sort_times,argc,argv)){<br /> if(0==deal_in(arr,num,N,infile)){<br /> arr1=new int[num];<br /> for(int i=sort_num-1;i>=0;i--){<br /> clock_t s = clock();<br /> for(int j=0;j<sort_times;j++){<br /> memmove(arr1,arr,sizeof(int)*num);<br /> (*sort_func[i])(arr1,num);<br /> }<br /> double timeUsed = (double)(clock()-s)/CLOCKS_PER_SEC;<br /> cout<<sort_name[i]<<" timeUsed is "<< timeUsed << "s" << endl;<br /> if(1==deal_out(arr1,num,outfile+sort_name[i])){<br /> cout << "incorrect write outfile" << endl;<br /> cout << help << endl;<br /> }<br /> }<br /> delete [] arr;<br /> delete [] arr1;<br /> }else{<br /> cout << "incorrect read infile" << endl;<br /> cout << help << endl;<br /> }<br /> }else{<br /> cout << "incorrect option" << endl;<br /> cout << help << endl;<br /> }<br /> return 0;<br /> }</p> <p>int string_to_num(char str[]){<br /> int len = strlen(str), sum=0;<br /> for(int i=0;i<len;i++){<br /> assert(str[i]>='0' && str[i]<='9');<br /> sum = sum*10 + str[i]-'0';<br /> }<br /> return sum;<br /> }<br /> int deal_opt(string& in,string& out,int& n, int& times, int argc,char *argv[]){<br /> for(int i=1;i<argc;i++){<br /> if(!strncmp("-i",argv[i],2) && i<argc-1){<br /> in = argv[i+1];<br /> i++;<br /> }else if(!strncmp("-o",argv[i],2) && i<argc-1){<br /> out = argv[i+1];<br /> i++;<br /> }else if(!strncmp("-n",argv[i],2) && i<argc-1){<br /> n=string_to_num(argv[i+1]);<br /> i++;<br /> }else if(!strncmp("-t",argv[i],2) && i<argc-1){<br /> times = string_to_num(argv[i+1]);<br /> i++;<br /> }else{<br /> return 1;<br /> }<br /> }<br /> return 0;<br /> }<br /> int deal_in(int*& A,int& n,int N,string file){<br /> FILE* fptr=NULL;<br /> A = new int[N];<br /> if((fptr=fopen(file.c_str(),"r"))!=NULL){<br /> int data;<br /> n=0;<br /> while(n<N && (fscanf(fptr,"%d",&data))!=EOF)<br /> A[n++]=data;<br /> fclose(fptr);<br /> return 0;<br /> }else{<br /> return 1;<br /> }<br /> }<br /> int deal_out(int A[],int n,string file){<br /> FILE* fptr=NULL;<br /> if((fptr=fopen(file.c_str(),"w"))!=NULL){<br /> for(int i=0;i<n;i++){<br /> fprintf(fptr,"%d/t",A[i]);<br /> if(i%num_per_line==num_per_line-1)<br /> fprintf(fptr,"/n");<br /> }<br /> fclose(fptr);<br /> return 0;<br /> }else{<br /> return 1;<br /> }<br /> }<br /> inline void swap(int& a,int& b){<br /> int tmp = a;<br /> a = b;<br /> b = tmp;<br /> }<br /> void bubble(int A[],int n){<br /> for(int i=1;i<n;i++)<br /> for(int j=1;j<=n-i;j++)<br /> if(A[j]<A[j-1])<br /> swap(A[j],A[j-1]);<br /> }<br /> void select(int A[],int n){<br /> for(int i=0;i<n-1;i++){<br /> int min=i;<br /> for(int j=i+1;j<n;j++)<br /> if(A[j]<A[min])<br /> min = j;<br /> swap(A[i],A[min]);<br /> }<br /> }<br /> void insert(int A[],int n){<br /> for(int i=1,j;i<n;i++){<br /> int tmp=A[i];<br /> for(j=0;j<i && A[j]<=tmp;j++);<br /> for(int k=i-1;k>=j;k--)<br /> A[k+1]=A[k];<br /> A[j]=tmp;<br /> }<br /> }<br /> void shell(int A[],int n){<br /> int h;<br /> for(h=1;h<n/9;h=3*h+1);<br /> for(;h>0;h/=3){<br /> for(int i=h,j;i<n;i+=h){<br /> int tmp=A[i];<br /> for(j=0;j<i && A[j]<=tmp;j+=h);<br /> for(int k=i-h;k>=j;k-=h)<br /> A[k+h]=A[k];<br /> A[j]=tmp;<br /> }<br /> }<br /> }<br /> void merge1(int A[], int l, int r){<br /> if(l<r){<br /> int mid=(r-l)/2+l;<br /> merge1(A,l,mid);<br /> merge1(A,mid+1,r);<br /> int *B = new int[r-l+1];<br /> int i=0, j=l, k=mid+1;<br /> while(j<=mid && k<=r) B[i++]=A[j]<A[k]?A[j++]:A[k++];<br /> while(j<=mid) B[i++]=A[j++];<br /> while(k<=r) B[i++]=A[k++];<br /> memmove(A+l,B,sizeof(int)*i);<br /> delete [] B;<br /> }<br /> }<br /> void merge(int A[],int n){<br /> merge1(A,0,n-1);<br /> }<br /> void heapify(int A[],int i,int n){<br /> #define LC(i) (2*i+1)<br /> #define RC(i) (2*i+2)<br /> while(i<n/2){<br /> int max = A[i],f=0;<br /> if(max<A[LC(i)] && LC(i)<n) max=A[LC(i)], f=1;<br /> if(max<A[RC(i)] && RC(i)<n) f=2;<br /> if(1==f){<br /> swap(A[i],A[LC(i)]);<br /> i=LC(i);<br /> }else if(2==f){<br /> swap(A[i],A[RC(i)]);<br /> i=RC(i);<br /> }else<br /> break;<br /> }<br /> }<br /> void heap(int A[],int n){<br /> if(n<=1) return;<br /> for(int i=n/2-1;i>=0;i--)<br /> heapify(A,i,n);<br /> swap(A[0],A[n-1]);<br /> for(int i=n-2;i>=1;i--){<br /> heapify(A,0,i+1);<br /> swap(A[0],A[i]);<br /> }<br /> }<br /> struct node{<br /> node(int a,int b):l(a),r(b){}<br /> int l, r;<br /> };<br /> void quick(int A[],int n){<br /> stack<node*> s;<br /> s.push(new node(0,n-1));<br /> while(!s.empty()){<br /> int l=s.top()->l;<br /> int r=s.top()->r;<br /> delete s.top();<br /> s.pop();<br /> if(l<r){<br /> int i=l, j=r, pivot=A[l];<br /> while(i<j){<br /> while(i<=j && A[i]<=pivot)<br /> i++;<br /> while(i<=j && A[j]>=pivot)<br /> j--;<br /> if(i<j) swap(A[i],A[j]);<br /> }<br /> swap(A[l],A[j]);<br /> if(j-1-l>0)<br /> s.push(new node(l,j-1));<br /> if(r-j-1>0)<br /> s.push(new node(j+1,r));<br /> }<br /> }<br /> }<br />

C/C++源码：data.cpp

功能：随机生成一定规模的随机数据

#include <iostream><br /> #include <cassert><br /> #include <cstring><br /> #include <ctime><br /> #include <cstdlib><br /> using namespace std;</p> <p>long long cal(char s[]){<br /> long long sum =0;<br /> int len = strlen(s);<br /> for(int i=0;i<len;i++){<br /> assert(s[i]>='0' && s[i]<='9');<br /> sum = sum*10 + (s[i]-'0');<br /> }<br /> return sum;<br /> }</p> <p>const int N = 1024*1024;<br /> const int NUM_PER_LINE = 10;</p> <p>int deal_opt(string& out,long long& n,int argc, char *argv[])<br /> {<br /> for(int i=1;i<argc;i++){<br /> if(!strncmp("-o",argv[i],2) && i<argc-1){<br /> out=argv[i+1];<br /> i++;<br /> }else if(!strncmp("-n",argv[i],2) && i<argc-1){<br /> n=cal(argv[i+1]);<br /> i++;<br /> }else<br /> return 1;<br /> }<br /> return 0;<br /> }<br /> int main(int argc, char *argv[])<br /> {<br /> srand(time(NULL));<br /> long long scale = 10000;<br /> string outfile("data.txt");<br /> string help("command [-o outfile] [-n num]");</p> <p> if(0==deal_opt(outfile,scale,argc,argv)){<br /> FILE *fptr = NULL;<br /> if((fptr=fopen(outfile.c_str(),"w"))!=NULL){<br /> for(long long i=0;i<scale;i++){<br /> fprintf(fptr, "%d/t", rand()%N);<br /> if(i%NUM_PER_LINE==NUM_PER_LINE-1)<br /> fprintf(fptr, "/n");<br /> }<br /> }else{<br /> cout << "incorrect write outfile" << endl;<br /> cout << help << endl;<br /> }<br /> }else{<br /> cout << "incorrect options" << endl;<br /> cout << help << endl;<br /> }<br /> return 0;<br /> }<br />

运行结果：

数据规模10无序数据集，迭代1W次

数据规模100有无序数据集，迭代1024次

数据规模100有序数据集，迭代1024次

数据规模10W无序数据集

数据规模10W有序数据集（注意quickSort性能下降）

数据规模100W无序数据集

1Billion无序数据集（quick,heap,merge，其它O²的方法已经淘汰）

 注意在小规模如果数据集全部可以装入内存，不考虑换页影响的话，三种排序时间复杂度都是O(nlgn)，其中数据显示快排是时间最快，归并时间与其差不多，堆排慢于其它两种方法，大概是1.5倍关系。但是当10亿数据，内存容量约为4G。快排与堆排需要遍历遍历整个数组，会造成颠簸，而归并的性质决定了它每次处理的数据有很强的局部性，不会很大颠簸，所以归并排比其它两种性能提高数倍。

转：各种文件系统大小限制

　
　　NTFS（Windows）：支持最大分区2TB，最大文件2TB
　
　　FAT16（Windows）：支持最大分区2GB，最大文件2GB
　
　　FAT32（Windows）：支持最大分区128GB，最大文件4GB
　
　　Ext2
　
　　最大文件大小： 1TB
　
　　最大文件极限： 仅受文件系统大小限制
　
　　最大分区/文件系统大小： 4TB
　
　　最大文件名长度： 255 字符
　
　　缺省最小/最大块大小： 1024/4096 字节
　
　　缺省inode分配： 每4096字节为1
　
　　在强制FS检查前的最大装载： 20（可配置）
　
　　//REDHAT9默认是ext3的文件系统
　
　　Ext3
　
　　最大文件大小： 1TB
　
　　最大文件极限： 仅受文件系统大小限制
　
　　最大分区/文件系统大小： 4TB
　
　　最大文件名长度： 255 字符
　
　　缺省最小/最大块大小： 1024/4096 字节
　
　　缺省inode分配： 每4096字节为1
　
　　在强制FS检查前的最大装载： 20（可配置）
　
　　ReiserFS
　
　　最大文件大小： 1TB
　
　　最大文件极限： 32k目录，42亿文件
　
　　最大分区/文件系统大小： 4TB
　
　　最大文件名长度： 255 字符
　
　　JFS
　
　　最小文件系统大小 16 MB
　
　　最大文件大小： 受体系结构限制
　
　　最大文件极限： 受文件系统大小限制
　
　　缺省最小/最大块大小： 1024/4096 字节
　
　　缺省inode分配： 动态