◆劉順程 岳思穎 李楠鍵
基于背包問題與貪心算法的高效數(shù)據(jù)整合系統(tǒng)
◆劉順程 岳思穎 李楠鍵
(重慶郵電大學(xué)軟件工程學(xué)院 重慶 400065)
隨著互聯(lián)網(wǎng)+時代的到來,各行各業(yè)為使其業(yè)務(wù)更易于管理,紛紛將數(shù)據(jù)以及結(jié)構(gòu)化報表通過計算機(jī)進(jìn)行動態(tài)生成;這使得如何高效處理數(shù)據(jù)并生成結(jié)構(gòu)化體系成為了當(dāng)務(wù)之急,比如生成線上考試試卷、商品的規(guī)格參數(shù)列表、公司流程報表等。本文以高效數(shù)據(jù)整合算法為研究重點,分別介紹了傳統(tǒng)數(shù)據(jù)整合的方法與缺陷,同時重點介紹了基于背包問題與貪心算法的高效數(shù)據(jù)整合算法——一種更高效安全的數(shù)據(jù)整合框架。
背包問題;貪心算法;數(shù)據(jù)整合;容器組件
隨著互聯(lián)網(wǎng)的普及,黨和國家號召充分利用互聯(lián)網(wǎng)資源,使得將各行各業(yè)的紙質(zhì)化資料進(jìn)行網(wǎng)絡(luò)化、虛擬化成為了趨勢。當(dāng)前傳統(tǒng)的數(shù)據(jù)整合方法在高并發(fā)環(huán)境中由于效率較低,易導(dǎo)致服務(wù)器系統(tǒng)崩潰。于是,基于背包問題與貪心算法的高效數(shù)據(jù)整合系統(tǒng)應(yīng)運(yùn)而生。
貪心算法的基本思路是從問題的某一個初始解出發(fā)一步一步地進(jìn)行,根據(jù)某個優(yōu)化測度,每一步都要確保能獲得局部最優(yōu)解。每一次只考量一個數(shù)據(jù),是否選取該數(shù)據(jù)取決于是否滿足局部最優(yōu)的條件,直到把所有的數(shù)據(jù)枚舉完成,或者滿足了某優(yōu)化條件后,算法終止。從全局看來,每種選擇方案依賴于已作出的選擇,而不依賴于未作出的選擇;因此最終的結(jié)果也成為了該問題的最優(yōu)方案[1]。
背包問題是一種組合優(yōu)化的NP完全問題。問題可以簡單描述為:給定一組物品和一個背包,每個物品有其對應(yīng)的重量和價值,而背包則有其所能裝載重量的上限。因此,我們要通過合理選擇來使得在不超過背包裝載量的上限下,背包所裝載物品的價值盡可能地大。背包問題可以抽象成一個容器-物品填充模型,即當(dāng)前可供選擇的物品中,能否通過合理選擇,使得容器被填滿且其承載價值達(dá)到最大[2]。
在傳統(tǒng)數(shù)據(jù)整合方案中,常常使用某種單一的數(shù)據(jù)類為物品,需求結(jié)構(gòu)體為容器,來進(jìn)行自動化數(shù)據(jù)組合生成需求結(jié)構(gòu)。首先構(gòu)建結(jié)構(gòu)體容器,使用相應(yīng)約束條件定義背包容量,隨后以每條數(shù)據(jù)的特性來進(jìn)行容器填充,當(dāng)容器中的約束條件達(dá)到預(yù)設(shè)值后,數(shù)據(jù)組合成功;若在遍歷完所有數(shù)據(jù)后仍沒有達(dá)到背包容器預(yù)設(shè)值,則數(shù)據(jù)組合失敗。然后又將另一種數(shù)據(jù)類定義為物品,相應(yīng)需求結(jié)構(gòu)體為容器,繼續(xù)進(jìn)行上述操作,直到將所有的結(jié)構(gòu)體所需的數(shù)據(jù)填充完成,數(shù)據(jù)整合結(jié)束。
隨著大數(shù)據(jù)時代的來臨,這種傳統(tǒng)方案暴露出了組合效率低下、存在線程死鎖風(fēng)險等諸多問題。例如,在實驗環(huán)境中,數(shù)據(jù)類物品存放于內(nèi)存中,遍歷數(shù)據(jù)能迅速完成;但是在實際生產(chǎn)環(huán)境中,數(shù)據(jù)類物品存放于數(shù)據(jù)庫中。相比于內(nèi)存讀取,數(shù)據(jù)庫的讀取速度是及其緩慢的;面對實際環(huán)境中的多線程、高并發(fā)的服務(wù)操作,傳統(tǒng)數(shù)據(jù)組合算法會對數(shù)據(jù)庫進(jìn)行反復(fù)讀寫,這樣極易造成數(shù)據(jù)庫連接數(shù)達(dá)到上限,從而引起數(shù)據(jù)庫阻塞,程序線程死鎖等惡劣情況,導(dǎo)致整個系統(tǒng)崩潰。
本方案的基于背包問題與貪心算法的高效數(shù)據(jù)填充系統(tǒng),包括多背包容器組件、物品屬性組件、本地模擬填充組件和數(shù)據(jù)存儲組件。
多背包容器組件,用于將傳統(tǒng)背包方案的單個容器擴(kuò)充為多個容器用于數(shù)據(jù)填充中對多種數(shù)據(jù)結(jié)構(gòu)體的描述。比如在實際的數(shù)據(jù)整合過程中,我們所需的填充項一定不止一個。于是,我們使用多背包容器組件來描述整個數(shù)據(jù)填充項集合,使得單次運(yùn)行該算法即可完成所有的數(shù)據(jù)填充,避免了多次操作數(shù)據(jù)庫易引起的問題。
物品屬性組件,用于將傳統(tǒng)方案中的數(shù)據(jù)集轉(zhuǎn)化為虛擬物品,虛擬物品在初始化后,需要調(diào)用本地模擬填充模塊進(jìn)行屬性賦值。比如將容器所需的某種數(shù)據(jù)虛擬化為物品,而該物品屬性數(shù)量一定大于傳統(tǒng)背包物品的兩個屬性(V,W),所以我們需要調(diào)用本地模擬填充模塊進(jìn)行數(shù)據(jù)庫查詢,將數(shù)據(jù)物品項的屬性進(jìn)行賦值,使其得到多重屬性,以便完善后續(xù)的填充需求。
本地模擬填充組件,用于將傳統(tǒng)數(shù)據(jù)整合算法中,反復(fù)讀取數(shù)據(jù)庫來提取數(shù)據(jù)進(jìn)行容器填充的過程轉(zhuǎn)化為只進(jìn)行一次數(shù)據(jù)庫提取;獲取所有數(shù)據(jù)信息后,首先對物品屬性組件的每個物品進(jìn)行屬性填充,從而記錄整合時候每個結(jié)構(gòu)體應(yīng)具備的約束條件;隨后使用貪心算法,在本地容器組件中對容器進(jìn)行數(shù)據(jù)填充,填充規(guī)則按照容器定義以及物品屬性,并使用貪心算法根據(jù)屬性權(quán)值進(jìn)行優(yōu)先集填充;直到所有的容器填充完成,本地模擬填充結(jié)束。
數(shù)據(jù)存儲組件,用于將傳統(tǒng)整合算法中通過模塊約束條件在數(shù)據(jù)庫中選取數(shù)據(jù)并進(jìn)行數(shù)據(jù)庫存儲轉(zhuǎn)化為通過本地模擬填充容器保存的相關(guān)數(shù)據(jù)直接存儲在數(shù)據(jù)庫中;從而讓系統(tǒng)獲得數(shù)據(jù)整合結(jié)果,使得數(shù)據(jù)庫的讀取次數(shù)再次減少,提升程序運(yùn)行效率。
(1)通過需求結(jié)構(gòu)體構(gòu)造多個背包,并且設(shè)置為虛擬容器;
(2)向容器添加描述其屬性(如某某數(shù)據(jù)容器),直到所有虛擬容器添加完成;
(3)根據(jù)需求,創(chuàng)建單個或多個物品組件(使用容器完成),初始化物品組件的屬性均為Null;
(4)從數(shù)據(jù)庫讀取數(shù)據(jù)整合所需的所有相關(guān)數(shù)據(jù);
(5)根據(jù)數(shù)據(jù)與相關(guān)需求,將S3中創(chuàng)建的物品組件進(jìn)行屬性填充,為每個物品容器的屬性進(jìn)行賦值,直到所有物品組件填充完畢;
(6)根據(jù)背包問題,依照貪心算法,對S1中創(chuàng)建的背包容器進(jìn)行物品填充,以當(dāng)前容器指向的描述物品(屬性),對物品的當(dāng)前的屬性權(quán)值由高到低為策略繼續(xù)選擇,將選擇結(jié)果保存在當(dāng)前背包容器中;
(7)判斷本地模擬填充的背包容器是否滿足需求數(shù)據(jù)的約束。若滿足則準(zhǔn)備開始填充下一個背包容器執(zhí)行S8,否則執(zhí)行S9;
(8)判斷背包中所有容器是否填充完成,若完成則執(zhí)行S12,否則執(zhí)行S6;
(9)判斷在剩余的物品數(shù)據(jù)(當(dāng)前物品沒有匹配的屬性)中是否有物品集合可供選擇,若有執(zhí)行S10,否則執(zhí)行S11;
(10)調(diào)整該物品的屬性權(quán)值,允許背包容器進(jìn)行填充,執(zhí)行S6;
(11)拋出錯誤,算法運(yùn)行失敗,返回空值,系統(tǒng)結(jié)束;
(12)將本地模擬填充模塊填充完成的背包容器數(shù)據(jù),存儲在數(shù)據(jù)庫中;
(13)所有調(diào)用完成,系統(tǒng)結(jié)束。
進(jìn)入互聯(lián)網(wǎng)+時代,眾多行業(yè)都需要更高效精準(zhǔn)的數(shù)據(jù)管理方案?;诒嘲鼏栴}與貪心算法的高效數(shù)據(jù)整合系統(tǒng),能將數(shù)據(jù)集進(jìn)行自動整合并提供更安全、更高效的解決方案,同時有效解決了傳統(tǒng)方案中存在的安全隱患。相信該系統(tǒng)在未來的大數(shù)據(jù)領(lǐng)域中會得到更好的發(fā)展。
[1]常友渠,肖貴元,曾敏.貪心算法的探討與研究[J].重慶電力高等專科學(xué)校學(xué)報,2008.
[2]史今馳.背包問題的實用求解算法研究[D].山東;山東大學(xué),2005.