首页 诗词 字典 板报 句子 名言 友答 励志 学校 网站地图
当前位置: 首页 > 教程频道 > 软件管理 > 软件架构设计 >

有10亿个浮点数中找到1万个最大的数(bit比较法)

2012-07-30 
有10亿个浮点数中找出1万个最大的数(bit比较法)网上已经有很多多的算法,现考虑一下用bit位比较法,请各位看

有10亿个浮点数中找出1万个最大的数(bit比较法)
网上已经有很多多的算法,现考虑一下用bit位比较法,请各位看看有没有问题~

算法思想:
以正整数为例(浮点数类似),假设从总数为total的正整数中求最大的max个数,正整数最高位到最低位分别对应第32-1位:

Proc:
将第i位(i=32)为1的放入文件A中,假设有n个数在A中,
1. 如果n>max,则问题变成求这n个数中最大的max个数,可设total=n, i--然后递归Proc;
2. 如果n<max,则输出这n个数,问题变成求剩下的(total-n)个数中最大的(max-n)个数,可设total=total-n, max=max-n, i-- 然后递归Proc;
3. 如果n==max则这n个数即是所求,输出这n个数,返回即可。

该算法最差需要对每个数查询32次,但时间复杂度仍为O(n).


下面分析浮点型的处理:
浮点数在内存中的存储
单精度浮点数: 1位符号位 8位阶码位 23位尾数
双精度浮点数: 1位符号位 11位阶码位 52位尾数

浮点表示的一般形式为:R=M*2^e (R:Real M:Mantissa尾数 e:exponent阶码)
float型浮点数125.5转化成32位二进制浮点数:
125.5的二进制码为1111101.1,写成二进制的科学计数为:1.111101*2^6(因为科学计数法“整数”部分大于1,在二进制中,“整数”部分只能恒为1)即向左移6位,则e=6,则E=e+127=133,而E的二进制码为10000101,而1.111101把“整数”部 分去除1之后为111101,之后补0,共23b,形成了阶码。
所以125.5的32位二进制浮点数为:
0 10000101 11110100000000000000000

由此,我们知道首先比较符号位,然后再比较阶码位,最后再比较尾数即可解决该问题。


[解决办法]

探讨

1. 如果所有的数值的最高位都为1,则会比较次高位,...,这样一位一位递归下来最多也只要遍历32次(32位正整数)啊,想不明白为什么会到O(nLogn)
2. 比较之前必须确定数值的表示方法,统一用一种表示方法。

[解决办法]
时间复杂度是低了,但空间复杂度太高了,是o(n),对于本题,最坏情况(所有都是正数或负数)是10*10000*10000*sizeof(float)=4g,这么高的空间复杂度,在实际运行中是非常耗时的
[解决办法]
我弄错了,抱歉。
不过好像还是是o(nlogn)的。
相当于根据从高到低的bit位将被排序数据进行了分段。在局部内进行选择。
每次分段的过程需要将所有的数据遍历一次,分段之后,再对局部内的数据再次遍历。
所以遍历的次数是logn,分段内的复杂度是o(段长度)
由于待选择的总数小于n,所以不需要对每一个分段都进行遍历,所以是小于o(nlogn)的,但是貌似大于o(n)

探讨
1. 如果所有的数值的最高位都为1,则会比较次高位,...,这样一位一位递归下来最多也只要遍历32次(32位正整数)啊,想不明白为什么会到O(nLogn)
2. 比较之前必须确定数值的表示方法,统一用一种表示方法。

热点排行