DELPHI盒子
!实时搜索: 盒子论坛 | 注册用户 | 修改信息 | 退出
检举帖 | 全文检索 | 关闭广告 | 捐赠
技术论坛
 用户名
 密  码
自动登陆(30天有效)
忘了密码
≡技术区≡
DELPHI技术
移动应用开发
Web应用开发
数据库专区
报表专区
网络通讯
开源项目
论坛精华贴
≡发布区≡
发布代码
发布控件
文档资料
经典工具
≡事务区≡
网站意见
盒子之家
招聘应聘
信息交换
论坛信息
最新加入: runx1680
今日帖子: 27
在线用户: 13
导航: 论坛 -> 发布代码 斑竹:liumazi,ruralboy  
作者:
男 chineseswish (swish) ▲▲▲▲▲ -
普通会员
2012/7/24 22:40:11
标题:
Delphi多线程排序代码-来自QDAC 开源项目 浏览:2153
加入我的收藏
楼主: 大家知道,快速排序是一种比较高效的算法,对于快速排序的一种改进,就是IntroSort算法。维基关于Introsort的说明:
    Introsort (或称为内省排序)是由David Musser在1997年设计的排序算法。这个排序算法首先从快速排序开始,当递归深度超过一定深度(深度为排序元素数量的对数值)后转为堆排序。采用这个方法,Introsort既能在常规数据集上实现快速排序的高性能,又能在最坏情况下仍保持 O(N log N) 的时间复杂度。由于这两种算法都属于比较排序算法,所以Introsort也是一个比较排序算法。

QDAC项目实现了IntroSort算法,并实现了其多线程版本,在I7 2630的联想Y470上,对一个2000万的随机整数列表排序,对比结果如下(时间单位为毫秒):

测试次数 普通排序 多线程排序 速度比
 1       4899    1731      281%
 2       4976    1935      257%
 3       4945    1716      288%
 4       4961    1779      279%
 5       4945    1794      276%
平均     4945    1791      276%

性能相对单线程,可以看到明显的提高。

源码包含threadsort和mmdsworkers两个单元。

threadsort单元下载:

https://sourceforge.net/p/qdac/code/ci/9cc21bf439c943cc0b6934aee034204b959f79d1/tree/Common/threadsort.pas?format=raw

mmdsworkers单元下载:

https://sourceforge.net/p/qdac/code/ci/9cc21bf439c943cc0b6934aee034204b959f79d1/tree/Common/mmdsworkers.pas?format=raw

其中,threadsort单元依赖于mmdsworkers,如果不想要多线程支持,将QueueIntroSort函数中相应的代码注释掉即可。
----------------------------------------------
QDAC 开源数据库访问组件欢迎大家关注讨论和使用 官网(博客):http://www.qdac.cc ;讨论QQ群:250530692 QLang 多语言组件快速让你的程序走向海外
作者:
男 chineseswish (swish) ▲▲▲▲▲ -
普通会员
2012/7/24 22:44:40
1楼: 调用其排序很简单,示例代码如下:

const TestSize=20000000;

{提供一个比较函数来比较大小,实际只需要比较<小可以,其它返回非<0的值即可}
function DoPointerComapre(I1,I2:Pointer):Integer;
begin
if Integer(I1)<Integer(I2) then
  Result:=-1
else if Integer(I1)>Integer(I2) then
  Result:=1
else
  Result:=0;
end;

procedure TForm6.Button1Click(Sender: TObject);
var
  AItems,ACopy:TList;
  I,V:Integer;
  T1,T2:DWORD;
begin
AItems:=TList.Create;
ACopy:=TList.Create;
try
  Randomize;
  for I := 0 to TestSize - 1 do
    begin
    V:=Random(100);
    AItems.Add(Pointer(V));
    end;
  ACopy.Assign(AItems);
  T1:=GetTickCount;
  SortInThreads(AItems,DoPointerCompare,false);//使用主线程排序
  T1:=GetTickCount-T1;
  T2:=GetTickCount;
  SortInThreads(AItems,DoPointerCompare,false);//使用多线程排序
  T2:=GetTickCount-T2;
  Caption:='Single Threads:'+IntToStr(T1)+',MultiThreads:'+IntToStr(T2);
finally
  AItems.Free;
  ACopy.Free;
end;
end;
----------------------------------------------
QDAC 开源数据库访问组件欢迎大家关注讨论和使用 官网(博客):http://www.qdac.cc ;讨论QQ群:250530692 QLang 多语言组件快速让你的程序走向海外
作者:
男 chineseswish (swish) ▲▲▲▲▲ -
普通会员
2012/7/24 22:55:40
2楼: 打包下载地址:
http://q.weibo.com/1085250/file/155848111
----------------------------------------------
QDAC 开源数据库访问组件欢迎大家关注讨论和使用 官网(博客):http://www.qdac.cc ;讨论QQ群:250530692 QLang 多语言组件快速让你的程序走向海外
作者:
男 xaxingyun (千叶) ▲▲▲▲▲ -
普通会员
2012/7/25 0:11:53
3楼: 支持lz
----------------------------------------------
-
作者:
男 chineseswish (swish) ▲▲▲▲▲ -
普通会员
2012/7/25 12:56:23
4楼: 通过搜索,这可以互联网上第一份真正的多线程实用排序代码。
----------------------------------------------
QDAC 开源数据库访问组件欢迎大家关注讨论和使用 官网(博客):http://www.qdac.cc ;讨论QQ群:250530692 QLang 多语言组件快速让你的程序走向海外
作者:
男 forjoylee (天地无缘) ▲▲▲▲▲ -
普通会员
2012/7/30 10:51:07
5楼: 多线程其实就是归并
----------------------------------------------
这家伙很懒,什么都没有留下。
作者:
男 chineseswish (swish) ▲▲▲▲▲ -
普通会员
2012/7/30 14:50:15
6楼: 楼上的太武断了,这个并不是归并排序。Introsort算法实际上是快速排序的改进,而快速排序的分区特性,决定了它很适合多线程处理,而不需要额外的加锁。
----------------------------------------------
QDAC 开源数据库访问组件欢迎大家关注讨论和使用 官网(博客):http://www.qdac.cc ;讨论QQ群:250530692 QLang 多语言组件快速让你的程序走向海外
作者:
男 roguebear (旺财) ▲▲▲▲△ -
注册会员
2018/8/30 15:37:25
7楼: 好东西。。。。好好学习下
----------------------------------------------
-
作者:
男 machcat (机器猫) ★☆☆☆☆ -
盒子活跃会员
2018/8/30 19:43:32
8楼: 上面地址都无法下载了,哪位大侠提供下资源,感谢
----------------------------------------------
机器猫
作者:
男 keymark (keymark) ▲△△△△ -
注册会员
2018/8/30 20:53:12
9楼: http://blog.qdac.cc/?page_id=139
----------------------------------------------
m3u8播放器:DPlayer/hlsjs-p2p-engine/ckplayer/flashls-dev/sewise-player/http不能播https某些情况下dns服务:coredns/http服务:miniweb/!http://www.lib4dev.com/topics/delphi>http://www.lib4dev.com/topics/pascal?p=34&s=!http://www.lib4dev.com/topics/delphi
作者:
男 hawke2e (hawke2e) ▲▲▲▲△ -
注册会员
2018/8/31 10:45:55
10楼: 要用多线程排序要看有多少个计算核心,因为线程切换有消耗

我记得有新闻,美国负责量子计算机的专家说过,5年就可以破掉比特币,一般他们都会乐观估计。假设10年,量子计算机就能投入商用,量子计算机的编程跟现在有很大不同,类似楼主这类算法和结构届时没什么价值。
建议楼主把精力放在其它地方,比如,产品、新兴技术(区块链)。

未来10年是人类社会会发生剧烈变化,10年后你们会认同我这说法的。
我估计,5年内,国内长途车司机就得失业,10年内网约车 出租车司机 快递员都得失业。
----------------------------------------------
软件是什么,相信很多人都说不清。
作者:
男 hawke2e (hawke2e) ▲▲▲▲△ -
注册会员
2018/8/31 10:58:02
11楼: 现在的编程,我们总假设执行是按顺序的,所以有多线程概念
在量子计算机里,执行就是并发的,反而顺序是需要特别处理
很不一样
----------------------------------------------
软件是什么,相信很多人都说不清。
作者:
男 abcjingtong (jingtong) ▲▲▲▲△ -
注册会员
2018/8/31 13:00:10
12楼: 收藏,不错的知识和技术
----------------------------------------------
18114532@qq.com
作者:
男 kylix2008 (kylix2008) ★☆☆☆☆ -
普通会员
2018/9/2 8:30:53
13楼: 量子计算机供普通老百姓使用,恐怕要等20年以上吧?
楼主的东西还是很有价值的。
----------------------------------------------
-
作者:
男 star5 (星五) ★☆☆☆☆ -
盒子活跃会员
2018/9/2 9:07:45
14楼: pwidechar pansichar
----------------------------------------------
博客 - http://offeu.com
脚本模型 - http://webpascal.com
信息
登陆以后才能回复
Copyright © 2CCC.Com 盒子论坛 v2.1 版权所有 页面执行46.875毫秒 RSS