建站
咨詢
售后
建站咨詢
新聞中心
排序計算是一個非常消耗資源的操作，特別是對于大數(shù)據(jù)排序，如果內(nèi)存無法裝下數(shù)據(jù)，常規(guī)的做法就需要借助外存，不過因此也會增加對數(shù)據(jù)的讀寫操作，而讀寫操作通常又會比排序操作更消耗資源。
為華亭等地區(qū)用戶提供了全套網(wǎng)頁設(shè)計制作服務(wù)，及華亭網(wǎng)站建設(shè)行業(yè)解決方案。主營業(yè)務(wù)為成都網(wǎng)站制作、網(wǎng)站設(shè)計、華亭網(wǎng)站設(shè)計，以傳統(tǒng)方式定制建設(shè)網(wǎng)站，并提供域名空間備案等一條龍服務(wù)，秉承以專業(yè)、用心的態(tài)度為用戶提供真誠的服務(wù)。我們深信只要達(dá)到每一位用戶的要求，就會得到認(rèn)可，從而選擇與我們長期合作。這樣，我們也可以走得更遠(yuǎn)！
本文介紹的SPL排序優(yōu)化技巧，除了提供常規(guī)的排序算法外，還根據(jù)不同場景下的數(shù)據(jù)特性提供了排序的替代算法，從而減少比較次數(shù)和IO量，提升運算性能。
1內(nèi)存排序
當(dāng)數(shù)據(jù)可以輕松裝入內(nèi)存時，可以使用SPL的內(nèi)存排序函數(shù)，如A.sort()。SPL默認(rèn)的排序算法是基于merge sort的多線程排序算法，也就是說，此時的優(yōu)化方式主要是通過增加線程數(shù)量實現(xiàn)的。實際采用的線程數(shù)由集算器配置中的[最大并行數(shù)]指定。示例代碼如下：
| A | B | |
| 1 | =5000*1000 | /元素數(shù) |
| 2 | =A1\1000 | /隨機(jī)數(shù)最大值 |
| 3 | =to(A1).(rand(A2)) | /生成隨機(jī)序列 |
| 4 | =now() | /當(dāng)前時間 |
| 5 | =A3.sort() | /升序排序 |
| 6 | =interval@ms(A4,now()) | /排序花費的時間 |
實測使用的的測試機(jī)CPU是酷睿i7 ，4核心 8線程，根據(jù) [最大并行數(shù)]配置的不同，測試結(jié)果如下：
| 最大并行數(shù) | 平均花費時間（毫秒） |
| 1（即單線程） | 1800 |
| 4 | 800 |
| 8 | 660 |
可見，多核心CPU或多CPU計算機(jī)通過多線程排序可以充分利用每個核心的并行計算能力，顯著提升排序性能。
此例中每個值的重復(fù)量平均為1000，對A.sort()函數(shù)來說，重復(fù)數(shù)量的多少對性能影響不大。但在重復(fù)數(shù)量較多時，我們還可以通過分組法A.group@s()進(jìn)行排序，進(jìn)一步提高性能。此方法首先利用哈希法對元素進(jìn)行分組，然后再對組進(jìn)行排序，最后合并排序后的組得到排序結(jié)果。示例代碼如下：
| A | B | |
| 1 | =5000*1000 | /元素數(shù) |
| 2 | =A1\1000 | /隨機(jī)數(shù)最大值 |
| 3 | =to(A1).(rand(A2)) | /生成隨機(jī)序列 |
| 4 | =now() | /當(dāng)前時間 |
| 5 | =A3.group@s() | /每個值平均有1000個重復(fù)的，使用分組法進(jìn)行升序排序 |
| 6 | =interval@ms(A4,now()) | /排序花費的時間 |
使用分組法排序后，平均花費時間為360毫秒，可見，此方法適合重復(fù)數(shù)量較多的數(shù)據(jù)，重復(fù)數(shù)量越多性能越好。
2外存排序
當(dāng)數(shù)據(jù)量大到無法裝入內(nèi)存時就需要借助外存進(jìn)行排序。外存排序會分步讀入數(shù)據(jù)，排序后寫出到臨時文件，最后對所有生成的臨時文件歸并得到最終結(jié)果。
臨時文件的數(shù)量會影響排序的效率，如果數(shù)量過多，歸并階段會占用更多的資源，而歸并路數(shù)過多也會影響歸并效率。所以每次讀入較多的數(shù)據(jù)量可以提升sortx的性能。
SPL外存排序的函數(shù)是cs.sortx()，排序中生成的臨時文件數(shù)量由原始數(shù)據(jù)量和每次讀入的數(shù)據(jù)量決定，而每次讀入的數(shù)據(jù)量可以通過sortx函數(shù)的參數(shù)指定。用戶可以根據(jù)記錄大小和空閑內(nèi)存容量指定一個合理的每次讀入數(shù)據(jù)量以達(dá)到最優(yōu)的性能。如果沒有指定，SPL會根據(jù)虛擬機(jī)可用內(nèi)存估算出一個大概值。
臨時文件的釋放會在結(jié)果游標(biāo)取數(shù)結(jié)束或者close方法被調(diào)用時觸發(fā)。
測試外存排序需要大數(shù)據(jù)量，而由于使用JDBC從數(shù)據(jù)庫取數(shù)的效率非常差，因此本文將采用效率更好的集文件進(jìn)行測試。
測試數(shù)據(jù)模擬訂單數(shù)據(jù)，表結(jié)構(gòu)為{ order_id ,order_datetime , customer_id, employee_id , product_id , quantity ,price}，按order_id 、order_datetime有序，隨機(jī)生成2000萬條記錄。
測試數(shù)據(jù)的生成也使用SPL，造數(shù)代碼如下：
| A | B | |
| 1 | 2018-01-01 00:00:00 | =file("orders_2018.btx") |
| 2 | =to(1000*1000) | 0 |
| 3 | for 20 | =A2.new(B2+~:order_id, elapse@s(A1,order_id):order_datetime, rand(1000000) + 1:customer_id, rand(1000) + 1:employee_id, rand(10000) + 1:product_id, rand(1000) + 1:quantity, rand(100000000)/100:price) |
| 4 | =B1.export@ab(B3) | |
| 5 | >B2=B2+A2.len() |
排序計算的代碼如下：
| A | B | |
| 1 | =now() | |
| 2 | =file("orders_2018.btx").cursor@b() | /生成訂單集文件的取數(shù)游標(biāo) |
| 3 | =A2.sortx(customer_id; 2000000) | /對游標(biāo)按客戶編碼排序，第二個參數(shù)為每次讀入的數(shù)據(jù)量 |
| 4 | =file("orders_customer_2018.btx").export@b(A3) | /導(dǎo)出排序結(jié)果到集文件 |
| 5 | =interval@s(A1,now()) | /耗時，單位秒 |
測試結(jié)果如下：
| 每次讀入數(shù)據(jù)量 | 耗時（秒） |
| 200萬 | 73 |
| 20萬 | 216 |
3多路歸并
使用SPL處理大數(shù)據(jù)運算時，為了獲取更好的性能通常會把數(shù)據(jù)外置成集文件或組表，同時按照常用的過濾維度排序以獲得更高的過濾性能。這樣，如果有新的數(shù)據(jù)要追加到歷史文件，并需要對所有數(shù)據(jù)重新排序，我們就可以利用集文件或者組表的這個特點了。由于歷史數(shù)據(jù)已經(jīng)有序，此時我們可以先把新數(shù)據(jù)按照維度排序，然后再和歷史數(shù)據(jù)進(jìn)行歸并就可以得到最終的有序數(shù)據(jù)了。使用這個方法排序涉及的數(shù)據(jù)量遠(yuǎn)小于對所有數(shù)據(jù)進(jìn)行大排序的數(shù)據(jù)量。具體的測試如下：
在前面外存排序的造數(shù)代碼中，將A1格改為2017-01-01 00:00:00，B1格改為=file("orders_2017.btx")，生成模擬2017年的訂單數(shù)據(jù)文件“orders_2017.btx”。然后使用外存排序代碼按customer_id字段排序，生成排序結(jié)果文件“orders_2017_customer.btx”。
然后，我們需要將2017、2018兩年的所有數(shù)據(jù)進(jìn)行整體排序，也就是使用歸并方法合并orders_2017_customer.btx、orders_2018_customer.btx兩個文件成一個新的有序文件。示例代碼如下：
| A | B | |
| 1 | =now() | |
| 2 | =file("orders_2017_customer.btx").cursor@b() | |
| 3 | =file("orders_2018_customer.btx").cursor@b() | |
| 4 | =[A2,A3].mergex(customer_id) | /對兩個按customer_id有序的游標(biāo)做歸并，合成一個按customer_id有序的新游標(biāo) |
| 5 | =file("orders1.btx").export@b(A4) | /把排序后的數(shù)據(jù)導(dǎo)出到集文件 |
| 6 | =now() | =interval@s(A1,A6) |
| 7 | =file("orders_2017_customer.btx").cursor@b() | |
| 8 | =file("orders_2018_customer.btx").cursor@b() | |
| 9 | =[A7,A8].conjx().sortx(customer_id; 2000000) | /縱向連接兩個游標(biāo)并進(jìn)行外存排序 |
| 10 | =file("orders2.btx").export@b(A9) | |
| 11 | =now() | =interval@s(A6,A11) |
前6行代碼采用了歸并方法，耗時30秒，而后5行代碼模擬了簡單的大排序方法，耗時133秒。
4前半有序
如果需要按照多個字段對數(shù)據(jù)進(jìn)行排序，而數(shù)據(jù)已經(jīng)按照排序字段中的幾個字段有序了，則可以按照已經(jīng)有序的字段分組讀入數(shù)據(jù)，在內(nèi)存排序后輸出。這種處理方法比cs.sortx()少了一遍讀寫操作，因此性能大幅優(yōu)于cs.sortx()。
例如訂單表的數(shù)據(jù)是按照日期時間有序生成的，如果想按照日期、客戶兩個字段對訂單表進(jìn)行排序則可以使用這個方法。示例代碼如下：
| A | B | |
| 1 | =now() | |
| 2 | =file("orders_2017.btx").cursor@b() | |
| 3 | =A2.run(order_datetime=date(order_datetime)) | /把日期時間轉(zhuǎn)為日期類型 |
| 4 | =A2.group@qs(order_datetime;customer_id) | /數(shù)據(jù)已按order_datetime有序，對數(shù)據(jù)按order_datetime,customer_id排序 |
| 5 | =file("orders_2017_date_customer.btx").export@b(A4) | |
| 6 | =interval@s(A1,now()) |
經(jīng)測試耗時為38秒（A6格的值），而如果把A4格表達(dá)式替換為下面代碼則耗時95秒。
| A | B | |
| 4 | =A2.sortx(order_datetime,customer_id;2000000) | /數(shù)據(jù)已按order_datetime有序，對數(shù)據(jù)按order_datetime,customer_id排序 |
5索引排序
SPL的組表提供了為某些列創(chuàng)建索引的功能，一些常用的列也可以存到索引里，這樣如果訪問的列都在索引里就不需要再訪問整個源文件，從而節(jié)省大量IO操作。而如果排序字段是索引字段，并且需要訪問的字段也都在索引里，則可以利用索引的有序性，使用T.icursor@s()返回有序游標(biāo)。
創(chuàng)建索引的代碼如下：
| A | B | |
| 1 | 2018-01-01 00:00:00 | =file("orders.ctx") |
| 2 | =to(1000*1000) | 0 |
| 3 | =B1.create@y(#order_id,#order_datetime,customer_id,employee_id,product_id,quantity, price) | |
| 4 | /以下循環(huán)為創(chuàng)建組表數(shù)據(jù)程序 | |
| 5 | for 20 | =A2.new(B2+~:order_id, elapse@s(A1,order_id):order_datetime, rand(1000000) + 1:customer_id, rand(1000) + 1:employee_id, rand(10000) + 1:product_id, rand(1000) + 1:quantity, rand(100000000)/100:price) |
| 6 | =A3.append(B5.cursor()) | |
| 7 | >B2=B2+A2.len() | |
| 8 | =A3.index(PriceIndex;price;product_id,order_datetime) | /按金額字段建索引，同時保持產(chǎn)品,日期兩個字段的值 |
利用索引產(chǎn)生有序游標(biāo)代碼如下：
| A | B | |
| 1 | =now() | =file("orders.ctx").create() |
| 2 | =B1.icursor@s(order_datetime,product_id,price;true,PriceIndex) | /利用索引返回有序游標(biāo) |
| 3 | for A2,10000 | /遍歷游標(biāo)數(shù)據(jù) |
| 4 | =now() | =interval@ms(A1,A4) |
| 5 | =B1.cursor(order_datetime,product_id,price) | |
| 6 | =A5.sortx(price) | /外存排序 |
| 7 | for A6,10000 | /遍歷游標(biāo)數(shù)據(jù) |
| 8 | =now() | =interval@ms(A4,A8) |
經(jīng)測試有序游標(biāo)耗時為4秒（B4格的值），而外存排序遍歷耗時為54秒（B8格的值）。
標(biāo)題名稱：SPL排序優(yōu)化技巧
URL網(wǎng)址：http://www.ef60e0e.cn/article/iiogsd.html
