场景介绍：有100万篇文章生成了100个html文件，后来删除部分文章，但是文件并未删除，通过遍历html文件所在目录然后根据已知的ID集合判断是否该删除文件导致IO访问过于频繁且执行时间极长。

算法介绍：

这里有100万个数字组成的ID，其中ID是自增但是不连续的，现在需要求出中断部分的ID集合。

思路：已知这100万个ID是有序但不连续的，可以尝试构造一个for循环，使用二分查找判断是否存在于这100万个元素中，如果不存在则加入到中断部分集合。

遇到的问题：由于数据源过大导致二分查找消耗内存巨大且运行时间非常长，需要改进思路。后来经过分析，这两个集合都是正序的，完全可以定义一个游标进行单层循环。

代码实现：

<?php
set_time_limit(0);

header("Content-type: text/html; charset=utf-8");

$stime = microtime(true);

// 按照ID正序排列, 假设有1000000个ID, 1/10000几率中断
$checkIdListSize = 1000000;

$checkIdList = generateList($checkIdListSize, $checkIdListSize/10000);

p("初始: ".tosize(memory_get_usage()));

// 得到没有审核的ID集合
$uncheckIdList = array();
$cursorList = array();

// 使用偏移计数器
$offset = 0;

// 不能以$checkIdList的最小值和最大值作为边界，而应该以1和可能存在的最大ID作为边界
for($i = 1; $i<$checkIdList[count($checkIdList)-1]; $i++) {
	$cursor = $checkIdList[$offset];
	if($i == $cursor) {
		$offset++;
		continue;
	}else if($i < $cursor) {
		$cursorList[] = $i;
	}
}

// 打印中断的ID
p(implode(",", $uncheckIdList));
p(implode(",", $cursorList));


// 打印中断的ID
//p(implode(",", $uncheckIdList));

p("使用: ".tosize(memory_get_usage()));

p("峰值: ".tosize(memory_get_peak_usage()));

//获取程序执行结束的时间
$etime = microtime(true);
//计算差值
$total = $etime-$stime;

p("当前页面执行时间为：{$total} 秒");

/**
 * 随机生成一个正序排列、不连续的数组
 * $maxSize 数组大小
 * $disruptedNum 中断、不连续的数量
 */
function generateList($maxSize, $disruptedNum) {
	$checkIdList = array();
	$shuffleKeys = array();
	// 模拟这1000000个的key
	for($i=0; $i<$maxSize; $i++) {
		$shuffleKeys[] = $i;
		$checkIdList[] = $i+1;
	}
	// 打乱顺序
	shuffle($shuffleKeys);

	// 随机删除其中10000个ID
	$randomKeys = array_slice($shuffleKeys, 0, $disruptedNum);

	// 设置为null保证$checkIdList的长度不会改变
	foreach($randomKeys as $randomKey) {
		$checkIdList[$randomKey] = null;
	}

	// 删除为null的元素并重新索引以保证后面进行二分查找时传入的是有序数组
	$checkIdList = array_values(array_filter($checkIdList));

	return $checkIdList;
}

/**
 * 二分查找法, $array必须是已经排好序的数组
 * $array为数据源
 * $find为待查找的数字
 */
function binarySearch($array, $find) {
	if(empty($array)) {
		return -1;
	}
    $start = 0;
    $end = count($array)-1;
    while ($start <= $end) {
        $mid = floor(($start + $end) / 2);
        if ($array[$mid] == $find) {
            return $mid;
        }
        if ($array[$mid] > $find) {
            //left
            $end = $mid - 1;
        } else {
            $start = $mid + 1;
        }
    }
	return -1;
}

//打印变量
function p($var) {
    echo "<pre>";
    if($var === false)
    {
        echo 'false';
    }else if($var === null){
        print_r('null');
    }else if($var === ''){
        print_r("''");
    }else{
        print_r($var);
    }
    echo "</pre>";
}

/**
*@功能：将filesize大小转化为常用大小
*@参数：类型为number，$bytes是filesize结果，大小Byte
*@返回：类型为string
 */
function tosize($bytes) {
    if ($bytes >= 1099511627776) {                  //如果提供的字节数大于等于2的40次方，则条件成立
        $return = round($bytes / 1099511627776, 2); //将字节大小转换为同等的T大小
        $suffix = 'TB';                             //单位为TB
    } elseif ($bytes >= 1073741824) {               //如果提供的字节数大于等于2的30次方，则条件成立
        $return = round($bytes / 1073741824, 2);    //将字节大小转换为同等的G大小
        $suffix = 'GB';                             //单位为GB
    } elseif ($bytes >= 1048576) {                  //如果提供的字节数大于等于2的20次方，则条件成立
        $return = round($bytes / 1048576, 2);       //将字节大小转换为同等的M大小
        $suffix = 'MB';                             //单位为MB
    } elseif ($bytes >= 1024) {                     //如果提供的字节数大于等于2的10次方，则条件成立
        $return = round($bytes / 1024, 2);          //将字节大小转换为同等的K大小
        $suffix = 'KB';                             //单位为KB
    } else {                                        //否则提供的字节数小于2的10次方，则条件成立
        $return = $bytes;                           //字节大小单位不变
        $suffix = 'Byte';                           //单位为Byte
    }
    return $return ." " . $suffix;                  //返回合适的文件大小和单位
}

--------------------------------------------------------------------------------------

当然，当数据量超过百万，很有可能出现一种情况，就是单个结果集就超过了内存上限，解决办法就是适当的切割大小。一般我们从数据库中查询出来的数据不能太大，使用limit做限制后得到的结果集比较小，所以还是可以用上面的方式获取中断的ID部分。

本文地址：http://www.phprm.com/start/million-id.html

转载随意，但请附上文章地址:-)