Drkcore

12092011 Python

分割数の漸化式

プログラミングコンテストチャレンジブック(2-3)の漸化式の説明が分からなかったのでググりをかましたら、わかりやすいのを見つけた。

プログラミングコンテストチャレンジブック
秋葉拓哉
毎日コミュニケーションズ / 3444円 ( 2010-09-11 )

特にGoで書く必要もなかったのでPythonでDP

n=4
m=3
M=10000
dp = [[0]*(n+1) for i in range(m+1)]

dp[0][0] = 1

for i in range(1,m+1):
    for j in range(n+1):
        if j-i >= 0:
            dp[i][j] = (dp[i-1][j] + dp[i][j-i]) % M
        else:
            dp[i][j] = dp[i-1][j]
        print i,j,dp

print dp[m][n]

dpを表示させてナニが起きてるのか確認。

1 0 [[1, 0, 0, 0, 0], [1, 0, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0]]
1 1 [[1, 0, 0, 0, 0], [1, 1, 0, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0]]
1 2 [[1, 0, 0, 0, 0], [1, 1, 1, 0, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0]]
1 3 [[1, 0, 0, 0, 0], [1, 1, 1, 1, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0]]
1 4 [[1, 0, 0, 0, 0], [1, 1, 1, 1, 1], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0]]
2 0 [[1, 0, 0, 0, 0], [1, 1, 1, 1, 1], [1, 0, 0, 0, 0], [0, 0, 0, 0, 0]]
2 1 [[1, 0, 0, 0, 0], [1, 1, 1, 1, 1], [1, 1, 0, 0, 0], [0, 0, 0, 0, 0]]
2 2 [[1, 0, 0, 0, 0], [1, 1, 1, 1, 1], [1, 1, 2, 0, 0], [0, 0, 0, 0, 0]]
2 3 [[1, 0, 0, 0, 0], [1, 1, 1, 1, 1], [1, 1, 2, 2, 0], [0, 0, 0, 0, 0]]
2 4 [[1, 0, 0, 0, 0], [1, 1, 1, 1, 1], [1, 1, 2, 2, 3], [0, 0, 0, 0, 0]]
3 0 [[1, 0, 0, 0, 0], [1, 1, 1, 1, 1], [1, 1, 2, 2, 3], [1, 0, 0, 0, 0]]
3 1 [[1, 0, 0, 0, 0], [1, 1, 1, 1, 1], [1, 1, 2, 2, 3], [1, 1, 0, 0, 0]]
3 2 [[1, 0, 0, 0, 0], [1, 1, 1, 1, 1], [1, 1, 2, 2, 3], [1, 1, 2, 0, 0]]
3 3 [[1, 0, 0, 0, 0], [1, 1, 1, 1, 1], [1, 1, 2, 2, 3], [1, 1, 2, 3, 0]]
3 4 [[1, 0, 0, 0, 0], [1, 1, 1, 1, 1], [1, 1, 2, 2, 3], [1, 1, 2, 3, 4]]
4

O(n*m)の計算量ですな。

07092011 Python Go

Goでフィボナッチのメモ化

Goでつくる簡易Wikiのサンプルは楽しいですね。標準ライブライブラリにhttpやHTML5用のパーサが入っているのはポイント高いですな。あとGAEにも対応したしね。

なかなか楽しいので少し覚えるためにプログラミングコンテストチャレンジブックをGoで書いていくことにしようかなと。

プログラミングコンテストチャレンジブック
秋葉拓哉
毎日コミュニケーションズ / 3444円 ( 2010-09-11 )

定番のフィボナッチ（メモ化）

package main

import "fmt"

var memo [100]int

func fib(n int) int {
   if n <= 1 {
       return n
   }
   if memo[n] != 0 {
       return memo[n]
   }
   memo[n] = fib(n-1) + fib(n-2)
   return memo[n]
}

func main() {
   fmt.Println(fib(10))
}

こっちはPythonで

memo = [0]*100

def fib(n):
    if n <= 1:
        return n
    if memo[n] != 0:
        return memo[n]
    else:
        memo[n] = fib(n-1) + fib(n-2)
        return memo[n]

if __name__ == '__main__':
    print fib(10)

02092011 Python

Pythonのリストのリストでちょいはまる

すっかり忘れてたがこんなのです。

shallow = [[1,2,3]] * 3
shallow[1][1] = 0
shallow # [[1, 0, 3], [1, 0, 3], [1, 0, 3]]
deep = [[1,2,3 ] for f in [1,2,3]]
deep[1][1] = 0
deep # [[1, 2, 3], [1, 0, 3], [1, 2, 3]]

という備忘録

31082011 Python

PyConJP2011に参加してきた

スタッフ、スピーカーのみなさんお疲れ様でした。とても楽しませてもらいました。私用によりLTを見られなかったのが残念だったが、色々刺激をうけて大変満足な一日だった。

参加したのは以下のセッション。

Keynote [Tarek Ziade]
C API への誘(いざな)い / An Introduction to the C API
Webフォームウィジェットツールキットを総括する / Exploring Web Form Widget Toolkits
Python と MongoDB でWEB開発 / Web Application Development with Python and MongoDB
GAEのpython2.7対応の話

TarekのKeynoteは文句なく良かったが、個人的にもっとも興味深かく聞けたのはC APIの話ですね。あれは面白かった。

実務的にはWebフォームウィジェットの話が参考になった。Flaskばっか使っているのでWTFormsを使おうと思った。

PythonとMongoDBの話はちょっと展開がはやすぎて追いづらかった。というか、うっかりTornadoのドキュメントを読むのにトラップされて、追いていかれた感が。スライドとかコードとか公開されてんのかな？あとで調べる。

最後にGAEのPython2.7対応の話を聞けてよかった。かなり楽しみな感じなので、なんかサービス作っておこうっと。

エキスパートPythonプログラミング
Tarek Ziade
アスキー・メディアワークス / 3780円 ( 2010-05-28 )

30082011 Python

multiprocessingのpmapヤバイ

multiprocessingのpmapは普通に書いたpythonプログラムをちょっと書き直せば並行して実行できるようになる。

しかもmapしたいところで、

p = Pool(2)
p.map(answer, problems)

って、書くだけなので超お手軽。

ちょっとがんばってc++で書いたほうがよかったかなーと思うプログラムをPythonで書いてしまい、高速化で悩んだのだけど、2コアだとこれだけで2倍近くはやくなるし4コアだと相当はやい。

8コアは試してない。

multiprocessingを試す前にpypyでもと思いコンパイル(1.6の64bitバイナリは10.5では動かなかった)したら、いつまでたってもコンパイルが終わらなくて投げ出した。

というわけで、明日の朝起きたら110の壁を超えている予定。

19082011 Python

Couldn't import standard bz2ってでてmercurialがインストール出来ない場合

さくらのVPSにmercurialをインストールしようとしたら

Setup script exited with Couldn't import standard bz2 (incomplete Python install).

っていうエラーが出てなんでかなぁと、インストールメモを見たらbzip2-develを入れてなかった。

yum install bzip2-devel

ついでにPython-2.7.2にバージョンをあげてからmercurial入れた。

17082011 Python Flask

blohg - Mercurial+Flaskのブログシステム

blohgってのが面白そうだったのでコードを読みつつ手元のmacbookにインストールして触ってみた。

sudo easy_install-2.7 blohg
mkdir myblohg
cd myblohg/
blohg initrepo
hg commit -Am 'initial commit'
blohg runserver

エントリを追加する場合にはcontent/post/にあたらしくrstファイルを追加してaddしてコミットする。

blohg

で、コード読んでたら

from werkzeug.contrib.atom import AtomFeed, FeedEntry

ってあって、werkzeugにフィード生成用の仕組みが用意されていることを知った。自分のブログ(Flask製)ではfeedgeneratorを使っているのだけど、こっちでもいいかなと思った。

おまけ

What SCM-based blog engines are there?

fujinismもblohgベースに変えようかなぁ

06082011 Python GAMESS

テトラゾールの負電荷はどこにたまるのか？

生物学的等価体として知られているものにカルボン酸とテトラゾールがありますね。

医薬化学において、テトラゾール環はカルボン酸の等価体と見なされ、医薬品の部分構造に汎用されている。これは前述のようにpKaがほぼ等しいため、

Wikipedia

tetrazole

テトラゾールってこんな構造だからpKaは同じだとしてもアニオン化した状態で負電荷どこにたまるのかなという素朴な疑問を持っていた。

ま、計算すればいいだけなので、pygamessを使って計算してみた。以下コード。チャージがcontrlセクションに入力するっていうのが気持ち悪い。

あと、最適化がなかなか終わらないのでmaxitとnstepは増やした。デフォルトをこの値にしてもいいかもしれない。

from pygamess import Gamess, GamessError
import openbabel as ob

g = Gamess()
g.contrl['maxit'] = 200
g.contrl['icharg'] = -1
g.statpt['nstep'] = 300
g.system['mwords'] = 80
g.basis_type('631g')
g.run_type('optimize')

obc = ob.OBConversion()
obc.SetInAndOutFormats("mol","mol")

mol = ob.OBMol()
obc.ReadFile(mol, "tetrazole.mol")
print g.gamess_input(mol)

try:
    newmol = g.run(mol)
except GamessError, gerr:
    print gerr.value
else:
    for obatom in ob.OBMolAtomIter(newmol):
        print obatom.GetIdx(), obatom.GetType(), obatom.GetPartialCharge()

いろいろ試していたので、GAMESSインプットを出力するようにしてある。

結果を見ると、確かに6,9番目の窒素のマイナスチャージが大きくなっているので、カルボン酸等価なんだろうなと納得したのであった。

$ /opt/local/bin/python optimize.py
 $contrl runtyp=optimize scftyp=rhf icharg=-1 maxit=200 mult=1  $end
 $basis gbasis=N31 ndfunc=1 ngauss=6 $end
 $system mwords=80  $end
 $statpt opttol=0.0001 nstep=300  $end
 $DATA

C1
C      6.0     -5.1500000000    0.5694000000    0.3351000000 
C      6.0     -3.6632000000    0.3894000000    0.3044000000 
H      1.0     -5.3940000000    1.6144000000    0.4937000000 
H      1.0     -5.6014000000   -0.0166000000    1.1314000000 
H      1.0     -5.6123000000    0.2533000000   -0.5982000000 
N      7.0     -2.8049000000    1.3874000000    0.2522000000 
N      7.0     -1.6217000000    0.7950000000    0.2303000000 
N      7.0     -1.7700000000   -0.4762000000    0.2679000000 
N      7.0     -3.0563000000   -0.7807000000    0.3162000000 
 $END

1 C3 -0.5149
2 Car 0.437823
3 HC 0.153658
4 HC 0.142616
5 HC 0.138266
6 Nar -0.487902
7 Nar -0.192393
8 Nar -0.188063
9 Nar -0.489106

量子化学計算っていうのは意外にトライアンドエラーが多い。だからといってGUIのコンソールからちまちまと作業すると時間が取られて困るし、作業ログが残りにくいので、こういったスクリプトで幾つかの条件を用意してforループでグルグルまわして計算させれば手順がきちんとドキュメントとして残るのでよい。

01082011 Python

QRコードにtwitterアイコンを埋め込むPythonスクリプト

xooqで本を渡す際に、背表紙の裏側にtwitterアイコン入りのQRコードシールを張っておいたらウッフィーが増えて面白いかなと思い、簡単なPythonスクリプトを書いてみた。

import urllib
import Image
from cStringIO import StringIO

twitter_id = "kzfm"

url = "http://chart.apis.google.com/chart?chs=200x200&cht=qr&chl=http://twitter.com/%s" % twitter_id
buffer = urllib.urlopen(url).read()
qr_image = Image.open(StringIO(buffer))

twurl = "http://img.tweetimag.es/i/%s_m" % twitter_id
twbuffer = urllib.urlopen(twurl).read()
tw_image = Image.open(StringIO(twbuffer))

qr_image.paste(tw_image, (147, 147))

qr_image.save("twqr.png")

TwQR

27072011 Python HTML5 Flask

FlaskでDrag and Drop APIとXHR2で画像をポストする

HTMLガイドブックはphpなのでFlaskでやってみた。この本は良書ですね、オススメです(最後のほうにNode.jsのサンプルも載ってるし)。

徹底解説 HTML5 APIガイドブックコミュニケーション系API編
小松健作
秀和システム / 2730円 ( 2010-12 )

青い囲みの中にドラッグドロップするとアップロードされるが、ドラッグドロップAPIのためにスペースを用意するっていうのはなんかいまいちだなぁ。もうちょっと洗練されたドラッグドロップのインターフェースはないものかね。

file_upload

ディレクトリ構成

$ tree
.
├── static
│   └── uploads
├── templates
│   └── index.html
└── uploader.py

サーバー側

from flask import Flask, request, url_for, render_template, make_response
import os

DEBUG = True
SECRET_KEY = 'development key'
UPLOAD_FOLDER = 'static/uploads'
ALLOWED_EXTENSIONS = set(['txt', 'pdf', 'png', 'jpg', 'jpeg', 'gif'])

app = Flask(__name__)
app.config.from_object(__name__)

def allowed_file(filename):
    return '.' in filename and \
           filename.rsplit('.', 1)[1] in ALLOWED_EXTENSIONS

@app.route('/')
def show_index():
    return render_template('index.html')

@app.route('/upload', methods=['POST'])
def do_upload():
    file = request.files['xhr2upload']
    if file and allowed_file(file.filename):
        filename = file.filename
        file.save(os.path.join(app.config['UPLOAD_FOLDER'], filename))
    response = make_response(url_for('static', filename='uploads/'+filename, _external=True))
    response.headers['Access-Control-Allow-Origin'] = '*'
    return response

if __name__ == '__main__':
    app.run()

クライアント側(templates/index.html)

<!doctype html>
<html>
  <head>
  <meta charset="utf-8">
  <title>File Uploader</title>
  <script src="//ajax.googleapis.com/ajax/libs/jquery/1.6.1/jquery.js"></script>
  <style>
  #dropbox {
    width: 500px;
    height: 200px;
    border: 1px solid blue;
    background: #eee;
  }
  #urllists {
    margin-top: 30px;
    width: 400px;
    height: 300px;
    overflow: auto;
    floar: left;
    boader: 1px solid blue;
  }
  #currentimage {
    margin-left: 420px;
    margin-top: 30px;
  }
  </style>
  </head>
<body>
<h1>File Uploader</h1>
<div id=dropbox></div>
<div id=urllists></div>
<div id=currentimage></div>
<script>
var DnDUploader = function (base_id) {
  if(typeof(base_id) != "string" || base_id.length == 0 || document.getElementById(base_id) == null)
    return false;

  var __body = document.getElementsByTagName('body')[0];
  var parent = document.getElementById(base_id);
  __body.addEventListener("drop", function(e){e.stopPropagation();e.preventDefault();}, false);
  __body.addEventListener("dragenter", function(e){e.stopPropagation();e.preventDefault();}, false);
  __body.addEventListener("dragover", function(e){e.stopPropagation();e.preventDefault();}, false);
  parent.addEventListener("drop", function(e){e.stopPropagation();e.preventDefault();_handleDrop(e);}, false);
  parent.addEventListener("dragenter", function(e){e.stopPropagation();e.preventDefault();}, false);
  parent.addEventListener("dragover", function(e){e.stopPropagation();e.preventDefault();}, false);

  var _handleDrop = function(e) {
    var x = e.layerX, y = e.layerY;
    var dt = e.dataTransfer, files = dt.files, count = files.length;

    var types = [
            'image/png',
            'image/gif',
            'image/jpeg'
    ];

    for (var i=0; i < count; i++) {
    if (files[i].fileSize < 1048576) {
        var file = files[i];
        var type = file.type;
        var filename = file.fileName;

        if($.inArray(file.type, types) == -1) {
        alert(file.type + 'はサポート外です。');
        continue;
        }

        var reader = new FileReader();
        reader.readAsDataURL(file);
        _upload(file);

        reader.onload = function(e) {
        var fileData = e.target.result;
        _drawImage(x, y, fileData);
        }
    } else {
        alert('ファイルが大きすぎます');
    }
    }
  };

    var _drawImage = function(x, y, file) {
    var imgElement = document.createElement('img');
    imgElement.src = file;
    imgElement.style.position = 'absolute';
    imgElement.style.display = 'none';
    parent.appendChild(imgElement);

    setTimeout(function(e) {
        var o_w = imgElement.width;
        var o_h = imgElement.height;
        imgElement.width = o_w > 100 ? 100 : o_w;
        imgElement.height = parseInt( o_h * imgElement.width / o_w);

        var w = imgElement.width;
        var h = imgElement.height;
        imgElement.style.left = (x-w / 2)+'px';
        imgElement.style.top = (y-h / 2)+'px';
        imgElement.style.display = 'block';
    },1);
    };

    var _upload = function(file) {
    var fd = new FormData();
    fd.append("xhr2upload", file);
    var xhr = new XMLHttpRequest()
    xhr.open("POST", "http://www.kzfmix.com:5000/upload");
    xhr.send(fd);

    xhr.onload = function(e) {
        var url = e.target.responseText;
        $('#urllists').prepend('<p><a href="' + url + '">'+url+'</a></p>');
        $('#currentimage').html('<img src="' +url+ '">');
    }
    }
}

DnDUploader('dropbox');
</script>
</body>
</html>

もう5年目(wishlistありマス♡)
最近はPythonとDeepLearning
日本酒自粛中
ドラムンベースからミニマルまで
ポケモンGOゆるめ