腾讯-1亿个数据取前1万大的整数-题解答
浏览:9043次 出处信息
题目描述:
1亿个数据取前1万大的整数
常规思路:
运用数据结构里面描述的常规排序算法,快速排序法是常规排序中速度最快的
我的思路:
====我的机器太差,就不跑1亿数据了,10000吧
1、把1亿个数据分成10000个数组,
2、求出10000个数组的最大值,保存到$max 数组中,
3、对$max本身用快速排序法排序 $max数组中保存了一个有序序列数组
4、遍历1亿个数据,依次对比$max从大到小的数据,如果比max数组中的数据大,就替换。
5、获得10000个从大到小的数据$max.
代码:
以下是代码片段:
< ?php
/**
* 交换两个数据的值
*
* @param unknown_type $x
* @param unknown_type $y
*/
function swap(&$x,&$y)
{
$c = $x;
$x = $y;
$y = $c;
}
/**
* 快速排序函数
*
*/
function quicksort( $arr, $l = 0 , $r = NULL ) {
static $list = array();
if( $r == NULL )
$list = $arr;
if( $r == NULL )
$r = count($list)-1;
$i = $l;
$j = $r;
$tmp = $list[(int)( ($l+$r)/2 )];
do {
while( $list[$i] < $tmp )
$i++;
while( $tmp < $list[$j] )
$j--;
if( $i <= $j )
{
swap($list[$i],$list[$j]);
$i++;
$j--;
}
}while( $i <= $j );
if( $l < $j )
quicksort(NULL, $l, $j);
if( $i < $r )
quicksort(NULL, $i, $r);
return $list;
}
/**
* 计算运行时间类
*
*/
class timer
{
var $StartTime = 0;
var $StopTime = 0;
var $TimeSpent = 0;
function start()
{
$this->StartTime = microtime();
}
function stop()
{
$this->StopTime = microtime();
}
function spent()
{
if ($this->TimeSpent)
{
return $this->TimeSpent;
}
else
{
$StartMicro = substr($this->StartTime,0,10);
$StartSecond = substr($this->StartTime,11,10);
$StopMicro = substr($this->StopTime,0,10);
$StopSecond = substr($this->StopTime,11,10);
$start = doubleval($StartMicro) + $StartSecond;
$stop = doubleval($StopMicro) + $StopSecond;
$this->TimeSpent = $stop - $start;
return substr($this->TimeSpent,0,8)."秒";
}
}
}//end class timer;
//构造1000000个数据的数组
// $number 拆分1000*1000数组
// $number2 1000000个数据的1维数组
for($i=0;$i< = 999;$i++)
{
for($j=0;$j<=999;$j++)
{
$number2[] = $number[$i][$j] = rand(0,10000);
}
}
$timer = new timer;
$timer->start();
$max = array();
foreach ($number as $list)
{
$maxvalue = 0;
foreach ($list as $value)
{
if($maxvalue < $value)
{
$maxvalue = $value;
}
}
$max[] = $maxvalue;
}
$max = quicksort($max,0);
for($i=0;$i < 1000000;$i++)
{
//如果数组的数据大于max最小值,则从大到小对比其他数据
if($number2[$i] >$max[0])
{
for ($k=999;$k>=0;$k--)
{
if($max[$k] < $number2[$i])
{
//替换数据
$max[$k] = $number2[$i];
break;
}
}
}
}
$timer->stop();
echo ’第一次排序时间:’.$timer->spent();
/*print_r($max);*/
$timer2 = new timer();
$timer2->start();
quicksort($number2,0);
$timer2->stop();
echo ’第2次排序时间:’.$timer2->spent();
/*print_r($number2);*/
运行结果:
第一次排序时间:2.370435秒
第2次排序时间:38.43304秒
ps:
运行时间可能有所变化,我是在几年前的笔记本上,ZEND测试的,不过显然第一次排序结果速度更快
建议继续学习:
- 如何使用1M的内存排序100万个8位数 (阅读:10902)
- 快速排序(Quicksort)的Javascript实现 (阅读:10090)
- 谷歌(Google)2011年校园招聘笔试题 (阅读:8913)
- 你是那10%可以实现二分查找算法的程序员吗? (阅读:6509)
- 深入浅出插入类排序算法(直接插入, 折半插入, 希尔排序) (阅读:6188)
- 深入浅出交换类排序算法(冒泡排序,快速排序) (阅读:5986)
- 15道使用频率极高的基础算法题 (阅读:5616)
- 新浪微博笔试题:找出共有2个以上标签的用户对 (阅读:4971)
- 有道实习生笔试总结 (阅读:4542)
- Java程序员必知的8大排序算法 (阅读:4458)
QQ技术交流群:445447336,欢迎加入!
扫一扫订阅我的微信号:IT技术博客大学习
扫一扫订阅我的微信号:IT技术博客大学习
<< 前一篇:关于新闻网页正文抽取的一些思路
后一篇:基于trie数据字典的php中文分词 >>
文章信息
- 作者:排头兵 来源: 排头兵 @ Talk
- 标签: 排序 海量数据 笔试
- 发布时间:2010-07-21 09:49:17
建议继续学习
近3天十大热文
- [54] IOS安全–浅谈关于IOS加固的几种方法
- [52] android 开发入门
- [52] 如何拿下简短的域名
- [51] 图书馆的世界纪录
- [49] Oracle MTS模式下 进程地址与会话信
- [49] Go Reflect 性能
- [47] 【社会化设计】自我(self)部分――欢迎区
- [46] 读书笔记-壹百度:百度十年千倍的29条法则
- [35] 程序员技术练级攻略
- [29] 视觉调整-设计师 vs. 逻辑