我在公司有一個文件瀏覽器的開發(fā)項目，需要很快的去遍歷某一路勁下的所有的"圖片文件"镰禾、"視頻文件"、"音頻文件"唱逢、"文檔文件"吴侦；在一接到這個需求的時候，我首先翻了一下我司前人的杰作——舊版的文件管理器坞古。他們是使用java實現(xiàn)的备韧，用的深度優(yōu)先遞歸寫法，加上后綴的判定方式是直接比較字符串痪枫，就是string的equals方法织堂。想想，多可怕奶陈。完了以后呢易阳，他們又吧所有的文件，用了一個中文轉英文的庫吃粒，把文件名翻譯成拼音潦俺，然后再排序，用的Collections的sort方法徐勃，總共這一系列神操作下來呢事示，一個1w文件的目錄耗時15s左右。
我的老大也受夠了這么慢的"文件瀏覽器",所以他想讓我優(yōu)化優(yōu)化……
首先疏旨，我分析了一下很魂，這個文件瀏覽器遍歷搜索花了5s左右,然后排序10s+.
然后我詢問了老大的意見，他說排序太廢時間了檐涝，直接砍了吧遏匆。嗯，那就是沒有排序谁榜，就文件遍歷幅聘，然后耗時5s。
這時候有機制的小伙伴就發(fā)現(xiàn)了窃植，安卓下的文件不是可以通過ContentProvider去做查詢嗎帝蒿。需要這么費力嗎？是的巷怜，小伙子有在認真思考哦葛超，誠然暴氏，安卓內置的或者掛載了很久的存儲器確實可以這么做的。但是绣张，你沒想到的時答渔，我壓根不是給手機開發(fā)文件管理器。而是給一個安卓大屏開發(fā)文件管理器侥涵。
我最開始的思路沼撕，在java層，使用深度優(yōu)先遞歸方式去遍歷文件芜飘，然后务豺，我在文件過濾器里使用equals去獲取文件類型，然后根據類型把他加入一個map嗦明，所有的"圖片文件"笼沥、"視頻文件"、"音頻文件"招狸、"文檔文件"都放入一個map里敬拓，然后我后面再去map里拿邻薯。似乎沒少毛病吧裙戏？
一、更加糟糕的代碼和復雜度
這是遞歸獲取文件的方式：
/**
* 獲得某一路徑下的所有的文件
*/
public static void getAllFiles(File directory, FileFilter filter) {
if (isDirectory(directory)) {
File[] children = directory.listFiles(filter);
if (children != null) {
for (File child : children)
getAllFiles(child, filter);
}
}
}
現(xiàn)在回過頭來看厕诡，我的過濾器咋寫的吧:{ps,似乎也沒毛病}
/**
* 數(shù)據分類
*/
private static Map<Integer, List<File>> classiferData(String rootPath) {
Map<Integer, List<File>> map = new HashMap<>();
getAllFiles(new File(rootPath), new FileFilter() {
@Override
public boolean accept(File file) {
int fileType = getFileType(file);
int fileParentType = getFileParentType(fileType);
if (fileParentType == MainConstants.FileType.TYPE_IMAGE
|| fileParentType == MainConstants.FileType.TYPE_VIDEO_OR_AUDIO
|| fileParentType == MainConstants.FileType.TYPE_DOC) {
if (map.get(fileParentType) != null) {
map.get(fileParentType).add(file);
} else {
map.put(fileParentType, new ArrayList<>());
}
}
return true;
}
});
return map;
}
這是我的文件類型獲取方式:{這里怕不是就已經有很高的復雜度了吧}
/**
* 獲取文件類型
*/
public static @FileTypeAnnotation int getFileType(File file) {
if (file.isHidden()) {
return MainConstants.FileType.TYPE_HIDDEN;
}
if (isDirectory(file)) {
return MainConstants.FileType.TYPE_FOLDER;
}
String suffix = getSuffix(file);
if (memberOf(suffix, IMAGE_SUFFIXES)) {
return MainConstants.FileType.TYPE_IMAGE;
} else if (memberOf(suffix, AUDIO_SUFFIXES)) {
return MainConstants.FileType.TYPE_AUDIO;
} else if (memberOf(suffix, VIDEO_SUFFIXES)) {
return MainConstants.FileType.TYPE_VIDEO;
} else if (memberOf(suffix, PDF_SUFFIXES)) {
return MainConstants.FileType.TYPE_DOC_PDF;
} else if (memberOf(suffix, PPT_SUFFIXES)) {
return MainConstants.FileType.TYPE_DOC_PPT;
} else if (memberOf(suffix, EXCEL_SUFFIXES)) {
return MainConstants.FileType.TYPE_DOC_EXCEL;
} else if (memberOf(suffix, WORD_SUFFIXES)) {
return MainConstants.FileType.TYPE_DOC_WORD;
} else if (memberOf(suffix, TXT_SUFFIXES)) {
return MainConstants.FileType.TYPE_DOC_TXT;
} else if (memberOf(suffix, COMPRESS_SUFFIXES)) {
return MainConstants.FileType.TYPE_COMPRESS;
} else if (memberOf(suffix, EXECUTE_SUFFIXES)) {
return MainConstants.FileType.TYPE_EXECUTE;
} else {
return MainConstants.FileType.TYPE_UNKNOWN;
}
}
然而累榜，你沒想到的是——我還有更高的復雜度：
/**
* 是否是數(shù)組中的一個成員
*/
public static boolean memberOf(String one, String[] members) {
if (members != null) {
for (String member : members) {
if (member.equalsIgnoreCase(one)) {
return true;
}
}
}
return false;
}
這樣，我的代碼很容易遍歷所有文件的時候就是一次性遍歷三種分類的文件灵嫌，即圖片類型文件壹罚，音視頻類型文件，文檔型文件寿羞。然后這個操蛋的獲取類型的方式猖凛。我成功的把分類時間干到了15s以上。我可真牛逼绪穆。我還在為我搞出了一個很好的常量表而沾沾自喜呢辨泳。
大概是這樣的:
interface GroupTypes {
String[] IMAGE_SUFFIXES=new String[]{"png","gif", "jpg", "jpeg", "bmp"};
String[] AUDIO_SUFFIXES=new String[]{"wav", "ogg", "mid", "mp2", "mp3", "aac", "m4a"};
String[] VIDEO_SUFFIXES=new String[]{"mp4", "mkv", "mpg", "mpeg", "mpeg", "swf", "3gp", "avi", "flv", "wmv", "webm"};
String[] PDF_SUFFIXES=new String[]{"pdf"};
String[] PPT_SUFFIXES=new String[]{"ppt","pptx"};
String[] EXCEL_SUFFIXES=new String[]{"xls","xlsx"};
String[] WORD_SUFFIXES=new String[]{"doc","docx"};
String[] TXT_SUFFIXES=new String[]{"txt","log","rtf","xml"};
String[] COMPRESS_SUFFIXES=new String[]{"zip","rar"};
String[] EXECUTE_SUFFIXES=new String[]{"apk"};
}
/**
* 文件類型采用組合類型方式
* 對于int的低16位都是類型
* 對于低16位中的高8位，是父類型玖院，共有256種取值
* 對于低16位中的低8位菠红，是子類型，共有256種取值
* 從子類型轉到父類新子類型&0xff00 == 父類型
*/
interface FileType {
/**
* 未知類型
*/
int TYPE_UNKNOWN = 0x0000;
/**
* 文件類型
*/
int TYPE_FOLDER = 0x0100;
/**
* 圖片資源類
*/
int TYPE_IMAGE = 0x0200;
/**
* 視頻大類
*/
int TYPE_VIDEO_OR_AUDIO = 0x0300;//父類型
//子類型
int TYPE_VIDEO = 0x0301;
int TYPE_AUDIO = 0x0302;
/**
* 文檔類型
*/
int TYPE_DOC = 0x0400;//父類型
//子類型
int TYPE_DOC_PDF = 0x0401;
int TYPE_DOC_PPT = 0x0402;
int TYPE_DOC_EXCEL = 0x0403;
int TYPE_DOC_WORD = 0x0404;
int TYPE_DOC_TXT = 0x0405;
/**
* 壓縮文件類型
*/
int TYPE_COMPRESS=0x0500;
/**
* 安卓可執(zhí)行文件
*/
int TYPE_EXECUTE=0x0600;
/**
* 隱藏文件
*/
int TYPE_HIDDEN=0x0700;
/**
* 子類轉父類的掩碼
*/
int PARENT_MASK=0xff00;
}
二难菌、似乎漸入佳境试溯，然而也只是掩耳盜鈴
直接比較后綴這種方式確實傻，一次性加載所有類型的文件到map郊酒，后面獲取其他類型的文件從map中去讀不可取遇绞，“犧牲你第一次的時間键袱，換來你后面更快的速度∧∶觯”是行不通的杠纵。所以這一次，我做了一點點改變钩骇。我不再直接比較后綴了比藻，也不會說上來就把所有的文件先加載好，后面你用的時候在從map中拿倘屹。我是用了正則去匹配文件的后綴银亲，并且加入了LRUCache。
使用正則分類纽匙，但是务蝠，還是一連串的if
/**
* 獲取文件類型
*/
public static @FileTypeAnnotation int getFileType(File file) {
if (file.isHidden()) {
return MainConstants.FileType.TYPE_HIDDEN;
}
if (file.isDirectory()) {
return MainConstants.FileType.TYPE_FOLDER;
}
String fileName=file.getName().toLowerCase();
if(match(fileName,IMAGE_PATTERN))
return MainConstants.FileType.TYPE_IMAGE;
if(match(fileName,AUDIO_PATTERN))
return MainConstants.FileType.TYPE_AUDIO;
if(match(fileName,VIDEO_PATTERN))
return MainConstants.FileType.TYPE_VIDEO;
if(match(fileName,DOC_PATTERN)){
if(match(fileName,PDF_PATTERN))
return MainConstants.FileType.TYPE_DOC_PDF;
if(match(fileName,PPT_PATTERN))
return MainConstants.FileType.TYPE_DOC_PPT;
if(match(fileName,EXCEL_PATTERN))
return MainConstants.FileType.TYPE_DOC_EXCEL;
if(match(fileName,WORD_PATTERN))
return MainConstants.FileType.TYPE_DOC_WORD;
if(match(fileName,TXT_PATTERN))
return MainConstants.FileType.TYPE_DOC_TXT;
}
if(match(fileName,COMPRESS_PATTERN))
return MainConstants.FileType.TYPE_COMPRESS;
if (match(fileName,EXCUTE_PATTERN))
return MainConstants.FileType.TYPE_EXECUTE;
return MainConstants.FileType.TYPE_UNKNOWN;
}
不再使用文件過濾器去拿文件，而是用正則去匹配文件的后綴
private static List<File> getAllFiles(File dir, Pattern regex) {
List<File> result = new ArrayList<>();
if (dir.isDirectory()) {
File[] files = dir.listFiles();
for (File file : files) {
result.addAll(getAllFiles(file, regex));
}
} else {
if (regex != null) {
if (regex.matcher(dir.getName()).matches()) {
if(!dir.isHidden())
result.add(dir);
}
}
}
return result;
}
private static List<File> getAllAudioAndVideo(File dir) {
return getAllFiles(dir, MainConstants.Patterns.AV_PATTERN);
}
private static List<File> getAllDoc(File dir) {
return getAllFiles(dir, MainConstants.Patterns.DOC_PATTERN);
}
private static List<File> getAllImages(File dir) {
return getAllFiles(dir, MainConstants.Patterns.IMAGE_PATTERN);
}
正則:
interface Regexs{
String IMAGE_REGEX="^.+\\.(?i)(png|gif|jp(e)?g|bmp)$";
String AUDIO_REGEX="^.+\\.(?i)(aac|wav|ogg|m(id|p(2|3)))$";
String VIDEO_REGEX="^.+\\.(?i)(m(kv|p(4|(e)?g))|swf|3gp|avi|flv|w(mv|ebm))$";
String AV_REGEX="^.+\\.(?i)(m(id|kv|p(2|3|4|(e)?g))|swf|3gp|a(vi|ac)|flv|w((a|m)v|ebm)|ogg)$";
String DOC_REGEX="^.+\\.(?i)(p(df|pt(x)?)|((xls|doc)(x)?)|txt|log|rtf|xml)$";
String PDF_REGEX="^.+\\.(?i)(pdf)$";
String PPT_REGEX="^.+\\.(?i)(ppt(x)?)$";
String EXCEL_REGEX="^.+\\.(?i)(xls(x)?)$";
String WORD_REGEX="^.+\\.(?i)(doc(x)?)$";
String TXT_REGEX="^.+\\.(?i)(txt|log|rtf|xml)$";
String COMPRESS_REGEX="^.+\\.(?i)(zip|rar)$";
String EXCUTE_REGEX="^.+\\.(?i)(apk)$";
}
interface Patterns{
Pattern IMAGE_PATTERN=Pattern.compile(Regexs.IMAGE_REGEX);
Pattern AUDIO_PATTERN=Pattern.compile(Regexs.AUDIO_REGEX);
Pattern VIDEO_PATTERN=Pattern.compile(Regexs.VIDEO_REGEX);
Pattern DOC_PATTERN=Pattern.compile(Regexs.DOC_REGEX);
Pattern PDF_PATTERN=Pattern.compile(Regexs.PDF_REGEX);
Pattern PPT_PATTERN=Pattern.compile(Regexs.PPT_REGEX);
Pattern EXCEL_PATTERN=Pattern.compile(Regexs.EXCEL_REGEX);
Pattern WORD_PATTERN=Pattern.compile(Regexs.WORD_REGEX);
Pattern TXT_PATTERN=Pattern.compile(Regexs.TXT_REGEX);
Pattern COMPRESS_PATTERN=Pattern.compile(Regexs.COMPRESS_REGEX);
Pattern EXCUTE_PATTERN=Pattern.compile(Regexs.EXCUTE_REGEX);
Pattern AV_PATTERN=Pattern.compile(Regexs.AV_REGEX);
}
這一次烛缔，我第一次分類的時候去拿1w文件所耗費的時間大概是4-5s左右
三馏段、更進一步，使用非遞歸的廣度優(yōu)先搜索
使用非遞歸的廣度優(yōu)先遍歷践瓷，少一層入棧（隊）院喜，節(jié)約了一丟丟時間，并且晕翠，可以拿到一部分數(shù)據就返回一點數(shù)據了
/**
* 文件遍歷非遞歸方式
* @param dir
* @param regex
* @return
*/
private static List<File> getAllFilesNR(File dir, @NonNull Pattern regex) {
List<File> result = new LinkedList<>();
Queue<File> queue = new LinkedList<>();
queue.add(dir);
while (!queue.isEmpty()) {
File temp = queue.remove();
if (temp.isDirectory()) {
File[] files = temp.listFiles();
if (files != null)
for (File file : files)
if (file.isDirectory()) //文件夾
queue.add(file);
else //文件
if(regex.matcher(file.getName()).matches())
result.add(file);
}
}
return result;
}
不同的文件分類使用不同的正則,減少了一些語句
public static @FileTypeAnnotation int getDocType(File file){
String fileName = file.getName().toLowerCase();
if (match(fileName, PDF_PATTERN)) {
return MainConstants.FileType.TYPE_DOC_PDF;
}
if (match(fileName, PPT_PATTERN)) {
return MainConstants.FileType.TYPE_DOC_PPT;
}
if (match(fileName, EXCEL_PATTERN)) {
return MainConstants.FileType.TYPE_DOC_EXCEL;
}
if (match(fileName, WORD_PATTERN)) {
return MainConstants.FileType.TYPE_DOC_WORD;
}
if (match(fileName, TXT_PATTERN)) {
return MainConstants.FileType.TYPE_DOC_TXT;
}
return MainConstants.FileType.TYPE_UNKNOWN;
}
public static @FileTypeAnnotation int getAVType(File file){
String fileName = file.getName().toLowerCase();
if (match(fileName, AUDIO_PATTERN)) {
return MainConstants.FileType.TYPE_AUDIO;
}
if (match(fileName, VIDEO_PATTERN)) {
return MainConstants.FileType.TYPE_VIDEO;
}
return MainConstants.FileType.TYPE_UNKNOWN;
}
這一次喷舀，我第一次分類的時候去拿1w文件所耗費的時間大概是3-4s左右
四、給人們一種假象淋肾，善意的謊言
無需等全部文件都分類完硫麻，才去顯示內容，而是只要有數(shù)據了樊卓，就去顯示拿愧，雖然拿完所有的數(shù)據耗時還是原來的時間，但給人的感覺卻是變快了碌尔。
private static void getAllFilesNR(String rootPathNav,File dir, @NonNull Pattern regex,@NonNull FileInfoCallback callback) {
List<FileInfo> result = new LinkedList<>();
Queue<File> queue = new LinkedList<>();
queue.add(dir);
while (!queue.isEmpty()) {
File temp = queue.remove();
if (temp.isDirectory()) {
File[] files = temp.listFiles();
if (files != null) {
for (File file : files)
if (file.isDirectory()) //文件夾
{
queue.add(file);
} else //文件
if (regex.matcher(file.getName()).matches()) {
int fileType = getFileType(file);
result.add(new FileInfo(file,fileType));
}
}
}
callback.update(result);
}
if (result.size() > cache.maxSize()) {
cache.resize((int) (cache.maxSize() * 2));
}
cache.put(rootPathNav, result);
}
五浇辜、山窮水盡疑無路，柳岸花明又一村
在java層七扰，大概這也就是比較快的速度了吧奢赂，除了獲取文件類型很慢，還有優(yōu)化的空間颈走。遍歷文件的方式似乎再也沒有更好的解決方案了膳灶。然而，我覺得遍歷文件主要還是太慢了。要是我能提高這個速度轧钓，就好了序厉。我也沒想著能用c++做到主工程中去，只是覺得這個思路不錯毕箍。然后我在后面花了點時間去寫了個小demo去驗證了一下弛房，我使用jni去分類，而這一次而柑，我雖然使用的是字符串比較這種笨辦法去分類文捶，但是卻用了500ms。
int getFilesNR(char *path) {
queue<string> mQueue;
mQueue.push(path);
while (!mQueue.empty()) {
string currentPath = mQueue.front();
mQueue.pop();
DIR *dir = opendir(currentPath.c_str());
if (dir == NULL) {
perror("open dir error");
continue;
}
Dirent ptr;
while ((ptr = readdir(dir)) != NULL) {
char *cur;//如果路勁過長加上文件名過長可能導致bug
if (strcmp(ptr->d_name, ".") == 0 ||
strcmp(ptr->d_name, "..") == 0)//current dir or parent dir
continue;
else if (ptr->d_type == 8 || ptr->d_type == 4) {//file or linked file
//得到當前文件路徑
//為什么是2? 一個'/'加上一個'\0'
int strLen = strlen(currentPath.c_str()) + strlen(ptr->d_name) + 2;
cur = new char[strLen];
memset(cur, '\0', sizeof(cur));
sprintf(cur, "%s/%s", currentPath.c_str(), ptr->d_name);
if (ptr->d_type == 8) {
LOGD("path:%s",ptr->d_name);//1.可以在這里對文件獲取類型和分類處理
} else {
mQueue.push(cur);
}
}
delete cur;
}
closedir(dir);
}
return 1;
}
上述代碼注釋1處我首先是使用笨辦法對文件進行分類媒咳，寫法如下:
bool isavs(char *str) {
char **audioAndVideo = new char *[]{"mp3", "mp4", "ogg", "wav", "3gp", "avi"}
char *suffix = getSuffix(str);
bool flag = false;
for (int i = 0; i < sizeof(audioAndVideo); ++i) {
if (strcmp(suffix, audioAndVideo[i]) == 0) {
flag = true;
break;
}
}
delete suffix;
return flag;
}
后面我優(yōu)化了根據后綴獲取類型的方法粹排，使用了tire樹，然后這個速度就達到了現(xiàn)在的最優(yōu)時間:100ms內涩澡，實測60ms左右顽耳。{雖然如此，但還是有優(yōu)化的空間妙同，那就是把變量放入native中射富，本地分頁去取，可能能在50ms內粥帚，但是內存回收不好做胰耗，萬一沒有回收，就是內存泄露了茎辐。所以目前不打算這么做宪郊。}
/**
* 獲取路勁的后綴
* @param path 路勁
* @return 后綴
*/
char *getSuffix(char *path) {
char *ret = strrchr(path, '.');
if (ret) {
return ret + 1;
}
return "";
}
int getFileType(SuffixTire *suffixTire, char *name) {
char *suffix = getSuffix(name);
int suffixLen = strlen(suffix);
if (suffixLen == 0)
return TYPE_UNKNOWN;
int type = suffixTire->search(suffix);
return type;
}
bool isImage(SuffixTire *suffixTire, char *name) {
return getFileType(suffixTire, name) == TYPE_IMAGE;
}
bool isDocs(SuffixTire *suffixTire, char *name) {
return (getFileType(suffixTire, name) & PARENT_MASK) == TYPE_DOC;
}
bool isAvs(SuffixTire *suffixTire, char *name) {
return (getFileType(suffixTire, name) & PARENT_MASK) == TYPE_VIDEO_OR_AUDIO;
}
SuffixNode:
class SuffixNode {
public:
char ch;
int type;
bool isLeaf;
vector<SuffixNode> children;
public:
SuffixNode() : ch(NULL), type(0), isLeaf(false),children(vector<SuffixNode>()) {
}
~SuffixNode(){
}
};
SuffixTire
class SuffixTire {
private:
SuffixNode *root;
public:
SuffixTire() {
root = new SuffixNode();
}
/**
* 構造字典樹
* @param suffix 后綴
* @param type 后綴類型
*/
void insert(char *suffix, int type);
/**
* 查詢字典
* @param suffix 后綴
* @return 后綴類型
*/
int search(char* suffix);
~SuffixTire(){
LOGD("NDK:SuffixTire析構");
delete root;
}
};
void SuffixTire::insert(char *suffix, int type) {
LOGD(">>>SuffixTire insert, suffixes: %s,type:%d", suffix, type);
assert(suffix != NULL);
int suffixLen = strlen(suffix);
assert(suffixLen != 0);
SuffixNode *node = root;
for (int i = 0; i < suffixLen; ++i) {
int index = 0;
for (; index < node->children.size(); ++index) {
if (node->children[index].ch == suffix[i])
break;
}
if (index < node->children.size()) {//找到了
node = &(node->children[index]);
} else if (index == node->children.size()) {//未找到節(jié)點
SuffixNode temp;
temp.ch = suffix[i];
node->children.push_back(temp);
node = &(node->children.back());
}
}
node->isLeaf = true;
node->type = type;
LOGD("<<<SuffixTire insert");
}
int SuffixTire::search(char *suffix) {
assert(suffix != nullptr);
int suffixLen = strlen(suffix);
assert(suffixLen != 0);
SuffixNode *node = root;
for (int i = 0; i < suffixLen; ++i) {
int index = 0;
for (; index < node->children.size(); ++index) {
if (node->children[index].ch == suffix[i])
break;
}
if (index == node->children.size()) {//未找到
return 0;
}
node = &(node->children[index]);
}
if (node->isLeaf)
return node->type;
else
return 0;
}
最后掂恕，java也是用字典樹拖陆，ndk也是用字典樹，所有文件相同懊亡，在我們的產品上的耗時差距比較依啰。
最后一版java版算法和NDK算法對比
