解释型程序python\java与编译型程序C在IO以及运行上的效率差异
最近特别喜欢使用python编写一些短小而且实用的程序，并且由于专业上的需求（python在科学程序上的应用非常的广泛，我们实验室的密码库基本上都是含有C封装的python模块），所以我想将python应用到更广泛的范围。但是据说python在解释上的效率相当的不理想，由此我想到了三个问题：
1.如果写一个python版的快速排序，测试一下，运行的时间有多少
2.再写一个java版本的实现，与python的运行时间进行对比，看看他们在虚拟机的效率上到底有多大差别
3.再写一个C语言的编译型程序，与python和java进行对比，看一下编译型程序与解释性程序的差距有多大，看看不论是java还是python，解释型的程序与编译型的程序在运行时间上有多大的差距
扩展的课题：
1.如果是考虑到web上的问题，那么IO效率将是一个很重要的考量方向，所以可以再将需要排序的数据通过从文件读取的方式来加载，测试3种语言的IO效率。（其实在IO的问题上，我一直不是很清楚IO的内在运行机制，不论是编译型语言，还是解释型语言，我总感觉IO的效率是操作系统相关的，是系统调用相关的，不知道哪个大神能否解释一下）
2.如果将C的快速排序作为python的扩展效果会是怎么样的？
我实现的python版本快速排序如下所示（不知道是不是最好的实现方式）：
1 ''' 2 QucikSort algorithm 3 Description:For QuickSort,there's two way to realise: 4 First, base on recursion. 5 Second, based on non-recursion 6 7 Date:2014-01-12 8 Author:DongyuanShi 9 Version:0.1 10 ''' 11 12 import time 13 14 #here,we use a list of emulate the data array. 15 #But in my opinion, list is not the most efficient 16 #way to realize. So If there's a much better way to 17 #realize a static array like C. 18 def qucikSort(datarray): 19 length=len(datarray) 20 start=0 21 end=length-1 22 qucikSortCoreNonRecursion(datarray,start,end) 23 24 25 def qucikSortCore(datarray,start,end): 26 27 if start<end: 28 mid=partition(datarray,start,end) 29 qucikSortCore(datarray,start,mid-1) 30 qucikSortCore(datarray,mid+1,end) 31 32 33 def qucikSortCoreNonRecursion(datarray,start,end): 34 35 stack=[] 36 if start<end: 37 stack.append(start) 38 stack.append(end) 39 40 while len(stack)!=0: 41 end=stack.pop() 42 start=stack.pop() 43 mid=partition(datarray,start,end) 44 if mid+1<end: 45 stack.append(mid+1) 46 stack.append(end) 47 if start<mid-1: 48 stack.append(start) 49 stack.append(mid-1) 50 51 52 53 54 55 56 def partition(datarray,start,end): 57 58 tag=datarray[end] 59 i=start-1 60 61 for j in xrange(start,end): 62 if datarray[j]<=tag: 63 i=i+1 64 temp=datarray[i] 65 datarray[i]=datarray[j] 66 datarray[j]=temp 67 i=i+1 68 temp=datarray[i] 69 datarray[i]=tag 70 datarray[end]=temp 71 72 return i 73 74 75 76 77 if __name__=='__main__': 78 79 data=[5,4,3,2,1,10,9,8,7,6] 80 data=data*100 81 82 start=time.clock() 83 qucikSort(data) 84 end=time.clock() 85 86 #print data 87 print 'runtime:',end-start 88 print data
实现的JAVA版本的排序算法如下：
import java.util.Stack;
// QucikSort algorithm
// Description:For QuickSort,there's two way to realise:
// First, base on recursion.
// Second, based on non-recursion
// Date:2014-01-26
// Author:DongyuanShi
// Version:0.1
public class quickSort
{
public void sort(int[] data){
this.qucikSortCoreNonRecursion(data,0,data.length-1);
}
private void sortCore(int[] data,int start,int end){
if (start<end){
int mid;
mid=this.partition(data,start,end);
this.sortCore(data,start,mid-1);
this.sortCore(data,mid+1,end);
}
}
private int partition(int[] data,int start,int end){
int tag;
int i,j,temp;
tag=data[end];
i=start-1;
for(j=start;j<end;j++){
if(data[j]<=tag){
i=i+1;
temp=data[i];
data[i]=data[j];
data[j]=temp;
}
}
i=i+1;
temp=data[i];
data[i]=tag;
data[end]=temp;
return i;
}
public void qucikSortCoreNonRecursion(int[] datarray,int start,int end){
Stack<Integer> stack=new Stack<Integer>();
if(start<end){
stack.push(start);
stack.push(end);
}
int mid;
while(!stack.empty()){
end=stack.pop();
start=stack.pop();
mid=this.partition(datarray,start,end);
if(mid+1<end){
stack.push(mid+1);
stack.push(end);
}
if(start<mid-1){
stack.push(start);
stack.push(mid-1);
}
}
}
public static void main(String args[]){
quickSort qs=new quickSort();
int[] data=new int[10000];
for(int i=0;i<1000;i++){
for(int j=0;j<10;j++){
data[i*10+j]=j+1;
}
}
long startTime=System.currentTimeMillis();
qs.sort(data);
long endTime=System.currentTimeMillis();
System.out.println("Time:"+startTime);
System.out.println("Time:"+endTime);
System.out.println("Time:"+(endTime-startTime));
}
}C语言版本的快速排序如下：
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include "quickSort.h"
#include "stack.h"
void initArray(int data[],int length){
int i;
int randomNum;
for(i=0;i<length;i++){
randomNum=rand()%100;
data[i]=randomNum;
}
}
void printArray(int data[],int length){
int i;
for(i=0;i<length;i++){
printf("%d,",data[i]);
}
printf("\n");
}
void quickSort(int data[],int length){
quickSortCore(data,0,length-1);
}
void quickSortCore(int data[],int start,int end)
{
int mid;
if(start<end){
mid=partition(data,start,end);
quickSortCore(data,start,mid-1);
quickSortCore(data,mid+1,end);
}
}
int partition(int data[],int start,int end)
{
int seed=data[end];
int i,j;
int mid;
i=start-1;
for(j=start;j<end;j++){
if(seed>=data[j]){
i+=1;
mid=data[i];
data[i]=data[j];
data[j]=mid;
}
}
i+=1;
mid=data[i];
data[i]=data[j];
data[j]=mid;
return i;
}
void quickSortNonRecursion(int data[],int length)
{
STACK stack;
initStack(&stack);
push(&stack,0);
push(&stack,length-1);
while(!isEmpty(&stack)){
int start,end;
int mid;
pop(&stack,&end);
pop(&stack,&start);
if(start<end){
mid=partition(data,start,end);
push(&stack,mid+1);
push(&stack,end);
push(&stack,start);
push(&stack,mid-1);
}
}
}
int main(int argc,char* argv[])
{
int data[2000];
double startTime,endTime;
initArray(data,2000);
printArray(data,2000);
startTime=(double)clock();
//quickSort(data,100);
quickSortNonRecursion(data,2000);
endTime=(double)clock();
printArray(data,2000);
printf("Time:%fms",(endTime-startTime));
}- 上一篇 »2021还不多学几种创建型模式，创建个对象！
- 下一篇 »java基础——简单工厂模式
