[TOC]

INF580(programmation par contraintes) 大概是在X学到的最有用的一门课, 它让我能够用把运筹学(MAP557)里学到的东西和计算机结合起来: 用电脑的力量解决(大规模)运筹问题.

这门课的projet是去年巴黎谷歌举行的一个比赛的题目: 最优化谷歌街景拍照小车的路线. 做这个projet的三周里, 我和Manu从一开始信心满满, 到中间一筹莫展, 再到后来柳暗花明, 以及最后乘胜追击终于在今晚得到了近乎完美的解答, 非常精彩, 这里特意一记.

问题描述

谷歌那次比赛的题目在这里(我们做的是Main Round的题目): https://sites.google.com/site/hashcode2014/tasks

简单来说, 就是已知巴黎的道路信息, 设法用八辆车(每辆车的行驶时间有限)从巴黎谷歌出发, 尽可能多的走遍巴黎的所有街道, 参赛者给出这些车的路线, 他们的分数就是这八辆车走过的街道的长度之和(重复走的街道不算分).

去年四月份我们也参加了这个比赛, 不过当时纠结于如何设计每辆车的路线, 最后只是用了贪心算法, 再加上一点点的随机, 得到的结果并不好... 当时ENS的人包揽了前三名, 而且比赛后进一步把分数刷到了满分: 他们的路线可以把所有街道都跑遍.

这学期学了INF580以后 …

压缩pdf

convert 只简单指定resize好像不太好使:

convert -resize 50% input.pdf out.pdf

gs(http://blog.sciencenet.cn/blog-467089-773990.html):

gs -sDEVICE=pdfwrite -dCompatibilityLevel=1.4 -dPDFSETTINGS=/screen -dNOPAUSE -dQUIET -dBATCH -sOutputFile=out.pdf input.pdf

后来发现老是compress以后的结果不好, 看到这篇帖子发现convert有好多选项. 最后实验下来这样convert的效果很好, 既能压缩文件, 又保证了压缩后还足够清楚:

convert -density 200 -compress jpeg input.pdf …

在处理大量数的时候, 如果输出类似 "process i out of n files..." 这样的内容来指示进度的话, 虽然可以显示目前的进度(用来安慰等待的心情...)但有个问题是, 如果输出了太多行(比如一万行...), 就看不到前面的内容了...

所以想找一个命令行下面的进度条, 其实python已经有了(不止一个)进度条的包了, 比如progressbar, 但是不知为什么这个包在windows下面没有能做到刷新显示 -- 就是刷新进度的时候, 没有把原先那一行去掉, 而是在下面再输出了一行... (不过后来在linux下面使用这个包是没问题的, 好奇怪...)

所以想办法自己写了一个, 发现要实现一个简单的进度条还是很简单的, 关键就是使用\r, 这样会把光标移动到当前行的开头: 这样下次输出的时候就会把原先的内容冲掉了.

代码只有不到二十行:

import sys

class SimpleProgressBar():
    def __init__(self, width=50):
        self.last_x = -1
        self.width = width

    def …

[TOC]

以前虽然也用过正则表达式(比如那个饮水思源的PPP版图片下载器...)但是那时候基本上是网上到处搜 然后把代码拿过来改, 没有系统的学过这个东西. 前一段实习一开始的时候要处理很大量的文本, 从文本里提取出需要的信息, 所以用到了不少的正则表达式, 也好好的学了一下, 现在回来进行一下总结.

什么是正则表达式

很多时候,我们需要在文本里寻找满足一种模式(pattern)的一段子字符串(substring), 注意是一种模式而不是某一个具体的字符串. 举个例子, 在一段文本里寻找这里面出现的所有的网址, 那么对应的模式就是:

"以www.开头, 中间有一些东西(可以是字母也可以是数字等), 最后以 .com/.org/.edu... 结尾的所有的字符串"

再比如, 要查找文本中出现的电话号码, 电话号码的格式是区号加横线再加号码, 那么模式就应该是:

"以3个或4个数字开头, 三个或四个数字之后跟一个横线, 横线后再跟7个或8个数字"

再再比如, 要查找出现的电子邮件地址, 那么模式大概是:

"以字母或数字或下划线开头, 之后跟着一个@符号, @符号以后一些用点分隔的字母或数字, 最后应该以.com/.org …

最近要用SSH连接服务器, Windows下面当然就是用putty了, 遇到的问题总结一下.

保存session

打开putty.exe以后, 输入服务器ip, 之后先别点击登录, 先保存一下session下一次就不用再输入了:

之后点击登录就好了.

本地和服务器之间传输文件

传输的时候貌似不能用linux里的scp命令, 而需要使用另一个putty的工具: psftp

下载的时候那个putty.zip压缩包里有一个psftp.exe, 点击它就打开了. psftp也是一个命令行的工具, 和ssh类似, 用pwd/ls/cd等在服务器的文件系统里进行移动.

而在本地的文件系统里移动的话, 用lpwd/lcd/lls.

移动到了想要传输文件的目录以后(本地和服务器都移动好了以后), 使用put filename上传本地文件到服务器, 使用 get filename 下载服务器文件到本地.

http://www.lellansin.com/putty …

[TOC]

Learning IPython for Interactive Computing and Data Visualization这本书的前两章的笔记, 这本书还被放在了IPython官网上, 虽然只有一百页多一点点, 但是讲的内容却很丰富, 介绍了IPython, numpy, pandas以及并行计算等方面.

(在开始系统学IPython之前简单使用过IPython, 那时候我还是更喜欢bpython的代码提示功能...)

ch1: 10 IPython essentials

  • 在任何变量后面加问号?或者双问号??, 将会输出详细的信息(按q退出), ??的信息更加详细些
  • Tab Completion: 没啥好说的 没有bpython做的好 也凑合吧...
  • _, __, ___保存最近三次的输出; _i, __i, ___i保存最近三次的输入(作为字符串保存)

magic commands

  • 在IPython里面可以使用一些标准unix命令, 比如cd, pwd,ls …

[TOC]

首先, 导入pandas import pandas as pd

以及开启pylab: IPython里输入%pylab

http://www.bearrelroll.com/2013/05/python-pandas-tutorial/

基本操作

http://cloga.info/python/%E6%95%B0%E6%8D%AE%E7%A7%91%E5%AD%A6/2013/09/17/pandas_intro/

pandas和numpy的关系: pandas是建立在numpy上面的, pandas可以处理不同类型的数据集合(heterogeneous data set: DataFrame), numpy处理的是相同类型的数据集合(homogeneous data set: ndarray …

Eclipse让我很喜欢的最大原因大概就是它的好用的快捷键了, 这里进行一下总结, 掌握这些快捷键可以让编辑代码变得更加高效.

基本快捷键

  • 格式化代码: ctrl+alt+F

非常实用的快捷键, 暂时还不知道别的编辑器还没有发现有同样功能的. 按一下代码就自动缩进得非常整齐了!

  • 注释/反注释: ctrl+alt+C
  • pydev下面的注释/反注释: ctrl+/

另外一些有用的快捷键

  • 显示提示: alt+/

这个可以说是eclipse快捷键里面最有用的一个. 可以显示代码提示的窗口, 这也是我喜欢eclipse的原因之一. 虽然编写代码的时候eclipse的提示框也会在适当的时候出来, 比如按下了.的时候, 但是当它没有出现的时候我们总可以按下alt+/让提示框弹出来. 尤其在使用Java的时候, eclipse的提示相当智能, 也就是说会根据上下文以及函数的定义等东西来提示那些可能出现的项目. 另外, 有时候可能定义了一个超长名字的变量(这样代码可能比较清楚一些), 然后用这个快捷键, 就只需要打一下这个很长名字的前几个字母就可以自动补全了(如果补全的不是想要的, 只需要多按几次这个快捷键就会显示其他可能了)!

  • 打开函数/变量的声明: F3

比方说在程序的某一段看到了调用一个函数, 然后想看看这个函数的内容, 这是不需要拿着鼠标上下滚动着找(有时候定义的函数可能在另一个文件里, 那就更难找了), 只需要按下 …

Eclipse被称为编程的瑞士军刀, 意思就是只用一个eclipse就可以做很多事情.

最近越来越喜欢eclipse了, 因为作为编辑器而言, eclipse的编辑器让我用起来最舒服的一个(配合一些快捷键以后更是非常爽). 这半年多来发现了一些非常好用的eclipse的插件, 有了这些插件, eclipse可以做更多的事情... 接下来简单介绍一下:

插件安装的方法

先简单说一下eclipse的插件安装方法, 在eclispe界面上, 点击: Help->Install New Software:

之后添加对应的URL就可以了...

ADT

链接

eclipse里添加的URL:

https://dl-ssl.google.com/android/eclipse/

这个不用说了吧, Eclipse已经基本上是android开发的御用IDE了.

PyDev

链接

URL:

http://pydev.org/updates

python的开发更需要有一个提示的东东(好像叫pyLint, 就是可以发现代码里的一些显然的错误), 这个插件装好以后我就很少用geany写python程序了, 尤其是当程序超过100行以后...

但是让人不爽的是, 他需要新建一个project才能运行. 这也是Eclipse的一个让人不爽的方面. 如果是一个小的python程序的话我还是会用geany. 另外, 强烈推荐 …

python的pickle/unpickle机制可以非常方便的保存一些计算的中间结果, 这一点java虽然也可以做到, 但是java里面的包的名字实在是长的让人记不住...

不过今天在使用pickle的时候遇到了一个很奇怪的问题.

是这样的, 原本写了一个程序main.py, 这个程序里进行了一些计算并且pickle下了这些内容, 后来我觉得一个程序main.py写这么多实在太长了, 于是就把那些辅助函数以及class的定义通通放进了一个util.py文件里. 并且在main.py的第一行写上:

from util import *

按理说这应该没有问题, 和一个main文件时运行的效果相同的, 但是当我运行的时候却显示util.py里面这行unpickle的语句有错误:

    airport_info = pk.load(file('airport_info.dict', 'rb')) 
    >>AttributeError: 'module' object has no attribute 'Airport'

其中Airport是我定义的一个类, 本来在main.py里面, 后来被我移动到了util.py里面...

感觉很奇怪, 于是去水源求助 …