Archive for the ‘Discoveries’ Category

My GPG Public Key


07 Feb
Key Id: 7C4D54E2
Key Server: pgp.mit.edu
Key Fingerprint: 2486 491E 9FE2 D615 E17C  B407 88B2 366F 7C4D 54E2

简单翻译Python Reference中关于Data Model的内容


31 Jan

最近在学习Python,官方文档之详细之实用,大大超乎了我的想象。而我觉得最值得一读就是其中对于Python数据抽象理念的描述(Data Model一章)。读完它之后,Python的大致感觉也就有了,剩下的就是学习各种语言特性了。 写得很不错,自然想试试逐步翻译成中文。英语语文水平不敢恭维,希望大家指正。

 

 

 

对象是Python对于数据的抽象方式。所有在Python程序里面的数据都是以对象或以其之间的关系的形式来表现的(在某种意义上,遵循Von Neumann“储存程式型电脑”的模型,代码本身也用对象来表示)。

每个对象都有个与之对应的身份信息、所属类型和值。 一个对象一旦被创建,它的身份信息就再也不会改变。你可以把它当作是这个对象在内存中对应的地址。“is”操作符能比较两个对象的标识符,而“id()”函数能返回一个代表该对象身份的整数值(目前被实现作它的内存地址)。对象的类型也是不可变的。一个对象的类型决定了此对象支持的操作(比如说: “它有长度吗?”)并且定义了那个类型的对象可能的值。“type()”函数返回一个对象的类型(其实它自身也是一种对象)。有些对象的值可以变化。那些自身值可以变化的对象也被称作“可变对象”mutable,而一经创建,值就不可改变的对象叫“不可变对象”immutable。(不可变容器对象中包含的引用指向的另一个可变对象的值是可以改变的,但是容器本身却仍然被认为是不可变的,因为它包含的内容不可变。因此,“不可变”性 并不直接等价于有一个不变的值,它更为精妙。)

对象不需要被显式地销毁,当他们一旦变得无法再被使用到就可能被回收。
让垃圾回收延迟或是被彻底忽略在实现上都被允许—-这只是个关乎实现质量好坏的事情,只要对象在能被访问到时不会被回收就行了。

Objects are Python’s abstraction for data. All data in a Python program is represented by objects or by relations between objects. (In a sense, and in conformance to Von Neumann’s model of a “stored program computer,” code is also represented by objects.)
Every object has an identity, a type and a value. An object’s identity never changes once it has been created; you may think of it as the object’s address in memory. The ‘is‘ operator compares the identity of two objects; the id() function returns an integer representing its identity (currently implemented as its address). An object’s type is also unchangeable. 1 An object’s type determines the operations that the object supports (e.g., “does it have a length?”) and also defines the possible values for objects of that type. The type() function returns an object’s type (which is an object itself). The value of some objects can change. Objects whose value can change are said to be mutable; objects whose value is unchangeable once they are created are called immutable. (The value of an immutable container object that contains a reference to a mutable object can change when the latter’s value is changed; however the container is still considered immutable, because the collection of objects it contains cannot be changed. So, immutability is not strictly the same as having an unchangeable value, it is more subtle.)
An object’s mutability is determined by its type; for instance, numbers, strings and tuples are immutable, while dictionaries and lists are mutable.
Objects are never explicitly destroyed; however, when they become unreachable they may be garbage-collected. An implementation is allowed to postpone garbage collection or omit it altogether — it is a matter of implementation quality how garbage collection is implemented, as long as no objects are collected that are still reachable.

Radix Sort && Counting Sort && Pigeonhole Sort && Bucket Sort


05 Nov

一直以来就没有搞清楚基数排序(Radix Sort)计数排序(Counting Sort)还有桶排序(Bucket Sort)的关系,今天wiki了一下,总算有了答案。

基数排序是利用排序关键字具有字典序特征的特点,对关键字进行分割,分若干轮子排序来达到最后使整个序列排好序的效果。至于子排序,可以以是其他的各种排序方法,基数排序仅仅指的是关键字分割这一思想。

计数排序顾名思义,就是开一个与关键字相匹配范围的表,对数据进行登记(即计数)。再通过按顺序遍历表,算出表中每个关键字序比它小的关键字有多少个。最后重新遍历原数据,根据处理过的表直接得出应该放的位置。注意表中记录的仅仅是数值,而没有把待排序的对象放进去。

这个算法有个特殊应用,如果需要排序关键字就是对象的全部,就可以在遍历表时,直接输出表中对应数值个相同对象就行了。

而桶排序是指将数据按关键字放入表中后,分别递归地对每个表内部进行排序,再按序遍历表输出。

基数排序的子排序算法常常使用计数排序实现(就是网上一搜一大把的那种开3个数组for3次,下标嵌套3层的那种)

有些资料上什么链表式基数排序又是怎么回事呢?

链表式是指子排序不是使用计数排序,而是一种叫鸽巢排序(Pigeonhole Sort)算法,其实就是桶排序省掉“递归地对每个表内部进行排序”步骤得到的算法,实际上递归的那部分被基数排序的多轮排序给完成了,使用了计数的基数排序本质上是拥有递归思想桶排序的一种特殊实现。

 

参考文献:

http://en.wikipedia.org/wiki/Radix_sort

http://en.wikipedia.org/wiki/Counting_sort

http://en.wikipedia.org/wiki/Pigeonhole_sort

http://en.wikipedia.org/wiki/Bucket_sort

Extract the resources of Topcoder!


23 Sep

由于学校最近总是隔三差五停网,感到压力很大,遂研究如何离线做TC的题。本以为google一下全是方法,结果搜了半天才好不容易翻到一个人在github上传的python脚本。

结果发现用不了,无奈看了下代码,改了一处。最终用是用上了,可是获取数据太慢了,二来我不太会python。于是想写个bash script(其实我也不熟。。= =)。因为以前写过一个POJ邮件批量发送器,所以登录神马的就用curl来解决,个人觉得比wget高效。

最让人头疼的是分析html,从中提取数据的部分了。 我本来就只会点sed,多行匹配弄死人啊啊啊~(人家python可以用BeautifulSoup来搞定)看来是该好好学学“二外”了,python,bash神马的,awk神马的,都应该熟练掌握啊。

最终还是把脚本搞出来了,私认为看上去不错。

http://repo.tedyin.com/tcget/

先运行./fecth.sh获取SRM最近200次比赛列表,结果会存到/tmp/matches里。然后编辑tcget.sh里面的username和passwd,改成自己的(下数据时要用)。最后./tcget.sh 脚本就会根据matches上的比赛把所有的题目和数据搞下来,挺快的。

注意因为是利用Topcoder官网的Top Submission中A了的代码下面附带的数据来得到题目数据的,对于那些比赛中无一人A的题就没法了。但90%题目应该都有数据,那些没有数据的说明我根本做不了啊(比赛时无一人A。。。)。

Git Repository


17 Sep

不打算同步到sf上了,于是研究了一下如何在虚拟空间里面搞个代码仓库。

成果总算有了~ http://www.tedyin.com/webrepo/

 

介绍:

Git是一个版本控制系统(Version Control System),和SVN以及Mercurial类似。简单地说就是一个可以同步和管理代码的工具。比如开发一个工程,如果没有版本控制系统,那么就很难协调几个成员同时对这个工程的开发。所以为了让工程的开发更加透明和易于管理,一般在一个大家都能访问的服务器上设置一个仓库(Repository),然后这个服务器上运行着一个接受对于仓库请求的服务。对于开发人员,可以用客户端连接到服务器进行工程副本的获取和修改同步等等操作。Git就是这样的一个软件,由Linus Torvalds亲自操刀编写,为的是更好地维护日益暴涨的Linux内核代码。不过由于它简单快捷,所以就风靡了。

我在网站的空间里面用一个目录来放置Repository,为了让仓库可以从Web界面浏览,使用了一个轻量级Git的Web前端——CGIT。这样就可以从网页上浏览仓库里的文件了。

 

Update 20111009:

搞定了语法高亮。自己配了个颜色,感觉不错。详见这里

 

Teddy

Studies,OI and Love