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

1、基于內(nèi)存映射文件的進化算法數(shù)據(jù)存儲引擎姜三義，代真真，李陽，周愛民JIANG Sanyi, DAI Zhenzhen, LI Yang, ZHOU Aimin華東師范大學 計算機科學技術(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摘 要：為了觀察和分析進化算法的執(zhí)行情況，往往需要將算法執(zhí)行過程中產(chǎn)生的大量數(shù)據(jù)存儲在磁盤文件中。用于 進 化 算 法 的 嵌 入 式 數(shù) 據(jù) 存 儲 引 擎 EADB（Evolutionary Algorithm Database）提 供 了 簡 便 靈 活 的 數(shù) 據(jù) 存 儲 接 口 ，通 過使用內(nèi)存映射文件技術(shù)來實現(xiàn)數(shù)據(jù)的快速和大量存儲。相較于傳統(tǒng)文件 I/O 存儲方式和一般的通用數(shù)據(jù)存儲引

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

21、數(shù)據(jù)字段。本文為簡單起見，只考慮染色體和適應度值 信息。使用 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 對象宏“ASON”返 回 的 是 抽 象 數(shù) 據(jù) 結(jié) 構(gòu) 類 型 AS

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

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

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

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

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

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

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

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

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

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

32、 open、close、Add 和 Get 四個方法。Open 和 Close 用于 打開（創(chuàng)建）和關(guān)閉一個數(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)容及長度一致：一致 則 可 以 使 用 ASON 對 象 的 精 簡 存 儲 ；參 數(shù)“fileStepSiz” 用 于 指 示 數(shù) 據(jù) 文 件 擴 容 的 步 長 。 根 據(jù) 不 同 算 法 設 定 合 理的步長，可以在一定程度上加快存儲速度。4.6 數(shù)據(jù)文件的查看與數(shù)據(jù)導出EADB 支 持 通 過 存 入 的 順 序 來 訪 問 數(shù) 據(jù) 記 錄 。 為 了查看數(shù)據(jù)文件中的數(shù)據(jù)，本研究開發(fā)了 GUI 數(shù)據(jù)文件 管 理 程 序 ，用 于 顯 示 數(shù) 據(jù) 文 件 的 基 本 信 息 ，例 如 迭 代 次 數(shù)、種群數(shù)量等，查詢算法記錄，或

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

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

36、映射文件進行數(shù) 據(jù)寫入和讀取的操作。同時假定由 MAP-VIEW 算法來 創(chuàng)建內(nèi)存映射區(qū)域，所創(chuàng)建區(qū)域的內(nèi)存地址為 position， MEMORY-COPY 算法執(zhí)行內(nèi)存復制。算法 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ù)記錄，其中的 對 象“obj”是 ASONObj 類 型 的 實 例 。 偏 移 地 址 address 不包含文件頭部長度，需要在訪問數(shù)據(jù)文件內(nèi)容時將其 納入。姜三義，代真

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

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

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

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

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

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

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

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

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

47、認證 機制J.計算機應用，2010，30（8）：2120-2124.7 宋 成 ，孫 宇 瓊 ，彭 維 平 ，等.改 進 的 直 接 匿 名 認 證 方 案 J.北 京郵電大學學報，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.參考文獻：1 Ateniese G，Herzberg mobility or how toA，Krawczyk H，et al.Untraceabletravel incognitoJ.Computer Net-9 田子健，王繼林，伍云霞.一個動態(tài)的可追蹤匿名認證方案J.電子與信息學報，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)絡匿名認證J.通信學報，2012，33（8）：208-213.12 石潤華，仲紅，黃劉生.公開可驗證的門限秘密共享方案J.微電子學與計算機，2008，25（1）：29-33.13 殷鳳梅，濮光寧.允許新成員加入的無可信中心秘密共享 方 案 分 析 J. 重 慶 科 技 學 院 學 報 ：自 然 科 學 版 ，2011，13（6