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

ncream 2017-11-22 02:36 PM

迎來全新sorting algorithm 開CODE測試。

因為最近係咁SET WIFI AP,好唔得閒,裝機裝到要死。無咩時間改program,原本諗住再改下,依家要暫時收檔,等無咁忙先。

依家係食飯時間,用來出下post。

我諗呢個sorting algorithm 時,無睇過其他人點諗,正如上次鴿巢一樣,係我諗左,用左幾年,偶爾上wiki先揾到,原來一早有人諗左並命名。睇來現在做創作真係好難,幾乎所有可能都被人諗左。

就好似呢次咁,我都係自己諗左,點知網上揾到類似,重要係2016年,早幾年我又係呢到又遇到煙師兄出呢d問題幾好呢,不過無得如果。

我同網上個sort最大分別係:我係用LSD,佢係用MSD。顯然佢係因為想做IN PLACE先用MSD,我就首要速度。

單thread同2 thread code如下:

等各位ching測試。

單thread: [url=https://www.sendspace.com/file/95ownu]https://www.sendspace.com/file/95ownu[/url]

2 thread: [url=https://www.sendspace.com/file/j5p19h]https://www.sendspace.com/file/j5p19h[/url]

我不斷有新諗法,等一有時間就會試另一D sorting model。

[[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);
   
    uint32_t* address = (uint32_t*)mmap(nullptr, mapped_size, PROT_READ | PROT_WRITE, MAP_SHARED, fd, 0);
   
    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] << " ";
    }
   
    munmap(address, mapped_size);
    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]

要用-O3先快。請再試下。

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]


要用-O3先快。請再試下。 [/quote]
已經係Xcode optimized的時間
汪汪呢個同你地之前的唔同

汪汪係玩緊sorting file data
係包括埋file IO速度

[[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]

已經係Xcode optimized的時間
汪汪呢個同你地之前的唔同

汪汪係玩緊sorting file data
係包括埋file IO速度 [/quote]

明白,讀埋IO已經好快。勁快。

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]
因為最近係咁SET WIFI AP,好唔得閒,裝機裝到要死。無咩時間改program,原本諗住再改下,依家要暫時收檔,等無咁忙先。

依家係食飯時間,用來出下post。

我諗呢個sorting algorithm 時,無睇過其他人點諗,正 ... [/quote]
這個Sorting Algorithm的限制是只能Sort Unsigned Integer (32/64-bit)...... Signed Integer, Double, Float, String都不能Sort.....

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]

已經係Xcode optimized的時間
汪汪呢個同你地之前的唔同

汪汪係玩緊sorting file data
係包括埋file IO速度 [/quote]

不過扣左FILE IO,都無可能1.5秒內完成。所以要努力寫得再快D。:smile_o12:

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]
因為最近係咁SET WIFI AP,好唔得閒,裝機裝到要死。無咩時間改program,原本諗住再改下,依家要暫時收檔,等無咁忙先。

依家係食飯時間,用來出下post。

我諗呢個sorting algorithm 時,無睇過其他人點諗,正 ... [/quote]Thread的用法效率不足, 正常應該是Create定Thread然後不停重用, 而不是Sorting途中才Create Thread

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]
Thread的用法效率不足, 正常應該是Create定Thread然後不停重用, 而不是Sorting途中才Create Thread [/quote]

明白,開與關thread都要晒時間,下個SORTING MODEL 會改進。

多謝師兄指點。:smile_o06::smile_o06:

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]


不過扣左FILE IO,都無可能1.5秒內完成。所以要努力寫得再快D。:smile_o12: [/quote]
段code冇得扣除file IO 時間
因為直接係file 上sort

汪汪寫呢個
理論上只要harddisk 有位的話幾多GB都sort到
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]

這個Sorting Algorithm的限制是只能Sort Unsigned Integer (32/64-bit)...... Signed Integer, Double, Float, String都不能Sort..... [/quote]

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]
佢應該講緊佢個算法係把資料拆做byte sequence
然後一個個byte咁compare

string 用utf8去拆都仲可以

但double 無得直接拆byte sequence

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]

佢應該講緊佢個算法係把資料拆做byte sequence
然後一個個byte咁compare

string 用utf8去拆都仲可以

但double 無得直接拆byte sequence [/quote]但一個個Byte Compare, Sort出來的會不太合理, 因此是不可用的, 還有String是Variable Length, 不適合用在這個Algorithm內

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]
但一個個Byte Compare, Sort出來的會不太合理, 因此是不可用的, 還有String是Variable Length, 不適合用在這個Algorithm內 [/quote]
佢個算法對於Variable Length應該唔大問題
做少少改動就可以

但汪汪反而諗到佢個算法有個更大的弱點
如果資料係唔平均的話

佢準備的table隨時唔夠位裝

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]
但一個個Byte Compare, Sort出來的會不太合理, 因此是不可用的, 還有String是Variable Length, 不適合用在這個Algorithm內 [/quote]

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

但floating要加comparison sort。應該可以sort到。

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]

佢個算法對於Variable Length應該唔大問題
做少少改動就可以

但汪汪反而諗到佢個算法有個更大的弱點
如果資料係唔平均的話

佢準備的table隨時唔夠位裝 [/quote]

要預位,依家每個數要int ,4 byte unsigned ,40幾億個,即要sorting既數超過40億就要轉64bit,如此類推。

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再努力。

不過要有時間。老細放過我啦。:smile_o16:

煙民母親生賤種 2017-11-23 03:24 AM

[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]
的確唔錯。上一排我先諗想用呢類方式, 原來 c++ 已 經有實作。不過實用起上來, 唔知比起 fread i/ostream 之類快幾多... :fst_002: [/quote]
你n咁多年前講DAM果時汪汪已經寫緊mmap

http://computer.discuss.com.hk/viewthread.php?tid=24930392

呢個也都講過好耐
用file 當memory 咁用

https://www.discuss.com.hk/viewthread.php?tid=26952603&utm_source=copy&utm_campaign=ios&utm_medium=share

[[i] 本帖最後由 Susan﹏汪汪 於 2017-11-23 12:24 PM 編輯 [/i]]
頁: [1]
查看完整版本: 迎來全新sorting algorithm 開CODE測試。