# 查看完整版本 : 迎來全新sorting algorithm 開CODE測試。

ncream 2017-11-22 02:36 PM

## 迎來全新sorting algorithm 開CODE測試。

[[i] 本帖最後由 ncream 於 2017-11-22 02:43 PM 編輯 [/i]]

Susan﹏汪汪 2017-11-22 03:23 PM

1GB的sorted random numbers寫入file[code]#include <random>
#include <iostream>
#include <fcntl.h>
#include <unistd.h>
#include <sys/types.h>
#include <sys/mman.h>
#include <ctime>

template <class T> void swap (T& a, T& b)
{
T c(std::move(a)); a=std::move(b); b=std::move(c);
}

template <class Compare, class RandomAccessIterator>
void quick_sort(RandomAccessIterator first, RandomAccessIterator last, Compare comp)
{

typedef typename std::iterator_traits<RandomAccessIterator>::value_type value_type;

const auto _l = last - 1;

if (first < _l) {

auto forward = first, backward = _l;
const value_type val = *_l;

for (; forward < backward; ++forward)
{
while (comp(*forward, val) && forward < backward) ++forward;
while (comp(val, *backward) && forward < backward) --backward;
swap(*forward, *backward);
}
swap(*backward, *_l);

quick_sort(first, backward, comp);
quick_sort(backward, last, comp);
}
}

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

clock_t t;

int mapped_size = 1073741824;   // 1GB
int n = mapped_size / sizeof(uint32_t);

int fd = open("/Users/Susan/Desktop/large_file", O_RDWR | O_CREAT, S_IRUSR | S_IWUSR);
ftruncate(fd, mapped_size);

std::mt19937 generator(0);

t = clock();

for (auto start = address, end = address + n; start < end; ++start) {
*start = generator();
}

t = clock() - t;
std::cout << "generate random: " << (((double)t)/CLOCKS_PER_SEC) << std::endl;

t = clock();

quick_sort(address, address + n, [](auto a, auto b) { return a < b; });

t = clock() - t;
std::cout << "sorting: " << (((double)t)/CLOCKS_PER_SEC) << std::endl;

for (int i = 0; i < 100; ++i) {
std::cout << address[i] << " ";
}

close(fd);

return 0;
}[/code]result:[code]generate random: 2.34
sorting: 29.1001
16 25 41 62 70 88 109 118 128 197 197 224 228 242 246 257 271 339 347 375 400 407 421 428 442 480 488 498 525 530 552 557 574 589 611 621 648 648 683 688 699 744 753 757 767 771 792 810 812 851 856 892 896 932 936 985 1006 1046 1090 1099 1099 1114 1128 1131 1132 1134 1144 1146 1177 1189 1208 1219 1221 1223 1241 1261 1263 1272 1294 1300 1322 1325 1326 1333 1338 1364 1403 1460 1497 1534 1559 1593 1645 1645 1646 1653 1658 1677 1680 1682 [/code]

ncream 2017-11-22 03:27 PM

[quote]原帖由 [i]Susan﹏汪汪[/i] 於 2017-11-22 03:23 PM 發表 [url=http://computer.discuss.com.hk/redirect.php?goto=findpost&pid=471291756&ptid=27075646][img]http://computer.discuss.com.hk/images/common/back.gif[/img][/url]
1GB的sorted random numbers寫入file#include
#include
#include
#include
#include
#include
#include

template  void swap (T& a, T& b)
{
T c(std::move(a)); a=std::move(b); b=std::move ... [/quote]

Susan﹏汪汪 2017-11-22 03:30 PM

[quote]原帖由 [i]ncream[/i] 於 2017-11-22 03:27 PM 發表 [url=http://www.discuss.com.hk/redirect.php?goto=findpost&pid=471291932&ptid=27075646][img]http://www.discuss.com.hk/images/common/back.gif[/img][/url]

[[i] 本帖最後由 Susan﹏汪汪 於 2017-11-22 03:31 PM 編輯 [/i]]

ncream 2017-11-22 03:56 PM

[quote]原帖由 [i]Susan﹏汪汪[/i] 於 2017-11-22 03:30 PM 發表 [url=http://computer.discuss.com.hk/redirect.php?goto=findpost&pid=471292088&ptid=27075646][img]http://computer.discuss.com.hk/images/common/back.gif[/img][/url]

sswroom 2017-11-22 03:56 PM

[quote]原帖由 [i]ncream[/i] 於 2017-11-22 02:36 PM 發表 [url=http://computer.discuss.com.hk/redirect.php?goto=findpost&pid=471289727&ptid=27075646][img]http://computer.discuss.com.hk/images/common/back.gif[/img][/url]

ncream 2017-11-22 03:57 PM

[quote]原帖由 [i]Susan﹏汪汪[/i] 於 2017-11-22 03:30 PM 發表 [url=http://computer.discuss.com.hk/redirect.php?goto=findpost&pid=471292088&ptid=27075646][img]http://computer.discuss.com.hk/images/common/back.gif[/img][/url]

sswroom 2017-11-22 04:00 PM

[quote]原帖由 [i]ncream[/i] 於 2017-11-22 02:36 PM 發表 [url=http://computer.discuss.com.hk/redirect.php?goto=findpost&pid=471289727&ptid=27075646][img]http://computer.discuss.com.hk/images/common/back.gif[/img][/url]

ncream 2017-11-22 04:03 PM

[quote]原帖由 [i]sswroom[/i] 於 2017-11-22 04:00 PM 發表 [url=http://computer.discuss.com.hk/redirect.php?goto=findpost&pid=471293498&ptid=27075646][img]http://computer.discuss.com.hk/images/common/back.gif[/img][/url]

Susan﹏汪汪 2017-11-22 04:13 PM

[quote]原帖由 [i]ncream[/i] 於 2017-11-22 03:57 PM 發表 [url=http://www.discuss.com.hk/redirect.php?goto=findpost&pid=471293329&ptid=27075646][img]http://www.discuss.com.hk/images/common/back.gif[/img][/url]

ram容量不是問題

ncream 2017-11-22 04:24 PM

[quote]原帖由 [i]sswroom[/i] 於 2017-11-22 03:56 PM 發表 [url=http://computer.discuss.com.hk/redirect.php?goto=findpost&pid=471293307&ptid=27075646][img]http://computer.discuss.com.hk/images/common/back.gif[/img][/url]

SIGNED / STRING 我想加上去，可惜無時間。 係可以SORT到。

FLOATING 要加埋comparison sorting algorithms

sswroom 2017-11-22 04:51 PM

[quote]原帖由 [i]ncream[/i] 於 2017-11-22 04:24 PM 發表 [url=http://computer.discuss.com.hk/redirect.php?goto=findpost&pid=471294566&ptid=27075646][img]http://computer.discuss.com.hk/images/common/back.gif[/img][/url]

SIGNED / STRING 我想加上去，可惜無時間。 係可以SORT到。

FLOATING 要加埋comparison sorting algorithms [/quote]String也是要Comparison Sort........

"A123456" < "A0234567"
"A123456" > "A0123456"

Susan﹏汪汪 2017-11-22 04:56 PM

[quote]原帖由 [i]sswroom[/i] 於 2017-11-22 04:51 PM 發表 [url=http://www.discuss.com.hk/redirect.php?goto=findpost&pid=471295804&ptid=27075646][img]http://www.discuss.com.hk/images/common/back.gif[/img][/url]
String也是要Comparison Sort........

"A123456" < "A0234567"
"A123456" > "A0123456" [/quote]

string 用utf8去拆都仲可以

sswroom 2017-11-22 05:00 PM

[quote]原帖由 [i]Susan﹏汪汪[/i] 於 2017-11-22 04:56 PM 發表 [url=http://computer.discuss.com.hk/redirect.php?goto=findpost&pid=471296015&ptid=27075646][img]http://computer.discuss.com.hk/images/common/back.gif[/img][/url]

string 用utf8去拆都仲可以

Susan﹏汪汪 2017-11-22 05:05 PM

[quote]原帖由 [i]sswroom[/i] 於 2017-11-22 05:00 PM 發表 [url=http://www.discuss.com.hk/redirect.php?goto=findpost&pid=471296226&ptid=27075646][img]http://www.discuss.com.hk/images/common/back.gif[/img][/url]

ncream 2017-11-22 05:10 PM

[quote]原帖由 [i]sswroom[/i] 於 2017-11-22 05:00 PM 發表 [url=http://computer.discuss.com.hk/redirect.php?goto=findpost&pid=471296226&ptid=27075646][img]http://computer.discuss.com.hk/images/common/back.gif[/img][/url]

length 不同，短的要補0。逐個byte最有效率。

ncream 2017-11-22 05:11 PM

[quote]原帖由 [i]Susan﹏汪汪[/i] 於 2017-11-22 05:05 PM 發表 [url=http://computer.discuss.com.hk/redirect.php?goto=findpost&pid=471296449&ptid=27075646][img]http://computer.discuss.com.hk/images/common/back.gif[/img][/url]

assembly.jc 2017-11-22 06:55 PM

single thread 1443 ms[code]108  165  291  306  458  481  523  566  576  580  614  618  623  641  667  688
697  697  726  770  791  846  907  913  946  1025  1049  1059  1081  1102  1208
1236  1326  1329  1437  1438  1457  1632  1662  1721  1788  1841  1861  1887  1
900  1927  1986  2002  2026  2094  2107  2124  2262  2265  2277  2293  2306  236
5  2466  2608  2620  2620  2657  2866  2944  2989  3003  3089  3090  3097  3158
3207  3329  3343  3414  3475  3485  3541  3583  3585  3603  3662  3710  3732  3
750  3789  3790  3846  3921  3955  4024  4092  4207  4249  4311  4362  4530  460
5  4642  4645

time used for sorting with CPU: 1443.000000 ms[/code]multi thread: 1185 ms[code]108  165  291  306  458  481  523  566  576  580  614  618  623  641  667  688
697  697  726  770  791  846  907  913  946  1025  1049  1059  1081  1102  1208
1236  1326  1329  1437  1438  1457  1632  1662  1721  1788  1841  1861  1887  1
900  1927  1986  2002  2026  2094  2107  2124  2262  2265  2277  2293  2306  236
5  2466  2608  2620  2620  2657  2866  2944  2989  3003  3089  3090  3097  3158
3207  3329  3343  3414  3475  3485  3541  3583  3585  3603  3662  3710  3732  3
750  3789  3790  3846  3921  3955  4024  4092  4207  4249  4311  4362  4530  460
5  4642  4645

time used for sorting with CPU: 1185.000000 ms[/code]和 ska sort 差不多。

ncream 2017-11-22 08:18 PM

[quote]原帖由 [i]assembly.jc[/i] 於 2017-11-22 06:55 PM 發表 [url=http://computer.discuss.com.hk/redirect.php?goto=findpost&pid=471301759&ptid=27075646][img]http://computer.discuss.com.hk/images/common/back.gif[/img][/url]
single thread 1443 ms108  165  291  306  458  481  523  566  576  580  614  618  623  641  667  688
697  697  726  770  791  846  907  913  946  1025  1049  1059  1081  1102  1208
1236  1326  1329  ... [/quote]

Thanks ching。已經可以同gpu接近水平。下一個model再努力。

[quote]原帖由 [i]Susan﹏汪汪[/i] 於 2017-11-22 03:23 PM 發表 [url=http://computer.discuss.com.hk/redirect.php?goto=findpost&pid=471291756&ptid=27075646][img]http://computer.discuss.com.hk/images/common/back.gif[/img][/url]
1GB的sorted random numbers寫入file#include
#include
#include
#include
#include
#include
#include

template  void swap (T& a, T& b)
{
T c(std::move(a)); a=std::move(b); b=std::move ... [/quote]的確唔錯。上一排我先諗想用呢類方式, 原來 c++ 已 經有實作。不過實用起上來, 唔知比起 fread i/ostream 之類快幾多... :fst_002:

Susan﹏汪汪 2017-11-23 09:10 AM

[quote]原帖由 [i]煙民母親生賤種[/i] 於 2017-11-23 03:24 AM 發表 [url=http://www.discuss.com.hk/redirect.php?goto=findpost&pid=471322060&ptid=27075646][img]http://www.discuss.com.hk/images/common/back.gif[/img][/url]