陶昕　計(jì)春雷

摘 要：針對(duì)傳統(tǒng)裝箱算法在處理海量數(shù)據(jù)時(shí)所存在的的運(yùn)行效率與空間利用率低的問(wèn)題，在深入研究已有裝箱算法的基礎(chǔ)上，在分布式系統(tǒng)中定義一種可變大小的箱子，結(jié)合動(dòng)態(tài)和靜態(tài)算法的優(yōu)勢(shì)，提出基于MapReduce的動(dòng)態(tài)裝箱算法。實(shí)驗(yàn)結(jié)果表明，針對(duì)海量動(dòng)態(tài)數(shù)據(jù)，運(yùn)用基于MapReduce的動(dòng)態(tài)裝箱算法，結(jié)果接近最優(yōu)解，同時(shí)具有很高的處理效率。

關(guān)鍵詞：裝箱算法；海量數(shù)據(jù)；分布式系統(tǒng)； MapReduce

DOIDOI：10.11907/rjdk.151567

中圖分類號(hào)：TP312 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1672-7800（2015）007-0066-05

0 引言

隨著云計(jì)算和物聯(lián)網(wǎng)技術(shù)的快速發(fā)展，數(shù)據(jù)量呈爆炸性增長(zhǎng)。據(jù)WinterCorp統(tǒng)計(jì)顯示，互聯(lián)網(wǎng)產(chǎn)生的數(shù)據(jù)量每?jī)赡暝鲩L(zhǎng)3倍[1]。在互聯(lián)網(wǎng)技術(shù)極速發(fā)展的背景下，大數(shù)據(jù)應(yīng)運(yùn)而生，人們生活正在逐漸被巨大的數(shù)據(jù)量所包圍。企業(yè)經(jīng)營(yíng)信息、電子商務(wù)商品物流信息、社交網(wǎng)絡(luò)交互信息、位置信息等數(shù)據(jù)量遠(yuǎn)遠(yuǎn)超越現(xiàn)有企業(yè)IT架構(gòu)和基礎(chǔ)設(shè)施的承載能力，實(shí)時(shí)性要求也大大超越現(xiàn)有的計(jì)算能力。大數(shù)據(jù)正在逐漸影響人們的生活方式。同時(shí)，大數(shù)據(jù)的產(chǎn)生給傳統(tǒng)的數(shù)據(jù)管理帶來(lái)了巨大的挑戰(zhàn)。針對(duì)海量數(shù)據(jù)的處理將成為大數(shù)據(jù)時(shí)代必須面對(duì)的問(wèn)題。

Hadoop是一個(gè)開源的、具有高可靠性和良好可伸縮性的分布式計(jì)算框架，可以對(duì)海量數(shù)據(jù)進(jìn)行分布式處理，其分布式計(jì)算模型MapReduce可以將數(shù)據(jù)集分割成若干小數(shù)據(jù)單元，這些小數(shù)據(jù)單元可以被放置在任何一個(gè)節(jié)點(diǎn)上進(jìn)行處理[2]。Hadoop分布式文件系統(tǒng)（HDFS）專門為存儲(chǔ)和管理海量數(shù)據(jù)而設(shè)計(jì)，其默認(rèn)存儲(chǔ)單元值為64M，但實(shí)際應(yīng)用中所產(chǎn)生的數(shù)據(jù)大多小于64M，直接處理這些數(shù)據(jù)將造成內(nèi)存浪費(fèi)，降低整個(gè)系統(tǒng)性能。

MapReduce是Hadoop分布式框架中的并行計(jì)算模型，可以對(duì)海量數(shù)據(jù)進(jìn)行并行處理。它最早由Google提出并實(shí)現(xiàn)，運(yùn)行在Google的分布式文件系統(tǒng)GPS（Google File System）上。MapReduce將海量數(shù)據(jù)處理分散到各個(gè)分節(jié)點(diǎn)共同完成，然后整合所有分節(jié)點(diǎn)的中間結(jié)果得到最終結(jié)果[3]。隨著數(shù)據(jù)量的不斷增長(zhǎng)，傳統(tǒng)算法效率較低，同時(shí)造成很大的資源浪費(fèi)。隨著云計(jì)算技術(shù)的發(fā)展，面向云計(jì)算平臺(tái)對(duì)傳統(tǒng)算法進(jìn)行改進(jìn)，可以提高海量數(shù)據(jù)處理效率。

裝箱問(wèn)題是最經(jīng)典的組合優(yōu)化問(wèn)題之一，將若干大小不同的物件，通過(guò)某種填裝策略，將所有物件放置到盡可能少的箱子內(nèi)[4]。該模型在現(xiàn)實(shí)生活中廣泛應(yīng)用于各領(lǐng)域，例如資源調(diào)度分配、內(nèi)存動(dòng)態(tài)分配、物流貨物裝載等。裝箱問(wèn)題的思想也可運(yùn)用在海量數(shù)據(jù)處理上，例如在數(shù)據(jù)存儲(chǔ)與傳輸過(guò)程中，將數(shù)據(jù)進(jìn)行裝箱存儲(chǔ)或傳輸，可很好地提高數(shù)據(jù)處理效率。隨著數(shù)據(jù)量的指數(shù)級(jí)增長(zhǎng)，傳統(tǒng)裝箱策略處理的結(jié)果已不能滿足實(shí)際需求，處理效率與空間利用率較低。據(jù)此，本文在深入研究已有裝箱算法的基礎(chǔ)之上，結(jié)合動(dòng)態(tài)和靜態(tài)兩種算法的優(yōu)勢(shì)，基于MapReduce并行計(jì)算模型對(duì)海量數(shù)據(jù)裝箱算法進(jìn)行研究。

1 相關(guān)研究

裝箱問(wèn)題算法已經(jīng)被證明是一個(gè)NP難解問(wèn)題，所以針對(duì)裝箱問(wèn)題的研究通常運(yùn)用近似算法[5，6]。所謂近似算法即該算法可以求得與精確解接近的結(jié)果，但不一定得到最優(yōu)解。裝箱算法具有很好的實(shí)際應(yīng)用價(jià)值，諸多學(xué)著對(duì)裝箱算法進(jìn)行了廣泛研究。Johnson等[7]證明了裝箱問(wèn)題是個(gè)NP難解問(wèn)題，此后的研究專注于相關(guān)近似算法研究。針對(duì)一維裝箱問(wèn)題本文給出如下描述：

任意給定一個(gè)含有N個(gè)數(shù)據(jù)項(xiàng)目的序列：S1，0≤Si≤1，0≤Si≤1…0≤Si≤1，使得0≤Si≤1。項(xiàng)目不可被切割，這些數(shù)據(jù)需要存儲(chǔ)在內(nèi)存容量為1的內(nèi)存“箱”中，目標(biāo)是盡可能用最少的箱子存儲(chǔ)這些數(shù)據(jù)[8]。假設(shè)K為箱容量，則一維裝箱問(wèn)題可以表示為：

∑Si≤Ki（1）

其中，0≤i≤n。目前，針對(duì)裝箱問(wèn)題的研究主要集中在物流貨物存儲(chǔ)和系統(tǒng)中的任務(wù)資源分配方面。針對(duì)貨物存放，將盡可能多的貨物存放在盡可能少的不同大小箱子中，并且存放在盡可能小的空間內(nèi)。在處理海量數(shù)據(jù)時(shí)，將數(shù)據(jù)進(jìn)行裝箱處理，可以使數(shù)據(jù)傳輸次數(shù)減少，從而有效提高系統(tǒng)處理效率，降低系統(tǒng)功耗。一維裝箱問(wèn)題的近似算法按照其特征可以分為動(dòng)態(tài)算法和靜態(tài)算法兩種[9， 10]。其中，動(dòng)態(tài)算法主要有首次適應(yīng)算法（FF First Fit Algorithm）、下次適應(yīng)算法（NF Next Fit Algorithm）和最佳適應(yīng)算法（BF Best Fit Algorithm）。而靜態(tài)算法主要有降序首次適應(yīng)算法（FFD First Fit Decreasing Algorithm）和降序最佳適應(yīng)算法（BFD Best Fit Decreasing Algorithm）。動(dòng)態(tài)是指按照數(shù)據(jù)的先后順序進(jìn)行輸入裝箱，不知道后面數(shù)據(jù)的具體情況，即數(shù)據(jù)到達(dá)便直接進(jìn)行裝箱，不考慮后續(xù)數(shù)據(jù)情況[11]；反之，靜態(tài)是指需要被裝箱的數(shù)據(jù)個(gè)數(shù)和大小全部是已知的，從而按照一定的策略進(jìn)行最優(yōu)裝箱。裝箱算法的靜態(tài)算法效率要優(yōu)于動(dòng)態(tài)算法，能在較短時(shí)間內(nèi)提供最優(yōu)解決策略。動(dòng)態(tài)算法更為實(shí)際，在局部范圍內(nèi)可以取得最優(yōu)解。常見近似算法及運(yùn)算過(guò)程如下：（1）首次適應(yīng)算法：從空閑存儲(chǔ)區(qū)的開頭開始檢索，將最先能夠容納數(shù)據(jù)的區(qū)域分給該數(shù)據(jù)，這種算法的優(yōu)點(diǎn)是可以大大減少查找所消耗的時(shí)間[12， 13]。（2）下次適應(yīng)算法：在分配數(shù)據(jù)時(shí)需要記住前一次分配數(shù)據(jù)的位置，然后實(shí)施分配時(shí)從該位置后開始查找一個(gè)合適的空閑存儲(chǔ)區(qū)[14]。（3）最佳適應(yīng)算法：該算法過(guò)程與首次適應(yīng)算法相似，區(qū)別在于數(shù)據(jù)不是存儲(chǔ)在最先能夠容納它的存儲(chǔ)區(qū)，而是存儲(chǔ)在最適合該數(shù)據(jù)的存儲(chǔ)區(qū)，如果沒有合適的存儲(chǔ)區(qū)，則存儲(chǔ)在下一塊空閑存儲(chǔ)區(qū)。這種算法的優(yōu)點(diǎn)是既可以滿足存儲(chǔ)空間需求，又盡可能少地占用空閑存儲(chǔ)區(qū)。這樣使得空閑存儲(chǔ)區(qū)被分配數(shù)據(jù)后，剩下的空間盡可能小，使得內(nèi)存利用率最大化[15]。（4）降序首次適應(yīng)算法：首先按照數(shù)據(jù)容量對(duì)數(shù)據(jù)進(jìn)行降序排序，然后按照首次適應(yīng)算法對(duì)數(shù)據(jù)進(jìn)行裝箱存儲(chǔ)處理。（5）降序最佳適應(yīng)算法：首先按照數(shù)據(jù)容量對(duì)數(shù)據(jù)進(jìn)行降序排序，然后按照最佳適應(yīng)算法對(duì)數(shù)據(jù)進(jìn)行裝箱存儲(chǔ)處理。舉例對(duì)上述5種裝箱算法過(guò)程進(jìn)行描述。假設(shè)箱容量為10，項(xiàng)目列表中項(xiàng)目大小分別為：8，4，2，3，7，3，6，5。分別運(yùn)用上述算法將項(xiàng)目列表中的項(xiàng)目裝入箱中，結(jié)果如圖1所示。

圖1 不同裝箱算法過(guò)程

如圖1所示，裝箱算法靜態(tài)算法的運(yùn)算結(jié)果要優(yōu)于動(dòng)態(tài)算法，但在實(shí)際應(yīng)用中經(jīng)常要面對(duì)動(dòng)態(tài)環(huán)境，故動(dòng)態(tài)環(huán)境下運(yùn)用靜態(tài)算法來(lái)處理數(shù)據(jù)值得深入研究，可以高效地對(duì)海量數(shù)據(jù)進(jìn)行最優(yōu)處理，并明顯提高內(nèi)存利用率。

動(dòng)態(tài)規(guī)劃算法DP（Dynamic Programming Algorithm）是一種多階段最優(yōu)化決策解決問(wèn)題的過(guò)程[16-17]，其基本思想與MapReduce并行計(jì)算模型相似，即將原問(wèn)題分解為相似的子問(wèn)題，在求解過(guò)程中通過(guò)子問(wèn)題的解求出原問(wèn)題的解。主要優(yōu)勢(shì)在于可以避免重復(fù)計(jì)算，可以在獲得問(wèn)題最優(yōu)解的同時(shí)有效降低時(shí)間復(fù)雜度。針對(duì)動(dòng)態(tài)規(guī)劃算法本文給出如下描述：

任意給定一個(gè)含有M數(shù)據(jù)項(xiàng)目的序列：S1，S2，S3…Sm，使得0≤i≤1。數(shù)據(jù)元素i開始，到元素j為止所有元素構(gòu)成的子段有多個(gè)，選擇所有子段中子段和最大的子段。則動(dòng)態(tài)規(guī)劃算法可以表示為：

Sj=max1≤i≤j∑jk=iak（2）

其中，1≤j≤m。如果S[j-1]>0，那么S[j]=S[j-1]+a[j]；如果S[j-1]≤0，那么S[j]=a[j]。舉例對(duì)動(dòng)態(tài)規(guī)劃算法過(guò)程進(jìn)行描述。假設(shè)箱容量為10，項(xiàng)目列表中項(xiàng)目大小分別為：8，4，2，3，7，3，2，5。運(yùn)用動(dòng)態(tài)規(guī)劃算法將項(xiàng)目列表中的項(xiàng)目進(jìn)行裝箱，結(jié)果如圖2所示。

圖2 動(dòng)態(tài)規(guī)劃算法裝箱過(guò)程示意圖

由圖2可知，運(yùn)用動(dòng)態(tài)規(guī)劃算法顯然可以使得在盡可能短的時(shí)間內(nèi)獲得最優(yōu)局部最優(yōu)解。在MapReduce計(jì)算模式下，用戶設(shè)定一個(gè)Map函數(shù)，將原數(shù)據(jù)分解成一批鍵值對(duì)作為輸入，計(jì)算產(chǎn)生一批中間結(jié)果鍵值對(duì)，然后通過(guò)設(shè)定的另一個(gè)函數(shù)Reduce將所有的中間結(jié)果按照相同的key值進(jìn)行合并處理，從而得到最終結(jié)果，MapReduce處理大數(shù)據(jù)集的過(guò)程如圖3所示。MapReduce框架函數(shù)方程如下：

Map：→（3）

Reduce：→（4）

數(shù)據(jù)集通過(guò)Map函數(shù)被分解成一批鍵值對(duì)，通過(guò)合并key值產(chǎn)生一個(gè)列表。

圖3 MapReduce處理大數(shù)據(jù)集的過(guò)程

本文主要針對(duì)海量數(shù)據(jù)裝箱問(wèn)題運(yùn)用基于MapReduce的FFD算法和DP算法進(jìn)行研究。

2 算法描述

2.1 基于MapReduce的FFD裝箱算法設(shè)計(jì)

在動(dòng)態(tài)環(huán)境中，設(shè)置一個(gè)緩沖區(qū)，將所有輸入數(shù)據(jù)項(xiàng)目逐一輸入到這個(gè)緩沖區(qū)，當(dāng)緩沖區(qū)裝滿數(shù)據(jù)項(xiàng)目時(shí)，將其提交給MapReduce的主節(jié)點(diǎn)進(jìn)行Map和Reduce操作處理，同時(shí)緩沖區(qū)開始接收數(shù)據(jù)，準(zhǔn)備再次向MapReduce主節(jié)點(diǎn)進(jìn)行傳輸。如此設(shè)計(jì)的優(yōu)點(diǎn)在于使裝箱算法在動(dòng)態(tài)環(huán)境下具備靜態(tài)算法的優(yōu)點(diǎn)，故本算法設(shè)計(jì)可以對(duì)海量并發(fā)數(shù)據(jù)進(jìn)行高效裝箱處理，提高系統(tǒng)利用率?；贛apReduce的FFD裝箱算法的步驟如下：

（1）輸入。緩沖區(qū)接收需要處理的數(shù)據(jù)集，根據(jù)已收集的數(shù)據(jù)輸入箱容量和數(shù)量。當(dāng)緩沖區(qū)接收滿數(shù)據(jù)，將數(shù)據(jù)提交至MapReduce主節(jié)點(diǎn)。（2）Map。將被提交的數(shù)據(jù)集傳輸?shù)礁饔成涔?jié)點(diǎn)，每個(gè)映射節(jié)點(diǎn)都獨(dú)立對(duì)數(shù)據(jù)集進(jìn)行處理。將特定箱容量的數(shù)據(jù)項(xiàng)目列表提取出來(lái)，并使用快速排序?qū)α斜磉M(jìn)行升序排序。將箱容量作為key，然后將排序好的項(xiàng)目列表作為value。（3）合并列表。將Map處理后產(chǎn)生的鍵值對(duì)在本地按照鍵值進(jìn)行合并，并對(duì)其進(jìn)行升序排序。將產(chǎn)生的結(jié)果輸入到Reduce處理階段。（4）Reduce。Reduce節(jié)點(diǎn)將上階段完成排序的映射項(xiàng)目列表作為輸入。Reduce在此處運(yùn)用降序首次適應(yīng)算法，將輸入數(shù)據(jù)進(jìn)行裝箱。由于特定大小的箱中數(shù)據(jù)項(xiàng)目已排序，所以此階段得到的結(jié)果是已提交數(shù)據(jù)的最佳裝箱方案。經(jīng)過(guò)MapReduce對(duì)算法進(jìn)行優(yōu)化，產(chǎn)生的結(jié)果包括箱容量和裝箱后箱子最優(yōu)分配列表。算法偽代碼如圖4所示。

2.2 基于MapReduce的DP裝箱算法設(shè)計(jì)

該算法與FFD裝箱算法的算法步驟相同，唯一的區(qū)別在于Reduce階段使用了動(dòng)態(tài)規(guī)劃算法。算法偽代碼如圖5所示。

2.3 算法分析

由于兩種算法中設(shè)置的箱子大小為可變，可以理解為箱子大小總是與物體剛好合適。這樣在裝箱過(guò)程中，可以獲得良好的利用空間。即使箱子大小上限會(huì)因系統(tǒng)的設(shè)置對(duì)空間利用造成一定影響，但在處理海量數(shù)據(jù)的過(guò)程中依然可以很好地利用存儲(chǔ)空間。這種設(shè)計(jì)思想來(lái)源于，在裝箱過(guò)程中往往預(yù)先設(shè)定了箱子大小，然后考慮物品如何進(jìn)行裝箱。如果存在一種箱子，其大小可變，總是可以與將要處理的物品大小相同，那么當(dāng)物品輸入開始進(jìn)行處理時(shí)，便可以直接進(jìn)行裝箱處理，且具有較高的空間利用率。其時(shí)間復(fù)雜度分析如下：基于MapReduce的FFD裝箱算法在Map階段使用了快速排序，因此其復(fù)雜度為O（nlogn），其中n為每個(gè)key對(duì)應(yīng)的項(xiàng)目數(shù)。在Reduce階段，將非遞減項(xiàng)目列表分配到特定的箱子中，本文使用降序首次適應(yīng)算法，所以Reduce階段的復(fù)雜度為O（n）。假設(shè)一共有m個(gè)箱子，則兩個(gè)階段整體復(fù)雜度為：

F（n）=m（O（nlogn）+O（n））（5）

在并行計(jì)算模式下，假設(shè)在Hadoop框架中設(shè)置了N個(gè)節(jié)點(diǎn)，算法中設(shè)置了x個(gè)Mapper和y個(gè)Reducer，則算法復(fù)雜度為：

F（n）=O（mnlognNx）+O（mnNy）（6）

可化簡(jiǎn)為：

F（n）=O（nlogn）（mNx）+O（n）（mNy）（7）

可以看出，算法運(yùn)行時(shí)間與節(jié)點(diǎn)數(shù)量成反比，并且與Mapper和Reducer的個(gè)數(shù)成線性關(guān)系。由于算法主要計(jì)算在Map階段，所以通過(guò)增加節(jié)點(diǎn)和Mapper的個(gè)數(shù)可以在短時(shí)間內(nèi)獲得更好的結(jié)果。計(jì)算基于MapReduce的DP裝箱算法的復(fù)雜度，其在Map階段使用了快速排序，復(fù)雜度為O（nlogn），n為每個(gè)key對(duì)應(yīng)的項(xiàng)目數(shù)。在Reduce階段，將非遞減項(xiàng)目列表分配到特定的箱子中使用了動(dòng)態(tài)規(guī)劃算法，其復(fù)雜度為O（n2）。假設(shè)一共有m個(gè)箱子，則整體復(fù)雜度為：

F（n）=m（O（nlogn）+O（n2））（8）

同樣，在并行計(jì)算模式下，假設(shè)在Hadoop框架中設(shè)置了N個(gè)節(jié)點(diǎn)，算法中設(shè)置了x個(gè)Mapper和y個(gè)Reducer，則算法復(fù)雜度為：

F（n）=O（mnlognNx）+O（mn2Ny）（9）

可化簡(jiǎn)為：

F（n）=O（nlogn）（mNx）+O（n2）（mNy）（10）

可以看出，兩種算法運(yùn)行時(shí)間均與節(jié)點(diǎn)數(shù)量成反比，與Mapper和Reducer的個(gè)數(shù)成線性關(guān)系。由于動(dòng)態(tài)規(guī)劃算法中主要的計(jì)算在Reduce階段完成，所以通過(guò)增加節(jié)點(diǎn)和Reducer的個(gè)數(shù)可以在短時(shí)間內(nèi)獲得更好的結(jié)果。

本文通過(guò)實(shí)驗(yàn)設(shè)置不同的節(jié)點(diǎn)個(gè)數(shù)，并且設(shè)置不同的Mapper和Reducer個(gè)數(shù)，將兩種算法進(jìn)行對(duì)比。實(shí)驗(yàn)結(jié)果表明，兩種算法運(yùn)行時(shí)間均與節(jié)點(diǎn)數(shù)量成反比，與Mapper和Reducer的個(gè)數(shù)成線性關(guān)系。

3 實(shí)驗(yàn)結(jié)果

本文所作算法研究的實(shí)驗(yàn)環(huán)境建立在虛擬機(jī)集群上，所提算法在Hadoop集群上運(yùn)行測(cè)試。Hadoop集群有10臺(tái)機(jī)器構(gòu)成，其中1臺(tái)作為主節(jié)點(diǎn)，其余的作為分節(jié)點(diǎn)，電腦配置均為奔騰雙核、4G內(nèi)存，操作系統(tǒng)為L(zhǎng)inux，Hadoop版本為hadoop-0.20.2，Java版本為JDK1.6.0_37。

實(shí)驗(yàn)?zāi)M動(dòng)態(tài)環(huán)境，隨機(jī)選取若干10K到10MB的圖像數(shù)據(jù)作為輸入，箱容量設(shè)置為接收數(shù)據(jù)的數(shù)量為100個(gè)。分別設(shè)定1，4，8個(gè)節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)先設(shè)置為默認(rèn)的2Mapper-2Reducer，然后分別運(yùn)用兩種算法進(jìn)行實(shí)驗(yàn)。然后設(shè)定2個(gè)節(jié)點(diǎn)，分別設(shè)置每個(gè)節(jié)點(diǎn)，部署2Mapper-4Reducer和4mapper-2Reducer，對(duì)本文提出的兩種算法進(jìn)行實(shí)驗(yàn)。

本文運(yùn)用傳統(tǒng)FFD算法和DP算法對(duì)上述數(shù)據(jù)進(jìn)行實(shí)驗(yàn)，與本文所提的基于MapReduce的FFD算法和DP算法對(duì)系統(tǒng)內(nèi)存利用率進(jìn)行比較。

由表1可知，兩種算法在對(duì)海量數(shù)據(jù)進(jìn)行裝箱處理時(shí)，隨著設(shè)置節(jié)點(diǎn)的增加，運(yùn)行時(shí)間縮短，并且隨著數(shù)據(jù)量的增加，時(shí)間縮短越來(lái)越明顯。在面對(duì)海量數(shù)據(jù)的情況下，本文所提兩種算法均可以通過(guò)增加節(jié)點(diǎn)來(lái)縮短運(yùn)行時(shí)間，提高數(shù)據(jù)處理效率。

通過(guò)上文對(duì)兩種算法復(fù)雜度的分析，由表2和表3可知，在節(jié)點(diǎn)不變的情況下，增加Reducer數(shù)量時(shí)，基于MapReduce的DP裝箱算法處理海量數(shù)據(jù)運(yùn)行時(shí)間將大大縮短，相比FFD算法更高效。同樣，在增加Mapper數(shù)量時(shí)，基于MapReduce的FFD裝箱算法處理海量數(shù)據(jù)運(yùn)行時(shí)間大大縮短，相比DP算法更高效。

由圖6可以看出，本文所提基于MapReduce的FFD算法和DP算法在對(duì)海量數(shù)據(jù)進(jìn)行處理時(shí)，相比傳統(tǒng)FFD算法和DP算法可以獲得較高的系統(tǒng)內(nèi)存利用率。

綜上，本文所述兩種算法可以高效地對(duì)海量數(shù)據(jù)進(jìn)行處理，具有很好的系統(tǒng)內(nèi)存利用率。同時(shí)，減少處理時(shí)間，有效地降低了時(shí)間成本，并且通過(guò)算法復(fù)雜度分析和實(shí)驗(yàn)驗(yàn)證了兩種算法運(yùn)行效率與節(jié)點(diǎn)數(shù)量設(shè)置，以及節(jié)點(diǎn)上Mapper和Reducer的數(shù)量設(shè)置均有關(guān)聯(lián)。根據(jù)實(shí)際情況，通過(guò)調(diào)整節(jié)點(diǎn)數(shù)量和Mapper-Reducer數(shù)量可以使該算法處理海量數(shù)據(jù)得到最優(yōu)結(jié)果。

4 結(jié)語(yǔ)

本文針對(duì)已有裝箱算法在處理海量數(shù)據(jù)時(shí)所存在的時(shí)空效率較低的問(wèn)題，在深入調(diào)研已有算法的基礎(chǔ)之上，結(jié)合在線、離線兩種算法的優(yōu)勢(shì)，提出了基于MapReduce的并行裝箱算法，并在Hadoop集群上進(jìn)行了實(shí)測(cè)驗(yàn)證，結(jié)果良好。本文所提可變大小的箱子，對(duì)于裝箱算法的研究有很好的啟發(fā)，具有研究空間。本文研究尚處在初級(jí)階段，所提算法只能應(yīng)用于一維裝箱場(chǎng)景中，而且成果只達(dá)到局部最優(yōu)，二維或多維以及近似全局最優(yōu)是未來(lái)研究的重點(diǎn)。

參考文獻(xiàn)：

[1] 王珊， 王會(huì)舉， 覃雄派等.架構(gòu)大數(shù)據(jù)： 挑戰(zhàn)、現(xiàn)狀與展望[J].計(jì)算機(jī)學(xué)報(bào)， 2011，34（10）：1741-1751.

[2] CHUCK LAM. Hadoop實(shí)戰(zhàn)[M].韓冀中譯.北京： 人民郵電出版社， 2011.

[3] 劉鵬.實(shí)戰(zhàn)Hadoop（第二版）[M].北京： 電子工業(yè)出版社， 2011.

[4] 陳建新， 楊宇航， 龔玲等.兩種在線裝箱算法[J].計(jì)算機(jī)工程， 2006，32（13）： 4-6.

[5] 邵飛牛.一維裝箱問(wèn)題啟發(fā)式算法的設(shè)計(jì)與分析[D].沈陽(yáng)： 東北大學(xué)信息科學(xué)與工程學(xué)院， 2013.

[6] ROLICH T. Testing of several overlapping optimization methods for bin-packing problem[C]. Information & Communication Technology Electronics & Microelectronics （MIPRO）， Opatija， 2013. Croatia： Hrvatska， 2013： 975-980.

[7] COFFMAN E G， GAREY J M R， JOHNSON D S. Approximation algorithms for bin packing：a survey[M]. Approximation Algorithms for NP-Hard Problems， Boston： PSW publish， 1997.

[8] ANIKA， GARG D. Parallelizing generalized one-dimensional bin packing problem using MapReduce[C]. 2014 IEEE International Conference on Advance Computing Conference （IACC）， Gurgaon， 2014. India： ITM University India， 2014： 628-635.

[9] LEAH EPSTEIN，LENE M，F(xiàn)AVRHOLDT， et al.Comparing online algorithms for bin packing problems[J]. Journal of Scheduling，2012.

[10] LI LUO，YANG YOU. Surgical scheduling based on offline bin-packing[C]. Service Systems and Service Management （ICSSSM）， Shanghai，China： Economics & Management School， Tongji University， 2012： 491-494.

[11] LEAH EPSTEIN， ROB VAN STEE.Optimal online algorithms for multidimensional packing problem[J].SIAM Journal on Computing，2005.

[12] 馬玉玲.遺傳算法在物流業(yè)裝箱環(huán)節(jié)中的應(yīng)用研究[D].濟(jì)南：山東大學(xué)，2008.

[13] 楊雙全.虛擬化動(dòng)態(tài)資源調(diào)度的算法設(shè)計(jì)與系統(tǒng)實(shí)現(xiàn)[D].杭州： 浙江大學(xué)，2012.

[14] 田愛雪.基于海量數(shù)據(jù)存儲(chǔ)的性能測(cè)試與優(yōu)化研究[D].長(zhǎng)春：長(zhǎng)春理工大學(xué)，2014.

[15] 邰建華.Hadoop平臺(tái)下的海量數(shù)據(jù)存儲(chǔ)技術(shù)研究[D].大慶： 東北石油大學(xué)， 2012.

[16] 張瑩.動(dòng)態(tài)規(guī)劃算法綜述[J].科技視界，2014，28（10）：126.

[17] 吳海洋，程國(guó)建，趙坤鵬，等.基于動(dòng)態(tài)規(guī)劃的整車物流裝載方案優(yōu)化研究[J].電腦知識(shí)與技術(shù)，2014，33（10）：8046-8050.

（責(zé)任編輯：陳福時(shí)）