2012感恩节最短源代码比赛edit代码解析

〇〇

newkid 发表于 2012-12-4 03:58
我用SQL的方法和楼主代码比较，SQL吃亏在硬解析，如果都比较第二次运行结果则差不多，在我机器上都是0.2秒 ...

看来效率要多个样本才能测得出来

solomon_007

还是NEWKID 最NB！

dingjun123

good job

edit

newkid 发表于 2012-12-4 03:58
我用SQL的方法和楼主代码比较，SQL吃亏在硬解析，如果都比较第二次运行结果则差不多，在我机器上都是0.2秒 ...

递归的劣势就在于层级越深的时候  尝试的次数成次方增长

而其中无效的尝试会很多 要占用很多时间

想提高效率  需要尽可能减少这样的无效尝试  优化判断的方法

lastwinner

edit 发表于 2012-12-4 09:31
递归的劣势就在于层级越深的时候  尝试的次数成次方增长

而其中无效的尝试会很多 要占用很多时间

递归的优势也正是在可以提前结束无效的尝试，而sql中的connect by就做不到但11g的CTE可以
所以为了提高效率，其实有些判断可以提前进行

newkid

如果有强大的剪枝条件，及时去除无效的中间结果，递归的效率也是很高的。比如这道题我们只关心平移到左上角的形状，那些已知不在轴上的、必定重复的就可以尽早去掉。

我看好几个人都自己实现了排序？要是我写纯PLSQL解法，我会用INDEX BY TABLE。但是访问得用NEXT, PRIOR, 不能用FOR LOOP了。比起SQL方法是可以更早发现重复记录。