第16週目のプロジェクト--ビッグデータセット上のソートアルゴリズムのパフォーマンスの体験
12691 ワード
/*Copyright(c)2015、煙台大学コンピュータと制御工学学院*All rights reserved*著者:李宗政*完成日:2015年12月7日*バージョン番号:V 1.0*コンテンツの説明:
少なくとも5万件のレコードのデータセットを生成する関数を設計します.同じデータセットでは,直接挿入ソート,バブルソート,高速ソート,直接選択ソート,スタックソート,集計ソート,基数ソートなどのアルゴリズムでソートを行い,必要な時間を記録し,比較を経て複雑度の異なる各種アルゴリズムの実行時間に対する感性認識を得た.
ヒント1:このプロジェクトは多種のソートアルゴリズムを統合する必要があり、まずソートアルゴリズムライブラリを建設することを考慮することができ、私たちのこの授業のアルゴリズムライブラリの収官の作品として考えることができる.ヒント2:本プロジェクトは複雑度の異なるアルゴリズムに対する感性認識を得ることを目的とし、データ分布の特徴、コンピュータの運行状態などが異なるため、その結果はアルゴリズムの複雑度に対する理論分析に完全に代わることができない.ヒント3:C言語標準で提供される時間関数は秒までしか正確ではないため、いくつかのO(nlog 2 n)レベルのアルゴリズムは、5万件の記録の圧力の下で、優劣を明らかに見ることができず、直接挿入ソート、泡ソート、この3つの比較的非効率なアルゴリズムを直接選択します(時間を節約します.長時間の実行に耐えられるなら、勝手にしてください).データ量を10倍に増やして観察する.
*/
テスト用のマスタ関数
ヘッダファイルh
アルゴリズムのデバッグsort.cpp
演算結果:なし
y改善すべき
少なくとも5万件のレコードのデータセットを生成する関数を設計します.同じデータセットでは,直接挿入ソート,バブルソート,高速ソート,直接選択ソート,スタックソート,集計ソート,基数ソートなどのアルゴリズムでソートを行い,必要な時間を記録し,比較を経て複雑度の異なる各種アルゴリズムの実行時間に対する感性認識を得た.
ヒント1:このプロジェクトは多種のソートアルゴリズムを統合する必要があり、まずソートアルゴリズムライブラリを建設することを考慮することができ、私たちのこの授業のアルゴリズムライブラリの収官の作品として考えることができる.ヒント2:本プロジェクトは複雑度の異なるアルゴリズムに対する感性認識を得ることを目的とし、データ分布の特徴、コンピュータの運行状態などが異なるため、その結果はアルゴリズムの複雑度に対する理論分析に完全に代わることができない.ヒント3:C言語標準で提供される時間関数は秒までしか正確ではないため、いくつかのO(nlog 2 n)レベルのアルゴリズムは、5万件の記録の圧力の下で、優劣を明らかに見ることができず、直接挿入ソート、泡ソート、この3つの比較的非効率なアルゴリズムを直接選択します(時間を節約します.長時間の実行に耐えられるなら、勝手にしてください).データ量を10倍に増やして観察する.
*/
テスト用のマスタ関数
#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
#include <time.h>
#include "sort.h"
void GetLargeData(RecType *&R, int n)
{
srand(time(0));
R=(RecType*)malloc(sizeof(RecType)*n);
for(int i=0; i<n; i++)
R[i].key= rand(); // 0~RAND_MAX
printf(" %d
", n);
}
// ，
long Sort(RecType *&R, int n, void f(RecType*, int))
{
int i;
long beginTime, endTime;
RecType *R1=(RecType*)malloc(sizeof(RecType)*n);
for (i=0;i<n;i++)
R1[i]=R[i];
beginTime = time(0);
f(R1,n);
endTime = time(0);
free(R1);
return endTime-beginTime;
}
// ，
long Sort1(RecType *&R, int n)
{
long beginTime, endTime;
RadixRecType *p;
CreateLink(p,R,n);
beginTime = time(0);
RadixSort(p);
endTime = time(0);
DestoryLink(p);
return endTime-beginTime;
}
int main()
{
RecType *R;
int n = MaxSize; // , MaxSize 50W
GetLargeData(R, n);
printf(" ：
");
printf(" ：%ld
", Sort(R, n, InsertSort));
printf(" ：%ld
", Sort(R, n, ShellSort));
printf(" ：%ld
", Sort(R, n, BubbleSort));
printf(" ：%ld
", Sort(R, n, QuickSort));
printf(" ：%ld
", Sort(R, n, SelectSort));
printf(" ：%ld
", Sort(R, n, HeapSort));
printf(" ：%ld
", Sort(R, n, MergeSort));
printf(" ：%ld
", Sort1(R, n));
free(R);
return 0;
}ヘッダファイルh
#ifndef SORT_H_INCLUDED
#define SORT_H_INCLUDED
#define MaxSize 50000 // ， 5 ， ，
//
#define Radix 10 //
#define Digits 10 //
typedef int KeyType; //
typedef char InfoType[10];
typedef struct //
{
KeyType key; //
InfoType data; // , InfoType
} RecType; //
typedef struct node
{
KeyType data; // ，
struct node *next;
} RadixRecType;
void InsertSort(RecType R[],int n); //
void ShellSort(RecType R[],int n); //
void BubbleSort(RecType R[],int n); //
void QuickSort(RecType R[],int n); //
void SelectSort(RecType R[],int n); //
void HeapSort(RecType R[],int n); //
void MergeSort(RecType R[],int n); //
//
void CreateLink(RadixRecType *&p,RecType R[],int n); //
void DestoryLink(RadixRecType *&p); //
void RadixSort(RadixRecType *&p); //
#endif // SORT_H_INCLUDED
アルゴリズムのデバッグsort.cpp
#include "sort.h"
#include <malloc.h>
//1. R[0..n-1]
void InsertSort(RecType R[],int n)
{
int i,j;
RecType tmp;
for (i=1; i<n; i++)
{
tmp=R[i];
j=i-1; // R[0..i-1] R[i]
while (j>=0 && tmp.key<R[j].key)
{
R[j+1]=R[j]; // R[i].key
j--;
}
R[j+1]=tmp; // j+1 R[i]
}
}
//2.
void ShellSort(RecType R[],int n)
{
int i,j,gap;
RecType tmp;
gap=n/2; //
while (gap>0)
{
for (i=gap; i<n; i++) // gap
{
tmp=R[i];
j=i-gap;
while (j>=0 && tmp.key<R[j].key)// gap
{
R[j+gap]=R[j];
j=j-gap;
}
R[j+gap]=tmp;
j=j-gap;
}
gap=gap/2; //
}
}
//3.
void BubbleSort(RecType R[],int n)
{
int i,j,exchange;
RecType tmp;
for (i=0; i<n-1; i++)
{
exchange=0;
for (j=n-1; j>i; j--) // ,
if (R[j].key<R[j-1].key)
{
tmp=R[j]; //R[j] R[j-1] ,
R[j]=R[j-1];
R[j-1]=tmp;
exchange=1;
}
if (exchange==0) // ，
return;
}
}
//4. R[s] R[t]
void QuickSortR(RecType R[],int s,int t)
{
int i=s,j=t;
RecType tmp;
if (s<t) //
{
tmp=R[s]; // 1
while (i!=j) // , i=j
{
while (j>i && R[j].key>=tmp.key)
j--; // , 1 tmp.key R[j]
R[i]=R[j]; // R[j],R[i]"R[j]
while (i<j && R[i].key<=tmp.key)
i++; // , 1 tmp.key R[i]
R[j]=R[i]; // R[i],R[i]"R[j]
}
R[i]=tmp;
QuickSortR(R,s,i-1); //
QuickSortR(R,i+1,t); //
}
}
//4. ， ，
void QuickSort(RecType R[],int n)
{
QuickSortR(R, 0, n-1);
}
//5.
void SelectSort(RecType R[],int n)
{
int i,j,k;
RecType temp;
for (i=0; i<n-1; i++) // i
{
k=i;
for (j=i+1; j<n; j++) // R[i..n-1] key R[k]
if (R[j].key<R[k].key)
k=j; //k
if (k!=i) // R[i] R[k]
{
temp=R[i];
R[i]=R[k];
R[k]=temp;
}
}
}
//6. ——
void sift(RecType R[],int low,int high)
{
int i=low,j=2*i; //R[j] R[i]
RecType temp=R[i];
while (j<=high)
{
if (j<high && R[j].key<R[j+1].key) // , j
j++; // 2i+1
if (temp.key<R[j].key)
{
R[i]=R[j]; // R[j]
i=j; // i j ,
j=2*i;
}
else break; //
}
R[i]=temp; //
}
//6.
void HeapSort(RecType R[],int n)
{
int i;
RecType temp;
for (i=n/2; i>=1; i--) //
sift(R,i,n);
for (i=n; i>=2; i--) // n-1 ,
{
temp=R[1]; // R[1]
R[1]=R[i];
R[i]=temp;
sift(R,1,i-1); // R[1] , i-1
}
}
//7. 1——
void Merge(RecType R[],int low,int mid,int high)
{
RecType *R1;
int i=low,j=mid+1,k=0; //k R1 ,i、j 1、2
R1=(RecType *)malloc((high-low+1)*sizeof(RecType)); //
while (i<=mid && j<=high) // 1 2
if (R[i].key<=R[j].key) // 1 R1
{
R1[k]=R[i];
i++;
k++;
}
else // 2 R1
{
R1[k]=R[j];
j++;
k++;
}
while (i<=mid) // 1 R1
{
R1[k]=R[i];
i++;
k++;
}
while (j<=high) // 2 R1
{
R1[k]=R[j];
j++;
k++;
}
for (k=0,i=low; i<=high; k++,i++) // R1 R
R[i]=R1[k];
}
//7. 2——
void MergePass(RecType R[],int length,int n) //
{
int i;
for (i=0; i+2*length-1<n; i=i+2*length) // length
Merge(R,i,i+length-1,i+2*length-1);
if (i+length-1<n) // , length
Merge(R,i,i+length-1,n-1); //
}
//7.
void MergeSort(RecType R[],int n) //
{
int length;
for (length=1; length<n; length=2*length) // log2n
MergePass(R,length,n);
}
// ，
//8. ，
void CreateLink(RadixRecType *&p,RecType R[],int n) //
{
int i;
RadixRecType *s,*t;
for (i=0; i<n; i++)
{
s=(RadixRecType *)malloc(sizeof(RadixRecType));
s->data = R[i].key;
if (i==0)
{
p=s;
t=s;
}
else
{
t->next=s;
t=s;
}
}
t->next=NULL;
}
//8. ，
void DestoryLink(RadixRecType *&p)
{
RadixRecType *q;
while(p!=NULL)
{
q=p->next;
free(p);
p=q;
}
return;
}
//8. :*p , R D
void RadixSort(RadixRecType *&p)
{
RadixRecType *head[Radix],*tail[Radix],*t; //
int i,j,k;
unsigned int d1, d2=1; // i ，
for (i=1; i<=Digits; i++) //
{
// i ， d1=10^i ， i ， d2=10^(i-1) i
// ， 1 ， ， d1=10 ， d2=1
// ， 2 ， ， d1=100 ， d2=10
// ，d2 1， 10
// d2， d1
d1=d2*10;
for (j=0; j<Radix; j++) // 、
head[j]=tail[j]=NULL;
while (p!=NULL) //
{
k=(p->data%d1)/d2; // i k
if (head[k]==NULL) //
{
head[k]=p;
tail[k]=p;
}
else
{
tail[k]->next=p;
tail[k]=p;
}
p=p->next; //
}
p=NULL; // p
for (j=0; j<Radix; j++) //
if (head[j]!=NULL) //
{
if (p==NULL)
{
p=head[j];
t=tail[j];
}
else
{
t->next=head[j];
t=tail[j];
}
}
t->next=NULL; // next NULL
// i d2
d2*=10;
}
}
演算結果:なし
y改善すべき