アルゴリズムいろいろ

Erlang

404 Blog Not Found:プログラマーでなくても名前ぐらい覚えておきたいアルゴリズムx10


プログラマーなのに名前すら知らなかったアルゴリズムがほとんどでした。なんてこったい。
有名なところは覚えておきたいなーと思ったので身に付けるために実装してみることにしました。

ユークリッドの互除法

２つの整数の最大公約数を求める手順です。

AとBの最大公約数は、Bと「AをBで割った余り」の最大公約数に等しい。

という法則を発見した人がいて、これを応用すると２つの数の最大公約数が簡単に求められるのだそうです。
詳しい方法がWikipediaに載ってたので、それを見ながらErlangで実装してみたら…

gcd(A, 0) -> A;
gcd(A, B) -> gcd(B, A rem B).

なんということでしょうー。
上に書いた

AとBの最大公約数は、Bと「AをBで割った余り」の最大公約数に等しい。

と

Aと0の最大公約数はA。

これ以外何も書いてない関数ができあがりました。これでちゃんと動いてるんだから自分でもびっくりです。


うおー。なんだかわからんがすごい。
ユークリッドさんがすごいのかErlangがすごいのかよくわからない。
よくわからないけどエラいものを見てしまったような気がする。
なんだかめちゃくちゃ興奮してるんだけど上手く説明できない。残念です。

エラトステネスのふるい

素数を漏れなく無駄なく求める手順。
自然数の集まりをふるいにかけて「倍数」を除いていけば素数だけが残るよねっていうスンポーです。
これもユークリッドさんのみたいにスポーンとシンプルに実装できたりするのかな。いやーんどうしようとかおかしな妄想をしてフガフガいいながら書いてました。

%% エラトステネスのふるい（N以下の素数を全部返す）
primes(N) -> sieve(lists:seq(2, N)).

% 素数の候補をふるいにかける
sieve(Nums) ->
  [Num|_] = Nums,
  Max = lists:last(Nums),
  if
    (Num * Num) > Max -> Nums;
    true -> [Num|sieve(reject_multiple(Nums, Num))]
  end.

% ListからNの倍数を除去する
reject_multiple(List, N) ->
  lists:filter(fun(X) -> X rem N /= 0 end, List).

なんか妄想してたのと違う…。

つづき

勢いに乗って全部実装しようと思ったのですが時間が足りませんでした。
っていうかニュートン法 - Wikipediaを見たら数式がいっぱい出てきて頭が爆発しました。
気力が尽きなければgistで続きを書いていこうと思います。

感想

関数型言語の入門とかチュートリアルとか読んでると、最初の例でいきなり微分方程式が出てきたり「Hello World」の次がいきなりクイックソートだったりで、数学とかコンピューター学をまともに勉強してこなかった人間にとっては何がなんだかさっぱり理解できないことだらけで悲しくなることが多いのですが、あれは別に初心者をいじめてるわけではなくて、関数型言語と数学が非常に相性のいい関係で、関数型言語の特徴を示すには数学の問題を解かせるプログラムとかが最適な場合が多いので、いつもああいう感じになってしまうのだなーと思いました。

ErlangでFizzBuzz

Erlang

やったー！ErlangでFizzBuzzできたー！

-module(fizzbuzz).
-export([exec/0]).

% 1からNまでのリストを作る関数
seq(0) -> [];
seq(N) -> seq(N-1) ++ [N].

% 数値を対応するFizzBuzz文字列に変換する関数
num_to_fizzbuzz(N) ->
  if
    N rem 15 == 0 -> "FizzBuzz";
    N rem  5 == 0 -> "Buzz";
    N rem  3 == 0 -> "Fizz";
    true          -> integer_to_list(N)
  end.

% 数値のリストをFizzBuzz文字列のリストに変換する関数
nums_to_fizzbuzzs(Ns) -> lists:map(fun num_to_fizzbuzz/1, Ns).

% 文字列のリストを連結する関数
join(_, []) -> "";
join(Delimiter, [X|XS]) -> X ++ Delimiter ++ join(Delimiter, XS).

% 1からNまでのFizzBuzz文字列を作成する関数
fizzbuzz(N) -> join("~n", nums_to_fizzbuzzs(seq(N))).

% FizzBuzz実行
exec() ->
  io:format(fizzbuzz(100)).

新しく覚えたこと

「%」より右はコメントになる。

% コメントだよ
increment(N) -> N + 1 % 1をプラスする関数だよ


リストの連結は「++」

[1,2,3] ++ [4,5,6]. % [1,2,3,4,5,6]

文字列もリストなので「++」で連結する。

"Hello " ++ "World!". % "Hello World!"


関数の引数にパターンマッチできる。Haskellみたい。
以下は1からNまでのリストを作る関数

seq(0) -> [];              % 引数が0だったら空のリストを返す。
seq(N) -> seq(N-1) ++ [N]. % 引数が0じゃなかったらseq(N-1)の末尾にNを加えたものを返す。

引数のパターンで分けた各関数たちは「;」でつながないといけないみたいだ。


if式もパターンマッチみたいに書く。

  if
    N rem 15 == 0 -> "FizzBuzz";
    N rem  5 == 0 -> "Buzz";
    N rem  3 == 0 -> "Fizz";
    true          -> integer_to_list(N)
  end.

ifからendまでが1つの式で、条件を上から順番に評価していって最初にtrueになったところの式を評価して返す。


関数定義には１つの式しか書けない。

exec() ->
  Result = fizzbuzz(100).
  io:format(Result).

こんな風には書けない。
でも複数の式を連結して１つの式にする「,」という演算子があるので

exec() ->
  Result = fizzbuzz(100),
  io:format(Result).

っていう風に書けばいける。


無名関数は「fun」と「end.」を使って書く。

Fn = fun(N) -> N + 1 end.


名前のついた関数を値として使う時も「fun」を使う。名前だけじゃダメで引数の数まで指定してあげないといけない。

incr(N) -> N + 1.
Fn = fun incr/1.


ループがない。変数の再代入ができないのだからループ構文というのはできないとのこと。
リストを作ってlists:mapやlists: foreachでエンヤコラするしかない。

  lists:foreach(fun(N) -> io:format("~b~n", [N]) end, [1,2,3]).

  lists:map(fun(N) -> N * 2 end, [1,2,3]). % [2,4,6]

Erlangを触ってみる

Erlang

ScalaのActorについて調べるために「Erlang」という言語を触ってみることにしました。

インストール

まずはErlangをインストールします。

sudo apt-get install erlang

けっこう時間がかかります。競馬中継を見てたら終わりました。アサクサキングス。

Hello World

まずはHello Worldを書いてみます。
PB memoを参考にしながら書きました。


helloworld.erl

-module(helloworld).
-export([sayHello/0]).

sayHello -> io:format("Hello World!~n").


式の終わりには「.」（ピリオド）をつける。
「-module」でモジュール宣言。「-export」で関数をエクスポートして外から使えるようにするみたいです。[関数名]/[引数の数]っていう書き方。
関数定義は[関数名] -> [関数の中身]って具合に書くようです。

コンパイル

Erlangのソースをコンパイルするには、対話式のインタープリタ「erl」を起動してインタープリタからコンパイルするんですって。へー。

$ erl

erlを起動します。

Erlang (BEAM) emulator version 5.6.3 [source] [async-threads:0] [kernel-poll:false]

Eshell V5.6.3  (abort with ^G)
1>

こんな感じで対話式のインタープリタが始まります。終了するには「Ctrl + G」を押して「q」と入力するみたい。


コンパイルしてみます。

1> c(helloworld).
{ok,helloworld}

sayHello関数を実行してみます。

2> helloworld:sayHello().
Hello World
ok

おおー


マルチスレッドについての話はまだ出てこない。
もう少し進めてみよう。

ActorとアクターモデルとErlang

Scala

ここ数日「ScalaのActorが良く分からない」と一人嘆いていたのですが、なんかとっかかりになりそうな情報を見つけました。

アクターモデル

むかーしむかし、アメリカの大学の偉い教授が「アクターモデル」という研究をしていました。これは「並行計算の数学的モデルの一種」というもので、なんだかよくわからないけど難しい数学の研究なのだそうです。
で、ScalaのActorフレームワークはこの難しい研究を実装しているようです。ScalaのActorを理解して使うにはこのアクターモデルというものを学んだ方が近道のような気がしました。
というわけで、場末のプログラマーにも理解できるようにアクターモデルを親切丁寧に解説してくれるサイトや本はないかと探したのですが、そんな上手い話はありませんでした。残念です。

Erlang

絶望的な気持ちになっていたときに↓の記事をみつけました。


アクターモデル - GIOの日記

Erlangの並列処理を学ぶことでアクターモデルの理解ができた！


これだ！
大学教授の研究はよくわからないけどプログラミング言語なら理解できるだろう（多分）
日本語で書かれた本も出てるみたいだし、非常に心強い。

プログラミングErlang

プログラミングErlang

お給料もらったら買ってこよう

それにしても

「Javaの亜種だから簡単だろう」という軽い気持ちでScalaに手を出したのに、関数型言語の作法とか常識を学ぶためにHaskellを調べたり、今度はアクターモデルの基礎を知るためにErlangを調べることになったり、そういえばtraitもRubyのMixinが前提知識でなければ何のことやらさっぱりわかんなかっただろうなー。
調べてるうちに色んなプログラミング言語を横断的に渡り歩くハメになる言語なのだなあと思いました。

Actorを学ぶ

Scala

Actorがまだよくわからない。インターネットで検索したり色んな人のブログを見たりしてもまだよくわからない。
APIを見てもtraitのActorとobjectのActorがあってうんにゃかもんにゃかだ。

JavaのThreadクラスみたい

objectのActorはひとまず置いといて、traitのActorから攻めてみよう。
これはなんだかJavaのThreadクラスみたいな感じだ。
actメソッドを実装してstartメソッドを呼ぶと、actメソッドの中身が非同期に実行されるみたい。

ちょっとやってみよう

Actorを継承したオブジェクトを定義する。actメソッドの中身は1秒sleepしてから「アクション！」と出力するようにしておく。

import scala.actors.Actor

object MyActor extends Actor {
  def act = {
    Thread.sleep(1000)
    println("アクション！")
  }
}

actを直接呼ぶと（1秒待ってから「アクション！」と出力）が3回繰り替えされる。

object HelloActor {
  def main(args:Array[String]) = {
    for(i <- 1 to 3) MyActor.act
  }
}

startを呼ぶと、1秒待った後に「アクション！」が3行一気に出力されて終了する。

object HelloActor {
  def main(args:Array[String]) = {
    for(i <- 1 to 3) MyActor.start
  }
}

よし、ここまでは分かった。

本家サイトのチュートリアル

本家サイトにActorのチュートリアルがあった。どういうわけか全編英語で書かれてるので何がなんだかさっぱりわからない。Excite翻訳とスペースアルクの力を借りて、日本語に変換しながら読んでみる。

Scala Actors: A Short Tutorial

Introduction


With the advent of multi-core processors concurrent programming is becoming indispensable. Scala's primary concurrency construct is actors. Actors are basically concurrent processes that communicate by exchanging messages. Actors can also be seen as a form of active objects where invoking a method corresponds to sending a message.

The Scala Actors library provides both asynchronous and synchronous message sends (the latter are implemented by exchanging several asynchronous messages). Moreover, actors may communicate using futures where requests are handled asynchronously, but return a representation (the future) that allows to await the reply.

This tutorial is mainly designed as a walk-through of several complete example programs that can be readily compiled and run using Scala 2.4 or newer.

チュートリアル


マルチコアプロセッサが到来して並列プログラミングは不可欠になっています。Scalaの主要な同時並行性の構成概念はactorsです。Actorsってのは要するにメッセージを交換することによって交信する並行処理です。メッセージ送信がメソッド呼び出しに対応する場合、Actorsはアクティブオブジェクトのフォームのようにも見えます。（？）
ScalaのActorsライブラリは非同期と同期両方のメッセージ送信を提供します（後者は、いくつかの非同期なメッセージを交換することによって、実行されます）。そのうえ、actorsは、要求が非同期に処理されるところで先物取引を使用することで交信するかもしれませんが、それで回答をお待ちしている表現(未来)を返してください。（！？）
このチュートリアルは、主にScala2.4以降ですぐにコンパイルして実行できるいくつかの完全なプログラム例の段階的な説明として設計されました。

Actorsってのは要するにメッセージを交換することによって交信する並行処理です。
ここだけ理解できた。素晴らしい。
2本の線がお互いパスしながら平行して進んでいくような感じなんだな。マルチスレッドプログラミングとかいうアレだな。


後はなんだかよくわからなかった。
なんでいきなり先物取引の話になるんだ？
なにかの例えなのか？
アメリカンジョークなのか？
もうだめだ。ジャンプ買ってこよう。

Scalaで何か作ってみよう２

Scala TwitterBot

HttpClientを使ってTwitterにPostすることができました。やったね！
http://twitter.com/syttru/status/1327714655

ハマったとこ

TwitterにPostするとき、以下のリクエストヘッダーを送ると417エラーが返ってきてしまうみたいです。

Except: 100-Continue

このリクエストヘッダーが何なのかはよくわかりませんでしたが、DefaultHttpClientでPostしようとするとこのヘッダーが自動的に送られてしまうようで、こいつを外す方法が分からずにハマりました。

val client = new DefaultHttpClient
client.getParams.setParameter(CoreProtocolPNames.USE_EXPECT_CONTINUE, false)

HttpClientのパラメータで「ExpectContinueを使う」みたいなのがあるみたいで、そいつをオフにするとヘッダーはつかなくなるようです。
こんなもんわかるかー！！


あと、POSTするときはコンテントタイプを指定してあげないといけないみたいです。

val post = new HttpPost("http://twitter.com/statuses/update.xml")
post.addHeader("Content-Type", "application/x-www-form-urlencoded")

どうしてExpectContinueなんていうマニアックなものは自動的にリクエストヘッダに追加してくれるのに、コンテントタイプは追加してくれないんだー。って思いました。

ソースコード

package syttru.twitter

import org.junit._
import Assert._

import org.apache.http.client.methods.HttpPost
import org.apache.http.entity.StringEntity
import org.apache.http.auth.{AuthScope,UsernamePasswordCredentials}
import org.apache.http.impl.client.DefaultHttpClient
import org.apache.http.params.CoreProtocolPNames

import java.io.{BufferedReader,InputStreamReader}

@Test
class HttpClientTest {
    
    @Test
    def testTwitterUpdate() {
      val client = new DefaultHttpClient
      client.getCredentialsProvider.setCredentials(
        new AuthScope("twitter.com", 80), 
        new UsernamePasswordCredentials("syttru@gmail.com", "********"))
      client.getParams.setParameter(CoreProtocolPNames.USE_EXPECT_CONTINUE, false)
      
      val post = new HttpPost("http://twitter.com/statuses/update.xml")
      post.addHeader("Content-Type", "application/x-www-form-urlencoded")
      post.setEntity(new StringEntity("status=テスト更新あああ", "UTF-8"))
      
      val response = client.execute(post)
      
      val input = new BufferedReader(new InputStreamReader(response.getEntity.getContent))
      var line = ""
      while({line=input.readLine; line != null}) {
        println(line)
      }
      
      client.getConnectionManager.shutdown
    }

}

長い…

思ったこと

何も考えずに書くと非常に長くなってしまう。HttpClientの実装を作らないといかん。
リクエストパラメータがキーと値のマップで指定できないと不便だ。


HttpClientのjavadocがcoreとclientの2つに分かれてしまったので非常に見づらい。
ここにリンクを張っておこう。

Scalaで何か作ってみよう１

Scala TwitterBot

プロジェクトフォルダを作る

scalaでの開発にもMavenが使えるらしいです。MavenはJavaの開発で色々とお世話になってすっごく便利だったので使ってみよう。
DOSプロンプトから以下の長ーいコマンドを入力する。

mvn archetype:generate
  -DarchetypeGroupId=org.scala-tools.archetypes
  -DarchetypeArtifactId=scala-archetype-simple
  -DarchetypeVersion=1.2
  -DremoteRepositories=http://scala-tools.org/repo-releases
  -DgroupId=syttru.twitter
  -DartifactId=scalabot

（ホントは一行）


そうするとコマンドラインから質問される。

Define value for version:  1.0-SNAPSHOT: :
Confirm properties configuration:
groupId: syttru.twitter
artifactId: scalabot
version: 1.0-SNAPSHOT
package: syttru.twitter
 Y: :

英語で質問されるので何を言ってるのかよくわからない。「イエースイエース」とか言いながらエンターキーを押します。
scalaのプロジェクトフォルダができた。便利！

pom.xmlをいじる

pom.xmlファイルができたので中身を見てみました。
「scala.version」という項目に「2.7.0」とあります。こないだ2.7.3-finalがリリースされてたので「2.7.3」に置き換えておきましょう。


変更前

  <properties>
    <scala.version>2.7.0</scala.version>
  </properties>

変更後

  <properties>
    <scala.version>2.7.3</scala.version>
  </properties>

pom.xmlに必要なライブラリを書く

Mavenは必要なライブラリを自動的にかき集めてきてくれるので非常に楽です。今回はtwitterのbotを作るのでjakartaプロジェクトのcommons-httpclientが必要になるだろうと思いました。


http://hc.apache.org/


httpclientはいつの間にかjakartaプロジェクトから独立してHTTPComponentsという名前になってました。なんてこったい。
以下の一文をpom.xmlのに追加します。

    <dependency>
      <groupId>org.apache.httpcomponents</groupId>
      <artifactId>httpclient</artifactId>
      <version>4.0-beta2</version>
      <scope>compile</scope>
    </dependency>

HTTPClient試運転

実装する前にHTTPClientライブラリを試してみようと思い、testフォルダで適当に書いてみました。
書いてて気がついたのですが、バージョン4になって使い方が大幅に変更されたようです。
HttpClientクラスがインターフェースになってて、DefaultHttpClientという実装クラスを使うみたいです。
GetMethodクラスやPostMethodクラスは、それぞれHttpGet HttpPostという名前になってました。
／(＾o＾)＼ﾅﾝﾃｺｯﾀｲ

package syttru.twitter

import org.junit._
import Assert._

import org.apache.http.client.methods.HttpGet
import org.apache.http.impl.client.BasicResponseHandler
import org.apache.http.impl.client.DefaultHttpClient

import java.io.{BufferedReader,InputStreamReader}

@Test
class HttpClientTest {

    @Test
    def testGet() = {
      val client = new DefaultHttpClient
      val get = new HttpGet("http://search.twitter.com/search.atom?lang=ja&q=scala")
      
      val response = client.execute(get)
      val entity = response.getEntity
      
      val input = new BufferedReader(new InputStreamReader(entity.getContent))
      var line = ""
      while({line=input.readLine; line != null}) {
        println(line)
      }
      
      client.getConnectionManager.shutdown
    }

}

うーん。。。
急にscalaの世界からJavaの世界に連れ戻されたような感覚です。Javaのライブラリをそのまんま使うのはよくないなあ。勉強のためにラッパーを書きたいなあ。既にあるのかなあ。探してみよう。


今日はここまで

追記

寝る前にぐぐったらHttpClientとか使わずに1行で実現できることが判明しました。私は悲しい。

import scala.io.Source

object Main {
  def main(argv: Array[String]) {
    Source fromURL "http://search.twitter.com/search.atom?lang=ja&q=scala" foreach (c=>print(c))
  }
}