2010-11-06

平方数の無限リスト（っぽいもの）を作る

Python

itertoolsモジュールのcountを使えば整数を無限に生成できる。countを使って例えば平方数を無限に生成しようとする。ビルトインのmapは有限のシーケンスに対してのみ動作するので、要素数に限りがないcountに適用することはできない。このような場合にはitertoolsの他の関数が役に立つ。

import itertools
squares = itertools.imap(lambda x:x*x, itertools.count(1))

# 使用例：10000以下の平方数のリストを作る
print list(itertools.takewhile(lambda n:n<10000, squares))

今回使用したimapやtakewhileを含め、itertoolsの関数の多くはiterableなオブジェクトを返すだけなので、特定要素に複数回アクセスする場合などはlistやtupleで実体化する必要があるので注意。

2010-10-27

自動的に拡張される素数リストの実装

Python

Pythonの素数ジェネレータの実装は結構有名なはず。ProjectEulerのために、ランダムアクセス可能で必要に応じて拡張される素数リストを、素数ジェネレータを利用して作成した。ジェネレータの実装は4 TopCoderより。

from itertools import ifilter
from itertools import count

class Prime(object):
    def __init__(self):
        self.gen = sieve()
        self.primes = []
    def __getitem__(self,index):
        if len(self.primes) <= index:
            shortage = index - len(self.primes) + 1
            new_primes = [p for i,p in zip(range(shortage),self.gen)]
            self.primes.extend(new_primes)
        return self.primes[index]

def sieve():
    g = count(2)
    while True:
        prime = g.next()
        yield prime
        g = ifilter(lambda x,prime=prime: x%prime,g)

使い方はこんな感じ。

primes = Prime()
print primes[1000]
print primes[2000]
for prime in primes:
    print prime

あまり速くはないが、クラスに機能を加えていけば便利そう。

2010-10-03

cutilDeviceInitの使い方

CUDA

cutilDeviceInitを使えばマシンが複数のGPUを搭載しているときの切り替えが簡単にできる。

#include<cutil.h>

〜

int main(int argc, char** argv){
    cutilDeviceInit(argc, argv);

    〜

}

実行時にコマンドラインオプションでデバイス番号を指定する。

$ a.out --device=1

SDKのサンプルでも利用されている。

$ matrixMul --device=1

2010-08-16

■

Python GAE Django

App Engine Helper for DjangoはModelFormが使えないといった問題があり，それらを改善したプロジェクトとしてapp-engine-patchが紹介されている．しかしapp-engine-patchも既に開発が止まっていてDjango-nonrelを使えとのこと．Django-nonrelを使えばApp Engine上でもDjangoの機能の多くを利用することができる．一方でGAE DjangoやAEPにあったGoogleアカウント認証機能やログインURLテンプレートタグはDjango-nonrelでは失われているようだ．というわけ認証サポートをサクっと作ってみた．
まずはdjangoのモデルとGAE上のユーザを結びつけるモデルの定義．

project_dir/gaeutils/auth/models.py

from django.db import models
from django.contrib.auth.models import User

class GoogleProfile(models.Model):
    user = models.ForeignKey(User)
    google_user_id = models.CharField()

次に認証バックエンド．最初は認証ミドルウェアを置き換えようとしていたがdjangoの元の認証機能を最大限に活用しようと思うとバックエンドだけ変えた方が良さそうだった．ModelBackendのサブクラスとして実装したが，確認していない機能がほとんどなのでうまく動かない部分があるかもしれない．

project_dir/gaeutils/auth/backends.py

from django.contrib.auth.models import User
from django.contrib.auth.backends import ModelBackend
from google.appengine.api import users as gae_users
from gaeutils.auth.models import GoogleProfile

class GAEBackend(ModelBackend):
    def authenticate(self):
        gae_user = gae_users.get_current_user()
        if not gae_user:
            return None
        try:
            profile = GoogleProfile.objects.get(google_user_id=gae_user.user_id())
            return profile.user
        except GoogleProfile.DoesNotExist:
            user = User.objects.create_user(gae_user.nickname(), gae_user.email())
            profile = GoogleProfile(user=user, google_user_id=gae_user.user_id())
            profile.save()
            return user

最後に実際に認証処理を呼び出すビュー．

project_dir/gaeutils/auth/views.py

from django.contrib.auth import authenticate
from django.contrib.auth import login as auth_login
from django.contrib.auth import logout as auth_logout
from django.contrib.auth import REDIRECT_FIELD_NAME
from django.core.urlresolvers import reverse
from django.http import HttpResponseRedirect
from google.appengine.api import users
import urllib

def login(request):
    dest = request.GET.get(REDIRECT_FIELD_NAME, '/')
    user = authenticate()
    if user is None:
        continued = bool(request.GET.get('continued', False))
        if continued:
            return HttpResponseRedirect('/')
        query = request.GET.items()
        query.append(('continued', 1))
        url = '%s?%s' % (reverse('login'), urllib.urlencode(query))
        return HttpResponseRedirect(users.create_login_url(url))
    auth_login(request, user)
    return HttpResponseRedirect(dest)

def logout(request):
    dest = request.GET.get(REDIRECT_FIELD_NAME, '/')
    auth_logout(request)
    return HttpResponseRedirect(users.create_logout_url(dest))

これらを有効にするためにsettings.pyとurls.pyに追記する．

settings.py

AUTH_PROFILE_MODULE = 'gaeutils.auth.models.GoogleProfile'
AUTHENTICATION_BACKENDS = ('gaeutils.auth.backends.GAEBackend', )

urls.py

urlpatterns = patterns('',
    # 省略
    url(r'^accounts/login', auth_views.login, name='login'),
    url(r'^accounts/logout', auth_views.logout, name='logout'),
)

これでlogin_requiredなども使える．

※このエントリは間違いを含んでいる可能性が多分にあります．ご了承ください．

2010-08-13

AppEngine Helper for DjangoでGoogleアカウントの認証を簡単にする

GAE Django Python

setting.pyで認証関係の設定を有効にする．以下の3カ所のコメントアウトを外します．

MIDDLEWARE_CLASSES = (
    'django.middleware.common.CommonMiddleware',
#    'django.contrib.sessions.middleware.SessionMiddleware',
    'django.contrib.auth.middleware.AuthenticationMiddleware', # コメントアウトを外す
#    'django.middleware.doc.XViewMiddleware',
)

TEMPLATE_CONTEXT_PROCESSORS = (
    'django.core.context_processors.auth', # コメントアウトを外す
    'django.core.context_processors.debug',
    'django.core.context_processors.i18n',
#    'django.core.context_processors.media',  # 0.97 only.
#    'django.core.context_processors.request',
)

ROOT_URLCONF = 'urls'

ROOT_PATH = os.path.dirname(__file__)
TEMPLATE_DIRS = (
    os.path.join(ROOT_PATH, 'templates')
)

INSTALLED_APPS = (
     'appengine_django',
     'test',
     'django.contrib.auth', # コメントアウトを外す
#    'django.contrib.contenttypes',
#    'django.contrib.sessions',
#    'django.contrib.sites',
)

templateでこんな感じで書く．

{% if user.is_anonymous %}
    <a href="{% auth_login_url %}">ログイン</a>
{% else %}
    こんにちは{{ user.username }}さん
    <a href="{% auth_logout_url %}">ログアウト</a>
{% endif %}

特定のビューでログインを強制するデコレータも使用可能．

from appengine_django.auth.decorators import login_required

@login_required
def add_event(request):
    # 省略

ほぼ通常のDjangoに近い形で使えるようです．

2010-08-09

RSA暗号

RSA暗号の解読といえば素因数分解に目が行きがちですが、RSA暗号の原理を理解しなければ素因数分解に成功しても暗号解読には至りません。
そこで、RSA暗号の原理及び鍵生成で重要な役割を持つ拡張ユークリッド互除法を概説するためのスライドを作成しました。
http://www.slideshare.net/likr/rsa-4920274

2010-01-28

PythonでMapReduceの真似事

Python

MapReduceとはGoogleによって考案され，クラウドコンピューティングの要として注目されたアルゴリズムフレームワークです．Googleによる分散処理の実装自体をMapReduceと呼ぶことも少なくありませんが，アルゴリズムにおける分割統治法のように，並列コンピューティングにおける考え方の枠組みこそがMapReduceであると捉えることができます．Hadoop等のソフトウェアフレームワークを使用せずに，PythonのみでMapReduceを実践してみましょう．問題はオライリーから出版の「並行コンピューティング技法」より，friendly数の計算です．

問題

互いにfriendlyな自然数の組を，プログラム起動時に与えられた正の整数までの範囲で，すべて探索せよ．
2つの数のうち，一方の数のすべての約数の和をその数で除した比率が，もう一方の数を同じように処理した比率と等しい場合を，2つの数が互いにfriendlyであると言い，またこの比率をその数のabundancyと言います．
(例)30と140はfriendly

$\frac{1+2+3+5+6+10+15+30}{30} = \frac{72}{30} = \frac{12}{5}$
$\frac{1+2+4+5+7+10+14+20+28+35+70+140}{140} = \frac{336}{140} = \frac{12}{5}$

実装

#!/usr/bin/env python2.6

import multiprocessing
import fractions
import collections

def abundancy(n):
    numerator = n + 1
    for i in range(2, n/2):
        if n%i == 0:
            numerator += i
    return [[fractions.Fraction(numerator, n), n]]

def find_friend(mapped_value):
    abundancy, values = mapped_value
    num_values = len(values)
    result = []
    for i in range(num_values):
        for j in range(i+1, num_values):
            result.append((values[i], values[j]))
    return result

def partition(mapped_values):
    partitioned_data = collections.defaultdict(list)
    for sublist in mapped_values:
        for key, value in sublist:
            partitioned_data[key].append(value)
    return partitioned_data

def mapreduce(inputs):
    pool = multiprocessing.Pool()
    mapped_values = pool.map(abundancy, inputs)
    partitioned_data = partition(mapped_values)
    reduced_values = pool.map(find_friend, partitioned_data.items())
    return reduced_values

if __name__ == '__main__':
    results = mapreduce(range(1,10000))
    for result in results:
        for a,b in result:
            print '{0} and {1} are friendly'.format(a, b)

likr’s labo

平方数の無限リスト（っぽいもの）を作る

自動的に拡張される素数リストの実装

cutilDeviceInitの使い方

■

project_dir/gaeutils/auth/models.py

project_dir/gaeutils/auth/backends.py

project_dir/gaeutils/auth/views.py

settings.py

urls.py

AppEngine Helper for DjangoでGoogleアカウントの認証を簡単にする

RSA暗号

PythonでMapReduceの真似事

問題

実装

参考