php数组搜索算法
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了php数组搜索算法,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含2129字,纯文字阅读大概需要4分钟。
内容图文
![php数组搜索算法](/upload/InfoBanner/zyjiaocheng/235/4b345621cff343a48f81e748894db886.jpg)
$arr=array(1=>'a',20=>'ad',5002=>'ss',190023=>'sd',248=>'ff',76=>'sddd'...);
现在要获取数组$arr中键值大于500小于600的元素,不用foreach完全循环一遍的话是否有更高效的算法?
回复内容:
假设数组有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 foreach_test.php
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
不知道为何会这样
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))
即可
如果要讨论效率的话,不建议创建有10000个元素的数组。
用
array_walk()
可以不用再php的层面上去foreach,但array_walk的实现其实也是遍历整个hashtable。
除非是排好序的,要不然不遍历怎么保证不会漏掉数据呢
内容总结
以上是互联网集市为您收集整理的php数组搜索算法全部内容,希望文章能够帮你解决php数组搜索算法所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。