最新消息:yaf表单扩展中新增加了浮点数、日期和集合的校验。php yaf框架扩展实践三——表单

php方法array_slice的时间复杂度分析

PHP 4453浏览 0评论

array_slice方法就是从数组中根据指定的偏移量取出一段数据。在分页显示数据中非常有用,但是我发现如果数组比较大的话,取后面的数据会比取前面的数据慢许多。例如一个数组有100万个元素,取最前面100个非常快,取最后100个会很慢。

看下面代码,构造一个有100万数据的数组:

$array = array();
for ($i = 0; $i < 1000000; $i++) {
    array_push($array, $i);
}

从数组里取出前面100个

$temp = array_slice($array, 0, 100);

在我电脑上执行的时间是10的-5次方级别。

再取最后面100个

$temp = array_slice($array, 999900, 100);

在我电脑上执行的时间是10的-2次方级别。

两个时间相比,整整相差1000倍。

于是我猜测array_slice这个方法底层实现:是从第一个开始,一个一个的遍历,直到定位到那个位置,即偏移量(offset),例如上例的999900,然后取出后面的100个。这样随着offset的增大,遍历的次数也越来越大,遍历的次数为offset+100次,是成线性增长的。那么算法复杂度就是Tn = O(f(n)) + O(100)。O(100)是常量,可以忽略,f(n)等于n,所以Tn = O(n)。

后来我查看了array_slice的c语言实现,确实是这样。原本到这里就能结束了,但是我突然想到一个优化的方法。仔细观察上面的数组,会发现数组的键值是连续的,从0,1,2…..一直下去。立马补上优化方法:

$temp = array();
for ($i = 999900; $i < 1000000; $i++) {
    $temp[] = $array[$i];
}

在我电脑上执行的时间是10的-5次方级别,这个方法的时间复杂度就是Tn = O(100),是一个常量了,不管偏移量怎么变化,执行的时间都是一样的。这个方法虽然好,但是有使用限制,只有数组的键值是一段连续的数值才可以使用。

其实在很多操作中,数组的键值最后都会形成一段连续的键值,所以这个方法还是大有用处。像sort、array_chunk等等,其中最常见的就是从数据库中读出多条数据,然后存放到一个数组里了。

转载请注明:快乐编程 » php方法array_slice的时间复杂度分析

发表我的评论
取消评论

表情

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址