一 背景
有个需求，要从大量的文件中过滤需要的文件，文件名那是以时间命令（UTC时间）的，要过滤的文件范围也是符合一定时间段的文件。
二 初始版本
代码比较简单和直接，通过直接读取目录下的文件，获取每个文件的文件名信息，判断每个文件名是否在要求的时间范围内，是的话就放入到文件名列表中，最后返回。
这段代码，从感觉上，性能一般，如果有几百万个文件，甚至更多个文件，则每个文件名都要判断一次耗时是惊人的，那能不能根据文件名直接做二分查找的方式来过滤文件名那。
int thisFileNeedSearch(char* fileName, int startTime, int endTime)
{
if (fileName == NULL) {
return -1;
}
char* flag = ".";
char* ptmp = strdup(fileName);
strtok(ptmp, flag);
strtok(NULL, flag);
char* ret = strtok(NULL, flag);
if (ret != NULL) {
int iret = atoi(ret);
if (iret >= startTime && iret <= endTime) {
free(ptmp);
return 1;
} else {
free(ptmp);
return 0;
}
} else {
cl_error("file is error:%s", fileName);
free(ptmp);
return -1;
}
}
fileLists* getNeedSearchFilesOld(char* dir_name, int startTime, int endTime)
{
DIR* dir = opendir(dir_name);
struct dirent* p = NULL;
struct stat statbuf;
fileLists* lst = NULL;
cl_infos("Scan dir is:%s", dir_name);
if (lstat(dir_name, &statbuf)) {
cl_error("Stat error:%s", dir_name);
return NULL;
}
if (!S_ISDIR(statbuf.st_mode) && !S_ISLNK(statbuf.st_mode)) {
cl_error("Dir :%s is not dir mode is:%d!", dir_name, statbuf.st_mode);
return NULL;
}
while ((p = readdir(dir)) != NULL) {
// 过滤掉. 和..
if (p->d_name[0] == '.') {
continue;
}
if (thisFileNeedSearch(p->d_name, startTime, endTime) == 1) {
if (lst == NULL) {
lst = (fileLists*)malloc(sizeof(fileLists));
assert(lst != NULL);
lst->fileName = strdup(p->d_name);
lst->next = NULL;
lst->size = 1;
lst->tail = lst;
} else {
fileLists* plst = (fileLists*)malloc(sizeof(fileLists));
assert(plst != NULL);
plst->fileName = strdup(p->d_name);
plst->next = NULL;
plst->size = 1;
lst->tail->next = plst;
lst->tail = plst;
lst->size += 1;
}
} else {
cl_debug("file:%s not in start:%d end:%d", p->d_name, startTime, endTime);
}
}
closedir(dir);
return lst;
}
三 二分查找版本
要查找文件的范围是个区间[starttime,endtime],一般endtime和starttime的差值并不算多大，那么我们可以先对文件名做个排序，然后根据二分查找的算法，查找到开始遍历starttime的文件名，逐步对后遍历即可。
直接读目录的方式，在排序挺麻烦，幸好linux有另外一个遍历文件的接口如下：
#include <dirent.h>
int scandir( const char *dir, struct dirent **namelist, int (*filter) (const void *b), int ( * compare )( const struct dirent **, const struct dirent ** ) );
int alphasort(const void *a, const void *b);
int versionsort(const void *a, const void *b);
提供两个接口，一个是filter接口，即过滤需要的文件名，二是比较接口，即比较排序的时候使用，我们可以直接使用alphasort进行文件名的比较。如下：
// 保留文件名中包含file的文件
int file_filter(const struct dirent* dir)
{
const char* name = dir->d_name;
int len = strlen(name);
if (MIN_FILE_NAME_LEN > len) {
return 0;
} else {
char* pos = strstr(dir->d_name, "file");
if (pos == NULL) {
return 0;
} else {
return 1;
}
}
}
fileLists* getNeedSearchFiles(char* dir_name, int startTime, int endTime)
{
struct dirent** entry_list = NULL;
int count = scandir(dir_name, &entry_list, pcap_filter, alphasort);
cl_infos("files number:%d", count);
if (count < 1) {
cl_infos("No find file is dir:%d", dir_name);
return NULL;
}
int fileStart = fileNameToInt(entry_list[0]->d_name);
cl_infos("start filename:%s", entry_list[0]->d_name);
// 最小值大于要查询的最大值 直接返回
if (fileStart > endTime) {
freeEntryList(entry_list, count);
free(entry_list);
cl_infos("file start time:%d is bigger than endtime:%d", fileStart, endTime);
return NULL;
}
if (count > 1) {
// 最大值比最小值都小 直接返回
int fileEnd = fileNameToInt(entry_list[count - 1]->d_name);
cl_infos("end filename:%s", entry_list[count - 1]->d_name);
if (fileEnd < startTime) {
freeEntryList(entry_list, count);
free(entry_list);
cl_infos("file end time:%d is small than start:%d", fileEnd, startTime);
return NULL;
}
}
int low = 0;
int high = count - 1;
fileLists* lst = NULL;
int startIndex = 0;
// 二分查找文件范围
while (low <= high) {
int mid = low + (high - low) / 2;
struct dirent* entry = entry_list[mid];
int filetime = fileNameToInt(entry->d_name);
// 说明要取得范围在左边
if (filetime > startTime) {
startIndex = mid;
high = mid - 1;
cl_infos("set startIndex:%d", startIndex);
}
// 说明文件范围在右边
else if (filetime < startTime) {
low = mid + 1;
} else {
// 找到最小值了
startIndex = mid;
break;
}
}
for (int j = startIndex; j < count; j++) {
int filetime = fileNameToInt(entry_list[j]->d_name);
if (filetime >= startTime && filetime <= endTime) {
addToFileList(&lst, entry_list[j]->d_name);
}
}
freeEntryList(entry_list, count);
free(entry_list);
return lst;
}
说明下 ： int mid = low + (high - low) / 2; 只所以有这种写法是为了防止low+high越界。
代码不算啥，给大家一个二分查找一段范围的文件的一点思路吧。
四 测试
写完了，免不了测试下，结果有点令人惊讶，如果文件数目少于9万个，其实老版本的性能反而更好，差别不是特别大，原因是scandir的过滤和排序拉慢了速度，而且核心逻辑只是转int和比较，在较小的数量级下，二分查找的性能不一定好于普通的查找。
五 诗词鉴赏
满庭芳·赠于瓦罐先生
朝代：[元代]
作者：[马钰]
有荣有辱，有利有害。有喜有忧相待。
有得有失，自是有成有败。
为人有生有死，但有形、必然有坏。休著有，自古来著，有有谁存在。
好认无为无作，道无情无念，无憎无爱。
无我无人无染，无著无碍。
无心有消业障，这无无、人还悟解。
无中趣，得无生无灭，超越三界。
网友评论