原題：SHPATH
题意很简单，但是因为测试数据非常庞大，非常容易超时。推荐使用Dijkstra+BinaryHeap的算法，不过我的程序是没有通过的，Python写的代码光是读取数据就要用8s，并且即使读取结束，也总会运行时错误。
在tutorial组的题目中有一个Turtle’s Shortest Path TSHPATH，题目完全一样，测试数据也一样，除了时间限制很宽松，可以用来测试程序是否正确。
我后来编写了C版本的Dijkstra+BinaryHeap的代码，却总是WA，而用我自己特地生成的随机数据进行测试结果却完全正确（对比了问牛人要来的代码运行的结果）。
下面是我的代码，如果有牛人路过，希望能指出其中的错误：
Python版（我记得有些许小错误，因为某些数据和C版本不一致），C版本
gengraph测试数据生成脚本，不过可能会产生孤点。
Tag Archives: python
SPOJ#15 The Shortest Path
2008年11月16日 – 5:34 下午
PRIME1解题笔记
2008年10月28日 – 9:46 下午
前几天JeffChen告诉我他要学习Python，后来他找到了SPOJ这个在线的算法竞赛网站，可以支持很多种不同的编程语言，其中包括Python。而我突然发现我很久以前就注册了我的帐号，现在一下又来了兴趣。虽然在中学的时候也搞过信息学奥赛，不过没有出过江苏省，和ACM的差距还是非常非常大。因为我数学功底不行，这方面没法深入，所以转投应用领域，加上很懒，所以喜欢用脚本语言。
言归正传，下面把我解决PRIME1这道问题的方法记录下来：
求质数最经典的方法是Eratosthenes筛选法，一般都是利用一个布尔数组作为筛选器，将下标作为目标数，元素作为该目标是否为质数的标志，并且对于给定范围1~n之间的数，只需要筛选掉1到sqrt(n)之间的质数的所有倍数，剩下的就都是质数了。
起初我使用Python是直接利用range函数生成列表，并没有用到筛选表，通过filter函数和取模%筛选掉质数，最后直接得到整个列表。但是问题在于性能低，另外对于大数则会内存不够（无法生成给定长度的列表），我也尝试过使用dict对象来建立筛选器，不过都失败了。
问题关键在于Python是脚本语言，对于速度，尤其是列表的遍历，不应该使用filter或者for循环，应该使用列表理解，,并且抛弃%运算，配合python列表的slice语法，即x[start:end:step]=[...]的方法，进行定长步长（以质数为步长）的批量替换。
对于内存不够，可以建立一个映射关系，最后的筛选数组中，不考虑偶数，把奇数转换成筛选数组的索引（n/2-3），但需要一些算法精确配合上面的slice语法计算起始位置和长度。
2008-8-30 Google AppEngine Camp小记
2008年08月30日 – 11:40 下午
有幸参加了谷歌上海组织的Google AppEngine Camp的技术交流会。很惭愧的是我还没有好好地去研究Google AppEngine（以下简称GAE），就来滥竽充数了，而且还因为某些原因，迟到了半个小时。
Google愧为开发者心目中的圣地，谷歌上海也充分反应了Google的企业文化。当我这个乡下人刚进入来福仕广场的办公楼的时候，顿时有一种非常豪华的感觉。进入了谷歌上海的办公室，第一印象就是专业，（非公司成员进入办公室都需要贴个条子，条子是用标签机打印出来的）。房间的配色给人感觉非常明亮，办公室的每一样设备都非常专业／高档：会议室的投影设备、视频、音频点播系统（恕我老土吧，我不知道那个机柜里面放的都是什么）。会议室旁边应该是一个很大的休息区域，估计也是活动区域，还放了电子琴、电吉他等。有一排书柜上放了不少杂志和书籍（有金庸全集），还有两个冰柜，放了各种饮料可以各取所需。甚至还有一个吧台，有微波炉、咖啡机等等。甚至（男）厕所都非常有个性。办公区域的显示屏也倍儿有面子，每个人桌上的东西也很有个性（各种谷歌的小玩意儿）。墙上随处可见Google的Doodle。
此次参加活动，除了以上的印象外，还有一个印象就是帅哥多，MacBook多。最大的遗憾就是没有带相机，否则可以将照片贴出来。
不过还是有一些我觉得不好的地方：
一部分人在演讲人讲话的同时在下面开小会讨论自己的问题。我认为这个是对演讲人和想听演讲的人的不尊重。其实完全可以走出去到活动厅讨论么。
演讲的同时，我还曾听见有人直接在底下接电话。
虽然演讲人说可以随时打断他的讲话并提问，但我认为既然有人主讲而不是以完全的沙龙形式，就应该控制时间，总是打断不利于提高效率，很多东西可以私下交流。
主讲人也应该注意控制时间，5分钟演讲大部分都大大超过这个时间。
此次活动最大的收获估计就是能参观一下传说中的谷歌办公室。希望下次还有机会去吧。
cElementTree备忘
2007年03月27日 – 6:18 下午
ElementTree是Python2.4下我常用的一个XML处理模块，而cElementTree则是它的C语言版本，有很好的性能。最终Python2.5则直接捆绑了ElementTree，变成了xml.etree.ElementTree和xml.etree.cElementTree. 特此备忘。
SQLObject的问题
2007年01月18日 – 10:45 上午
提到Python的ORM，首先想到的有两个SQLObject和SqlAlchemy，还有Django的ORM，另外，还有Zope的。
前几日和Nicholas又讨论到SQLObject这个东西，就目前Python现有的ORM工具来说，最容易使用还是它了，SqlAlchemy对于懒人、初学者的我来说，还是复杂了点；而Zope相对是个庞然大物，整体的解决方案，小东西往往也不会去用到。
当然SQLObject的问题不在于它使用了ActiveRecord模式，Django的ORM同样也用到了这个模式，因为起初用TurboGears（0.8.9，当时SO的版本可能还没到0.7）做了一个小东西，那个时候便发现了诸多问题，尤其在编码问题上卡住了。这一次正准备对原有的东西增加新的功能，便几乎无法做下去了。
比如业务领域有“角色”这个词，在业务上应当翻译成“Character”。我建立了一个Character类，SO在自动根据代码的Model建立表结构的时候，不会像Rails那样考虑单复数，因此它会尝试建立“character”表，而Character、Char在mysql中都是保留词，而SQLObject甚至都不知道在SQL语句中对其进行转义。为了解决这个问题，我指定SO去建立characters表，接下来的问题就是，SO在寻找Character表相关的外键时，是考虑了characters_id，而对于存在这个外键的表，SO在建表的时候还是使用了character_id这个名字，最终导致了错误。
另外编码又有新问题，Python中使用%格式化操作符时，左边或右边任意一方出现了unicode字符串，最后的结果都会是unicode，而SO也同样没有考虑到，最后导致本已经是unicode的查询字符串，SO还要去再decode一次，最后导致了错误。
所以不推荐大家使用SO，尤其要做复杂产品的时候。
另外，Django的ORM也可以拿出来单独使用，值得研究一下。
Python MySQLdb的重大疑问
2006年10月13日 – 6:35 下午
最近开发Python，数据库操作一直用的是SQLObject，但有个问题很让我头疼，就是MySQL的数据库的编码问题，主要是MySQL的。
起初我现在我在SQLite上测试开发，并没有出现问题。SQLObject的UnicodeCol工作很正常。而同时起初数据库中并没有任何非ASCII字符（也就是全英文），而后需求变化，增加了欧洲的一些内容，就涉及到latin1编码了，但奇怪的是，只要超出ascii范围（比如中文），即便通过Python将其转化为Unicode或者UTF-8编码的str（使用decode和encode方法），SQLObject在插入的时候就会出错。后来经过反复的检查，是MySQLdb的一个问题，SQLObject会通过获取数据库链接的character_set_name()，取得链接的字符集，然后对查询进行编码以符合这个字符集，但据调试，无论我用什么方法，比如链接的set_character_set()方法、执行“SET NAMES UTF8”这个语句，character_set_name()都总是返回“latin1”，这些可苦了我了，不知道这是不是算一个Bug。
简介延续“Continuation”
2005年10月18日 – 11:59 下午
作者： Denys Duchier
翻译： Shining Ray @ Nirvana Studio
写本文旨在回应comp.lang.python新闻组中关于延续的讨论。
对于call/cc（call with current continuation）的情结和关于他的操作解释粗糙的细节内容，至今一直掩盖了延续的简洁和优雅。在本文中，我想用两个方式来纠正这个问题：
首先用一个简单且直观的方式展示延续的概念。
第二通过提供_可运行的_Python代码，来描述如何使用延续而不用call/cc来实现搜索引擎。
我将展示：
一个针对命题公式确定性检查工具。
一个基本的带回溯和裁剪的prolog引擎。
我希望这能帮助那些对于这个论题有些迷惑的人搞清这个问题。我还想指出上面讲到的两个程序是我在今天晚上花了几个小时写的，他们应该可以给你关于下面将要讲述的技术的能力的一些衡量尺度。
1. 简化延续
习惯上一般来说，一个函数返回一个值是这样的：
def foo(x):
return x+1
这隐含了它的值返回的地方。而延续的想法是通过添加一个延续参数来明确要返回的地方。函数不“返回”值，而是通过把值作为一个参数传递给延续“继续”处理值。在基于延续的程序中，以上函数foo变成了：
def foo(x,c):
c(x+1)
从这个角度看，函数从不使用返回“return”。取代的是它“继续”。正因为这个原因，延续有时候会被描述为“带参数的goto”。
上面描述的想法是。更精确地说，它是CPS（Continuation Passing Style，延续传送风格）的一个初步代码转换。基本的想法是给每个函数添加一个额外的“延续”参数，并进一步转化函数体以便不用返回他的值，而是把值传送给这个额外的延续参数。
在foo函数的例子中已经大体描述了这个概念。然而，更确切的，要注意CPS转换同时展开了所有的非lambda算子的嵌套表达式（换句话说，就是他显式地连接了所有子表达式的计算）。让我们看一个例子：
def baz(x,y):
return 2*x+y
在延续传送的观点中，甚至像*和+之类的基本操作符都要带一个额外的延续参数。我们通过以下定义进行模拟：
def add(x,y,c): c(x+y)
def mul(x,y,c): c(x*y)
现在，CPS可以把上面的baz函数转换成：
def baz(x,y,c):
[...]
Python 不是 Java
2005年07月14日 – 12:14 下午
作者：Phillip J. Eby.
翻译：ShiningRay @ NirvanaStudio
原文地址：http://dirtsimple.org/2004/12/python-is-not-java.html
我最近正在看一个基于wxPython的GUI应用程序，大概45.5KLOC的样子，但我没有计算它用到的库的大小（如Twisted）。代码是由那些对Python相对生疏的Java的开发者写的，所以程序有很严重的性能问题（如三十秒的启动时间）。我在检查代码的时候发现他们写了很多对Java有意义但是对Python却很恐怖的东西。并不是因为“Python比Java慢”，而是因为在Python中有更方便的方法去完成同样的目标，甚至在Java中不可能的事情。
所以，可悲的事就是这些可怜人事倍功半，产生了很多很多不需要写的代码，从而比相应合乎Python习惯的写法慢得多得多。我们来看一些例子：
在Java中一个静态的方法（static）不能翻译成一个Python的类方法（classmethod）。哦，当然，多多少少他最终产生类似的效果，但类方法的目的实际上是做了一些通常在Java中不可能的事（如继承一个非默认的构造函数）。Java静态方法的习惯翻译通常是一个模块级函数，而不是一个类方法或静态方法（staticmethod）。（同时静态封闭（final）字段应该翻译成模块级常量。）
这并不是一个性能上的问题，但是一个Python程序员要用像这些类似Java习惯的代码的话，可能就会被在该输入Foo.someFunction时却要输入Foo.Foo.someMethod这种情况给惹毛了。但是请注意：调用一个类方法将会比调用一个静态方法和函数要多一部分额外的内存。
啊，那些Foo.Bar.Baz也不是省油的。在Java中，这些点分割的名称是由编译器去查找的，所以运行时根本无所谓你有多少点。在Python中，每次运行时都要查找，所以每个点都要计算在内。（Python中一定要记住这点，“平铺比嵌套好”，尽管比起性能，他和“可读性”和“简单就是美”更靠近。）
要用switch语句？Python翻译将是一个哈希表，不是一堆if-then语句。用一堆if-then在Java中也不是switch语句，如果有字符串参与了呢？他其实是一个哈希表。CPython字典实现用了性能最佳—在我们宇宙中目前所知道的—的哈希表的实现之一。你自己所写的代码也不会比这个再好了，除非你是Guido、Tim Peters和Raymond Hettinger的“私生子”——还是遗传增强了的。
XML不是答案。它也不是一个问题。要在正则表达式上解释Jamie Zawinski，“一些人，当遇到一个问题的时候，就想‘我知道，我要用XML’那这个时候，他们就有两个问题了。”
和Java比，这是一个不同的情况。因为比起Java代码，XML是轻巧而且有弹性的。但比起Python的代码来，XML就是一个船锚，一个绊脚石。在Python中，XML是用来做交换，而不是你的核心功能，因为你不需要这么做。在Java中，XML可能是你的大救星因为他让你实现了特定领域的语言并“不通过编码”提高了你的应用程序的适应性。在Java中，避免编码是一个很大的优势，因为编码意味着重新编译。但在Python中，更常见的是，写代码比写XML更方便简单。同时Python处理代码要远远比处理XML快。（不仅仅是这个，你必须书XML处理代码，同时Python自身就已经为你准备好了。）
如果你是一个Java程序员，对于你是否要在你的Python核心应用中使用XML作为一部分，不要相信你的本能。如果你不是因为信息交互的原因去实现一个已经存在的XML标准或是建立某种导入、导出格式或者建立某种XML编辑器或处理工具，那么就不要这么做。一次也别。甚至连想都不要想。现在，扔掉那个XML模式把你的手解放吧！如果你的应用程序或者平台要被Python开发者使用，他们只会感谢你不要在他们的工作量中添加使用XML的负担。
（这里唯一的例外是如果你的受众的的确确，确确实实需要XML，出于某种奇怪的理由。像，他们拒绝学习Python并只对你使用了XML而付钱给你，或者你打算给他们一个编辑XML的GUI，同时这个写XML的GUI呢是另一个人写的，同时你得到免费使用的权利。还有一些很少见的架构上的原因需要用到XML。相信我，他们不会出现在你的程序中。如果有疑问，对一个资深的Python开发员解释你的用例。或者，如果你脸皮厚的话，试试向一个Lisp程序解释你的程序为什么要用XML!）
Getter和setter是坏蛋。坏蛋，魔鬼！Python对象不是Java Bean。不要写什么getter和setter，然后还把它们包装在“属性”里面。它直到你能证明你需要比一个简单访问复杂一点的功能时才有意义，否则，不要写getter和setter。它们是CPU时间的浪费，更要紧的是，它们还是程序员宝贵时间的极大浪费。不仅仅对于写代码和测试的人，对于那些要阅读和理解它们的人也是。
在Java中，你必须使用getter和setter因为公共字段不允许你以后改变想法再去使用getter和setter。在Python中，这样做很傻，因为你可以以一个普通特性开始并可以在任何时间改变你的想法，而不用影响到这个类的任何客户。所以不要写getter和setter。
代码重复在Java中常常是一个不得不要的魔鬼，你必须经常一遍一遍写同一个方法而只有一点点的变化（通常是因为静态类型约束）。在Python中这样做是没有必要的也是不值得的（除了极少数一些特定的场合需要内联一些要求性能的函数）。如果你发现自己一遍一遍在写同样的代码而且变化很少，你就需要去学一下闭包。他们并不是真的很可怕。
这就是你要做的。你写了一个包含了函数的函数。这里内部的函数就是你要一遍遍写的函数的模版，但是在里面加入了针对不同情况的函数要使用变量。外部的函数需要刚刚提高的那种变量作为参数，并且将内部的函数作为结果返回。然后，每次你要写另一种略微不同的函数的时候，你只要调用这个外部的函数，并且把返回值赋给你要让“重复”函数出现的名字。现在，如果你需要改变这个工作方式，你只要改变一个地方：这个模版。
在我所看过的应用程序/平台中，只有一个很微不足道的程序使用了这个技术之后可以去掉数百行重复代码。事实上，自从开发者使用了特别的样板文件来为这平台开发插件，这会节省很多很多第三方开发人员的代码，同时也使那些程序员要学习的东西简化了。
这只是Java->Python思维方式转变的冰山一角而已，现在我可以让他转变成正确的而不用钻研这个程序的细节。本质上，如果你曾经用过一段时间Java，而且对Python比较陌生，不要太相信自己的本能。你的本能已经为Java调节，而不是Python。向后退一步，最重要的，不要写这么多代码了。
要这样做，让自己觉得更加需要Python。假装好像Python是可以做任何你想做的魔棒，却让你无须动一个手指。问一下，“Python是怎样解决我的问题的？”还有“Python语言的哪个特点和我的问题最相似？”你绝对会惊讶于你需要的东西其实已经有了某种固定形式。事实上，这种现象实在是太普遍了，甚至在很有经验的Python程序员中也会出现，以至于Python社区中给这种现象起了个名字。我们称之为“GUIDO的时间机器”，因为有时候看上去得到我们所需要的东西好像只有他知道的一种方法，但当我们自己知道了就不一样了。
所以，如果你不能感到你在使用Python时至少比用Java要多出10倍的生产力，！（同时如果你还怀念你的Java IDE，考虑一下这种可能性：因为你写的Python程序比他所需要的要复杂得多）
附录：（翻译自此篇文章的评论）
确实，哈希表==字典。举个最简单的例子，从Python
标准库中检出“pickle”和“copy”模块，这两个模块会从字典中查找类型并调用相应的函数。另一个有些诡异的例子是范型函数，我已经在最近的Blog中写了一下。
关于闭包的例子，我这里给出一个很笨的例子。假设你要写很多这样的函数：
def addOne(x): return x+1def addTwo(x): return x+2
然后你可以这样写：
def makeAdder(addend):… def add_it(x): return x+addend… return add_it
并且这样使用：
addOne = makeAdder(1)addTwo = makeAdder(2)
这样就可以等同于原来的定义了。
相关资料：http://www.razorvine.net/python/PythonForJavaProgrammers
