May 2014 – ASMCA

Install 1 click ymp file on SLES 11

cmd line option for those who s not working on Box.

1. download ymp file

2. set DISPLAY for root or use root passwd.

3. yast2

/bin/bash /sbin/yast2 OneClickInstallUI /home/ractest/suse/Download/sqlite3-devel.ymp

Compile python3 on SLES 11 SP2

Install following RPMs before Steps:

libopenssl-devel-0.9.8j-0.50.1
zlib-devel-1.2.3-106.34

1 2	libopenssl-devel-0.9.8j-0.50.1 zlib-devel-1.2.3-106.34

Python3 source from: Python 3.3.5

Without zlib-devel, You cannot enable zlib module built-in, install this RPM and re-compile python3 src.
about bzip2, SLES doesnt provide extra bzip2-devel package, so just install bzip2 RPM is ok.

Without libopenssl-devel, you cannot fetch https URL via easy_install, it reports “unknown url type: https”

To Enablle ipython notebook:

Please install sqlite-devel package: (UN OFFICIAL)
http://software.opensuse.org/package/sqlite3-devel
Im using:

http://software.opensuse.org/ymp/server:database/SLE_11_SP2/sqlite3-devel.ymp
?base=SUSE%3ASLE-11%3ASP2&amp;query=sqlite3-devel

yast2  OneClickInstallUI sqlite3-devel.ymp

http://software.opensuse.org/ymp/server:database/SLE_11_SP2/sqlite3-devel.ymp

?base=SUSE%3ASLE-11%3ASP2&query=sqlite3-devel

yast2 OneClickInstallUI sqlite3-devel.ymp

1. install zeromq: # for pyzmq

zypper -p http://download.opensuse.org/repositories/home:/fengshuo:/zeromq/SLE_11_SP2/ -v in zeromq
zypper -p http://download.opensuse.org/repositories/home:/fengshuo:/zeromq/SLE_11_SP2/ -v in zeromq-devel

1 2	zypper -p http://download.opensuse.org/repositories/home:/fengshuo:/zeromq/SLE_11_SP2/ -v in zeromq zypper -p http://download.opensuse.org/repositories/home:/fengshuo:/zeromq/SLE_11_SP2/ -v in zeromq-devel

Guide here: http://zeromq.org/distro:sles

2. install dependencies:
easy_install pyzmq jinja2 tornado
easy_install sphinx readline
##### easy_install pysqlite # DO NO RUN THIS CMD. here hit bug, fixing… pysqlite doesn’t support python3 now, use internal sqlite3

3. run #ipython notebook ok.

Install Ipython notebook on Fedora 15

Ipython now provides RPM(python-ipython-notebook) from Fedora 18.
http://ipython.org/install.html

Fedora 15 is too old… not providing RPM, but we can also install very easy.

1. Install zeromq: (Im using i686 boxes, no yum servers now provided for the old release, you can google for the RPMs)

zeromq-2.1.9-1.fc15.i686.rpm 
zeromq-devel-2.1.9-1.fc15.i686.rpm

1 2	zeromq-2.1.9-1.fc15.i686.rpm zeromq-devel-2.1.9-1.fc15.i686.rpm

2. using easy_install:

easy_install ipython
easy_install pyzmq
easy_install pyzmq tornado

easy_install ipython

easy_install pyzmq

easy_install pyzmq tornado

3. Run the service in your own directory:

[suse@suse ~/workspace/ipython-notebook]$ipython notebook

1	[suse@suse ~/workspace/ipython-notebook]$ipython notebook

...Created profile dir: u'/home/suse/.ipython/profile_default'
...Using MathJax from CDN: http://cdn.mathjax.org/mathjax/latest/MathJax.js
...Serving notebooks from local directory: /home/suse/workspace/ipython-notebook
...0 active kernels 
...The IPython Notebook is running at: http://127.0.0.1:8888/
...Use Control-C to stop this server and shut down all kernels (twice to skip confirmation).
...INFO:tornado.access:302 GET / (127.0.0.1) 1.20ms

...Created profile dir: u'/home/suse/.ipython/profile_default'

...Using MathJax from CDN: http://cdn.mathjax.org/mathjax/latest/MathJax.js

...Serving notebooks from local directory: /home/suse/workspace/ipython-notebook

...0 active kernels

...The IPython Notebook is running at: http://127.0.0.1:8888/

...Use Control-C to stop this server and shut down all kernels (twice to skip confirmation).

...INFO:tornado.access:302 GET / (127.0.0.1) 1.20ms

Codeeval Q130 Solving In Python

本文是写一道理的解决过程。

题目： [Sequence Transformation] In Python
https://www.codeeval.com/open_challenges/130/

简介
0可以表示连续的串”A”，
1可以表示连续的串”A” or 串”B”
给出一序列01组合和AB组合，判断是否可以匹配。

一上手我的第一印象就是用正则表达式。
https://github.com/asmca/codeeval/blob/master/130/130.old.py

这样的代码非常简单，而且小的CASE都能过，但比较大的就不行了，如
https://raw.githubusercontent.com/asmca/codeeval/master/130/a.test

然后就想着在正则上面下文章：

甚至也想了一个递归的办法，
https://github.com/asmca/codeeval/blob/master/130/old.py.recursive
但递归的较大问题是要重复计算小单元，这几乎是指数级的，而这一问题并不比上面的正则做法好多少。

MIN提醒我用动态规划来做。用矩阵存临时结果来取消回溯的w代价。
https://raw.githubusercontent.com/asmca/codeeval/master/130/min.jpg

于是我接下来的时间就同这个矩阵打交道了。花了几个小时的时间才最终通过提交。

这个是题目的输入示例
https://github.com/asmca/codeeval/blob/master/130/130.in

然后初稿就出来了
https://github.com/asmca/codeeval/blob/master/130/130.1928.py

这份代码一开始运行了15秒。
把函数ifmatching()优化了return的顺序，结果可以达到13秒。

问题在于这边的for循环，同样需要max to O(m*n*n)的复杂度(实际上约为m*n*logN) 依然难以接受。
提交的服务器上时间限制10s，而且很明显上面的限制资源要比我本地运行的慢得多。

这里，
mtx[i][j]设为1，表示这个s1[:i+1]能够匹配到s2[:j+1]我尝试去限定i和j的位置，比如j>=i 和j <len(s2)-len(s1)+i+1
即使如此，时间仍然只能达到11秒左右。
此时的版本
https://github.com/asmca/codeeval/blob/master/130/130.py.2203

这个时候基本上可以达到7s左右。但我还是没有找到问题的关键

像这样的代码仍然大量调用ifmatching()函数，复杂度是到了m*n ，我比较偷懒用了递归。

调整了递归出口，对于每次调用，先直接判定 mtx[x-1][y-1]如果设置，直接退出。这样时间就大量的节省了
可以做到2.5s左右能够完成，但此时提交服务器端仍然超时失败。

对于这样m*n的复杂度，发现还是会有大量对于ifmatching()的调用，下面的改动就达到了目的

    row=i+1
    for col in range(j+1,y-x+i+2):
        if not mtx[row][col]:
            if ifmatching(s1[row],s2[j+1:col+1]):
                mtx[row][col]=1
                markdown(row,col)

row=i+1

for col in range(j+1,y-x+i+2):

if not mtx[row][col]:

if ifmatching(s1[row],s2[j+1:col+1]):

mtx[row][col]=1

markdown(row,col)

    row=i+1
    for col in range(j+1,y-x+i+2):
        if not mtx[row][col]:
            if not ifmatching(s1[row],s2[j+1:col+1]):
                break
            mtx[row][col]=1
            markdown(row,col)

row=i+1

for col in range(j+1,y-x+i+2):

if not mtx[row][col]:

if not ifmatching(s1[row],s2[j+1:col+1]):

break

mtx[row][col]=1

markdown(row,col)

此时可以理解为，如果mtx[i][j]==0 (j>=i),那么，mtx[i][j+]以后都是0
即如果不能匹配一个字符串，那么这个字符串后新加字母，仍不能匹配。

这样的改变，直接中途跳出for循环，减少了对ifmatching的调用。
能达到0.2s的级别，提交直接成功
Final Code:
https://github.com/asmca/codeeval/blob/master/130/130.py

Rev	Language	Date	Status	Score	Time, ms	Memory, bytes	In ranking	Ranking Points
14	Python 2	May 11, 2014	Solved	100	917	4349952	yes	55.278

当然，就算这样修改后的循环代码，也没有这样的效率，仍然在9s左右徘徊。
https://github.com/asmca/codeeval/blob/master/130/130.2311.py