Archive for the ‘数据结构、算法’ Category

接上篇。尽管已经降到了十万分之一级别的几率,但并发下浏览器的不靠谱行为依旧存在。IE6-8下依旧为主要因素,这与使用者人数多也有关,基数大所以数量高。另外2次幂延迟算法对于单线程情况(aA)是能够完全纠正的,这点值得欣慰。
并发时,abAB、aABb、aAbB、ABba、abBA、AbBa、aBbA、aBAb几种情况按几率依次递减,想要完美解决必须全部纠正。在2次幂延迟算法纠正后,前面3个已经正确,但后面的还是错误的,它们可以统一概括为:ABba。结果原本应该赋给A的a跑到B的身上,互相错位了,所以要进行错位交换。
理论上前期不可能再进行处理了,我耗了很久发现前期处理是个悖论,剩下的可能只有运行时决定。
在运行时:
use(['a', 'b'], function(a, b) {
a.methodA();
b.methodB();
});
在错位情况下,a不具有methodA方法b才具有,b也反之。此时会抛异常。简单的做法是运行时try,捕捉到异常后交换错位的arguments再运行一次。看起来似乎不错,实际陷阱重重。
首先methodA和methodB可能方法名相同,甚至逻辑极为相似。这样就不会异常但运行结果是错的。这个概率很低。
然后这是在2个参数的情况下,2个以上排列比例太多,交换次数很恐怖,不切实际。
还有这只有1级递归,也就是a和b互相颠倒而已。如果a有依赖或b有依赖,所造成的错位可能有很多,那它们之间互相递归交换非常恐怖,根本不可能实现。
即使可以通过的define进行包裹一层,抽出factory返回的方法名来提升判断callback的参数顺序准确度,但依然不能解决上述所有问题。所以最后错位交换算法被pass。
IE下,通过getInteractiveScript的方法,可能提升并发准确度到百万分之一的级别,有待验证。

接上篇。另外对于基础性原理不清楚的请查看射雕的介绍:http://lifesinger.wordpress.com/2011/11/11/get-url-in-module-loader/
通过1周的海量数据多次测试与研究,我和射雕发现了所有浏览器下都有的共同bug:onload事件先于script标签的加载发生。这个结论直接表明,目前所有对于script的onload的侦听都不是完美的!一旦有了这个低几率问题,那些莫名的错误会让人十分困惑。
介于此,我尝试使用2^ delay的算法来延迟onload的运行。它的理论基础来源于抑制网络风暴的算法:即onload先检查script的exec,没有时延迟2 ^ 0单位时间后再检查、再没有延迟2 ^ 1、2 ^ 2……以此类推。
在昨天的海量观测数据下面,结果是惊喜的。没有1次发生了error,全部正确。但是依然存在低几率次序打乱的情况,这是接下来要着手解决的问题(或者干脆忽略掉)。
最后祝福下Firefox和IE10,你们的顺序是100%正确的。
other success
AaBb 1
BbAa 1
Aa 1
AaBb 1
Bb 1
BAba 1
ABab 1
BbAa 1
BAba 1
ABab 1
Aa 1
AaBb 2
BbAa 3
Aa 3
BAba 3
Bb 4
Aa 5
BbAa 8
ABab 11
Bb 12
ABab 23
AaBb 23
Aa 26
AaBb 28
Bb 28
Aa 91
Bb 97
ABab 171
opera success
BbAa 1
BAab 1
ABba 1
BaAb 1
ABab 28
Bb 2742
Aa 2783
AaBb 5484
ie8 success
ABba 2
AbBa 8
BAab 17
BaAb 29
BAba 30901
BbAa 82405
AaBb 233970
Bb 599658
Aa 600632
ABab 853122
webkit success
ABba 2
BAab 2
BaAb 4
AbBa 5
BbAa 50606
Aa 246173
Bb 246419
AaBb 441956
ie10 success
BAba 2
AaBb 8
BbAa 9
Aa 29
Bb 31
ABab 36
ie9 success
AbBa 2
BaAb 4
BAab 30
ABba 159
BAba 8915
BbAa 15603
AaBb 35080
Aa 104627
Bb 105027
ABab 149314
ie7 success
AbBa 8
BaAb 12
BAab 35
ABba 81
BAba 11900
BbAa 25614
AaBb 66317
Aa 193519
Bb 193970
ABab 282723
ie6 success
ABba 10
AbBa 14
BAab 21
BaAb 57
BAba 50272
BbAa 104528
AaBb 275505
Bb 811928
Aa 813622
ABab 1189557
FF success
ABab 90
BbAa 5578
Bb 34745
Aa 34866
AaBb 63339

这是我第3次做拼图游戏了。算法简单得很,而且是最少的9宫拼图,拿到设计稿后不外几个小时搞定。
记得2008年7月份,刚毕业被EOL拉进PCHome的时候,工作所做的第一个就是flash游戏拼图(9、16、25宫)。那时为了研究出如何防止拼图死局,着实花了不少功夫(小时候玩的金山文曲星中就经常出现这个bug)。为此我特地发了个帖子求助数学大人,最终问题得以解决。
那么,什么是拼图死局呢?
以最简单的9宫拼图为例,拼图的最终目的是将随机的数块移动到如下状态:
1 2 3
4 5 6
7 8
第9格是空的,用以让玩家能够任意移动某一个数块。但是,初始随机情况可能会是这样:
1 2 3
4 5 6
8 7
这种情况下,想要变换到正确的结束状态是不可能的。至于为什么,繁琐的数学证明就不贴了。记得曾经《读者》杂志上刊登过这个东西,说是国外某位数学家悬赏1000w美金让人来拼这个拼图,结果无一人能做到。最后他才公布为何不能做到:因为这种情况的开始逆序和和目标逆序和不同。
数学定义:
n*n的方格中放入1,2,3,…,n-1及一个空格,在任何一种状态A下,
定义:f(i)=k,表示i放在第k个格子中,k按照从左至右,从上到下排序;
定义:g(i,j)=1,如果(f(i)-f(j))(i-j)<0;否则为0;
定义:F(A)=SUMg(i,j),对所有i,j求和;
当n=3时;
目标状态F(Aobj)=0,你给的状态F(Abegin)=1;
而移动空格只有2种方式:在同行中移动不改变F值,在不同行中移动F值+2,-2或不变;
利用F函数可以解决所有n为奇数的情况;
当n为偶数时,定义F1(A)=F(A)+空格所在行&1;处理方式一样。
当初始随机情况出现死局时,逆序和就会不相等,那么发现之后该怎么办呢?当然不会重新去随机一次,这太傻了。解开锁的钥匙很简单,随便交换同行的2个数块的位置即可。
那个时候写的一个产生9、16宫随机初始数块顺序的工厂(现在看来无需用工厂方法,一个类就能搞定):
//GenMatrixFactory
package matrix {
public class GenMatrixFactory {

public static function getArray(i:int):Array {
var…