share ideas!!!: 2011

http://blog.sina.com.cn/s/blog_58ce6623010003dn.html

最短路径的应用是GIS中的基础。而最短路径的基础又是dijkstra算法。传统的dijkstra算法有一个最大的缺点，那就是用邻接矩阵，O（n*n）的代价是难以想象的，而且即使在dotNet编程环境下也无法构造出超过20000*20000的数组，这就是一些初学者的瓶颈。

对dijkstra算法的改进有多种方法，根据我的总结现有的优化方式有以下几种：1、用邻接表代替邻接矩阵。2、对需要搜索的点进行排序，以加快查找的速度。3、利用像a*算法的估价函数减少搜索的范围。4、双向搜索，不是传统的从起点到终点，而是起点和终点同时进行（个人认为这种方法比较适合两点间的最短路径）。5、估价函数（A*算法）。当然上次还看到了一种更土的做法：计算出图中所有点的最大出度，然后以此构造邻接矩阵（的确可以省不少空间，不过感觉就像在骗钱）。

现在总结一下。邻接表和排序是一定必须的，因为可以大量节约空间和时间上的开销。估价函数方面似乎很大的局限性，毕竟我们用来做最短路径的应用时会考虑到时间、空间以及其他一些因素，目前看到的估价函数也都是以欧氏距离为基础的，所以无法达到最佳效果；我暂时没有考虑这种有估价函数的方法，因为我觉得估价函数加入后，如果无法找到目标，极端的情况下必将遍历整个图，这也是个浪费。双向搜索似乎是一个不错的方法，可惜我也没有具体验证过到底能令效率提高多少。

不知大家是否记得传统dijkstra算法的做法，用两层for循环遍历图中所有节点，将找到最短路径的节点进行标记，并实时修改distance数组中的值，直到找到目标后结束循环。我这里要提出的思路同样基于dijkstra算法，但是最大的区别是我不像大多数实现那样在一开始就规定了扫描的次数。通常的做法使用一个排序的集合容纳需要稍描的节点，并在程序中动态修改这个集合，如果发现需要扫描的点则将其加入集合；每次取出集合第一位的值（权值最小的），扫描过之后则从集合中移除。扫描的结束条件是找到到所有终点的最短路径或者集合中没有任何点存在。为了防止形成回路和避免顺序集合的插入次数增多，标记法也是有必要的。

在另一帖里我说过，对PII或PIII的机子实现20000节点以上的路网可以在2~3秒内算出贯穿全程的两点间的最短路径表示怀疑，希望能有高手给出个实例看看，当然能有代码是最好的。

以下是我刚才所说的思路基于mapXtreme2004简单实现后的测试数据。

我的机器配置是PM1.5G，512M内存，32M显存。测试结果。1、基于福建省路网的测试：17111条道路，13701个节点，从北向南贯穿的最短路径计算平均时间在2500毫秒左右。2、基于全国路网的测试：27877条道路，22319个节点，计算从右上角到左下角贯穿的最短路径平均时间在6300毫秒左右。

最终结论，以前可能有朋友见过我发的帖子，有说过用Hashtable来实现。的确，我现在这个测试程序中也用了Hashtable。Hashtable的确能省一些事情，但是随之而来的是类型转换以及空间上的花费。如果将Hashtable用其他方法替换相信是完全可以提高效率的。

http://www.javaeye.com/topic/219844

一、函数的定义：

Python中使用def关键字定义函数，函数包括函数名称和参数，不需要定义返回类型，Python能返回任何类型：

Python代码  
#没有返回值的函数，其实返回的是None  
def run(name):  
       print name,'runing' #函数体语句从下一行开始，并且第一行必须是缩进的  
  
>>>run('xiaoming')  
xiaoming runing  
  
>>>print run('xiaoming')  
xiaoming runing  
None #如果没有ruturn语句，函数返回的是None  
  
  
#有返回值的参数  
def run(name):  
       return name+'runing'  
>>>r = run('xiaoming')  
>>>r  
xiaoming runing  

二、文档字符串：

在Python中注释是用#来表示的，暂时没有发现多行注释的写法。不过在函数内部可以使用多行字符串来写：

Python代码  
def run(name):  
       """ print somebody runing"""#写在函数体的第一行才叫文档字符串  
       print name,'runing'   

可以使用__doc__查看函数的文档字符串内容

Java代码  
>>>run.__doc__  
print somebody runing  

三、参数：

Python的函数的参数列表可以是任意多个，调用函数的时候，采取位置绑定和关键字绑定两种方式，确认传入的变量对应的参数！

上面演示的代码，都可以看作是位置绑定 。

下面看一下关键字绑定 ：

Python代码  
def run(name,age,sex):  
       print 'name :',name,'age:',age,'sex:',sex  
>>> run(age=23,name='xiaoming',sex='boy')#关键字绑定  
name:xiaoming age:23 sex:boy  

某个参数不能在一次调用中同时使用位置和关键字绑定

Python代码  
def run(name,age,sex):  
       print 'name :',name,'age:',age,'sex:',sex  
>>> run('xiaoming',name='xiaoming',sex='boy')  
SyntaxError: non-keyword arg after keyword arg  

函数调用的时候，如果第一个参数使用了关键字绑定，后面的参数也必须使用关键字绑定！

默认参数 :

Python代码  
def run(name,age=20,sex='girl'):  
       print name,age,sex  
>>>run('nana')  
nana 20 girl  
>>>run('nana',23)  
nana 23 girl  
>>>run('gg','boy')#使用的位置绑定，所以，python为将'boy'绑定在age上，而不是我们想要的sex上  
gg boy girl  
  
>>>run('gg',sex='boy')#混合关键字绑定，可以实现想要的效果  
gg 20 boy  

1、 如果一个函数的参数中含有默认参数，则这个默认参数后的所有参数都必须是默认参数 ，

否则会抛出：SyntaxError: non-default argument follows default argument的异常。

Python代码  
def run(name,age=10,sex):  
       print name ,age ,sex  
SyntaxError: non-default argument follows default argument gg 23 boy  

几个异常

Python代码  
def run(name,age,sex='boy'):  
       print name,age,sex  
  
>>>run()#required argument missing  
>>>run(name='gg',23)#non-keyword argument following keyword  
>>>run('gg',name='pp')#duplicate value for argument  
>>>run(actor='xxxx')#unknown keyword  
  
#第一种情况是丢失参数  
#第二种情况是：如果第一个使用了keyword绑定，后面的都必须使用keyword绑定  
#第三种情况：在一次调用中不能同时使用位置和keyword绑定  
#第四种情况：不能使用参数列表外的关键字   

2、默认参数在函数定义段被解析，且只解析一次 。

Python代码  
>>>i = 5  
>>>def f(arg=i):  
>>>    print arg  
>>>i = 6  
>>>f()  
5  #结果是5  

当默认值是一个可变对象，诸如链表、字典或大部分类实例时，会产生一些差异：

Python代码  
>>> def f(a, L=[]):  
>>>    L.append(a)  
>>>    return L  
  
>>> print f(1)  
>>> print f(2)  
>>> print f(3)  
[1]  
[1, 2]  
[1, 2, 3]  
  
#可以用另外一种方式实现：  
>>> def f(a, L=None):  
>>>    if L is None:  
>>>        L = []  
>>>    L.append(a)  
>>>    return L  

可变参数

参数被包装进一个元组。在这些可变个数的参数之前，可以有零到多个普通的参数：

Python代码  
def run(name,*args):  
       print name,'runing'  
       for a in args : print a  
  
>>> run('gg','mm')  
gg runing  
mm  
>>> run('gg',1,2,'mm')  
gg runing  
1  
2  
mm  
>>> run('gg',1,1.02,['mm','gm'])  
gg runing  
1  
1.02  
['mm','gm']  

可见可变参数可以是任意多个，而且是任意类型(并且能混合使用)

关键字绑定的可变参数 (**args这种形式，看原文档，不甚理解，暂且这样叫)

Python代码  
def run(name,**args):  
       keys = args.keys()  
       for k in keys :  
              print k,args[k]  
  
>>> run('nana',type='open')  
type open  
>>> run('nana',type='open',title='gogo')  
type open  
title gogo  
  
  
#*arg 必须在**args的前面  
def run(name,*arg,**args):  
       for a in arg :print a  
       keys = args.keys()  
       for k in keys :  
              print k,args[k]  
>>> run('nn','mm',1,2,'oo',type='open',title='gogo')  
mm  
1  
2  
oo  
type open  
title gogo  

参数列的分拆

Python代码  
>>> range(3, 6)             # normal call with separate arguments  
[3, 4, 5]  
>>> args = [3, 6]  
>>> range(*args)            # call with arguments unpacked from a list  
[3, 4, 5]  

通过 lambda 关键字，可以创建短小的匿名函数

Python代码  
#这个例子没怎么看懂  
  
>>> def make_incrementor(n):  
...     return lambda x: x + n #相当于创建了一个一x为参数的匿名函数？  
...  
>>> f = make_incrementor(42)#f = make_incrementor(n=42)，设置n的值  
>>> f(0)#其实调用的是匿名函数？  
42  
>>> f(1)  
43  
  
  
#看下面一个例子报的错误明白一点了  
>>>def t(n):  
...          print x*n  
>>>m = t(2)  
Traceback (most recent call last):  
  File "", line 1, in   
    m = t(2)  
  File "", line 2, in t  
    print x*n  
NameError: global name 'x' is not defined  
  
说是没有定义全局name 'x'  
  
>>> x =10  
>>> def t(n):  
...        print x*n  
>>> m = t(2)  
20  

博客归档

2011年7月29日星期五

Dijkstra算法-分析

2011年3月31日星期四

python 中的函数

二、文档字符串：

三、参数：

浏览统计

博客归档

2011年7月29日星期五

Dijkstra算法-分析

2011年3月31日星期四

python 中的函数

二、 文档字符串：

三、参数：

浏览统计

二、文档字符串：