| 技术论坛 |
|
|
| ≡技术区≡ ① |
| DELPHI技术 |
| lazarus/fpc/Free Pascal |
| 移动应用开发 |
| Web应用开发 |
| 数据库专区 |
| 报表专区 |
| 网络通讯 |
| 开源项目 |
| 论坛精华贴 |
| ≡发布区≡ ② |
| 发布代码 |
| 发布控件 |
| 文档资料 |
| 经典工具 |
| ≡事务区≡ ③ |
| 网站意见 |
| 盒子之家 |
| 招聘应聘 |
| 信息交换 |
| 论坛信息 |
|||
|
| 导航： | 论坛 -> 发布代码 斑竹:liumazi,ruralboy | |||||
| 作者： |
|
2012/7/24 22:40:11 | ||||
| 标题： |
|
加入我的收藏 | ||||
| 楼主： | 大家知道，快速排序是一种比较高效的算法，对于快速排序的一种改进，就是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 多语言组件快速让你的程序走向海外 |
|||||
| 作者： |
|
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 多语言组件快速让你的程序走向海外 |
|||||
| 作者： |
|
2012/7/24 22:55:40 | ||||
| 2楼： | 打包下载地址： http://q.weibo.com/1085250/file/155848111 ---------------------------------------------- QDAC 开源数据库访问组件欢迎大家关注讨论和使用 官网（博客):http://www.qdac.cc 讨论QQ群:250530692 QLang 多语言组件快速让你的程序走向海外 |
|||||
| 作者： |
|
2012/7/25 0:11:53 | ||||
| 3楼： | 支持lz ---------------------------------------------- - |
|||||
| 作者： |
|
2012/7/25 12:56:23 | ||||
| 4楼： | 通过搜索，这可以互联网上第一份真正的多线程实用排序代码。 ---------------------------------------------- QDAC 开源数据库访问组件欢迎大家关注讨论和使用 官网（博客):http://www.qdac.cc 讨论QQ群:250530692 QLang 多语言组件快速让你的程序走向海外 |
|||||
| 作者： |
|
2012/7/30 10:51:07 | ||||
| 5楼： | 多线程其实就是归并 ---------------------------------------------- 这家伙很懒，什么都没有留下。 |
|||||
| 作者： |
|
2012/7/30 14:50:15 | ||||
| 6楼： | 楼上的太武断了，这个并不是归并排序。Introsort算法实际上是快速排序的改进，而快速排序的分区特性，决定了它很适合多线程处理，而不需要额外的加锁。 ---------------------------------------------- QDAC 开源数据库访问组件欢迎大家关注讨论和使用 官网（博客):http://www.qdac.cc 讨论QQ群:250530692 QLang 多语言组件快速让你的程序走向海外 |
|||||
| 作者： |
|
2018/8/30 15:37:25 | ||||
| 7楼： | 好东西。。。。好好学习下 ---------------------------------------------- - |
|||||
| 作者： |
|
2018/8/30 19:43:32 | ||||
| 8楼： | 上面地址都无法下载了，哪位大侠提供下资源，感谢 ---------------------------------------------- 机器猫 |
|||||
| 作者： |
|
2018/8/30 20:53:12 | ||||
| 9楼： | http://blog.qdac.cc/?page_id=139 ---------------------------------------------- [alias] co = clone --recurse-submodules up = submodule update --init --recursiveupd = pullinfo = statusrest = reset --hard懒鬼提速  https://www.cctry.com/>http://qalculate.github.io/downloads.htmlhttps://www.cctry.com/
|
|||||
| 作者： |
|
2018/8/31 10:45:55 | ||||
| 10楼： | 要用多线程排序要看有多少个计算核心，因为线程切换有消耗 我记得有新闻，美国负责量子计算机的专家说过，5年就可以破掉比特币，一般他们都会乐观估计。假设10年，量子计算机就能投入商用，量子计算机的编程跟现在有很大不同，类似楼主这类算法和结构届时没什么价值。 建议楼主把精力放在其它地方，比如，产品、新兴技术（区块链）。 未来10年是人类社会会发生剧烈变化，10年后你们会认同我这说法的。 我估计，5年内，国内长途车司机就得失业，10年内网约车 出租车司机 快递员都得失业。 ---------------------------------------------- 软件是什么，相信很多人都说不清。 |
|||||
| 作者： |
|
2018/8/31 10:58:02 | ||||
| 11楼： | 现在的编程，我们总假设执行是按顺序的，所以有多线程概念 在量子计算机里，执行就是并发的，反而顺序是需要特别处理 很不一样 ---------------------------------------------- 软件是什么，相信很多人都说不清。 |
|||||
| 作者： |
|
2018/8/31 13:00:10 | ||||
| 12楼： | 收藏，不错的知识和技术 ---------------------------------------------- 18114532@qq.com |
|||||
| 作者： |
|
2018/9/2 8:30:53 | ||||
| 13楼： | 量子计算机供普通老百姓使用，恐怕要等20年以上吧？ 楼主的东西还是很有价值的。 ---------------------------------------------- - |
|||||
| 作者： |
|
2018/9/2 9:07:45 | ||||
| 14楼： | pwidechar pansichar ---------------------------------------------- 博客 - http://offeu.com 脚本模型 - http://webpascal.com 需要短信接口的请联系我，可发行业与营销内容。 |
|||||
| 信息 |
| 登陆以后才能回复 |
