一段二分查找代码

一 背景

有个需求，要从大量的文件中过滤需要的文件，文件名那是以时间命令（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和比较，在较小的数量级下，二分查找的性能不一定好于普通的查找。

五 诗词鉴赏

满庭芳·赠于瓦罐先生

朝代：[元代] 
      作者：[马钰] 

有荣有辱，有利有害。有喜有忧相待。
有得有失，自是有成有败。

为人有生有死，但有形、必然有坏。休著有，自古来著，有有谁存在。
好认无为无作，道无情无念，无憎无爱。

无我无人无染，无著无碍。
无心有消业障，这无无、人还悟解。
无中趣，得无生无灭，超越三界。