Fortran Coder

楼主: aliouying

[通用算法] [第一讲] 快速排序算法

[复制链接]

443

帖子

2

主题

0

精华

大宗师

F 币
2977 元
贡献
1772 点

水王勋章元老勋章热心勋章

发表于 2014-3-4 20:43:08 | 显示全部楼层
为啥不考虑直接上C的代码呢?利用iso c binding 写几个interface即可
回复 支持 反对

使用道具 举报

604

帖子

4

主题

0

精华

大师

农村外出务工人员

F 币
266 元
贡献
130 点

新人勋章爱心勋章水王勋章元老勋章

发表于 2014-3-4 21:03:15 | 显示全部楼层
pasuka 发表于 2014-3-4 20:43
为啥不考虑直接上C的代码呢?利用iso c binding 写几个interface即可

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

136

帖子

3

主题

0

精华

版主

F 币
1299 元
贡献
1015 点

帅哥勋章管理勋章爱心勋章新人勋章热心勋章元老勋章

 楼主| 发表于 2014-3-4 23:26:06 | 显示全部楼层
pasuka 发表于 2014-3-4 20:43
为啥不考虑直接上C的代码呢?利用iso c binding 写几个interface即可

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

443

帖子

2

主题

0

精华

大宗师

F 币
2977 元
贡献
1772 点

水王勋章元老勋章热心勋章

发表于 2014-3-10 13:25:18 | 显示全部楼层
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] 纯文本查看 复制代码
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] 纯文本查看 复制代码
#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);
}





136

帖子

3

主题

0

精华

版主

F 币
1299 元
贡献
1015 点

帅哥勋章管理勋章爱心勋章新人勋章热心勋章元老勋章

 楼主| 发表于 2014-3-11 18:57:47 | 显示全部楼层
pasuka 发表于 2014-3-10 13:25
简单测试了一下,分别调用QuickSortMod和Juli Rew 的qsort(修改为整数排序)以及gcc自带的qsort,随机整 ...

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

443

帖子

2

主题

0

精华

大宗师

F 币
2977 元
贡献
1772 点

水王勋章元老勋章热心勋章

发表于 2014-3-11 20:25:52 | 显示全部楼层
aliouying 发表于 2014-3-11 18:57
从结果来看,gcc自带的qsort貌似效率最高,不知fortran的代码编译时是否优化?
但QuickSortMod和Juli Rew ...

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

443

帖子

2

主题

0

精华

大宗师

F 币
2977 元
贡献
1772 点

水王勋章元老勋章热心勋章

发表于 2014-3-11 20:26:30 | 显示全部楼层
aliouying 发表于 2014-3-11 18:57
从结果来看,gcc自带的qsort貌似效率最高,不知fortran的代码编译时是否优化?
但QuickSortMod和Juli Rew ...

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

136

帖子

3

主题

0

精华

版主

F 币
1299 元
贡献
1015 点

帅哥勋章管理勋章爱心勋章新人勋章热心勋章元老勋章

 楼主| 发表于 2014-3-12 16:58:31 | 显示全部楼层
pasuka 发表于 2014-3-11 20:26
如果有兴趣,还可以gfortran调用gsl再测试一下

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

66

帖子

5

主题

2

精华

版主

院士级水师

F 币
481 元
贡献
273 点

管理勋章帅哥勋章爱心勋章规矩勋章

QQ
发表于 2014-4-11 22:29:26 | 显示全部楼层
排序是个很好的课题,方法应该有很多种,期待看到别的排序方法,都拿来比较下
科研穷三代,读博毁一生

18

帖子

3

主题

0

精华

熟手

F 币
116 元
贡献
73 点
发表于 2014-5-26 14:02:13 | 显示全部楼层
快排纵然好理解,但是个人总感觉递归的效率可能不高,正如Davis将所有递归利用压栈弹栈来操作一样,虽然在汇编级递归确实也是不断的弹栈压栈过程。。。
不知诸君有何见解?
您需要登录后才可以回帖 登录 | 极速注册

本版积分规则

QQ|捐赠本站|Archiver|关于我们 About Us|群聊|Fcode

GMT+8, 2018-7-21 00:38

Powered by Discuz! X3.2

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表