C++: 編集距離を求めるアルゴリズム
編集距離(edit distance)とは二つの文字列がどの程度異なっているかを示す数値であり、レーベンシュタイン距離(Levenshtein distance)を指すことが多い。文字の挿入、削除、置換それぞれを一つの操作として必要な操作の最小数を求めるものだ。例えば、kittenとsittingの編集距離を求める場合、下記のように3回の操作でkittenをsittingに変更できるので編集距離は3となる。 1. sitten (k を s に置換） 2. sittin (e を i に置換） 3. sitting (g を挿入) そこで今回は編集距離を求める複数のアルゴリズムについてC++で実装してみた。 動的計画法 編集距離を求めるもっとも一般的なアルゴリズムは、動的計画法(dynamic programming)だろう。計算時間はO(mn)であり、手軽だ。C++で書いたコードを下に示
C++0xでYコンビネータ
stackoverflow.comのFixed point combinators in C++ (C++による不動点結合子)に載っていたC++とboostで書かれたYコンビネータ(Y combinator)のサンプルコードをC++0xを使って書き直してみた。C++0xだと標準ライブラリだけでこれだけ簡潔に書ける。 #include <iostream> #include <functional> using namespace std; // Y-combinator for the int type function<int(int)> y(function<int(function<int(int)>, int)> f) { return bind(f, bind(&y, f), placeholders::_1); } int main() { // Y-combinator co
Android端末による自動通訳を一行のPythonコードで実装する
最近このブログではAndroidのSL4Aネタが多いのだけど、それだけ遊べるのだから仕方がない。SL4AのPythonを使えば実質一行で自動通訳プログラムを作ることもできる。日本語で喋った文章が翻訳されて英語の音声で返ってくる。 import android,urllib,urllib2,simplejson;droid=android.Android();droid.ttsSpeak(simplejson.loads(urllib2.urlopen('http://ajax.googleapis.com/ajax/services/language/translate?v=1.0&q=%s&langpair=%s%%7C%s'%(urllib.quote(droid.recognizeSpeech().result.encode('utf-8')),'ja','en')).read())
アルゴリズムの素晴らしさに気付かせてくれたのはエラトステネスの篩だった
Haskellによるエラトステネスの篩(sieve of Eratosthenes)の美しい実装を見て、初めてアルゴリズムの素晴らしさに気付かせてくれたのがエラトステネスの篩だったことを思い出した。たしか中学生の頃だ。そこで、当時を懐かしみながら簡単な実装を書き留めておくことにした。とりあえず、Haskell, C++, Pythonの実装を以下に示す。コードは比較的短いが、実行効率を優先させているわけではない。 Haskell これはHaskellのサンプルコードでよく出てくる無限リストと遅延評価による実装だが、とても分かりやすいし、美しいコードだと思う。 primes = sieve [2..] sieve (p:xs) = p : sieve [x | x <- xs, x `mod` p /= 0] 以下のように関数takeを使って必要な分だけ素数を取り出すことができる。ただし、実
プログラミングができるということは、人生を楽にできるということ
どのようにプログラマになったのか知るのは面白く、興味深い。そして、プログラミングに対するの様々な考え方や捉え方を知り、それを自分の知識に加えるのが楽しい。そこで自分自身がどのようにしてプログラミングを学んできたのか、そしてプログラミングについてどのように考えているのか述べたいと思う。たいした内容でもないが書いているうちに長文になってしまった。取り敢えず概要だけを知りたい方は、それぞれの段落の最初の文章を読めば何となく分かると思う。 最初のプログラミング 初めて触れたPCは、父親が購入したNECのPC-8801mkIIだった。当時のPCには最初からBASIC(N88-BASIC)が付属しており、これを使って手軽にプログラミングができた。ただ、BASICはインタプリタであり、当時のPCの性能と相まって処理速度が非常に遅く、高速化のためにはアセンブラが必要だった。そこで、父親の書籍を漁りつつ、ニ
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
