StupidBeauty
??Read times:83????Posted at:Mon Sep 11 05:40:37 2017?? - no title specified

并行QT算法,利用QT的并行计算框架将各种常用算法并行化

内容目录

1 快速下载

2 变更记录

2.1 2017.9.8

3 概述

4 DO IT!

4.1 下载/安装

4.2 使用

4.2.1 RangeSortSearch

5 示例程序代码

5.1 QT中标准的快速排序

5.1.1 下载

5.1.2 在线查看代码

5.1.3 输出结果

5.2 RangeSortSearch

5.2.1 下载

5.2.2 在线查看代码

5.2.3 输出结果

1 快速下载

击此处快速下载源代码压缩包:

https://bitbucket.org/hxcan/parallizedqalgorithms/downloads/ParallizedAlgorithms-1546.tar.gz

2 变更记录

2.1 2017.9.8

1546版本,是第一个版本,包含以下重磅变更:

  1. 1.实现算法:RangeSortSearch,用途是,从海量数据中搜索,找出按照某个比较规则,排在前面的若干个数据元素,确保所返回结果中的元素一定是排在前面的若干个元素,但不保证这个结果元素序列本身是有序排列的。例如,某个用于缓存的目录树下一共有1000000个文件,妳想找出其中最后修改时间最早的1000个文件,并将它们删除,在这种情况下,妳并不关心所找出的这1000个文件是否是有序排序的,只关心这1000个文件是1000000个文件中修改时间最早的1000个,那么,使用这个算法正合适。在不使用本算法的情况下,一般的做法是,将1000000个文件使用快速排序来完整地排序一次,再取出其中的前1000个元素。

3

本项目的出发点,就是,利用QT的并行计算框架,将那些常用的算法改写成并发版本,以便充分利用现代多核处理器的并发能力,加速算法的执行过程。

目前仅实现一个算法:RangeSortSearch,在一个巨大数据集中,寻找那些按照某个规则来看的话名列前茅的若干个元素,适合的场景是用于清理较旧的缓存文件。

4 DO IT!

下面说说肿么使用吧。

4.1 下载/安装

访问此网址以下载源代码压缩包:

https://bitbucket.org/hxcan/parallizedqalgorithms/downloads/ParallizedAlgorithms-1546.tar.gz

或者扫描以下二维码,再传送到电脑:

下载完毕之后,将得到一个名为“ParallizedAlgorithms-1546.tar.gz”的gz压缩包,将其解压之后,得到一个名为“ParallizedAlgorithms-1546”的目录。

进入个目录,执行以下命令行命令即可编译安装完成:

qmake-qt5

gmake

gmake install

4.2 使用

4.2.1 RangeSortSearch

在妳的QT项目中,要使用本算法的地方,做以下事情:

  1. 1. 声明一个RangeSortSearch<T>对象,例如名为 rangeSortSearch

  2. 2. 准备好要在其中做搜索的数据集,以QList<T>的形式表示,例如名为 FilesQueue

  3. 3. 并准备好用于对每两个元素进行比较的比较器对象,这个比较器对象应当派生自 PaComparator<QString>,例如名为fileTimeComparator

  4. 4.连接 rangeSortSearch的信号代理的finished信号,当整个搜索完成之后,对应的信号槽会被调用,例如这个信号槽函数名为startDelete;

  5. 5.调用rangeSortSearch的startSearch方法,并传入相应的参数,参数包括:数据集、比较器、要搜索的目标元素个数;

  6. 6.在之前连接的信号槽函数中,调用rangeSortSearch的getResult()方法即可获取到搜索结果,它也是一个QList<T>,

  7. 7.之后,对这个搜索结果列表做妳想做的事。

具体代码,参考下文中的示例程序代码。

5 示例程序代码

在本个示例程序中,会从 100000000 个整数中寻找出最小的 600 个,会分别使用QT中标准的快速排序和本算法中的RangeSortSearch来完成这一任务,并比较两种方式所用的时间。

5.1 QT中标准的快速排序

5.1.1 下载

https://bitbucket.org/hxcan/parallizedqalgorithms/downloads/QuickSortInt.tar.gz

5.1.2 在线查看代码

QuickSortInt.pro

代码内容:

TARGET = QuickSortInt

TEMPLATE = app

SOURCES += \

    main.cpp

main.cpp

代码内容:

#include <QList> //QList

#include <iostream> //cout

#include <QTime> //QTime

using namespace std; //cout

int main(int argc, char *argv[])

{

Q_UNUSED(argc);

Q_UNUSED(argv);

QList<int> intList;

    cout << __FILE__ << ", " << __LINE__ << ", " << __func__ << ", generating integers" << endl; //Debug.

for(auto intCounter=0;intCounter<100000000;intCounter++)

    {

int currentRandomNumber=qrand() % 1000000000;

        intList << currentRandomNumber;

    } //for(auto intCounter=0;intCounter<100;intCounter++)

    cout << endl << __FILE__ << ", " << __LINE__ << ", " << __func__ << ", finished generating integers" << endl; //Debug.

    cout << endl << __FILE__ << ", " << __LINE__ << ", " << __func__ << ", start search, time: " << QTime::currentTime ().toString ().toStdString () << endl; //Debug.

QTime timing;

    timing.start(); //开始计时。

qSort(intList); //快速排序。

QList<int> result=intList.mid (0,600); //获取结果。

    cout << endl << __FILE__ << ", " << __LINE__ << ", " << __func__ << ", finished search, time: " << QTime::currentTime ().toString ().toStdString () << endl; //Debug.

    cout << endl << __FILE__ << ", " << __LINE__ << ", " << __func__ << ", finished search, elapsed time: " << timing.elapsed() << "ms" << endl; //Debug.

    cout << __FILE__ << ", " << __LINE__ << ", " << __func__ << ", got result: " << endl; //Debug.

for(int currentValue:result)

    {

        cout << currentValue << ", ";

    } //for(int currentValue:result)

    cout << endl << __FILE__ << ", " << __LINE__ << ", " << __func__ << ", result over" << endl; //Debug.

return 0;

}

5.1.3 输出结果

Debugging starts

&"warning: GDB: Failed to set controlling terminal: \345\257\271\350\256\276\345\244\207\344\270\215\351\200\202\345\275\223\347\232\204 ioctl \346\223\215\344\275\234\n"

../QuickSortInt/main.cpp, 14, main, generating integers

../QuickSortInt/main.cpp, 23, main, finished generating integers

../QuickSortInt/main.cpp, 25, main, start search, time: 12:59:41

../QuickSortInt/main.cpp, 34, main, finished search, time: 13:00:51

../QuickSortInt/main.cpp, 36, main, finished search, elapsed time: 70394ms

../QuickSortInt/main.cpp, 38, main, got result:

1, 7, 13, 17, 21, 28, 33, 60, 62, 66, 70, 77, 89, 109, 111, 115, 119, 131, 138, 148, 158, 159, 168, 170, 175, 187, 197, 197, 207, 208, 219, 229, 236, 236, 239, 246, 246, 256, 257, 263, 266, 273, 285, 288, 295, 306, 315, 322, 327, 334, 337, 344, 344, 355, 364, 367, 371, 376, 383, 393, 393, 404, 413, 420, 442, 446, 453, 465, 469, 491, 495, 502, 514, 522, 524, 541, 544, 550, 551, 571, 573, 577, 589, 593, 599, 600, 612, 620, 622, 626, 638, 642, 648, 649, 659, 661, 669, 671, 681, 687, 691, 697, 698, 702, 708, 710, 718, 720, 730, 731, 736, 740, 746, 751, 757, 759, 780, 789, 795, 800, 806, 808, 818, 828, 838, 844, 849, 855, 857, 865, 877, 878, 887, 906, 926, 927, 942, 953, 966, 975, 976, 988, 991, 1002, 1004, 1014, 1015, 1024, 1034, 1035, 1040, 1044, 1055, 1062, 1066, 1073, 1083, 1084, 1093, 1094, 1100, 1111, 1112, 1122, 1122, 1133, 1142, 1143, 1149, 1160, 1163, 1171, 1171, 1181, 1182, 1209, 1210, 1212, 1220, 1220, 1231, 1240, 1251, 1258, 1261, 1269, 1269, 1280, 1296, 1300, 1307, 1317, 1318, 1329, 1338, 1341, 1345, 1349, 1371, 1378, 1398, 1400, 1415, 1420, 1427, 1427, 1438, 1447, 1449, 1459, 1476, 1487, 1496, 1498, 1503, 1508, 1518, 1525, 1536, 1545, 1547, 1557, 1562, 1567, 1572, 1584, 1585, 1596, 1611, 1616, 1621, 1623, 1633, 1634, 1643, 1644, 1655, 1656, 1660, 1665, 1670, 1672, 1682, 1683, 1693, 1704, 1709, 1714, 1731, 1732, 1742, 1753, 1754, 1758, 1763, 1768, 1774, 1781, 1790, 1803, 1807, 1812, 1817, 1823, 1829, 1830, 1861, 1866, 1872, 1878, 1879, 1899, 1901, 1915, 1921, 1927, 1928, 1932, 1938, 1940, 1950, 1961, 1964, 1970, 1976, 1981, 1987, 1999, 2009, 2010, 2030, 2036, 2038, 2046, 2056, 2058, 2067, 2068, 2074, 2078, 2085, 2085, 2088, 2095, 2105, 2107, 2113, 2116, 2127, 2134, 2137, 2144, 2144, 2156, 2176, 2183, 2186, 2193, 2205, 2221, 2225, 2232, 2242, 2242, 2254, 2262, 2270, 2274, 2281, 2291, 2296, 2303, 2311, 2319, 2323, 2324, 2330, 2334, 2340, 2344, 2352, 2363, 2372, 2379, 2389, 2401, 2412, 2421, 2422, 2428, 2432, 2442, 2450, 2450, 2461, 2470, 2471, 2477, 2481, 2491, 2499, 2519, 2520, 2526, 2530, 2537, 2540, 2547, 2548, 2559, 2568, 2569, 2581, 2585, 2589, 2595, 2597, 2601, 2608, 2618, 2628, 2630, 2634, 2638, 2650, 2656, 2657, 2667, 2677, 2679, 2687, 2693, 2699, 2705, 2706, 2726, 2732, 2736, 2742, 2748, 2754, 2777, 2781, 2785, 2797, 2804, 2815, 2824, 2826, 2840, 2851, 2853, 2857, 2863, 2864, 2875, 2886, 2895, 2900, 2906, 2912, 2913, 2923, 2934, 2955, 2961, 2972, 2983, 2984, 2993, 2998, 3004, 3010, 3011, 3020, 3021, 3033, 3037, 3042, 3043, 3047, 3053, 3059, 3063, 3069, 3081, 3086, 3089, 3096, 3101, 3108, 3111, 3118, 3118, 3129, 3138, 3141, 3145, 3150, 3167, 3167, 3178, 3187, 3190, 3199, 3206, 3216, 3220, 3227, 3236, 3239, 3248, 3255, 3259, 3269, 3276, 3276, 3288, 3298, 3304, 3308, 3314, 3315, 3318, 3325, 3337, 3346, 3353, 3357, 3374, 3374, 3386, 3395, 3396, 3402, 3406, 3423, 3435, 3445, 3451, 3455, 3462, 3472, 3472, 3484, 3492, 3494, 3500, 3504, 3505, 3511, 3514, 3521, 3521, 3526, 3533, 3543, 3549, 3553, 3554, 3560, 3563, 3570, 3575, 3582, 3602, 3603, 3608, 3612, 3618, 3629, 3631, 3639, 3651, 3652, 3661, 3667, 3678, 3700, 3701, 3710, 3716, 3727, 3729, 3740, 3765, 3770, 3782, 3788, 3789, 3798, 3799, 3811, 3814, 3819, 3825, 3831, 3838, 3848, 3858, 3860, 3880, 3896, 3897, 3907, 3917, 3923, 3929, 3935, 3936, 3945, 3946, 3956, 3958, 3962, 3966, 3968, 3972, 3984, 3985, 3988, 3994, 3995, 4005, 4011, 4021, 4027, 4033, 4037, 4043, 4044, 4054, 4056, 4064, 4076, 4081, 4083, 4086, 4112, 4115,

../QuickSortInt/main.cpp, 45, main, result over

Debugging has finished

5.2 RangeSortSearch

5.2.1 下载

https://bitbucket.org/hxcan/parallizedqalgorithms/downloads/RangeSortSearchInt.tar.gz

5.2.2 在线查看代码

RangeSortSearchInt.pro

代码内容:

TARGET = RangeSortSearchInt

TEMPLATE = app

SOURCES += \

    main.cpp \

    RangeSortSearchInt.cpp \

    LegacyIntComparator.cpp

HEADERS += \

    RangeSortSearchInt.h \

    LegacyIntComparator.h

QT+=concurrent

unix:!macx: LIBS += -lParallizedAlgorithms

LegacyIntComparator.cpp

代码内容:

#include "LegacyIntComparator.h" //LegacyIntComparator

int LegacyIntComparator::getDifference(int currentElement, int baseElement)

{

return currentElement-baseElement;

} //int getDifference(QString dir2Scan, QString compareBase) override

CompareResultRelation LegacyIntComparator::paCompare (int currentElement, int baseElement)

{

    CompareResultRelation result;

if (currentElement < baseElement)

    {

        result=LessThan;

    } //if (currentElement<baseElement)

else if (currentElement==baseElement)

    {

        result=Equal;

    } //else if (currentElement==baseElement)

else

    {

        result=GreaterThan;

    } //else

return result;

} //CompareResultRelation paCompare (QString currentElement, QString baseElement)

LegacyIntComparator.h

代码内容:

#ifndef LEGACYINTCOMPARATOR_H

#define LEGACYINTCOMPARATOR_H

#include <RangeSortSearch.h> //RangeSortSearch

class LegacyIntComparator : public PaComparator<int>

{

public:

int getDifference(int currentElement, int baseElement) override;

    CompareResultRelation paCompare (int currentElement, int baseElement) override;

};

#endif

main.cpp

代码内容:

#include "RangeSortSearchInt.h" //RangeSortSearchInt

int main(int argc, char *argv[])

{

QCoreApplication a(argc, argv);

    RangeSortSearchInt rangeSortSearchInt;

    rangeSortSearchInt.main();

return a.exec();

}

RangeSortSearchInt.cpp

代码内容:

#include "RangeSortSearchInt.h" //RangeSortSearchInt

#include "LegacyIntComparator.h" //LegacyIntComparator

/*!

 * \brief RangeSortSearchInt::showResult 搜索完毕,则显示结果。

 */

void RangeSortSearchInt::showResult()

{

    cout << endl << __FILE__ << ", " << __LINE__ << ", " << __func__ << ", finished search, time: " << QTime::currentTime ().toString ().toStdString () << endl; //Debug.

    cout << endl << __FILE__ << ", " << __LINE__ << ", " << __func__ << ", finished search, elapsed time: " << timing.elapsed() << "ms" << endl; //Debug.

QList<int> result=rangeSortSearch.getResult(); //获取结果。

    cout << __FILE__ << ", " << __LINE__ << ", " << __func__ << ", got result: " << endl; //Debug.

for(int currentValue:result)

    {

        cout << currentValue << ", ";

    } //for(int currentValue:result)

    cout << endl << __FILE__ << ", " << __LINE__ << ", " << __func__ << ", result over" << endl; //Debug.

QCoreApplication::quit();

} //void RangeSortSearchInt::showResult()

void RangeSortSearchInt::main()

{

QObject::connect(rangeSortSearch.getSignalProxy(), &PaSignalProxy::finished, this, &RangeSortSearchInt::showResult); //搜索完毕,则显示结果。

QList<int> intList;

    cout << __FILE__ << ", " << __LINE__ << ", " << __func__ << ", generating integers" << endl; //Debug.

for(auto intCounter=0;intCounter<100000000;intCounter++)

    {

int currentRandomNumber=qrand() % 1000000000;

        intList << currentRandomNumber;

    } //for(auto intCounter=0;intCounter<100;intCounter++)

    cout << endl << __FILE__ << ", " << __LINE__ << ", " << __func__ << ", finished generating integers" << endl; //Debug.

    cout << endl << __FILE__ << ", " << __LINE__ << ", " << __func__ << ", start search, time: " << QTime::currentTime ().toString ().toStdString () << endl; //Debug.

    timing.start(); //开始计时。

    LegacyIntComparator *legacyIntComparator=new LegacyIntComparator;

    rangeSortSearch.startSearch(intList,legacyIntComparator,600);

}

RangeSortSearchInt.h

代码内容:

#ifndef RANGESORTSEARCHINT_H

#define RANGESORTSEARCHINT_H

#include <RangeSortSearch.h>

class RangeSortSearchInt:public QObject

{

Q_OBJECT

public:

void main();

private:

void showResult(); //!<搜索完毕,则显示结果。

    RangeSortSearch<int> rangeSortSearch;

QTime timing;

}; //RangeSortSearchInt

#endif

5.2.3 输出结果

Debugging starts

&"warning: GDB: Failed to set controlling terminal: \345\257\271\350\256\276\345\244\207\344\270\215\351\200\202\345\275\223\347\232\204 ioctl \346\223\215\344\275\234\n"

../RangeSortSearchInt/RangeSortSearchInt.cpp, 33, main, generating integers

../RangeSortSearchInt/RangeSortSearchInt.cpp, 42, main, finished generating integers

../RangeSortSearchInt/RangeSortSearchInt.cpp, 44, main, start search, time: 12:55:01

../RangeSortSearchInt/RangeSortSearchInt.cpp, 9, showResult, finished search, time: 12:55:15

../RangeSortSearchInt/RangeSortSearchInt.cpp, 11, showResult, finished search, elapsed time: 13962ms

../RangeSortSearchInt/RangeSortSearchInt.cpp, 15, showResult, got result:

77, 446, 148, 757, 708, 661, 322, 413, 626, 197, 337, 746, 502, 159, 371, 740, 89, 70, 453, 334, 710, 622, 620, 795, 219, 288, 315, 491, 612, 730, 383, 671, 239, 33, 681, 759, 495, 669, 649, 17, 514, 600, 691, 642, 393, 442, 589, 522, 327, 789, 236, 246, 115, 62, 273, 13, 731, 697, 780, 109, 60, 295, 1, 720, 420, 364, 550, 119, 131, 28, 263, 355, 266, 111, 66, 718, 138, 541, 736, 599, 306, 344, 648, 702, 170, 593, 393, 187, 208, 7, 376, 285, 21, 698, 544, 573, 229, 469, 197, 687, 404, 257, 551, 367, 175, 524, 256, 207, 751, 236, 638, 571, 577, 246, 168, 344, 659, 465, 158, 1143, 1536, 1240, 800, 1341, 1015, 1122, 1111, 975, 1338, 1584, 1163, 1171, 906, 1112, 1572, 1100, 1149, 1567, 1487, 1083, 808, 828, 877, 1181, 1547, 1420, 1251, 1378, 927, 942, 1210, 865, 991, 1585, 1212, 1258, 1317, 1449, 1093, 1476, 1300, 857, 1182, 1508, 1220, 1034, 1498, 976, 1004, 1318, 1596, 1562, 1398, 1084, 1447, 1055, 1269, 1496, 1014, 855, 1518, 1525, 838, 1062, 1296, 1220, 1171, 1073, 1066, 1438, 849, 1160, 1616, 1002, 1280, 1035, 1400, 844, 1371, 1349, 1094, 966, 878, 1415, 1545, 1122, 1040, 1345, 806, 1231, 1557, 1142, 926, 953, 1459, 1611, 1427, 1133, 1307, 1329, 1503, 1209, 887, 1261, 818, 1269, 1427, 988, 1024, 1044, 3406, 1621, 2340, 3004, 3089, 2085, 3314, 2886, 3216, 2732, 2113, 2693, 2781, 2826, 2955, 1660, 3081, 1731, 3248, 1633, 1704, 3325, 2242, 2699, 1742, 2319, 1682, 2311, 1754, 3236, 3086, 2569, 2993, 2144, 2330, 2432, 3096, 1803, 1714, 3069, 3167, 1961, 3298, 2116, 2461, 3269, 2046, 2137, 1758, 3227, 2736, 2422, 1878, 2754, 1817, 3129, 3141, 2657, 2323, 2581, 3396, 2491, 2254, 2540, 1981, 1901, 2344, 1781, 3374, 1940, 1634, 1950, 3276, 1693, 2470, 2068, 2705, 3033, 2526, 2442, 2421, 2221, 2450, 2912, 1732, 2815, 2656, 2679, 2589, 2477, 2804, 3190, 2520, 3108, 2372, 2568, 3020, 3187, 1643, 3255, 3315, 2074, 2537, 3010, 2009, 2389, 1879, 1928, 2585, 2379, 2998, 2851, 2961, 2934, 1829, 2840, 3337, 2864, 2638, 1915, 2519, 2105, 2176, 2401, 2530, 1790, 2608, 2095, 2634, 2274, 2324, 2628, 1987, 2262, 3386, 2650, 1623, 2303, 3206, 3402, 2797, 3199, 1665, 3395, 2706, 1976, 2242, 2559, 2748, 3037, 2742, 1872, 2232, 1927, 2667, 3220, 3276, 2630, 2906, 2785, 2144, 1921, 1823, 2471, 2913, 2499, 1683, 2601, 2352, 3304, 2597, 1774, 2450, 2428, 1964, 1932, 1970, 2334, 2036, 2412, 2677, 3374, 3145, 2030, 3111, 2225, 1999, 2895, 2595, 2923, 2875, 1672, 2156, 3308, 2067, 2134, 2193, 2186, 3259, 3042, 2038, 3318, 3150, 2824, 2127, 2547, 2777, 3101, 1670, 2078, 2056, 3011, 2726, 2481, 1807, 1768, 3118, 3059, 2107, 1644, 3167, 1655, 1763, 2270, 2618, 1861, 2296, 2857, 2281, 2972, 1938, 2687, 2058, 1866, 3118, 1753, 2363, 1899, 1656, 2205, 3239, 3138, 3178, 1812, 3043, 3047, 3053, 3288, 2085, 2548, 3357, 2291, 3021, 2863, 2983, 3353, 3346, 1830, 3063, 1709, 2088, 2900, 2984, 2010, 2853, 2183, 3514, 3740, 3825, 3629, 3700, 3618, 3729, 3860, 3652, 3814, 3667, 3560, 3494, 3462, 3897, 3811, 3521, 3831, 3563, 3500, 3543, 3570, 3582, 3631, 3511, 3788, 3858, 3521, 3966, 3701, 3958, 3472, 3484, 3956, 3880, 3472, 3798, 3923, 3526, 3782, 3602, 3639, 3423, 3504, 3455, 3838, 3936, 3946, 3962, 3575, 3799, 3505, 3612, 3968, 3770, 3945, 3789, 3678, 3435, 3549, 3661, 3972, 3492, 3716, 3553, 3917, 3896, 3651, 3907, 3935, 3929, 3819, 3710, 3451, 3727, 3765, 3554, 3445, 3608, 3848, 3533, 3603, 3984, 3995, 3985, 3988, 3994, 4005, 4021, 4033, 4043, 4044, 4037, 4056, 4027, 4011, 4054, 4076, 4064, 4115, 4083, 4086, 4112, 4081,

../RangeSortSearchInt/RangeSortSearchInt.cpp, 22, showResult, result over

Debugging has finished