基于內(nèi)存映射文件的進(jìn)化算法數(shù)據(jù)存儲(chǔ)引擎

1、基于內(nèi)存映射文件的進(jìn)化算法數(shù)據(jù)存儲(chǔ)引擎姜三義，代真真，李陽，周愛民JIANG Sanyi, DAI Zhenzhen, LI Yang, ZHOU Aimin華東師范大學(xué) 計(jì)算機(jī)科學(xué)技術(shù)系，上海 200241Department of Computer Science & Technology, East China Normal University, Shanghai 200241, ChinaJIANG Sanyi, DAI Zhenzhen, LI Yang, et al. Data storage engine based on memory-mapped file for

2、evolutionary algorithms. Computer Engineering and Applications, 2015, 51（1）：49-53.Abstract：In order to observe and analyze the execution of Evolutionary Algorithms（EAs）, large volumes of data generatedduring algorithm execution are always stored in disk files. An embedded data storage engine, named

3、as the Evolutionary Algorithm Database（EADB）, provides simple yet flexible data storage interfaces for evolutionary algorithms, and facilitates fast large data storage by using memory-mapped files. Compared to storage methods using traditional file I/O and general database storage engine, EADB is tr

4、emendous faster.Key words：evolutionary algorithm; memory-mapped file; data storage engine; file I/O摘 要：為了觀察和分析進(jìn)化算法的執(zhí)行情況，往往需要將算法執(zhí)行過程中產(chǎn)生的大量數(shù)據(jù)存儲(chǔ)在磁盤文件中。用于 進(jìn) 化 算 法 的 嵌 入 式 數(shù) 據(jù) 存 儲(chǔ) 引 擎 EADB（Evolutionary Algorithm Database）提 供 了 簡(jiǎn) 便 靈 活 的 數(shù) 據(jù) 存 儲(chǔ) 接 口 ，通 過使用內(nèi)存映射文件技術(shù)來實(shí)現(xiàn)數(shù)據(jù)的快速和大量存儲(chǔ)。相較于傳統(tǒng)文件 I/O 存儲(chǔ)方式和一般的通用數(shù)據(jù)存儲(chǔ)引

5、擎，EADB 大大加快了存儲(chǔ)速度。關(guān)鍵詞：進(jìn)化算法；內(nèi)存映射文件；數(shù)據(jù)存儲(chǔ)引擎；文件 I/O文獻(xiàn)標(biāo)志碼：A中圖分類號(hào)：TP311doi：10.3778/j.issn.1002-8331.1303-01661引言基 于 統(tǒng) 計(jì) 和 機(jī) 器 學(xué) 習(xí) 的 進(jìn) 化 算 法 目 前 日 益 引 起 人 們的重視。進(jìn)化算法1是一種通過多次迭代搜索來獲取 全局最優(yōu)解的隨機(jī)優(yōu)化算法2。作為一類啟發(fā)式搜索算 法 ，是 否 具 備 良 好 的 搜 索 記 憶 功 能 ，即 通 過 一 定 方 式 存 儲(chǔ) 并 利 用 已 搜 索 的 解 空 間 ，是 評(píng) 價(jià) 算 法 好 壞 的 關(guān) 鍵 之 一。從本質(zhì)上來說，進(jìn)化算

6、法維護(hù)的種群和其他信息實(shí) 際 上 可 以 看 作 是 一 個(gè) 動(dòng) 態(tài) 變 化 的 數(shù) 據(jù) 集（數(shù) 據(jù) 庫）。 當(dāng) 前及歷史數(shù)據(jù)集隱含了進(jìn)化算法搜索的規(guī)律，因此可以 通 過 模 式 識(shí) 別 和 機(jī) 器 學(xué) 習(xí) 的 方 法 來 挖 掘 隱 含 在 這 些 數(shù) 據(jù) 集 中 的 規(guī) 律 并 指 導(dǎo) 進(jìn) 化 算 法 的 搜 索 。 有 效 存 儲(chǔ) 和 組 織當(dāng)前和歷史群體信息，是實(shí)現(xiàn)這類算法的前提。由于進(jìn)化算法的搜索空間往往比較大，存儲(chǔ)記憶時(shí) 需要平衡算法效率和磁盤空間3。隨著計(jì)算機(jī)磁盤容量的迅速增長(zhǎng)和單位容量成本的降低，可以將更多的算法數(shù)據(jù)存儲(chǔ)到磁盤中。但是在性能上，現(xiàn)有的通用數(shù)據(jù)庫 技 術(shù) 或 傳

7、統(tǒng) 文 件 存 儲(chǔ) 方 式 并 不 能 很 好 地 滿 足 這 種 需 求。使用通用數(shù)據(jù)庫時(shí)，需要額外搭建專有的數(shù)據(jù)服務(wù) 系 統(tǒng) ，進(jìn) 行 數(shù) 據(jù) 庫 維 護(hù) ，并 且 由 于 數(shù) 據(jù) 庫 索 引 等 機(jī) 制 的 存在，數(shù)據(jù)庫對(duì)于大量實(shí)時(shí)算法數(shù)據(jù)的存儲(chǔ)效率并不理 想 。 算 法 設(shè) 計(jì) 人 員 因 而 往 往 將 數(shù) 據(jù) 以 文 件 的 形 式 直 接 存 儲(chǔ) 到 磁 盤 上 。 由 于 磁 盤 I/O 的 效 率 問 題 ，采 用 傳 統(tǒng) 文 件 方 式 保 存 數(shù) 據(jù) 會(huì) 大 量 增 加 算 法 的 執(zhí) 行 時(shí) 間 。 現(xiàn) 代 操 作 系 統(tǒng) 支 持 基 于 虛 擬 內(nèi) 存 技 術(shù) 的 內(nèi)

8、 存 映 射 文 件 機(jī) 制 。 通 過 使 用 內(nèi) 存 映 射 文 件 ，存 儲(chǔ) 速 度 相 比 于 傳 統(tǒng) 文 件 I/O 方式可以得到極大提升4。內(nèi) 存 映 射 是 將 磁 盤 上 的 文 件 或 部 分 文 件 內(nèi) 容 映 射到 進(jìn) 程 地 址 空 間 內(nèi) 部 區(qū) 域 的 一 種 機(jī) 制 。 通 過 創(chuàng) 建 內(nèi) 存基金項(xiàng)目：國家自然科學(xué)基金（No.61273313）。作者簡(jiǎn)介：姜三義（1981），男，碩士研究生，研究領(lǐng)域?yàn)檫M(jìn)化算法，圖像處理；代真真（1987），碩士研究生，研究領(lǐng)域?yàn)檫M(jìn)化計(jì) 算，實(shí)驗(yàn)設(shè)計(jì)；李陽（1989），碩士研究生，研究領(lǐng)域?yàn)檫M(jìn)化計(jì)算；周愛民（1978），副教授，主研

9、領(lǐng)域?yàn)檫M(jìn)化計(jì)算，機(jī)器 學(xué)習(xí)。E-mail：sanyi0127收稿日期：2013-03-14修回日期：2013-06-04文章編號(hào)：1002-8331（2015）01-0049-05CNKI 網(wǎng)絡(luò)優(yōu)先出版：2013-06-26, 502015，51（1）Computer Engineering and Applications 計(jì)算機(jī)工程與應(yīng)用映射文件，應(yīng)用程序可以直接讀寫內(nèi)存來訪問磁盤文件數(shù) 據(jù) ，相 比 于 使 用 文 件 的 讀 寫 函 數(shù) 具 有 更 快 的 I/O 速 度 。 在 Windows 和 Linux 操 作 系 統(tǒng) 中 都 支 持 內(nèi) 存 映 射 文 件 機(jī) 制 ，通 過

10、使 用 系 統(tǒng) 提 供 的 編 程 接 口 ，應(yīng) 用 程 序 可 以利用內(nèi)存映射機(jī)制提高 I/O 效率。內(nèi)存映射文件可以被直接應(yīng)用于程序中，對(duì)于一些 簡(jiǎn) 單 的 程 序 是 完 全 可 行 的 。 但 是 在 進(jìn) 行 復(fù) 雜 數(shù) 據(jù) 結(jié) 構(gòu) 的存儲(chǔ)組織，并且需要確保大量數(shù)據(jù)和文件的可靠和安 全 時(shí) ，需 要 進(jìn) 行 復(fù) 雜 的 代 碼 設(shè) 計(jì) 和 編 碼 調(diào) 試 工 作 ，以 解 決合理分配和動(dòng)態(tài)擴(kuò)展數(shù)據(jù)文件，存儲(chǔ)不同數(shù)據(jù)結(jié)構(gòu)等 問 題 ，這 對(duì) 程 序 編 碼 人 員 提 出 了 很 高 的 要 求 ，在 很 大 程 度上限制了內(nèi)存映射文件技術(shù)被廣泛利用。本 文 介 紹 了 使 用 C +

11、編 程 語 言 實(shí) 現(xiàn) 的 嵌 入 式 數(shù) 據(jù) 存 儲(chǔ) 引 擎（EADB），EADB 利 用 內(nèi) 存 映 射 文 件 實(shí) 現(xiàn) 了 數(shù) 據(jù) 存 儲(chǔ) ，支 持 Linux 和 Windows 這 兩 個(gè) 不 同 平 臺(tái) ，提 供 統(tǒng)一的讀寫接口，支持復(fù)雜數(shù)據(jù)結(jié)構(gòu)的存儲(chǔ)組織。通過 使用 EADB，應(yīng)用程序在獲得 I/O 性能提升的同時(shí)，可以 減少編碼工作量。通過在進(jìn)化算法中使用 EADB，提高 了進(jìn)化算法執(zhí)行過程中的數(shù)據(jù)存儲(chǔ)效率。獨(dú)立的連續(xù)完整的地址空間。基于程序的局部性原理，操作系統(tǒng)僅將運(yùn)行進(jìn)程所必需的一部分指令裝入內(nèi)存， 在 進(jìn) 程 執(zhí) 行 時(shí) 通 過 請(qǐng) 求 調(diào) 入 和 置 換 功 能 進(jìn) 行

12、 內(nèi) 外 存 數(shù) 據(jù)交換，使進(jìn)程能夠持續(xù)運(yùn)行。虛 擬 內(nèi) 存 技 術(shù) 不 僅 僅 解 決 了 物 理 內(nèi) 存 容 量 不 足 的 問題，它的出現(xiàn)使得操作系統(tǒng)發(fā)生了巨大的變化。當(dāng)今 大 部 分 操 作 系 統(tǒng)（包 括 Windows 和 Linux）在 I/O 系 統(tǒng) 中 均 采 用 了 文 件 緩 存 機(jī) 制（在 Windows 中 稱 為 系 統(tǒng) 緩 存 ， 在 Linux 中稱為頁面緩存），在內(nèi)核虛擬地址空間中分配 一 個(gè) 分 段 用 于 文 件 數(shù) 據(jù) 緩 存 。 操 作 系 統(tǒng) 進(jìn) 一 步 將 該 分 段劃分為塊，每一塊包含若干分頁（在 32 位 Windows 系 統(tǒng) 中 ，頁 面

13、大 小 是 4 KB，分 塊 大 小 是 256 KB；在 32 位 Linux 系 統(tǒng) 中 ，頁 面 大 小 是 4 KB，分 塊 大 小 也 是 4 KB）。在 訪 問 文 件 時(shí) ，操 作 系 統(tǒng) 始 終 按 塊 為 單 位（即 使 只 訪 問 一個(gè)字節(jié)數(shù)據(jù)）將文件數(shù)據(jù)拷貝到文件緩存中。當(dāng)文件 緩存中的頁面被調(diào)度到物理內(nèi)存中后，內(nèi)存與磁盤文件 之間建立了字節(jié)上一對(duì)一的關(guān)系，在頁內(nèi)的數(shù)據(jù)訪問都 是在物理內(nèi)存中完成的，避免了頻繁的文件 I/O，極大提 高 了 讀 寫 能 力 。 同 時(shí) ，由 于 虛 擬 內(nèi) 存 的“ 按 需 調(diào) 度 ”原 則 ，只 將 一 部 分 數(shù) 據(jù) 而 非 整 個(gè) 文

14、 件 調(diào) 入 內(nèi) 存 ，因 而 可 以12-13節(jié)約大量物理內(nèi)存 。內(nèi) 存 映 射 文 件 在 此 基 礎(chǔ) 上 進(jìn) 一 步 加 快 了 文 件 訪 問 速 度 。 使 用 傳 統(tǒng) 文 件 I/O 方 式 時(shí) ，仍 然 需 要 通 過 系 統(tǒng) 調(diào) 用（即 文 件 讀 寫 函 數(shù)）從 內(nèi) 核 空 間 將 數(shù) 據(jù) 復(fù) 制 到 用 戶 空 間，即讀操作使用的內(nèi)存緩沖區(qū)。而建立內(nèi)存映射文件 后，操作系統(tǒng)將進(jìn)程的虛擬頁面直接映射到系統(tǒng)文件緩 存上，使得進(jìn)程可以直接訪問這一部分內(nèi)存。通過建立 內(nèi) 存 映 射 文 件 ，一 方 面 避 免 了 使 用 系 統(tǒng) 調(diào) 用 ，訪 問 速 度 得 到 數(shù) 量 級(jí) 的

15、提 升 ；另 一 方 面 ，在 用 戶 空 間 中 無 需 對(duì) 文 件 內(nèi) 容 進(jìn) 行 緩 沖 ，不 僅 減 少 了 物 理 內(nèi) 存 復(fù) 制 工 作 ，還 節(jié)2算法記錄本 文 稱 進(jìn) 化 算 法 迭 代 過 程 中 產(chǎn) 生 的 解 為“ 算 法 記 錄 ”。 不 同 進(jìn) 化 算 法 的 執(zhí) 行 框 架 基 本 相 同 ，首 先 進(jìn) 行 種 群隨機(jī)初始化和個(gè)體適應(yīng)度計(jì)算，然后進(jìn)行有限次數(shù)的 迭 代 使 得 群 體 在 搜 索 空 間 中 不 斷 進(jìn) 化 。 每 一 次 迭 代 包 含的步驟包括：重組、變異、適應(yīng)值評(píng)估和選擇等。每一次迭代產(chǎn)生的解包含染色體、適應(yīng)值或其他信息5。 進(jìn)化算法的種群個(gè)體

16、（即染色體）可以表示為確定長(zhǎng)度的二進(jìn)制位串或格雷碼，也可以使用符號(hào)集、實(shí)數(shù)或?qū)?數(shù)數(shù)組來表示。進(jìn)化算法作為一類啟發(fā)式搜索算法，也被成功應(yīng)用于多目標(biāo)優(yōu)化領(lǐng)域6-7。每個(gè)種群個(gè)體的適應(yīng)值，在單目標(biāo)優(yōu)化和多目標(biāo)優(yōu)化問題中的表示方式是不 一 樣 的 。 在 單 目 標(biāo) 優(yōu) 化 問 題 中 ，適 應(yīng) 值 是 一 維 的 變 量 ； 而 在 多 目 標(biāo) 優(yōu) 化 問 題 中 ，適 應(yīng) 值 則 一 般 是 多 維 的 向 量 。 由此分析，算法記錄中的內(nèi)容在形式上包括一維變量和 多維向量，所以可以使用數(shù)組來統(tǒng)一存儲(chǔ)記錄內(nèi)容8-9。同 一 個(gè) 進(jìn) 化 算 法 在 每 一 次 迭 代 中 需 要 保 存 的 數(shù)

17、據(jù) 記錄的數(shù)量有可能不同，例如在基于分解技術(shù)的多目標(biāo) 進(jìn)化算法（Decomposition based Multi-Objective Evolu- tionary Algorithm，MOEA/D）求 解 背 包 問 題 的 算 法 中 ， 每一代最優(yōu)群體的個(gè)體數(shù)量可能是不同的10。但是，在 同一個(gè)進(jìn)化算法的一次執(zhí)行過程中，算法記錄的內(nèi)容在 結(jié)構(gòu)上是一致的。14省了一半的物理內(nèi)存空間 。內(nèi) 存 映 射 文 件 帶 來 的 另 一 個(gè) 優(yōu) 點(diǎn) 是 在 編 寫 數(shù) 據(jù) 存 儲(chǔ)程序的時(shí)候，在內(nèi)存及外存中只需要定義一套數(shù)據(jù)結(jié) 構(gòu)，可以直接將內(nèi)存映射區(qū)域中的數(shù)據(jù)看作程序中定義 的數(shù)據(jù)結(jié)構(gòu)類型對(duì)應(yīng)的對(duì)象

18、15。內(nèi)存映射文件允許將文件的一部分映射到內(nèi)存中， 從 而 可 以 處 理 非 常 大 的 文 件 。 Windows 支 持 的 文 件 大小 最 大 達(dá) 到 16 EB。 Linux 支 持 的 最 大 文 件 大 小 在 不 同的 文 件 系 統(tǒng) 上 略 有 差 別 ，大 部 分 系 統(tǒng) 都 實(shí) 現(xiàn) 了 LFS（大 文件系統(tǒng)）技術(shù)，文件大小可以達(dá)到或超過 2 TB。4存儲(chǔ)引擎的實(shí)現(xiàn)與使用4.1存儲(chǔ)引擎的數(shù)據(jù)表示方法本 研 究 定 義 了 一 種 數(shù) 據(jù) 描 述 方 法 ：ASON（Algo- rithm Structured Object Notation），即 算 法 結(jié) 構(gòu) 化 對(duì)

19、象 表 示 法 ，來 描 述 算 法 記 錄 ，可 以 滿 足 進(jìn) 化 算 法 記 錄 的 數(shù)據(jù) 存 儲(chǔ) 要 求 。 每 一 個(gè) ASON 所 描 述 的 算 法 記 錄 可 以 包 含 若 干 個(gè) 數(shù) 據(jù) 字 段 ，每 一 個(gè) 數(shù) 據(jù) 字 段 都 是 一 個(gè) 鍵 值 對(duì)3內(nèi)存映射文件內(nèi) 存 映 射 文 件 的 實(shí) 現(xiàn) 借 助 于 操 作 系 統(tǒng) 底 層 的 虛 擬 內(nèi) 存 機(jī) 制 11。 使 用 虛 擬 內(nèi) 存 的 目 的 是 為 了 彌 補(bǔ) 物 理 內(nèi) 存的容量不足問題。在虛擬內(nèi)存系統(tǒng)中，每個(gè)進(jìn)程擁有姜三義，代真真，李 陽，等：基于內(nèi)存映射文件的進(jìn)化算法數(shù)據(jù)存儲(chǔ)引擎2015，51（1）51

20、（key-value pair），每 個(gè) 鍵 名 是 一 串 字 符 串 ，鍵 值 是 一 個(gè)數(shù)值數(shù)組。例如，ASON 可以表示如下使用鍵值對(duì)描述 的算法記錄： “popsiz”：200， “gen”：1， “fitness”：100，30，“chromo”：62 000，76 000，58 000，23 000記 錄 中 的“popsiz”、“gen”、“fitness”、“chromo”分 別 表 示 種 群 大 小 、當(dāng) 前 迭 代 值 、個(gè) 體 適 應(yīng) 度 和 染 色 體 。 使 用 ASON 可以實(shí)現(xiàn)對(duì)象內(nèi)數(shù)據(jù)字段的靈活組合，不僅可 以包含進(jìn)化算法的適應(yīng)度及染色體，還可以包含其他的

21、數(shù)據(jù)字段。本文為簡(jiǎn)單起見，只考慮染色體和適應(yīng)度值 信息。使用 C+宏“ASON”在程序中按照 C+數(shù)據(jù)流的序 列化方式構(gòu)建算法記錄，采用 STL 的 std：vector 容器作 為數(shù)組類型。宏 ASON 的使用方法參見如下代碼：std：vector<double>vec； / 填入數(shù)據(jù)，使 vec 包含100，30ASONObj obj=ASON（“popsiz”<<200<<“gen”<<1<<“fitness”<<vec）；/構(gòu)造 ASONObj 對(duì)象宏“ASON”返 回 的 是 抽 象 數(shù) 據(jù) 結(jié) 構(gòu) 類 型 AS

22、ONObj 的 對(duì) 象 實(shí) 例 。 在 內(nèi) 存 中 ，一 個(gè) ASONObj 對(duì) 象 表 示 為 二 進(jìn)制字節(jié)序列 。首先是 4 個(gè)字節(jié)表示對(duì)象長(zhǎng)度 ，緊接著 是若干個(gè)數(shù)據(jù)字段，最后是結(jié)束標(biāo)志符。每個(gè)數(shù)據(jù)字段 的 第 一 個(gè) 1 個(gè) 字 節(jié) 表 示 字 段 值 類 型 ；然 后 是 一 條 字 符 串 ，表 示 字 段 名 稱 ，由 字 符 0結(jié) 尾 ；接 著 是 4 個(gè) 字 節(jié) 表 示字段維數(shù)，然后是表示數(shù)組數(shù)據(jù)的若干個(gè)字節(jié)。這種 數(shù)據(jù)結(jié)構(gòu)支持了對(duì)象內(nèi)數(shù)據(jù)字段的遍歷。ASONObj 對(duì) 象的內(nèi)存結(jié)構(gòu)如圖 1 所示。ByteString=20，/變長(zhǎng)字節(jié)串MaxKey=127；其 中 的 Mi

23、nKey 和 MaxKey 表 示 類 型 代 號(hào) 的 最 小 、 最大值，分別是 1 和 127，這樣所有的類型值可以用一 個(gè) 字 節(jié) 表 示 。 因 為 數(shù) 據(jù) 字 段 的 第 一 個(gè) 字 節(jié) 表 示 字 段 值 的 類 型 ，所 以 結(jié) 束 字 段 只 需 要 一 個(gè) 字 節(jié) 用 于 存 儲(chǔ) EOO 表示對(duì)象結(jié)束，而無需作為一個(gè)完整的數(shù)據(jù)字段。ASONObj 提 供 objdata（）和 objsize（）函 數(shù) 將 數(shù) 據(jù) 提 供給調(diào)用者，表示整個(gè)對(duì)象的數(shù)據(jù)內(nèi)容和長(zhǎng)度。4.2數(shù)據(jù)文件結(jié)構(gòu)的設(shè)計(jì)數(shù) 據(jù) 文 件 的 內(nèi) 容 包 含 兩 部 分 ：文 件 頭 和 記 錄 列 表 。 文件頭部

24、包含數(shù)據(jù)存儲(chǔ)引擎的版本號(hào)、文件長(zhǎng)度等基本 信息，還包括文件空間的信息。記錄順序的保存在文件 中，每一條算法記錄又被封裝為一條“文件記錄”。類 DataFileHeader 定 義 了 數(shù) 據(jù) 文 件 的 頭 部 數(shù) 據(jù) 結(jié) 構(gòu)，其中的主要數(shù)據(jù)成員如圖 2 所示。版本號(hào)（version）8 Byte文件長(zhǎng)度（fileLength）8 Byte未使用位置（unused）8 Byte文件剩余空間長(zhǎng)度（unusedLength）定長(zhǎng)記錄標(biāo)記（fixed）緩存（cache）數(shù)據(jù)指針（data）8 Byte1 Byte64 512 Byte4 Byte圖 2 文件頭數(shù)據(jù)結(jié)構(gòu)文件的頭部占據(jù) 64 KB 的空

25、間。預(yù)留較大的空間便 于對(duì)文件頭部數(shù)據(jù)結(jié)構(gòu)的擴(kuò)展定義。文件頭部數(shù)據(jù)結(jié)構(gòu) 的頭部大小用“file_header_size”表示，值為 65 536。變 量“data”是 C + 中 的 一 種 實(shí) 現(xiàn) 手 法 ，變 量“data” 的地址就是指向第一條文件記錄的地址。變 量“unused”用 于 存 儲(chǔ) 未 使 用 位 置 在 文 件 中 的 地 址 偏 移 量 ，初 始 值 為 file_header_size。 變 量“unused- Length”用于存儲(chǔ)文件中尚未使用空間的字節(jié)數(shù)。數(shù)據(jù) 文 件 的 大 小 是 按 照 需 求 量 逐 步 擴(kuò) 充 的 。 當(dāng)“unused- Length”

26、小 于 下 一 條 文 件 記 錄 的 長(zhǎng) 度 時(shí) ，存 儲(chǔ) 引 擎 自 動(dòng) 地?cái)U(kuò)大文件，可以在實(shí)際過程中調(diào)整擴(kuò)增的大小。變 量“fixed”用 于 表 明 該 文 件 中 的 所 有 文 件 記 錄 是 否長(zhǎng)度相等。為了加快數(shù)據(jù)存儲(chǔ)速度，本研究并沒有在 數(shù) 據(jù) 文 件 中 加 入 任 何 索 引 機(jī) 制 。 對(duì) 于 所 有 文 件 記 錄 等 長(zhǎng) 的 情 況（fixed 等 于 1），EADB 可 以 通 過 類 似 C+數(shù) 組 下標(biāo)訪問的方式快速地訪問每一條文件記錄，這是最快 的 數(shù) 據(jù) 尋 址 方 式 。 對(duì) 于 變 長(zhǎng) 記 錄 則 需 要 通 過 遍 歷 每 一條文件記錄，獲取并疊加記

27、錄的長(zhǎng)度來逐步定位。數(shù)據(jù)字段 1對(duì)象長(zhǎng)度數(shù)據(jù)字段 2結(jié)束字段EOO值類型 字段名稱 字段名稱1 Byte 字符串長(zhǎng) 4 Byte度+1 Byte值數(shù)組N Byte4 Byte1 Byte圖 1 ASONObj 對(duì)象的內(nèi)存結(jié)構(gòu)圖中注明了各個(gè)域所占用的存儲(chǔ)空間大小，單位是 字節(jié)（Byte），其中值數(shù)組所占用的存儲(chǔ)空間大小 N = 值 維數(shù)×該類型數(shù)值變量所占用字節(jié)數(shù)。字段值的類型是 一個(gè) C+枚舉值：enum Type MinKey=1， EOO=0，/對(duì)象結(jié)束標(biāo)志符NumberDouble=1，/雙精度（8 Byte 存儲(chǔ)空間） NumberFloat=2，/單精度（4 Byte 存儲(chǔ)

28、空間） NumberInt=16，/32 位整型（4 Byte 存儲(chǔ)空間） NumberUInt=17，/無符號(hào) 32 位整型 NumberLong=18，/64 位整型（8 Byte 存儲(chǔ)空間） NumberULong=19，/64 為無符號(hào)整型52 2015，51（1）Computer Engineering and Applications 計(jì)算機(jī)工程與應(yīng)用每 一 條 文 件 記 錄 都 包 含 自 身 的 頭 部 結(jié) 構(gòu) 和 數(shù) 據(jù)體。在存儲(chǔ)進(jìn)化算法的算法記錄時(shí)，文件記錄的頭部只 需 包 含 文 件 記 錄 長(zhǎng) 度 。 類 FileRecord 定 義 了 文 件 記 錄 的數(shù)據(jù)結(jié)構(gòu)，

29、如圖 3 所示。FILE-WRITE-AT-POSITION 用 于 改 變 文 件 中 的 數(shù)據(jù) 。 對(duì) 于 新 增 加 數(shù) 據(jù) 記 錄 ，則 算 法 的 輸 入 address 即 為 變 量“unused”的 值 。 寫 入 數(shù) 據(jù) 時(shí) 執(zhí) 行 內(nèi) 存 拷 貝 操 作 MEMORY-COPY，然 后 調(diào) 整 文 件 頭 部 unused 和 unused- Length 兩個(gè)狀態(tài)變量的值。FILE-READ-AT-POSITION 用 于 讀 取 文 件 中 的 數(shù) 據(jù) 。 在 數(shù) 據(jù) 讀 取 時(shí) ，創(chuàng) 建 內(nèi) 存 映 射 區(qū) 域 之 后 ，根 據(jù) 偏 移 量定位，可以準(zhǔn)確獲得數(shù)據(jù)記錄在

30、內(nèi)存中的地址。通過 C+強(qiáng)制類型轉(zhuǎn)換，就可以從該地址構(gòu)造出指向數(shù)據(jù)結(jié) 構(gòu) DataFileHeader 對(duì) 象 的 指 針 ，從 而 獲 得 記 錄 的 數(shù) 據(jù) 內(nèi) 容和長(zhǎng)度，并最終轉(zhuǎn)換為 ASONObj 對(duì)象。4.4 ASON 對(duì)象的精簡(jiǎn)存儲(chǔ)每 一 個(gè) ASON 對(duì) 象 中 都 添 加 了 字 段 名 稱 以 及 其 他 的一些輔助信息，這將造成數(shù)據(jù)存儲(chǔ)空間的浪費(fèi)。為了 避 免 空 間 浪 費(fèi) ，當(dāng) DataFileHeader 的“fixed”變 量 為 1 的 時(shí)候，利用其中的“cache”字段，將一個(gè)完整的 ASONObj 對(duì)象保存在“cache”中，然后，在文件記錄中僅保存數(shù)據(jù) 字

31、段 的 值 數(shù) 組 。 這 樣 可 以 有 效 減 少 所 需 存 儲(chǔ) 空 間 。 在 獲 取 記 錄 的 時(shí) 候 ，根 據(jù)“cache”中 緩 存 的 ASONObj 結(jié) 構(gòu) 信 息 ，可 以 從 精 簡(jiǎn) 的 文 件 記 錄 中 快 速 的 構(gòu) 造 出 完 整 的 ASONObj 對(duì)象。使 用 上 述 方 法 要 求 算 法 記 錄 的 長(zhǎng) 度 不 超 過 64 512 字 節(jié) 。 此 外 ，若 是 文 件 中 記 錄 長(zhǎng) 度 不 一 致 ，也 無 法 使 用 如上所屬的精簡(jiǎn)存儲(chǔ)方式。4.5 存儲(chǔ)引擎程序應(yīng)用接口EADB 的 應(yīng) 用 接 口 通 過 C+類 EADB 提 供 ，主 要 包 括

32、 open、close、Add 和 Get 四個(gè)方法。Open 和 Close 用于 打開（創(chuàng)建）和關(guān)閉一個(gè)數(shù)據(jù)文件；Add 用于向數(shù)據(jù)文件 中 添 加 算 法 記 錄 ；Get 用 于 獲 取 算 法 記 錄 。 操 作 接 口 使 用的數(shù)據(jù)結(jié)構(gòu)是 ASONObj。Class EADBbool open（std：string filename，bool fixed，bool fileStepSiz，.）；void close（）；bool Add（ASONObj obj）；ASONObj Ge（t int32_t index）；Open 方 法 參 數(shù)“filename”表 示 數(shù) 據(jù) 文

33、件 名 稱 ；參 數(shù) “fixed”用于指示是否所有記錄的內(nèi)容及長(zhǎng)度一致：一致 則 可 以 使 用 ASON 對(duì) 象 的 精 簡(jiǎn) 存 儲(chǔ) ；參 數(shù)“fileStepSiz” 用 于 指 示 數(shù) 據(jù) 文 件 擴(kuò) 容 的 步 長(zhǎng) 。 根 據(jù) 不 同 算 法 設(shè) 定 合 理的步長(zhǎng)，可以在一定程度上加快存儲(chǔ)速度。4.6 數(shù)據(jù)文件的查看與數(shù)據(jù)導(dǎo)出EADB 支 持 通 過 存 入 的 順 序 來 訪 問 數(shù) 據(jù) 記 錄 。 為 了查看數(shù)據(jù)文件中的數(shù)據(jù)，本研究開發(fā)了 GUI 數(shù)據(jù)文件 管 理 程 序 ，用 于 顯 示 數(shù) 據(jù) 文 件 的 基 本 信 息 ，例 如 迭 代 次 數(shù)、種群數(shù)量等，查詢算法記錄，或

34、者將算法記錄根據(jù)某 種規(guī)則導(dǎo)出為文本文件，用以在 Matlab 或其他程序中使記錄長(zhǎng)度（length） 4 Byte數(shù)據(jù)指針（data） 4 Byte圖 3 文件記錄數(shù)據(jù)結(jié)構(gòu)記 錄 的 數(shù) 據(jù) 結(jié) 構(gòu) 的 變 量“l(fā)ength”存 放 記 錄 的 長(zhǎng) 度 ，其值中包含頭部自身的長(zhǎng)度。變量“data”是 C+中的一 種 實(shí) 現(xiàn) 手 法 ，變 量“data”的 地 址 就 是 記 錄 中 數(shù) 據(jù) 的 其 實(shí) 地址。文件記錄數(shù)據(jù)結(jié)構(gòu)的頭部大小用“record_header_ size”表示，值為 4。4.3內(nèi)存映射文件的數(shù)據(jù)訪問方法創(chuàng)建內(nèi)存映射文件的時(shí)候，新建文件的大小至少應(yīng) 為 文 件 頭 的 大

35、 ?。‵ileHeaderSize）。 在 執(zhí) 行 創(chuàng) 建 內(nèi) 存 映 射文件的步驟之后，需要對(duì)文件頭部數(shù)據(jù)結(jié)構(gòu)的字段進(jìn) 行初始化。在創(chuàng)建內(nèi)存映射文件時(shí)，可以得到內(nèi)存映射區(qū)域的 內(nèi) 存 地 址 ，通 過 該 地 址 可 以 在 內(nèi) 存 中 直 接 訪 問 文 件 數(shù) 據(jù)。如果從文件起始處建立內(nèi)存映射區(qū)域，則偏移位置0 就是 DataFileHeader 對(duì)象在內(nèi)存中的起始字節(jié)。 對(duì) 于 每 一 條 文 件 記 錄 ，也 是 相 同 方 法 ，從 文 件 中 偏移位置 65 536 開始，通過類型轉(zhuǎn)換得到文件記錄對(duì)象的 指針，可以實(shí)現(xiàn)文件記錄對(duì)象的逐條遍歷。算法 1 和算法 2 分別描述了對(duì)內(nèi)存

36、映射文件進(jìn)行數(shù) 據(jù)寫入和讀取的操作。同時(shí)假定由 MAP-VIEW 算法來 創(chuàng)建內(nèi)存映射區(qū)域，所創(chuàng)建區(qū)域的內(nèi)存地址為 position， MEMORY-COPY 算法執(zhí)行內(nèi)存復(fù)制。算法 1 內(nèi)存映射文件數(shù)據(jù)寫入FILE-WRITE-AT-POSITION（address，obj）1. robj->objdata（），obj->objsize（）2. positionMAP-VIEW（address）3. MEMORY-COPY（r，position）4. unusedunused+r->length5. unusedLengthunusedLength-r->length

37、算法 2 內(nèi)存映射文件數(shù)據(jù)讀取FILE-READ-AT-POSITION（address）1. addressaddress+file_header_size2. positionMAP-VIEW（address）3. rcast position to（FileRecord*）4. objconstruct ASONObj from r->data5. return obj算法 1 和算法 2 通過偏移地址訪問數(shù)據(jù)記錄，其中的 對(duì) 象“obj”是 ASONObj 類 型 的 實(shí) 例 。 偏 移 地 址 address 不包含文件頭部長(zhǎng)度，需要在訪問數(shù)據(jù)文件內(nèi)容時(shí)將其 納入。姜三義，代真

38、真，李 陽，等：基于內(nèi)存映射文件的進(jìn)化算法數(shù)據(jù)存儲(chǔ)引擎2015，51（1）53用算法記錄進(jìn)行算法可視化等分析工作。2.01.21.00.20文件 I/OEADBLevelDB5實(shí)驗(yàn)結(jié)果及分析5.1實(shí)驗(yàn) 1 基本性能測(cè)試為了測(cè)試數(shù)據(jù)存儲(chǔ)引擎的性能，本文將 EADB 與采 用 標(biāo) 準(zhǔn) C 函 數(shù) 庫 的 文 件 I/O 方 式 和 用 谷 歌 公 司 的 Lev- elDB 用 來 存 儲(chǔ) 變 長(zhǎng) 字 符 串 進(jìn) 行 實(shí) 驗(yàn) 對(duì) 比 ，觀 察 其 數(shù) 據(jù) 存 儲(chǔ) 速 度 。 LevelDB 是 谷 歌 公 司 推 出 的 超 高 性 能 文 件 數(shù)據(jù)庫，支持鍵值

39、對(duì)存儲(chǔ)和索引。本文分別用較長(zhǎng)數(shù)據(jù)和較短數(shù)據(jù)做比較，這樣更能 對(duì)比不同方法的性能。較短數(shù)據(jù)測(cè)試中，隨機(jī)生成小于201 字節(jié)的可讀字符串；較長(zhǎng)數(shù)據(jù)測(cè)試中，隨機(jī)生成小于5 001 字節(jié)的可讀字符串。兩個(gè)實(shí)驗(yàn)各自包含 30 組數(shù)據(jù)， 每組數(shù)據(jù)的數(shù)量分別為 20 000 的倍數(shù)。每次實(shí)驗(yàn)時(shí)對(duì)每 組 數(shù) 據(jù) 進(jìn) 行 30 次 測(cè) 試 然 后 計(jì) 算 耗 時(shí) 均 值 。 在 Windows2008 Server R2 64 位 操 作 系 統(tǒng) 上 運(yùn) 行 ，CPU 為 Intel Xeon X5680，3.33 GHz，96 GB 內(nèi) 存 ，外 部 存 儲(chǔ) 器 為 Promise VessRAID 1 84

40、0 s SCSI RAID5 磁 盤 陣 列 ，其 中 的 磁 盤 驅(qū) 動(dòng) 器 為 西 部 數(shù) 據(jù) WD2002FYPS 硬 盤（2 TB，7 200 r/s）。存儲(chǔ)較短數(shù)據(jù)的三種方式的效率曲線如圖 4所示。1020304050 60字符串?dāng)?shù)量/104 條Windows 上較長(zhǎng)數(shù)據(jù)實(shí)驗(yàn)結(jié)果圖 5由 此 可 見 ，對(duì) 于 存 儲(chǔ) 任 何 數(shù) 量 級(jí) 別 的 數(shù) 據(jù) ，EADB都 表 現(xiàn) 出 明 顯 的 優(yōu) 越 性 ，且 隨 著 數(shù) 據(jù) 的 增 多 ，性 能 優(yōu) 勢(shì) 越明顯。5.2 實(shí)驗(yàn) 2 多目標(biāo)進(jìn)化算法實(shí)驗(yàn)進(jìn)化算法有很多分支，本文選取較為復(fù)雜的 MOEA/D 算 法 求 解 多 目 標(biāo) 背 包

41、 問 題 進(jìn) 行 實(shí) 驗(yàn) 。 通 過 選 擇 多 個(gè) 不 同 的 測(cè) 試 題 ，設(shè) 定 不 同 的 背 包 個(gè) 數(shù)（代 表 目 標(biāo) 數(shù)）、物 品 數(shù)（即 變 量 數(shù) 、決 定 染 色 體 長(zhǎng) 度）和 種 群 大 小 ，來 代 表 不 同難易程度的問題。此 次 實(shí) 驗(yàn) 是 在 MOEA/D 算 法 的 每 一 代 計(jì) 算 之 后 保 存 染 色 體 、適 應(yīng) 度 以 及 權(quán) 重 三 個(gè) 指 標(biāo) ，這 三 個(gè) 指 標(biāo) 的 數(shù) 據(jù) 類 型 均 為 實(shí) 數(shù) 數(shù) 組 。 算 法 對(duì) 15 個(gè) 測(cè) 試 題 進(jìn) 行 6 輪 運(yùn) 算；測(cè)試環(huán)境與實(shí)驗(yàn) 1 相同。實(shí)驗(yàn)結(jié)果如表 1 所示。表 1 MOEA/D 算法

42、測(cè)試結(jié)果1 400文件 I/OEADBLevelDB1 2001 000800600400方法時(shí)間/s使用文件 I/O使用 EADB3 473570200由表 1 數(shù)據(jù)可以看出，在使用 MOEA/D 算法解決問題的過程中存儲(chǔ)算法數(shù)據(jù)時(shí)，使用 EADB 耗費(fèi)的時(shí)間僅 僅是文件 I/O 方式的 16%。換句話說，使用文件 I/O 方法 時(shí)，算法程序執(zhí)行所消耗的 84%以上時(shí)間是進(jìn)行文件 I/O 操作，真正執(zhí)行算法運(yùn)算的時(shí)間不足 16%。由此可以得 出 結(jié) 論 ：使 用 EADB 替 代 文 件 I/O 可 以 大 大 提 高 算 法 程 序執(zhí)行的效率。0102030405060字符串?dāng)?shù)量/10 條

43、4圖 4Windows 上較短數(shù)據(jù)實(shí)驗(yàn)結(jié)果圖 4 結(jié) 果 顯 示 出 ，對(duì) 于 短 數(shù) 據(jù) ，用 EADB 比 文 件 I/O和 LevelDB 的 速 度 快 。 隨 著 存 儲(chǔ) 數(shù) 據(jù) 的 數(shù) 量 的 增 加 ， EADB 的優(yōu)勢(shì)越來越明顯。由于各種因素的影響，例如 計(jì)算機(jī)中同步處理了大量其他任務(wù)，導(dǎo)致實(shí)驗(yàn)結(jié)果的曲 線 有 一 些 跳 躍 ，但 是 可 以 得 出 ，各 種 存 儲(chǔ) 方 式 的 存 儲(chǔ) 效 率均呈線形變化，這意味著數(shù)據(jù)存儲(chǔ)速度可以在數(shù)據(jù)量 持 續(xù) 增 大 時(shí) 基 本 保 持 不 變 。 比 較 來 說 EADB 方 式 性 能 最好，存儲(chǔ)速率最高。存儲(chǔ)較長(zhǎng)數(shù)據(jù)的三種方式的效

44、率曲線如圖 5 所示。 圖 5 結(jié) 果 顯 示 對(duì) 于 更 長(zhǎng) 數(shù) 據(jù) 的 存 儲(chǔ) ，EADB 仍 然 比文 件 I/O 和 LevelDB 快 ，并 且 隨 著 存 儲(chǔ) 數(shù) 據(jù) 的 數(shù) 量 的 增 加 ，EADB 速 度 上 的 優(yōu) 勢(shì) 越 來 越 明 顯 。 同 時(shí) 可 以 看 出 ， 隨 著 數(shù) 據(jù) 量 的 增 多 ，LevelDB 存 儲(chǔ) 方 式 越 來 越 不 穩(wěn) 定 。 比較來說 EADB 方式對(duì)長(zhǎng)數(shù)據(jù)的存儲(chǔ)性能也是最好，存 儲(chǔ)速率最高。6結(jié)語進(jìn)化算法的應(yīng)用范圍十分廣泛，已經(jīng)在眾多科學(xué)計(jì) 算 領(lǐng) 域 和 工 程 領(lǐng) 域 得 到 了 應(yīng) 用 16。 許 多 進(jìn) 化 算 法 的 執(zhí) 行

45、時(shí)間往往達(dá)到或超過數(shù)小時(shí)，其執(zhí)行過程中產(chǎn)生的算 法 記 錄 是 進(jìn) 行 算 法 分 析 的 重 要 依 據(jù) 。 EADB 通 過 采 用 內(nèi) 存 映 射 文 件 技 術(shù) ，實(shí) 現(xiàn) 了 快 速 數(shù) 據(jù) 存 儲(chǔ) ，減 少 進(jìn) 化 算 法執(zhí)行過程中因數(shù)據(jù)存儲(chǔ)而帶來的時(shí)間耗費(fèi)，有效促進(jìn) 了進(jìn)化算法的實(shí)現(xiàn)。同時(shí)，EADB 作為一個(gè)嵌入式數(shù)據(jù) 存儲(chǔ)引擎，不僅使用簡(jiǎn)便，還可以在多個(gè)方面進(jìn)行優(yōu)化， 進(jìn)一步提升速度。（下轉(zhuǎn) 101 頁）時(shí)間/ms時(shí)間/104ms殷鳳梅，濮光寧，張 江，等：基于線性方程組的門限匿名認(rèn)證方案2015，51（1）1014結(jié)束語基于線性方程組的求解理論，提出了一種門限匿名 認(rèn)證方案，其

46、安全性依賴于離散對(duì)數(shù)求解的困難性。與 已 有 的 方 案 相 比 ，本 文 方 案 不 僅 能 實(shí) 現(xiàn) 匿 名 認(rèn) 證 ，更 能 實(shí) 現(xiàn) 匿 名 追 蹤 ，且 具 有 門 限 性 質(zhì) 。 整 個(gè) 過 程 中 ，計(jì) 算 代 價(jià) 相 對(duì) 較 小 ，匿 名 認(rèn) 證 過 程 相 對(duì) 較 簡(jiǎn) 單 。 在 電 子 商 務(wù) 、 移動(dòng)通信等眾多領(lǐng)域，本文方案將具有廣闊的應(yīng)用前景。latorC/Proceedings of Communication Systems，Networksand Applications Conference，2010：56-59.6 周彥偉，吳振強(qiáng)，蔣李.分布式網(wǎng)絡(luò)環(huán)境下的跨域匿名

47、認(rèn)證 機(jī)制J.計(jì)算機(jī)應(yīng)用，2010，30（8）：2120-2124.7 宋 成 ，孫 宇 瓊 ，彭 維 平 ，等.改 進(jìn) 的 直 接 匿 名 認(rèn) 證 方 案 J.北 京郵電大學(xué)學(xué)報(bào)，2011，34（3）：62-65.8Hirose S，Yoshida S.A user authentication scheme withidentity and location privacyC/Proceedings of the 6th Australasian Conference on Information Security and Pri- vacy，Sydney，Australia，July 1

48、1-13，2001，2119：235-246.參考文獻(xiàn)：1 Ateniese G，Herzberg mobility or how toA，Krawczyk H，et al.Untraceabletravel incognitoJ.Computer Net-9 田子健，王繼林，伍云霞.一個(gè)動(dòng)態(tài)的可追蹤匿名認(rèn)證方案J.電子與信息學(xué)報(bào)，2005，27（11）：1737-1740.works，1999，31（8）：871-884.2 Kong J J，Hong X Y，Gerla M.An identity-free and on- demand routing scheme against ano

49、nymity threats in mobile Ad Hoc networksJ.IEEE Transactions on Mobile Com - puting，F(xiàn)requency，2007，6：888-902.3 Lee C H，Deng X T，Zhu H F.Design and sccurity anal- ysis of anonymous group identification protocolsC/Pro- ceedings of Pulic Key Cryptography，F(xiàn)ebruary 2002，Paris， France.Berlin Heidelberg：Spr

50、inger-Verlag，2002：188-198.4 Eliane J，Guillaume P.On the security of homage group authentication protocolC/Proceedings of Cayman Islands， British West Indies，F(xiàn)eb 19-22，2001，2339：106-116.5 Xu Z M，Tian H，Liu D S，et al.A ring-signature anony-10Paik J H，Kim B H，Lee D H.A3RP：anonymous andauthenticated ad

51、hoc routing protocolC/Proceedings of Information Security and Assurance Conference，2008.11 劉 方 斌 ，張 琨 ，李 海 ，等.無 可 信 中 心 的 門 限 追 蹤 Ad Hoc網(wǎng)絡(luò)匿名認(rèn)證J.通信學(xué)報(bào)，2012，33（8）：208-213.12 石潤(rùn)華，仲紅，黃劉生.公開可驗(yàn)證的門限秘密共享方案J.微電子學(xué)與計(jì)算機(jī)，2008，25（1）：29-33.13 殷鳳梅，濮光寧.允許新成員加入的無可信中心秘密共享 方 案 分 析 J. 重 慶 科 技 學(xué) 院 學(xué) 報(bào) ：自 然 科 學(xué) 版 ，2011，13（6