多线程排序-QWorker版本实现

当前处理器多核心已经成为标配,无论是手机还是PC,充分利用多核心处理资源,是程序员的职责所在。本次展示的例子,利用QWorker提供的多线程作业管理,演示了如何实现多线程排序。

要进行多线程排序,首先确定数据量是否足够大,太小的数据可能都不够线程创建和切换的开销,那就不如在单一线程中执行效率更高,毕竟线程创建和释放都会引起额外的开销。

接下来,由于是多线程排序,就牵涉到资源的争用问题。如果使用临界等锁定手段,虽然是线程安全了,但频繁的进出锁显然会造成额外的开销,对于多线程排序操作来说,是很明显不合理的选择。如果不使用锁,那么我们如果保证线程访问数据的安全呢?答案就是数据分区。

所谓的数据分区,就是通过最简单的比较算法,将数据分隔成多个不同的块,后一块的最小值要大于前一块的最大值,这样在每块排序完成后,整体自然就排序完成。

在数据分区完成后,将各块未排序的数据块直接当作作业提交给QWorker的作业管理对象Workers,然后就等待作业排序完成就好了。

算法的原理已经讲清楚了,现在我们看一下2000万个Double类型值的排序对比结果:

d8f9d72a6059252d7f348b39379b033b5bb5b9e8

5156/1546=3.34倍,性能提升应该说还算比较明显。

在这里,分区算法采用的是比较常规的冒泡比较,应该有很大的优化余地。

分享到:

3 条评论

沙发空缺中,还不快抢~