MyException - 我的异常网
当前位置:我的异常网» Java Web开发 » 最近遇到一个笔试题,求高手解决!解决方案

最近遇到一个笔试题,求高手解决!解决方案

www.MyException.Cn  网友分享于:2013-01-29  浏览:26次
最近遇到一个笔试题,求高手解决!
问题如下:
10亿个浮点数中,找出最大的10个浮点数,写出一个高性能算法。

求解。

------解决方案--------------------
分段排序不知道行不行

A.读取M*10条记录 (M>1) 排序取出最大的10条(排序算法根据每次读取的数量选择) 依大到小放进List[M*10]
B.List放满就排序 10条最大在最前面
C.还有记录就 继续 A 不过List开始的10条保留(从List[10]开始插入)
D.List 开始 10条是最大的

以上是单线程
在List填充了开始10条后
开M-1个线程(每个线程执行A步骤填充List[(1...M-1)*10])
然后List排序一次
不知道会不会快点





------解决方案--------------------
确切的说,排序算法是不错,最好的时间复杂度是n*Log(n),对于本问题,大概需要9*10^9次比较,不过牵扯的元素移动也比较多。
可以考虑设置1个10元素数组,用前10个值来初始化,然后挨个读取后续值,如果发现比其中的最小元素都大,那么把这个最小元素替换掉,者只需要浏览一边数据即可,时间复杂度10*10^9,这个的优点是不需要排序算法的元素移动量
------解决方案--------------------
楼上那些说排序的,都应该拉出去打40大板!

一个O(n)的遍历问题非要搞成O(n*lg(n))的排序问题,晕!
------解决方案--------------------
晕,干嘛要用排序,一次循环加个二分法插入(如果再加个多线程应该就会快很多)


Java code

    public static void main(String[] args) {
        int length = 1000000000;
        int[] numbers = new int[length];

        // 假设到此已经对10亿个的数字初始化完毕
        // 当然,也有可能,这10亿个数字是从别人地方来的,比如文件之类的
        int[] maxNumbers = new int[10];
        // 给maxNumbers赋值
        System.arraycopy(numbers, 0, maxNumbers, 0, 10);
        // 对10个数字进行其排序
        Arrays.sort(maxNumbers);

        for (int i = 10; i < length; i++) {
            binaryInsert(maxNumbers, numbers[i]);
        }
    }

    private static void binaryInsert(int[] numbers, int number) {
        // 二分法插入
        // 将number插入已经排序好的numbers中
        // 具体略过
    }

------解决方案--------------------
另外,到现在为止

插入10亿表到数据我已经等不下去了

环境:2003 + sql server 2000

插入3236347,花了16分钟多

算我机器慢,大家比我快上10倍,也要花上
49
分钟
------解决方案--------------------
探讨
引用:
晕,干嘛要用排序,一次循环加个二分法插入(如果再加个多线程应该就会快很多)


Java code
public static void main(String[] args) {
int length = 1000000000;
int[] numbers = new int[length];

// 假设到此已经对10亿个的数字初始化完毕
// 当然,也有可能,这10亿个数字是从别人地方来的,比如文件之类的
int[] maxNumbers = new int[10];
// 给maxN…


请问这位大虾:…

------解决方案--------------------
从10亿个浮点数中找出最大的1万个zt-part12008-05-16 12:34

从10亿个浮点数中找出最大的1万个。 


这是一道似易实难的题目,一般同学最容易中的陷阱就是没有重视这个“亿”字。因为有10亿个单精度浮点数元素的数组在32位平台上已经达到3.7GB之巨,在常见计算机平台(如Win32)上声明一个这样的数组将导致堆栈溢出。正确的解决方法是分治法,比如每次处理100万个数,然后再综合起来。不过这不是本文要讨论的主旨,所以本文把上题的10亿改为1亿,把浮点数改为整数,这样可以直接地完成这个问题,有利于清晰地讨论相关算法的优化(注2)。

不假思索

拿到这道题,马上就会想到的方法是建立一个数组把1亿个数装起来,然后用for循环遍历这个数组,找出最大的1万个数来。原因很简单,因为如果要找出最大的那个数,就是这样解决的;而找最大的1万个数,只是重复1万遍而已。

template< class T >

void solution_1( T BigArr[], T ResArr[] )

{

for( int i = 0; i < RES_ARR_SIZE; ++i )

{

int idx = i;

for( int j = i+1; j < BIG_ARR_SIZE; ++j )

{

if( BigArr[j] > BigArr[idx] )

idx = j;

}

ResArr[i] = BigArr[idx];

std::swap( BigArr[idx], BigArr[i] );

}

}

设BIG_ARR_SIZE = 1亿,RES_ARR_SIZE = 1万,运行以上算法已经超过40分钟(注3),远远超过我们的可接受范围。

稍作思考

从上面的代码可以看出跟SelectSort算法的核心代码是一样的。因为SelectSort是一个O(n^2)的算法(solution_1的时间复杂度为O(n*m),因为solution_1没有将整个大数组全部排序),而我们又知道排序算法可以优化到O(nlogn),那们是否可以从这方面入手使用更快的排序算法如MergeSor、QuickSort呢?但这些算法都不具备从大至小选择最大的N个数的功能,因此只有将1亿个数按从大到小用QuickSort排序,然后提取最前面的1万个。

template< class T, class I >

文章评论

“肮脏的”IT工作排行榜
“肮脏的”IT工作排行榜
每天工作4小时的程序员
每天工作4小时的程序员
“懒”出效率是程序员的美德
“懒”出效率是程序员的美德
不懂技术不要对懂技术的人说这很容易实现
不懂技术不要对懂技术的人说这很容易实现
当下全球最炙手可热的八位少年创业者
当下全球最炙手可热的八位少年创业者
聊聊HTTPS和SSL/TLS协议
聊聊HTTPS和SSL/TLS协议
总结2014中国互联网十大段子
总结2014中国互联网十大段子
为啥Android手机总会越用越慢?
为啥Android手机总会越用越慢?
程序猿的崛起——Growth Hacker
程序猿的崛起——Growth Hacker
Web开发人员为什么越来越懒了?
Web开发人员为什么越来越懒了?
看13位CEO、创始人和高管如何提高工作效率
看13位CEO、创始人和高管如何提高工作效率
漫画:程序员的工作
漫画:程序员的工作
5款最佳正则表达式编辑调试器
5款最佳正则表达式编辑调试器
什么才是优秀的用户界面设计
什么才是优秀的用户界面设计
如何区分一个程序员是“老手“还是“新手“?
如何区分一个程序员是“老手“还是“新手“?
程序员和编码员之间的区别
程序员和编码员之间的区别
老美怎么看待阿里赴美上市
老美怎么看待阿里赴美上市
程序员应该关注的一些事儿
程序员应该关注的一些事儿
10个调试和排错的小建议
10个调试和排错的小建议
我的丈夫是个程序员
我的丈夫是个程序员
做程序猿的老婆应该注意的一些事情
做程序猿的老婆应该注意的一些事情
我跳槽是因为他们的显示器更大
我跳槽是因为他们的显示器更大
Java 与 .NET 的平台发展之争
Java 与 .NET 的平台发展之争
程序员眼里IE浏览器是什么样的
程序员眼里IE浏览器是什么样的
中美印日四国程序员比较
中美印日四国程序员比较
60个开发者不容错过的免费资源库
60个开发者不容错过的免费资源库
旅行,写作,编程
旅行,写作,编程
代码女神横空出世
代码女神横空出世
十大编程算法助程序员走上高手之路
十大编程算法助程序员走上高手之路
Java程序员必看电影
Java程序员必看电影
鲜为人知的编程真相
鲜为人知的编程真相
程序员都该阅读的书
程序员都该阅读的书
初级 vs 高级开发者 哪个性价比更高?
初级 vs 高级开发者 哪个性价比更高?
 程序员的样子
程序员的样子
程序员的鄙视链
程序员的鄙视链
程序员周末都喜欢做什么?
程序员周末都喜欢做什么?
要嫁就嫁程序猿—钱多话少死的早
要嫁就嫁程序猿—钱多话少死的早
Web开发者需具备的8个好习惯
Web开发者需具备的8个好习惯
老程序员的下场
老程序员的下场
我是如何打败拖延症的
我是如何打败拖延症的
程序员最害怕的5件事 你中招了吗?
程序员最害怕的5件事 你中招了吗?
一个程序员的时间管理
一个程序员的时间管理
编程语言是女人
编程语言是女人
科技史上最臭名昭著的13大罪犯
科技史上最臭名昭著的13大罪犯
团队中“技术大拿”并非越多越好
团队中“技术大拿”并非越多越好
软件开发程序错误异常ExceptionCopyright © 2009-2015 MyException 版权所有