`
qiezi
  • 浏览: 497763 次
  • 性别: Icon_minigender_1
  • 来自: 上海
社区版块
存档分类
最新评论

[D语言] qsort的尴尬

    博客分类:
  • D
阅读更多
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要低一些。
分享到:
评论
2 楼 qiezi 2007-05-13  
thunk比较麻烦,最好能实现一个通用的Thunk类,主要用于一些只接受C回调函数的地方,一个简单的Thunk就可以让它接受委托了。

使用场合一,Windows窗口回调函数:
class Window {
private:
	alias Thunk!(CallType.Windows, LRESULT, HWND, UINT, WPARAM, LPARAM) ThunkType;
	ThunkType thunk;

public:
	this() {
		thunk = ThunkType(&WndProc);
	}

	void Create(){
		WNDCLASS wc;
		// ...
		wc.lpfnWndProc = thunk.proc;
		// ..
	}

	LRESULT WndProc(HWND, UINT, WPARAM, LPARAM) {
		// now we can use *this* pointer;
		return 0;
	}
}


使用场合二,qsort:
import std.c.stdlib;

void main() {
	int cmp(void*, void*){
		// ...
		return 1;
	}

	alias Thunk!(CallType.Cdecl, int, void*, void*) ThunkType;
	ThunkType thunk = ThunkType(&cmp);

	char[][] arr = ["a", "b", "c"];
	qsort(arr.ptr, arr.length, (char[]).sizeof, thunk.proc);
}

实现它是比较困难的,它是CPU架构相关的,还依赖于调用约定,依赖于OS(D调用约定在windows和linux上有所不同)。
1 楼 qiezi 2007-05-11  
这好像是一个普遍的问题,从普通的C回调函数到委托的转换,最好的办法应该是使用thunk,不知道能不能把它做成通用的。。

相关推荐

    qsort函数具体介绍

    qsort 函数是 C 语言标准库中的一种排序算法,用于对数组进行排序。它是快速排序(Quicksort)算法的一种实现,能够高效地对数组进行排序。下面是 qsort 函数的详细介绍。 一、qsort 函数的基本用法 qsort 函数的...

    qsort使用法和具体举例说明

    qsort 是一种快速排序算法,广泛应用于 C 语言编程中。它可以对数组中的元素进行排序,包括整数、字符、浮点数、结构体等类型的元素。下面是 qsort 使用法和具体举例说明: 函数原型 void qsort(void *base, size_...

    qsort 与sort 的比较

    本文主要讨论两种内置的排序函数:`qsort()` 和 `sort()`。`qsort()` 函数来源于C标准库 `&lt;cstdlib&gt;`,而`sort()` 是C++ STL(标准模板库)中的成员,位于 `&lt;algorithm&gt;` 头文件内。 `qsort()` 函数是一种通用的...

    qsort的七种用法.txt

    qsort的七种用法

    快速排序库函数qsort的调用细则

    快速排序库函数qsort的调用细则 快速排序库函数qsort是C标准库中的一种排序算法,用于对数组进行排序。qsort函数包含在头文件中,需要在函数头部加上#include以便调用。qsort函数有四个参数,分别是参与排序的数组...

    分离出的微软qsort算法

    微软的QSort算法是针对C语言标准库中的`qsort`函数的一种优化实现。`qsort`函数在C语言中被广泛用于对数组进行快速排序,它是一个通用的排序算法,适用于各种数据类型。在微软的实现中,可能对性能进行了特定的优化...

    七种qsort排序方法

    ### 七种qsort排序方法详解 #### 一、引言 `qsort`是C语言标准库中的一个函数,用于对数组进行快速排序。它提供了极大的灵活性,允许用户自定义比较函数来处理不同类型的数据。本文将详细介绍七种常见的`qsort`排序...

    qsort的详细用法

    ### qsort函数详解与应用实例 #### 一、qsort函数概述 `qsort`是C语言中的标准库函数,用于对数组中的元素进行排序,它位于`&lt;stdlib.h&gt;`头文件中。此函数适用于各种数据类型,不仅限于基本类型如`int`或`double`,...

    七种qsort排序

    标题:七种qsort排序 描述:本文详细介绍了七种使用C语言标准库函数`qsort()`进行排序的方法,适用于不同数据类型和复杂结构的排序需求。每种方法都提供了具体的示例代码,旨在帮助读者深入理解`qsort()`函数的使用...

    C库函数qsort七种使用方法示例

    本文将对 C 库函数 qsort 进行详细的介绍,并提供七种使用方法示例,帮助 C 语言初学者快速掌握 qsort 函数的使用方法。 一、对 int 类型数组排序 qsort 函数可以对 int 类型数组进行排序,下面是一个简单的示例...

    qsort

    函数名称: qsort &lt;br&gt;函数原型: void qsort(void *base, size_t nelem, size_t width, int (*fcmp)(const void *,const void *) &lt;br&gt;函数功能: 使用C.A.R.Hoare排序法对数组base进行排序 &lt;br&gt;函数返回: ...

    qsort函数常见用法v1.1

    ### qsort函数详解及其在ACM竞赛中的应用 #### 一、qsort函数概述 `qsort`函数是C语言标准库中用于通用数组排序的一个强大工具,它使用快速排序算法,提供了高度灵活的排序机制。`qsort`的原型在`&lt;stdlib.h&gt;`...

    C语言qsort排序大全 多种数据类型的qsort

    printf("%d ", arr[i]); } return 0; } ``` 六、优化与注意事项 1. 考虑到内存和性能,`qsort`并不适合处理非常大的数据集。对于大数据,可以考虑并行排序算法或更高效的排序算法。 2. `compar`函数应尽可能...

    VC中qsort源代码

    ### VC中qsort源代码解析 #### 知识点概览 在VC(Visual C++)环境中,`qsort`函数是C/C++标准库中用于数组排序的关键函数之一,其内部实现采用了快速排序算法。本文将深入分析VC中`qsort`源代码的核心逻辑、算法...

    qsort测试,闲人勿下

    标题中的“qsort测试”指的是一个关于C++标准库中的`qsort`函数的测试程序。这个测试可能包含了对`qsort`函数不同用法的验证,以及与C++标准库中的`std::sort`以及C运行时库(CRT)中的排序函数进行的性能比较。`qsort...

    qsort 各种用法

    ### qsort函数详解与应用实例 #### 引言 `qsort`是C语言标准库中的一个强大排序函数,它提供了灵活的通用性,能够处理各种数据类型和复杂度的数据结构排序需求。`qsort`函数的核心优势在于其比较函数参数,这允许...

    C语言qsort函数算法性能测试

    C语言qsort函数算法性能测试 C语言qsort函数是一种高效的排序算法,广泛应用于各个领域。了解qsort函数的算法性能对程序设计和优化具有重要意义。本文将通过实验测试,深入探讨C语言qsort函数的算法性能,并对其...

    C语言中qsort函数用法实例小结

    C语言中的`qsort`函数是用于对内存块中的元素进行排序的标准库函数,它包含在`&lt;stdlib.h&gt;`头文件中。`qsort`函数的使用非常灵活,可以处理不同数据类型的数据,包括基本类型如`int`、`char`、`double`以及结构体等...

    C快速排序qsort

    在C语言中,`qsort`函数是标准库`stdlib.h`中提供的一种通用排序接口,用于实现快速排序或者其他类型的排序。 `qsort`函数的原型如下: ```c void qsort(void *base, size_t nel, size_t width, int (*compar)...

Global site tag (gtag.js) - Google Analytics