phobos里面在stc.c.stdlib里提供了qsort,这是个传统的qsort:
void qsort(void *base, size_t nelems, size_t elemsize,
int (*compare)(void *elem1, void *elem2));
它接受的比较函数是个函数指针,如果我们想使用委托就比较麻烦了,委托是对象指针和函数指针的绑定。
phobos/internal/qsort2.d里实现了一个数组排序方法:
extern (C) long _adSort(Array a, TypeInfo ti)
{
synchronized
{
tiglobal = ti;
std.c.stdlib.qsort(a.ptr, a.length, cast(size_t)ti.tsize(), &cmp);
}
return *cast(long*)(&a);
}
当调用array.sort时就会使用它。它使用了一个全局变量,在比较函数里调用这个全局变量,所以能够知道是哪个ClassInfo对象,间接完成了委托功能。由于使用了全局变量,为了防止多个线程同时修改使用tiglobal,它增加了synchronized区块,代价是多个线程对多个数组排序将是顺序执行的。
当然可以避免使用这种临界区,或者是避免长时间锁住,有两种方法。
方法1是在_adSort里锁住临界区,赋值然后调用qsort,在qsort里复制全局的tiglobal以函数执行栈上,然后释放临界区,可以提高效率,也就是避免长时间锁住。带来的问题是qsort变成一个“不干净”的版本,它脏了,而且效率也比较低,临界区的开销不小。如果这样还不如给qsort和它的排序函数加一个参数呢:
void qsort(void *base, size_t nelems, size_t elemsize,
int (*compare)(void *elem1, void *elem2, void* arg), void* arg);
稍干净点,一样难看。
方法2是使用线程专有存储(TSS),我在phobos里面没有看到它使用,所以也比较麻烦,因为需要初始化和释放,修改Thread类?感觉不好。
搜索到一个帖子:
http://www.digitalmars.com/d/archives/137.html
看上去很美,不过没有实现亚,真是麻烦。。自己写线程类吧。。就为了这个接受委托的qsort。。。好像还是重写个qsort更简单一些。
phobos/internal/qsort.d提供了数组排序的不加锁版本,不过是专用的。
以上是打算调用std.c.stdlib.qsort来编写使用委托参数的qsort时遇到的麻烦。感觉还是写一个比较简单:
void qsort(T)(T* arr, size_t n, int delegate(T,T) dg) {
if (!n) return;
int i=0, k=n-1;
T t = arr[k>>1];
do {
while(dg(arr[i], t) < 0)
i++;
while(dg(t, arr[k]) < 0)
k--;
if (i>k)
break;
if (i!= k) {
T tmp = arr[i];
arr[i] = arr[k];
arr[k] = tmp;
}
k--;
i++;
}while(i<=k);
if (i<n)
qsort!(T)(arr+i, n-i, dg);
if (k)
qsort!(T)(arr, k+1, dg);
}
import std.stdio;
import std.perf;
void main() {
int cmp(int a, int b) {
return a - b;
}
PerformanceCounter counter = new PerformanceCounter;
counter.start();
for(int i=0; i<1000000; ++i) {
int[] arr = [5,2,4,1,3,8,5,9,7];
qsort(arr.ptr, arr.length, &cmp);
}
counter.stop();
writefln(counter.periodCount());
counter.start();
for(int i=0; i<1000000; ++i) {
int[] arr = [5,2,4,1,3,8,5,9,7];
arr.sort;
}
counter.stop();
writefln(counter.periodCount());
}
由于没有优化,所以效率比array.sort要低一些。
分享到:
相关推荐
qsort 函数是 C 语言标准库中的一种排序算法,用于对数组进行排序。它是快速排序(Quicksort)算法的一种实现,能够高效地对数组进行排序。下面是 qsort 函数的详细介绍。 一、qsort 函数的基本用法 qsort 函数的...
qsort 是一种快速排序算法,广泛应用于 C 语言编程中。它可以对数组中的元素进行排序,包括整数、字符、浮点数、结构体等类型的元素。下面是 qsort 使用法和具体举例说明: 函数原型 void qsort(void *base, size_...
本文主要讨论两种内置的排序函数:`qsort()` 和 `sort()`。`qsort()` 函数来源于C标准库 `<cstdlib>`,而`sort()` 是C++ STL(标准模板库)中的成员,位于 `<algorithm>` 头文件内。 `qsort()` 函数是一种通用的...
qsort的七种用法
快速排序库函数qsort的调用细则 快速排序库函数qsort是C标准库中的一种排序算法,用于对数组进行排序。qsort函数包含在头文件中,需要在函数头部加上#include以便调用。qsort函数有四个参数,分别是参与排序的数组...
微软的QSort算法是针对C语言标准库中的`qsort`函数的一种优化实现。`qsort`函数在C语言中被广泛用于对数组进行快速排序,它是一个通用的排序算法,适用于各种数据类型。在微软的实现中,可能对性能进行了特定的优化...
### 七种qsort排序方法详解 #### 一、引言 `qsort`是C语言标准库中的一个函数,用于对数组进行快速排序。它提供了极大的灵活性,允许用户自定义比较函数来处理不同类型的数据。本文将详细介绍七种常见的`qsort`排序...
### qsort函数详解与应用实例 #### 一、qsort函数概述 `qsort`是C语言中的标准库函数,用于对数组中的元素进行排序,它位于`<stdlib.h>`头文件中。此函数适用于各种数据类型,不仅限于基本类型如`int`或`double`,...
标题:七种qsort排序 描述:本文详细介绍了七种使用C语言标准库函数`qsort()`进行排序的方法,适用于不同数据类型和复杂结构的排序需求。每种方法都提供了具体的示例代码,旨在帮助读者深入理解`qsort()`函数的使用...
本文将对 C 库函数 qsort 进行详细的介绍,并提供七种使用方法示例,帮助 C 语言初学者快速掌握 qsort 函数的使用方法。 一、对 int 类型数组排序 qsort 函数可以对 int 类型数组进行排序,下面是一个简单的示例...
函数名称: qsort <br>函数原型: void qsort(void *base, size_t nelem, size_t width, int (*fcmp)(const void *,const void *) <br>函数功能: 使用C.A.R.Hoare排序法对数组base进行排序 <br>函数返回: ...
### qsort函数详解及其在ACM竞赛中的应用 #### 一、qsort函数概述 `qsort`函数是C语言标准库中用于通用数组排序的一个强大工具,它使用快速排序算法,提供了高度灵活的排序机制。`qsort`的原型在`<stdlib.h>`...
printf("%d ", arr[i]); } return 0; } ``` 六、优化与注意事项 1. 考虑到内存和性能,`qsort`并不适合处理非常大的数据集。对于大数据,可以考虑并行排序算法或更高效的排序算法。 2. `compar`函数应尽可能...
### VC中qsort源代码解析 #### 知识点概览 在VC(Visual C++)环境中,`qsort`函数是C/C++标准库中用于数组排序的关键函数之一,其内部实现采用了快速排序算法。本文将深入分析VC中`qsort`源代码的核心逻辑、算法...
标题中的“qsort测试”指的是一个关于C++标准库中的`qsort`函数的测试程序。这个测试可能包含了对`qsort`函数不同用法的验证,以及与C++标准库中的`std::sort`以及C运行时库(CRT)中的排序函数进行的性能比较。`qsort...
### qsort函数详解与应用实例 #### 引言 `qsort`是C语言标准库中的一个强大排序函数,它提供了灵活的通用性,能够处理各种数据类型和复杂度的数据结构排序需求。`qsort`函数的核心优势在于其比较函数参数,这允许...
C语言qsort函数算法性能测试 C语言qsort函数是一种高效的排序算法,广泛应用于各个领域。了解qsort函数的算法性能对程序设计和优化具有重要意义。本文将通过实验测试,深入探讨C语言qsort函数的算法性能,并对其...
C语言中的`qsort`函数是用于对内存块中的元素进行排序的标准库函数,它包含在`<stdlib.h>`头文件中。`qsort`函数的使用非常灵活,可以处理不同数据类型的数据,包括基本类型如`int`、`char`、`double`以及结构体等...
在C语言中,`qsort`函数是标准库`stdlib.h`中提供的一种通用排序接口,用于实现快速排序或者其他类型的排序。 `qsort`函数的原型如下: ```c void qsort(void *base, size_t nel, size_t width, int (*compar)...