遇到的一个追求速度的算法,国外有人控制在30秒内,小弟我却要6分钟
遇到的一个追求速度的算法,国外有人控制在30秒内,我却要6分钟.
算法题:通过最快的速度遍历下面黑盒中的字串(字串大于1G),并写入到文件.
内部数据的格式如下:
000000000000000000000000000000000000000000000001111111111111
111111111111111111111122222222222222222223333333333333333333
333300000000000000000000000001111111111111111111111111111122
222222222222333333333333333333333333333300000000000000000001
111111111111111111122222222222222222222222222223333333333333
333333333333333333333333333330000000000000000000000000000001
111111111111111111111111111111111122222222222222222222222222
333333333333333333333333300000000000000000000000001111111111
111111111111111111111112222222222222222222222222222333333333
333333333333333300000000000000000000000000000000111111111111
111111111111111222222222222222222222222222333333333333333333
333333333333333300000000000000000000000000000000000000000000
想获取黑盒里某处的值是多少,调用下面的函数(dwPos最大值等于黑盒中字串的长度).
BYTE GetPosValue(DWORD dwPos);
例如: 结果:
BYTE byVal = GetPosValue(0); byVal == 0;
BYTE byVal = GetPosValue(48); byVal == 1;(第一个1出现的位置是48)
黑盒中每一种数值连续出现的次数不一定是相同的.但即使不同,也不会相差太远.
例如:
不会出现的情况: 某处有10000个连续的1,紧接着出现50个连续的2.
常见的情况 : 某处有10000个连续的1,紧接着出现的2可能在7654--13456之间.
整个遍历过程中,调用GetPosValue这个函数的次数越少越好。
如果存在一种极端的情况:
就是上面提到的 : 某处有10000个连续的1,紧接着出现50个连续2.
这里的50个2可以忽略掉,把它当作它前面的1来保存也可以.
这个算法该怎么编写呢？请大家帮帮忙，谢谢啦~~~~~~~~~~~~~~~~~~~~~~~~~
------解决方案--------------------
第一次跳4min - 1，如果还是0，则继续跳3min
如果跳到不是0的，则继续条3min，直到跳到下一个循环，比如又跳到0
这样可以知道一个循环的大致总长度，进一步找分隔点时会更快。
------解决方案--------------------
关键是字符串的数字个数，同一个数字的重复次数不影响遍历算法的效率，但如果同样大小的字符串包含的数字个数多，那遍历的时间就会长。
举个例子，比如1G的字符串，0的重复次数如果是在10000次左右，而1的重复次数也在7000到13000之间，那字符串的数字个数大概可以这样计算：1024*1024*1024/10000=11000左右。而如果每个数字的重复次数很少，比如都在80到100之间的个数重复，那字符串包含的数字就会多出100倍。
------解决方案--------------------
请问楼主，允许一定的误差是每一段都允许呢？还是只能少部分的段允许？
如果错误的字符数总量相等，每一段都有很小的误差和只有几段有误差但是每段误差都比较大，那种情况更不能忍受？
------解决方案--------------------
应该要好好用这个属性：
黑盒中每一种数值连续出现的次数不一定是相同的.但即使不同,也不会相差太远.
例如:
不会出现的情况: 某处有10000个连续的1,紧接着出现50个连续的2.
常见的情况 : 某处有10000个连续的1,紧接着出现的2可能在7654--13456之间.
不如第一次间隔是4min-1，如果还是0，则间隔调整到 （4min-1） * ２＊（７６５４／１００００），如果还是０，则调整到已知‘０’的长度 ＊2 * （７６５４／１００００）直到找到非0的数。
------解决方案--------------------
推荐一个思路：试着预测每个串的长度，既然前面说了那么多规律，我想每个串的长度也是有规律的，或者说大部分情况都是有规律的。这样就能根据前面得到的数据预测后面的长度
------解决方案--------------------
我发样例程序共享在
http://download.csdn.net/detail/volcano3035112/3690980
有兴趣的朋友可以去看看.
算法题:通过最快的速度遍历下面黑盒中的字串(字串大于1G),并写入到文件.
内部数据的格式如下:
000000000000000000000000000000000000000000000001111111111111
111111111111111111111122222222222222222223333333333333333333
333300000000000000000000000001111111111111111111111111111122
222222222222333333333333333333333333333300000000000000000001
111111111111111111122222222222222222222222222223333333333333
333333333333333333333333333330000000000000000000000000000001
111111111111111111111111111111111122222222222222222222222222
333333333333333333333333300000000000000000000000001111111111
111111111111111111111112222222222222222222222222222333333333
333333333333333300000000000000000000000000000000111111111111
111111111111111222222222222222222222222222333333333333333333
333333333333333300000000000000000000000000000000000000000000
想获取黑盒里某处的值是多少,调用下面的函数(dwPos最大值等于黑盒中字串的长度).
BYTE GetPosValue(DWORD dwPos);
例如: 结果:
BYTE byVal = GetPosValue(0); byVal == 0;
BYTE byVal = GetPosValue(48); byVal == 1;(第一个1出现的位置是48)
黑盒中每一种数值连续出现的次数不一定是相同的.但即使不同,也不会相差太远.
例如:
不会出现的情况: 某处有10000个连续的1,紧接着出现50个连续的2.
常见的情况 : 某处有10000个连续的1,紧接着出现的2可能在7654--13456之间.
整个遍历过程中,调用GetPosValue这个函数的次数越少越好。
如果存在一种极端的情况:
就是上面提到的 : 某处有10000个连续的1,紧接着出现50个连续2.
这里的50个2可以忽略掉,把它当作它前面的1来保存也可以.
这个算法该怎么编写呢？请大家帮帮忙，谢谢啦~~~~~~~~~~~~~~~~~~~~~~~~~
------解决方案--------------------
第一次跳4min - 1，如果还是0，则继续跳3min
如果跳到不是0的，则继续条3min，直到跳到下一个循环，比如又跳到0
这样可以知道一个循环的大致总长度，进一步找分隔点时会更快。
------解决方案--------------------
关键是字符串的数字个数，同一个数字的重复次数不影响遍历算法的效率，但如果同样大小的字符串包含的数字个数多，那遍历的时间就会长。
举个例子，比如1G的字符串，0的重复次数如果是在10000次左右，而1的重复次数也在7000到13000之间，那字符串的数字个数大概可以这样计算：1024*1024*1024/10000=11000左右。而如果每个数字的重复次数很少，比如都在80到100之间的个数重复，那字符串包含的数字就会多出100倍。
------解决方案--------------------
请问楼主，允许一定的误差是每一段都允许呢？还是只能少部分的段允许？
如果错误的字符数总量相等，每一段都有很小的误差和只有几段有误差但是每段误差都比较大，那种情况更不能忍受？
------解决方案--------------------
应该要好好用这个属性：
黑盒中每一种数值连续出现的次数不一定是相同的.但即使不同,也不会相差太远.
例如:
不会出现的情况: 某处有10000个连续的1,紧接着出现50个连续的2.
常见的情况 : 某处有10000个连续的1,紧接着出现的2可能在7654--13456之间.
不如第一次间隔是4min-1，如果还是0，则间隔调整到 （4min-1） * ２＊（７６５４／１００００），如果还是０，则调整到已知‘０’的长度 ＊2 * （７６５４／１００００）直到找到非0的数。
------解决方案--------------------
推荐一个思路：试着预测每个串的长度，既然前面说了那么多规律，我想每个串的长度也是有规律的，或者说大部分情况都是有规律的。这样就能根据前面得到的数据预测后面的长度
------解决方案--------------------
我发样例程序共享在
http://download.csdn.net/detail/volcano3035112/3690980
有兴趣的朋友可以去看看.