[第一讲] 快速排序算法

pasuka

为啥不考虑直接上C的代码呢？利用iso c binding 写几个interface即可

楚香饭

pasuka 发表于 2014-3-4 20:43
为啥不考虑直接上C的代码呢？利用iso c binding 写几个interface即可

做这点计算，Fortran还是足以应对的。

aliouying

pasuka 发表于 2014-3-4 20:43
为啥不考虑直接上C的代码呢？利用iso c binding 写几个interface即可

欢迎大家把自己熟悉的代码拿过来做对比，我发这个贴只是抛砖引玉
算法一样时，计算机语言、编译器、系统等不同效率可能都有差别，所以可以让感兴趣的爱好者一起来参与

pasuka

chuxf 发表于 2014-3-2 20:17
我这里找了三个快速排序算法。

楼主这个，我称为 QuickSortMod，Intel Fortran 扩展的 Qsort，以及 Juli R ...

简单测试了一下，分别调用QuickSortMod和Juli Rew 的qsort（修改为整数排序）以及gcc自带的qsort，随机整型数组的长度由10的1次方增加到10的7次方（受制于内存，未测试更大的动态数组）测试平台：

OS： Debian 7.2 32bit

CPU： ARMv6-compatible processor 700Mhz OC 1000Mhz
Memory: 437.7MB
CC： gcc-4.7
FC： gfortran-4.7
计算结果：
=========================================================================
Fortran version of Quick Sort I
Len of array:        10 Time =  0.000 seconds.
Fortran version of Quick Sort II
Len of array:        10 Time =  0.000 seconds.
Fortran call C version of qsort
Len of array:        10 Time =  0.000 seconds.
Fortran version of Quick Sort I
Len of array:       100 Time =  0.000 seconds.
Fortran version of Quick Sort II
Len of array:       100 Time =  0.000 seconds.
Fortran call C version of qsort
Len of array:       100 Time =  0.000 seconds.
Fortran version of Quick Sort I
Len of array:      1000 Time =  0.000 seconds.
Fortran version of Quick Sort II
Len of array:      1000 Time =  0.000 seconds.
Fortran call C version of qsort
Len of array:      1000 Time =  0.010 seconds.
Fortran version of Quick Sort I
Len of array:     10000 Time =  0.010 seconds.
Fortran version of Quick Sort II
Len of array:     10000 Time =  0.020 seconds.
Fortran call C version of qsort
Len of array:     10000 Time =  0.010 seconds.
Fortran version of Quick Sort I
Len of array:    100000 Time =  0.180 seconds.
Fortran version of Quick Sort II
Len of array:    100000 Time =  0.160 seconds.
Fortran call C version of qsort
Len of array:    100000 Time =  0.110 seconds.
Fortran version of Quick Sort I
Len of array:   1000000 Time =  1.500 seconds.
Fortran version of Quick Sort II
Len of array:   1000000 Time =  1.750 seconds.
Fortran call C version of qsort
Len of array:   1000000 Time =  1.370 seconds.
Fortran version of Quick Sort I
Len of array:  10000000 Time = 17.660 seconds.
Fortran version of Quick Sort II
Len of array:  10000000 Time = 20.340 seconds.
Fortran call C version of qsort
Len of array:  10000000 Time = 16.110 seconds.

*******************************************************************************************************************************
初步意见：
1、ISO_C_BINDING对于混合编程相当便捷，fortran可以方便的使用成熟的C代码；
2、大数组排序，在linux或mingw环境下直接调用qsort更具优势
********************************************************************************************************************************
主程序

[Fortran] syntaxhighlighter_viewsource syntaxhighlighter_copycode

program SortTest
use QuickSortMod
use qsort_c_module
implicit none
interface
	subroutine qsort(a,length)bind(c,name="sort_integer")
	use,intrinsic::iso_c_binding
	integer(c_int),value::length	
	integer(c_int)::a(length)
	end subroutine
end interface

integer::N,i
integer,allocatable::IntDat(:),intDat2(:),intdat3(:)
real,allocatable::dat(:)
real::start,finish
do i=1,7
	N=10**i
	if(allocated(intdat))deallocate(intdat)
	if(allocated(intdat2))deallocate(intdat2)
	if(allocated(dat))deallocate(dat)
	if(allocated(intdat3))deallocate(intdat3)
	allocate(IntDat(n),intDat2(n),dat(n),intdat3(n))
	call random_seed()
	call random_number(dat)
	intDat = int((2*Dat-1)*100)
	intdat2 = intdat
	intdat3 = intdat
	call cpu_time(start)
	call quick_sort_i(intdat)
	call cpu_time(finish)
	write(*,*)"Fortran version of Quick Sort I"
	write(*,'("Len of array:",i10," Time = ",f6.3," seconds.")')n,finish-start
	
	call cpu_time(start)
	call QsortC(intdat3)
	call cpu_time(finish)
	write(*,*)"Fortran version of Quick Sort II"
	write(*,'("Len of array:",i10," Time = ",f6.3," seconds.")')n,finish-start
	
	call cpu_time(start)
	call qsort(intdat2,n)
	call cpu_time(finish)
	write(*,*)"Fortran call C version of qsort"
	write(*,'("Len of array:",i10," Time = ",f6.3," seconds.")')n,finish-start
	deallocate(intdat,intdat2,dat,intdat3)
enddo

end program

c接口程序代码：

[C] syntaxhighlighter_viewsource syntaxhighlighter_copycode

#include <stdlib.h> 
#include <stdio.h> 
/* qsort int comparison function */ 
int int_cmp(const void *a, const void *b) 
{ 
    const int *ia = (const int *)a; // casting pointer types 
    const int *ib = (const int *)b;
    return *ia  - *ib; 
	/* integer comparison: returns negative if b > a 
	and positive if a > b */ 
} 
/* integer array printing function */ 
void print_int_array(const int *array, size_t len) 
{ 
    size_t i;
    for(i=0; i<len; i++) 
        printf("%d | ", array[i]);
    putchar('\n');
} 
void sort_integer(int *a,size_t a_len)
{
	/* print original integer array */ 
    //print_int_array(a, a_len);	
	/* sort array using qsort functions */ 
    qsort(a, a_len, sizeof(int), int_cmp);
}

aliouying

pasuka 发表于 2014-3-10 13:25
简单测试了一下，分别调用QuickSortMod和Juli Rew 的qsort（修改为整数排序）以及gcc自带的qsort，随机整 ...

从结果来看，gcc自带的qsort貌似效率最高，不知fortran的代码编译时是否优化？
但QuickSortMod和Juli Rew的QSortC跟石头测出来的效率对比图恰恰相反，是否修改时出了点问题？

pasuka

aliouying 发表于 2014-3-11 18:57
从结果来看，gcc自带的qsort貌似效率最高，不知fortran的代码编译时是否优化？
但QuickSortMod和Juli Rew ...

gcc和gfortran都是默认的优化设置，没有修改过
我只是去掉了QuickSortMod的interface，因为gfotran编译报错

pasuka

aliouying 发表于 2014-3-11 18:57
从结果来看，gcc自带的qsort貌似效率最高，不知fortran的代码编译时是否优化？
但QuickSortMod和Juli Rew ...

如果有兴趣，还可以gfortran调用gsl再测试一下

aliouying

pasuka 发表于 2014-3-11 20:26
如果有兴趣，还可以gfortran调用gsl再测试一下

我在写毕业论文，所以没多少时间，等过段时间测试下

岸边的鱼

排序是个很好的课题，方法应该有很多种，期待看到别的排序方法，都拿来比较下

山大克鲁士

快排纵然好理解，但是个人总感觉递归的效率可能不高，正如Davis将所有递归利用压栈弹栈来操作一样，虽然在汇编级递归确实也是不断的弹栈压栈过程。。。
不知诸君有何见解？