任啟紅

（三江學(xué)院 計(jì)算機(jī)科學(xué)與工程學(xué)院，江蘇 南京 210012）

Linux系統(tǒng)自帶的find命令、locate命令、xagrs命令可以用于對(duì)文件路徑、文件內(nèi)容進(jìn)行檢索，但速度比較慢從幾分鐘到幾十分鐘不等（具體視文件數(shù)量、硬盤類型、目錄深度等等具體情形而定），如何快速進(jìn)行文件路徑和文件內(nèi)容檢索是一個(gè)比較重要的問題。本文提出基于內(nèi)存建立索引、根據(jù)用戶實(shí)時(shí)輸入快速檢索的計(jì)算方法。

1 概述

使用linux自帶的命令find、locate，效率比較低下，需要花費(fèi)數(shù)分鐘至數(shù)十分鐘才能完成檢索文獻(xiàn)[1]內(nèi)存文件列表的建立和內(nèi)存跳表的構(gòu)建兩個(gè)功能模塊，這兩種功能模塊都是基于自定義的內(nèi)存管理方法。先申請(qǐng)固定大小的內(nèi)存塊，里面包括32比特的位圖、32個(gè)數(shù)據(jù)塊，每一比特的位圖依次對(duì)應(yīng)一個(gè)數(shù)據(jù)塊，這種方案為每條索引記錄分配的內(nèi)存都相同，比較耗費(fèi)內(nèi)存；文獻(xiàn)[2]提出把文件系統(tǒng)內(nèi)生成子目錄散列槽，且通過唯一標(biāo)識(shí)符標(biāo)志每個(gè)子目錄散列槽并在文件系統(tǒng)內(nèi)快速接收文件的方法，把業(yè)務(wù)目錄根據(jù)業(yè)務(wù)人員分別配置權(quán)限，不過這個(gè)比較適用于詳細(xì)的某行業(yè)定制；文獻(xiàn)[3]采用把索引存放到數(shù)據(jù)庫進(jìn)行管理，我們采用把目錄、文件路徑存放到內(nèi)存進(jìn)行檢索，速度會(huì)更快。

2 快速檢索方案及實(shí)現(xiàn)

我們采用C語言實(shí)現(xiàn)，工具名為Found，開發(fā)的系統(tǒng)分為如下幾個(gè)步驟：

1）讀取配置文件（里邊有包含目錄或排除目錄），并解析需要包含的目錄列表；

2）根據(jù)目錄列表遞歸讀取所有文件和所在目錄，并存儲(chǔ)到內(nèi)存記為數(shù)組pAllFiles；

3）創(chuàng)建兩個(gè)線程、一個(gè)讀取鍵盤輸入；一個(gè)執(zhí)行操作（如檢索數(shù)組、更新索引）；

4）按每個(gè)路徑大小分配內(nèi)存，并建立索引，內(nèi)存額外開銷比較小；

5）每次輸入后進(jìn)行一次檢索，因?yàn)橛?jì)算機(jī)處理比鍵盤操作快約106倍，這樣節(jié)省了查詢的時(shí)間；

詳細(xì)流程圖如圖1。

圖1 系統(tǒng)工程流程圖

本軟件優(yōu)點(diǎn)：

1）軟件運(yùn)行中途也可更新檢索；

2）字符串比較采用KMP算法，減少檢索時(shí)比較次數(shù)；

3）采用上一次計(jì)算的結(jié)果更新索引（nextIndex）下一跳索引作為比較輸入，減少比較次數(shù)：

4）用C語言開發(fā)，速度快；

5）實(shí)時(shí)根據(jù)用戶輸入進(jìn)行檢索速度快；

6）可根據(jù)文件刪除、新增，手動(dòng)更新索引列表；

7）基于內(nèi)存比較，速度快；

8）每個(gè)路徑+文件名按照實(shí)際使用長度申請(qǐng)，浪費(fèi)的額外內(nèi)存較少；

9）可支持目錄排除建立索引；

圖2 每輪搜索更新下一跳示意圖

本軟件缺點(diǎn)：

1）界面不太友好；

2）建立索引需要時(shí)間（Linux下find命令不需要建立索引時(shí)間）；

3）每次讀取一個(gè)文件名都需要新申請(qǐng)內(nèi)存，添加到索引指針數(shù)組；

4）開始需要配置申請(qǐng)件數(shù)量大小指針數(shù)組空間，可能有一些浪費(fèi)；

5）當(dāng)前是全量更新索引；

6）更新索引不是自動(dòng)的；

進(jìn)行檢索時(shí)：設(shè)置線程睡眠時(shí)間為usleep(1000)；

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

測試環(huán)境：

處理器：Inter(R) Core(TM) i5-6200 CPU @ 2.30GHz 2.40GHz

內(nèi)存：8.00GB

主機(jī)操作系統(tǒng)Windows10，

使用VMware? Workstation 14 Pro版本：14.1.3 build-9474260

虛擬機(jī)操作系統(tǒng)：Ubuntu 20.10測試文件數(shù)量：1172814

測試用例及結(jié)果，如表1所示：

表1 測試結(jié)果

從結(jié)果看，F(xiàn)ound工具比find命令整體上是快不少。

4 結(jié)語

當(dāng)前軟件由于是純C實(shí)現(xiàn)，界面不太友好，需要進(jìn)一步完善。