-
-
[求助]工作中遇到的一个追求速度的算法,国外有人控制在30秒内,我却要6分钟.
-
发表于: 2011-10-12 18:57
-
|
|
|---|---|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
等s牛来弄个3秒的，吓死你。
|
|
|
其实我也蛮希望S大来关照一下哈。。什么算法对S牛来说都是浮云。。。。我对S牛的膜拜用登峰造极都形容不过来。。。。
|
|
|
|
|
|
|
|
|
呵呵
学习 了
|
|
|
|
|
|
没有这种最极端的情况.
可以保证0、1、2、3每个byte连续出现的个数至少在20000以上. 二分法的确不能保证数据全部正确,但当出现2W个1后面接几百个2的情况，可以忽略掉这几百个2 用write_to_binary_file(GetPosValue（pos++）)的确能保证百分百的精度，但那就不存在算法了啊。而且速度就。。。。 
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
多谢天易大侠指点,为了学习二分枚举,我翻了好多ACM题,但发现好多是英文题目。
 还在继续google中。。 如果大家还有其它的思路，也来发表发表呀。 |
|
|
|
|
|
谢谢你。我用的第一总方法与你提供的思路差不多。
我是用 0 10000 20000 30000 这样的dwPos来累加的。。 我发现现在最耗时的就是二分查找的时候。 如果要生成测试文件很简单。 以2W为基数,用一个1.6W 到 2.3W之间的随机值来写0、1、2、3.生成一个2G的文件就可以了。我这里的数据是在硬件中取的，提供不了伪文件 
|
|
|
|
|
|
二分查找某个数的位置的确很快的。
但我现在的二分是找相邻的两个byte不等. 所以比查找某个数位置的二分要耗时一些。。 现在我是这样做的(假设发现2W和4W的位置不等了)：
DWORD min = 2W;
DWORD max = 4W;
if (F(min) != F(max)) //这里只是做为递归的依据,
{
if ((F(max) == F(max-1)) && (F(max-1) != F(min)))
{//说明 max 处相邻的两个是 相等 的，并且 不等于 min的位置处,此时要max设为3W
....小值不变min = 2W,大值 max 为3W后递归....
}
if ((F(max) == F(max-1)) && (F(max-1) == F(min)))
{//说明 max 处相邻的两个是 相等 的，并且 等于 min处位置的值,
...此时要将 mix 设为3W,max 设为4W(这里的将max设为4W应该可以优化的,因为前面已经读过这里的值)...
}
if ((F(max) != F(max-1)) && (F(max-1) == F(min)))
{//max 不等于 max-1 ,说明找到分隔点了,直接返回max
return max
}
}
我的大致程序就是这样子的。感觉这个算法很迂回, 不行的，因为调用GetPosValue一次只能取一个byte. 如果我能全放到内存里*pBuf++ = GetPosValue(dwPos++); 相当于是全部遍历了一遍
|
