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 >

文章评论

软件开发程序错误异常ExceptionCopyright © 2009-2015 MyException 版权所有