84669 Lernen von Personen
152542 Lernen von Personen
20005 Lernen von Personen
5487 Lernen von Personen
7821 Lernen von Personen
359900 Lernen von Personen
3350 Lernen von Personen
180660 Lernen von Personen
48569 Lernen von Personen
18603 Lernen von Personen
40936 Lernen von Personen
1549 Lernen von Personen
1183 Lernen von Personen
32909 Lernen von Personen
假设数组有10000个元素,键值为小于1000000的无序的正整数,且不连续,如下
$arr=array(1=>'a',20=>'ad',5002=>'ss',190023=>'sd',248=>'ff',76=>'sddd'...);
现在要获取数组$arr中键值大于500小于600的元素,不用foreach完全循环一遍的话是否有更高效的算法?
人生最曼妙的风景,竟是内心的淡定与从容!
$res = array(); for(i=501;i<600;i++) { if(!isset($arr[$i])) continue; $res[] = $arr[$i]; }
@楼主 php内置的排序sort是快排序,时间复杂度是O(nlogn),然后你自己用个折半选择或者什么的,就能挑出来了。 总体时间复杂度为O(nlogn)
而如果遍历,每次时间复杂度为O(n),要查i个区段的数值,时间复杂度是O(i*n),i比较大,就差不多是O(n^2),但是实际情况应该i远远小于n,时间复杂度大约为O(n)
另外,如果先排序,需要副本的话,内存占用就会高一些 所以还是得掂量着办。
@周翔同学,我测试了一下,array_walk()用的时间比foreach还长,同样是调用同一个自定义函数。
walk_test.php <?php $arr_big = array(); for ( $i = 0; $i < 999999; $i++ ) { array_push($arr_big, 99); } function test_pow( $value ) { pow( $value, 3 ); } array_walk( $arr_big, "test_pow"); ?> foreach_test.php <?php $arr_big = array(); for ( $i = 0; $i < 999999; $i++ ) { array_push($arr_big, 99); } function test_pow( $value ) { pow( $value, 3 ); } foreach ( $arr_big as $value ) { test_pow($value); } ?>
root@debian:~/coding/php/test# time php foreach_test.php
real 0m2.286s user 0m1.088s sys 0m1.156s root@debian:~/coding/php/test# time php walk_test.php
real 0m2.653s user 0m2.352s sys 0m0.276s root@debian:~/coding/php/test# time php walk_test.php
real 0m2.689s user 0m1.864s sys 0m0.804s root@debian:~/coding/php/test# time php walk_test.php
real 0m2.700s user 0m2.460s sys 0m0.216s root@debian:~/coding/php/test# time php foreach_test.php
real 0m2.227s user 0m2.016s sys 0m0.188s root@debian:~/coding/php/test# time php foreach_test.php
real 0m2.276s user 0m2.056s sys 0m0.200s
不知道为何会这样
<?php function getItem(&$key, &$arr) { foreach($key as $v) { if($v > 600 || $v < 500) { continue; } yield $arr[$v]; } } //生成测试数组 $arr = []; for($i = 0; $i < 10000; $i++) { $k = mt_rand(1, 1000000); $arr[$k] = 'cdddsss'; } //获取数组key,对key排序,使用生成器,取出key值在500-600之间的数据 $st = microtime(true); $key = array_keys($arr); sort($key); $result = array(); foreach(getItem($key ,$arr) as $v) { $result[] = $v; } echo (memory_get_usage() / 1024 /1024) . "M\n"; echo microtime(true) - $st . "\n"; echo "原数组个数:" . count($arr) . "\n"; echo "结果数组个数" . count($result) . "\n";
根据题目,可知数组长度是固定的,1000,所以array_key获取key值sort排序 之后生成器获取需求区间值 优势:内置占用低,性能稳定可靠 需要PHP5.5版本 ps:上面所有答案都没有认真看清楚题主的题目,他要根据key返回数据,key的数量是固定的10000,所以sort(array_keys($arr))即可
sort(array_keys($arr))
如果要讨论效率的话,不建议创建有10000个元素的数组。
用
array_walk()
可以不用再php的层面上去foreach,但array_walk的实现其实也是遍历整个hashtable。
除非是排好序的,要不然不遍历怎么保证不会漏掉数据呢
$res = array();
for(i=501;i<600;i++) {
if(!isset($arr[$i])) continue;
$res[] = $arr[$i];
}
@楼主
php内置的排序sort是快排序,时间复杂度是O(nlogn),然后你自己用个折半选择或者什么的,就能挑出来了。
总体时间复杂度为O(nlogn)
而如果遍历,每次时间复杂度为O(n),要查i个区段的数值,时间复杂度是O(i*n),i比较大,就差不多是O(n^2),但是实际情况应该i远远小于n,时间复杂度大约为O(n)
另外,如果先排序,需要副本的话,内存占用就会高一些
所以还是得掂量着办。
@周翔同学,我测试了一下,array_walk()用的时间比foreach还长,同样是调用同一个自定义函数。
root@debian:~/coding/php/test# time php foreach_test.php
real 0m2.286s
user 0m1.088s
sys 0m1.156s
root@debian:~/coding/php/test# time php walk_test.php
real 0m2.653s
user 0m2.352s
sys 0m0.276s
root@debian:~/coding/php/test# time php walk_test.php
real 0m2.689s
user 0m1.864s
sys 0m0.804s
root@debian:~/coding/php/test# time php walk_test.php
real 0m2.700s
user 0m2.460s
sys 0m0.216s
root@debian:~/coding/php/test# time php foreach_test.php
real 0m2.227s
user 0m2.016s
sys 0m0.188s
root@debian:~/coding/php/test# time php foreach_test.php
real 0m2.276s
user 0m2.056s
sys 0m0.200s
不知道为何会这样
根据题目,可知数组长度是固定的,1000,所以array_key获取key值sort排序
之后生成器获取需求区间值
优势:内置占用低,性能稳定可靠
需要PHP5.5版本
ps:上面所有答案都没有认真看清楚题主的题目,他要根据key返回数据,key的数量是固定的10000,所以
sort(array_keys($arr))
即可如果要讨论效率的话,不建议创建有10000个元素的数组。
用
可以不用再php的层面上去foreach,但array_walk的实现其实也是遍历整个hashtable。
除非是排好序的,要不然不遍历怎么保证不会漏掉数据呢