挿入ソート

アルゴリズムクイックリファレンス買いました。

購入動機は、
・アルゴリズムは大学生以来(しかも1-2年の時)やってないのでかなり鈍っている
・グラフ系のアルゴリズムとか学生時代にほとんどやってない
・プログラミングコンテストの予選を突破できるようになりたいので正しいアルゴリズムをきちんと学びたい(正しいアルゴリズムを選べるようになる、計算量を意識できるようになる)
です。

つーことで早速挿入ソート
(多少Pythonicに直した…つもり)

def sort(a):
    for i, e in enumerate(a):
        insert(a, i, a[i])


def insert(a, pos, value):
    i = pos - 1
    while i >= 0 and a[i] > value:
        a[i + 1] = a[i]
        i = i - 1
    a[i + 1] = value


if __name__ == '__main__':
    data = [6, 3, 2, 1, 5, 4]
    sort(data)
    print data

オーダー
最良 O(n)
平均 O(n^2)
最悪 O(n^2)

挿入ソート特徴
要素数が少ない、最初からほぼ整列しているデータに対して有効

感想
かなり男らしい実装だが、
ほぼソートされている場合insert関数のwhileが小さくなるため、
結構高速に動作するらしい。

がんばって一冊みっちり勉強したいとこです。(意気込み)

Pythonの命名規則のおさらいじゃい

どうもこんにちわ。

いきなりですけどPythonのみでコーディングしている人は少ないのではないでしょうか。
私もJavaとPythonとjavascriptなどの複数の言語を業務で扱うことがあり、
ある程度慣れては来ていますが、命名規則がごっちゃになったりします。

つーことで今更ながらPythonの超基本命名規則(by PEP8)のおさらい。

名称	規約	例
module名	lowercase	hamegg.py
class名	CapWords	class HamEgg(object):…
exception名	CapWords	class HamEggException(Exception):…
関数名	lowercase_with_underscores	def ham_egg():…
関数名(既存の文脈※)	mixedCase	def hamEgg():…
メソッド名	lowercase_with_underscores	def ham_egg(self):…
インスタンス変数名	lowercase_with_underscores	self.ham_egg = None
定数	UPPER_CASE_WITH_UNDERSCORES	HAM_EGG = "ham_egg"

見返して思ったのはモジュール名にアンダースコアつけてるかも。恥ずかし。

※たまにあるビルトイン系の関数名がmixedCaseになっていると混乱する元になりますね。

Flask-Script

みなさんFlaskしてますか。
Flask相変わらず良いですね。
extensionの数も順調に増えていて良いですね。
mongoだのcouchだのの単語がみえてnosqlもバッチリですね。

ところでdjangoのmanage.py便利ですよね。
Flaskでもrunserverとかshellとかやりたい。
そんな時にはflask extensionsにあるFlask-Scriptですよ。

インストールはいつもの通り
easy_installなりpipなりでflask-scriptとしてください。

Webアプリ側はこんな感じ(applicaiton.py)

#web application
from flask import Flask
from flask import jsonify

app = Flask(__name__)

@app.route('/spam')
def spam():
    return jsonify(res='ok')

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

んでflask-script側。(manage.py)

#script
from flaskext.script import Manager
from application import app 
manager = Manager(app)

#manage.py にhelloコマンドの追加
@manager.command
def hello():
    print 'hello'

if __name__ == "__main__":
    manager.run()

managerにアプリ登録してやるだけです。

あとは
$python manage.py runserver
でサーバ起動とかできます。
$python manage.py shell
でインタラクティブシェル起動できます。

@manager.commandで独自コマンドも簡単に追加できるので重宝しそうです。

optionパーサも組み込まれているみたいなので、
applicationの起動に色々処理を追加したい場合などは使ってみると良いと思います。

詳細はこちらです。
http://packages.python.org/Flask-Script/

Whooshでの横断検索とか

Whooshの機能についての調査をある程度備忘録的に記載しておく。

まずUNIQUEなフィールドについて
Schema定義の際にフィールドのインスタンスにunique=Trueを渡すことで、
同じ値が入った時に上書きがされるようだ。

Solrなどで使われる複数のフィールドを横断して検索できる
DisMax系のモジュールがWhooshでも存在し、結構簡単に使える。

今回の検証スクリプトは下記

# -*- coding: utf-8 -*-
import sys 
from whoosh.index import create_in
from whoosh.fields import *
from whoosh.scoring import *
from whoosh.query import *
from whoosh.qparser import DisMaxParser

#idフィールドをユニークキーとする
schema = Schema(id=ID(stored=True,unique=True),
                name=NGRAM(stored=True),
                ruby=NGRAM(stored=True),
                address=NGRAM(stored=True),
                telephone=TEXT(stored=True))

ix = create_in("indexdir", schema)
writer = ix.writer()
writer.add_document(id=u"001",
                    name=u"コンビニA",
                    ruby=u"こんびにえー",
                    address=u"東京都",
                    telephone=u"0312345678")
writer.add_document(id=u"002",
                    name=u"コンビニB",
                    ruby=u"こんびにびー",
                    address=u"千葉県",
                    telephone=u"0471234567")
writer.commit()
from whoosh.qparser import QueryParser
searcher = ix.searcher()
q = sys.argv[1].decode('utf-8')
#nameとrubyとaddressとtelephoneフィールドを横断検索
parser = DisMaxParser({"name":0.5,"ruby": 0.5,"address": 0.2,"telephone": 0.1},schema)
query = parser.parse(q)

results = searcher.search(query)
for result in results:
    print result

ちょっとずつWhooshに慣れてきた。
かなりLuceneに近い使われ方を想定している模様。
Luceneを使っている人であれば結構簡単に使えるのでは。

形態素系のAnalyzerがないので、きついところもあるかもしれないが、
結構Pluggableに作られているようだし、
MecabなどのAnalyzerも簡単に作れるかも。
次はそこら辺を調べる予定。

Whoosh Fields

Whooshのフィールドの種類の種類は以下。
やっぱりフィールドの種類はluceneに比べるとすごく少ない。
普通の日本語のフィールドだとngram一択かな。


whoosh.fields.ID
シンプルな単一フィールド。
urlやファイルパス、カテゴリなどで使うと良いとのこと。
luceneやsolr経験者だとユニークキーのことかと思うかもしれないが、
この値が同じだと同じドキュメントになるわけではないので注意。
(同一のidのものを追加しても前のドキュメントは上書かれない)


whoosh.fields.STORED
ストアするがインデックス化はしないフィールド。
検索には引っかからないようにしたいデータを入れる。


whoosh.fields.KEYWORD
スペースやカンマで区切られている文字列をindex化するフィールド。
one two,threefourというデータであればone,two,threefourという3つのデータがインデックス化される。
フレーズ検索(続いた文字列群で検索)には対応していない。


whoosh.fields.TEXT
タームポジション(文字列出現箇所)を記憶しているフィールド。
フレーズ検索に対応。


whoosh.fields.NUMERIC
数値フィールド。
intおよびfloatの値に対応。


whoosh.fields.BOOLEAN
booleanフィールド。
TrueかFalseのみ。


whoosh.fields.DATETIME
日時フィールド。


whoosh.fields.NGRAM and whoosh.fields.NGRAMWORDS
ngramフィールドとngramwordフィールド。
ngramフィールドは文字列をn文字で分割してindex化。
2gramだと[test] -> [te] [es] [st]の3つのデータに分割される。

ngramwordフィールドはキーワードをn単位で分割してindex化。
2gramだと[one two three] -> [one two][two three]の2つのデータに分割される。

Whoosh Quick start

WhooshのQuickStartを試す。

from whoosh.index import create_in
from whoosh.fields import *

#スキーマの作成(フィールドはtitleとpathとcontentの3つ)
#stored=Trueのものはインデックスにオリジナルデータを持たせ、検索時に結果として返す。
#stored=False(デフォルトはFalse)のものはindex化されるので全文検索は可能だがオリジナルデータは検索時にはわからなくなっている。
schema = Schema(title=TEXT(stored=True), path=ID(stored=True), content=TEXT)

#作成したスキーマのインデックスディレクトリ(indexdir)を作成
ix = create_in("indexdir", schema)
#indexwriterを作成
writer = ix.writer()

#ドキュメントをインデックスに追加
writer.add_document(title=u"First document", path=u"/a",
                    content=u"This is the first document we've added!")
writer.add_document(title=u"Second document", path=u"/b",
                    content=u"The second one is even more interesting!")
#コミットの実行 indexファイルへの書き込み
writer.commit()


from whoosh.qparser import QueryParser
#indexsearcherを作成
searcher = ix.searcher()
#検索クエリの作成(contentにfirstを含むドキュメント)
query = QueryParser("content",schema = ix.schema).parse(u"first")
#検索の実行
results = searcher.search(query)
print results[0]

実行結果
Hit {'path': u'/a', 'title': u'First document'}


とりあえず使い始めは簡単。

Python上での全文検索

Pythonで全文検索したくて少し調べた。

pyluceneとWhooshというのがあるらしい。

pyluceneはJavaで作られた全文検索エンジンのluceneの
pythonバインディング版。
jccというpythonからJavaを呼び出すためのライブラリを利用している。
(jccはpyluceneのために作られた模様)
なので実処理はJavaで行われている。

Whooshは後発でpurepythonで書かれている。
LuceneのAPIに似せたAPIでLuceneを知っている人であれば割ととっつきやすいのかも。


どっちも少し触ってみた感想は、


pylucene
長所
・Luceneを知っていればAPI同じで学習のオーバーヘッドが少ない。
・Luceneからも読める。つまりJavaとインデックスを共有できる。(試してないけど当然Solrからも使えるはず)
短所
・インストール面倒。(特にJCC)
・起動処理が遅い。(JCCのinitVMでJavaVMの起動に時間がかかっている印象)


Whoosh
長所
・インストール簡単・
・使い方も結構分かりやすい。
短所
・日本語の機能的にLuceneより劣る(日本語用のAnalyzerが不足している)
不明
・速度的にLuceneより遅い?(検索/インデックス作成が静的型付け言語で行われるか、スクリプト言語で行われるかの差)


Lucene経験者としてはpyluceneがいい感じだが、
Whooshもかなりいい感じなので期待したいところ。

しばらくはWhooshを評価がてら使ってみることにする。