我在公司有一个文件浏览器的开发项目，需要很快的去遍历某一路劲下的所有的"图片文件"、"视频文件"、"音频文件"、"文档文件"；在一接到这个需求的时候，我首先翻了一下我司前人的杰作——旧版的文件管理器。他们是使用java实现的，用的深度优先递归写法，加上后缀的判定方式是直接比较字符串，就是string的equals方法。想想，多可怕。完了以后呢，他们又吧所有的文件，用了一个中文转英文的库，把文件名翻译成拼音，然后再排序，用的Collections的sort方法，总共这一系列神操作下来呢，一个1w文件的目录耗时15s左右。
我的老大也受够了这么慢的"文件浏览器",所以他想让我优化优化……
首先，我分析了一下，这个文件浏览器遍历搜索花了5s左右,然后排序10s+.
然后我询问了老大的意见，他说排序太废时间了，直接砍了吧。嗯，那就是没有排序，就文件遍历，然后耗时5s。
这时候有机制的小伙伴就发现了，安卓下的文件不是可以通过ContentProvider去做查询吗。需要这么费力吗？是的，小伙子有在认真思考哦，诚然，安卓内置的或者挂载了很久的存储器确实可以这么做的。但是，你没想到的时，我压根不是给手机开发文件管理器。而是给一个安卓大屏开发文件管理器。
我最开始的思路，在java层，使用深度优先递归方式去遍历文件，然后，我在文件过滤器里使用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);
}
}
}
现在回过头来看，我的过滤器咋写的吧:{ps,似乎也没毛病}
/**
* 数据分类
*/
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;
}
}
然而，你没想到的是——我还有更高的复杂度：
/**
* 是否是数组中的一个成员
*/
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;
/**
* 安卓可执行文件
*/
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左右
三、更进一步，使用非递归的广度优先搜索
使用非递归的广度优先遍历，少一层入栈（队），节约了一丢丢时间，并且，可以拿到一部分数据就返回一点数据了
/**
* 文件遍历非递归方式
* @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左右
四、给人们一种假象，善意的谎言
无需等全部文件都分类完，才去显示内容，而是只要有数据了，就去显示，虽然拿完所有的数据耗时还是原来的时间，但给人的感觉却是变快了。
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层，大概这也就是比较快的速度了吧，除了获取文件类型很慢，还有优化的空间。遍历文件的方式似乎再也没有更好的解决方案了。然而，我觉得遍历文件主要还是太慢了。要是我能提高这个速度，就好了。我也没想着能用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;
}
后面我优化了根据后缀获取类型的方法，使用了tire树，然后这个速度就达到了现在的最优时间:100ms内，实测60ms左右。{虽然如此，但还是有优化的空间，那就是把变量放入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()) {//未找到节点
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算法对比
