恵方を算出するScalaライブラリ
もう誰得よ?って感じですが作りました。
恵方って、4パターンしか無いんですね。
// http://ja.wikipedia.org/wiki/恵方#.E6.81.B5.E6.96.B9 object 恵方{ import java.util.{Date,Calendar} def 今年の恵方 = この年の恵方は_?( Calendar.getInstance ) def この年の恵方は_? ( 年:Calendar ):恵方 = 年.get( Calendar.YEAR ) % 5 match { case 0 => 恵方("庚の方","申と酉の中間","255°","西微南やや左","西南西やや右") case 1 => 恵方("丙の方","巳と午の中間","165°","南微東やや左","南南東やや右") case 2 => 恵方("壬の方","亥と子の中間","345°","北微西やや左","北北西やや右") case 3 => 恵方("丙の方","巳と午の中間","165°","南微東やや左","南南東やや右") case 4 => 恵方("甲の方","寅と卯の中間","75°","東微北やや左","東北東やや右") } def この年の恵方は_? ( 年:Date ):恵方 = { val カレンダー = Calendar.getInstance カレンダー.setTime( 年 ) この年の恵方は_? ( カレンダー ) } case class 恵方(正確に:String, 十二支:String, 方位角:String, 方位32:String, 方位16:String ) }
実行結果:
scala> 恵方.今年の恵方 res0: 恵方.恵方 = 恵方(庚の方,申と酉の中間,255°,西微南やや左,西南西やや右) scala> import java.util.Calendar import java.util.Calendar scala> val c = Calendar.getInstance c: java.util.Calendar = java.util.GregorianCalendar[time=1265340075314,areFieldsSet=true,areAllFieldsSet=true,lenient=true,zone=sun.util.calendar.ZoneInfo[id="Asia/Tokyo",offset=32400000,dstSavings=0,useDaylight=false,transitions=10,lastRule=null],firstDayOfWeek=1,minimalDaysInFirstWeek=1,ERA=1,YEAR=2010,MONTH=1,WEEK_OF_YEAR=6,WEEK_OF_MONTH=1,DAY_OF_MONTH=5,DAY_OF_YEAR=36,DAY_OF_WEEK=... scala> c.add( Calendar.YEAR , 1 ) scala> 恵方.この年の恵方は_?( c ) res2: 恵方.恵方 = 恵方(丙の方,巳と午の中間,165°,南微東やや左,南南東やや右)
来年の恵方は、「南南東やや右」ですよ!!
scalaでYコンビネータ
Yコンビネータの定義:
def Y[A,B]( f:((A => B), A ) => B, x:A ):B = f( ( y:A ) => Y( f,y ),x )
Yコンビネータってのは、要は
Y(f) = f(Y(f))
となる関数らしい。不動点演算子とか呼ばれていますがなんのことかわかりませんね。
「ある関数fをYに与えた結果できる関数をf'とすると、f'をまたYに与えてできる関数はfと同じ」になるように関数を作り出すものです。
何でこんなもん必要なの?
ある無名関数があるとしましょう。この無名関数は名前が定義されていないため、自身を再帰で呼び出す定義ができません。
単純に、0から引数nまで加算する関数を無名関数で定義しようとすると、
(i:Int) => i match{
case 0 => 0
case _ => i + ここで自分自身を再帰で呼びたいけど名前がない( i - 1 )
}
こんな風に名前がないのでできませんよね?
ここで、Yコンビネータ様の登場ですよ!!
Yコンビネータ様は、引数にもらった無名関数を変換して、無名関数自身に便宜的な名前(さっきの例ではf)をつけて引数に渡す関数を作ってくれます。
そうすると、Yコンビネータに渡す無名関数は、Yコンビネータが引数でもらうはずの自分自身をfという引数名でもらえるようになっているので、無名関数内でfという名前を使って自分自身を再帰で呼び出すことができます。
さっきの、無名関数では再帰が定義できない、という問題はYコンビネータにより解決されました。
もともとは、ラムダ式で再帰を定義するための物らしいです。ラムダで条件分岐と繰り返しが定義できれば、あらゆる計算はラムダ式で実現できるという。。。
フィボナッチをやってみる
scala> def Y[A,B]( f:((A => B), A ) => B, x:A ):B = f( (y:A) => Y(f,y),x) Y: [A,B](((A) => B, A) => B,A)B scala> Y( (f:Int => Int , n:Int) => n match{ | case m if m < 2 => m | case _ => f( n - 1 ) + f( n - 2 ) | },7) res2: Int = 13
これはフィボナッチ数を計算するfという関数があって、fを再帰で呼び出しているように見えますが、実はYに与えた関数自身には名前がありません。
無名関数で再帰できてますね。
ってことで、自分では理解したつもりですが、書いてみると難すぃ。。。
車輪の再発明 - Base64のencoder/decoderをScalaで書いてみた。
「何故、JDKにはBase64のencoder/decoderがないのだッ?!」
ってことで、書きました。
imutableなLIstをreverseしたりdropしたりしまくって、再帰でListを受け渡す形なのでパフォーマンスいくないです。
あと、decodeの時はフォーマットのチェックしてない適当さwww。
まぁ練習で書いたんで
／）
／／／）
／,.=ﾞ''"／
／ i f ,.r='"-‐'つ＿＿＿_ こまけぇこたぁいいんだよ！！
/ / _,.-‐'~／⌒ ⌒＼
／ ,i ,二ﾆ⊃（ ●）. （●）＼
/ ﾉ ilﾞフ::::::⌒（__人__）⌒::::: ＼
,ｲ｢ﾄ､ ,!,!| |r┬-| |
/ iﾄヾヽ_/ｨ"＼ `ー'´ ／
object Base64 { val BASE64 = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/" def encode( s:String ) = encodeBuffer( s.getBytes ) def encode( s:String, charset:String ) = encodeBuffer( s.getBytes( charset ) ) private def encodeBuffer( buf:Array[Byte] ) = { val bits = fill( buf.map{ b => if( b < 0 ) b + 256 else b.toInt }.map{ i => ("00000000" + i.toBinaryString).reverse.take(8).reverse }.mkString, "0", 6 ).toList def encodeBits( xs:List[Char] ):String = xs match{ case Nil => "" case ss => val (h,t) = ss.splitAt(6) BASE64( (0 /: h.reverse.zipWithIndex){ case( n, (c, i)) => n + (Math.pow( 2, i) * c.asDigit ).toInt } ) + encodeBits( t ) } fill( encodeBits( bits), "=", 4) } private def fill( s:String, fill:String, n:Int ) = s + ( fill * ( n - ( s.length % n ))) def decode( s:String ) = new String( decodeBuffer( s )) def decode( s:String , charset:String ) = new String( decodeBuffer( s ), charset ) def decodeBuffer( s:String ) = { val bits = s.map{ BASE64.indexOf(_)}. filter( 0 < ). map{ b => ("000000" + b.toBinaryString).reverse.take(6).reverse }.mkString.toList def decodeBits( xs:List[Char] ):List[Byte]= xs match { case Nil => Nil case ss => val (h,t) = ss.splitAt(8) (( (0 /: h.reverse.zipWithIndex){ case( n, (c, i)) => n + (Math.pow( 2, i) * c.asDigit ).toInt } ) match{ case b if b > 256 => (b - 256).toByte case b => b.toByte }) :: decodeBits( t ) } decodeBits( bits ).toArray } }
GeoHashのdecodeのアルゴリズムの解説します & ScalaのGeoHashライブラリを作ってみました(仮)
GeoHash(http://en.wikipedia.org/wiki/Geohash)は、緯度経度を文字列のハッシュで表現する仕様です。
GeoHashにより表現された緯度経度の情報は、一つの文字列で緯度と経度という2次元の情報に加えて精度も表すことができるという特徴を持っています。
例えば、どうでしょうバカの聖地である北海道札幌市の平岸高台公園は、北緯43.025東経141.377ですが、これをGeoHashで表現すると、"xpssc0"となります。
この"xpssc0"というGeoHash表現は、「北緯43.0224609375から43.0279541015625の間で、東経141.3720703125から141.383056640625の矩形範囲」であり、座標はこの矩形範囲の中心点になります。
@masuidrive blogさんの緯度経度を文字列で表すGeoHash - @masuidrive blogを読んでこの仕様を知り、面白そうだと思ってScala版のライブラリを作ってみました。GeoHashの解説もこちらの記事が非常に参考になります。
GeoHashをデコードするアルゴリズム
Wikipediaにも書いてありますが、文字列で表現されたGeoHashを実際の緯度経度にデコードするアルゴリズムを解説します。
1.Base32によるデコード
まず、GeoHashの文字列は、"BASE32"というエンコードが行われた結果の文字列です。
この"BASE32"は、0から32までの数値を、0から9までの数字と"a","i","l","o"を除いたアルファベットに変換するエンコードです。
具体的な変換テーブルは下記の通りです。
| 数値 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Base32 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | b | c | d | e | f | g |
| 数値 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Base32 | h | j | k | m | n | p | q | r | s | t | u | v | w | x | y | z |
で、先ほどの"xpssc0"というGeoHashをBase32によりデコードすると、以下のような結果になります。
| GeoHash(Base32) | x | p | s | s | c | 0 |
|---|---|---|---|---|---|---|
| 数値 | 31 | 21 | 24 | 24 | 11 | 0 |
次に、Base32によって変換された0から31までの数値を5bitのbit列の表現に変換します。
| GeoHash(Base32) | x | p | s | s | c | 0 |
|---|---|---|---|---|---|---|
| 数値 | 31 | 21 | 24 | 24 | 11 | 0 |
| bit列 | 11111 | 10101 | 11000 | 11000 | 01011 | 00000 |
2.デコードしたbit列から緯度と経度を分離させる
1でデコードした結果、"xpssc0"というGeoHashは、"11111 10101 11000 11000 01011 00000"というbit列の表現に変換されました。
このbit列から、緯度に対応するbitと経度に対応するbitを分離させます。
bit列の左から0を始点としてみて、偶数bitが経度、奇数bitが緯度に対応するbit列です。
| bit番号 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| bit列 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 1 | 0 | 1 | 1 | 1 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 0 |
| bit番号 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 |
|---|---|---|---|---|---|---|---|---|---|---|
| bit列 | 0 | 1 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 0 |
色をつけたところが奇数なので緯度、色がないところは偶数なので緯度です。
ここから取り出してみると、緯度経度は以下のようなbit列として分離できます。
| 経度(偶数bit) | 111001001000100 |
| 緯度(奇数bit) | 101111010011000 |
|---|
3.緯度経度それぞれのbit列から範囲を算出する
さて、ここまで緯度と経度それぞれのbit列に変換できました。ここで、このbit列から具体的な緯度経度の数値を算出します。
算出の方法ですが、bit列に応じて範囲を2分割しながら絞り込む形をとります。
緯度の場合で説明します。
緯度の場合は、絞り込みの範囲が"-90度から90度"の範囲で開始します。
まず、この-90度から90度の範囲を2分割します。2分割すると、"-90から0"と"0から90"の二つの範囲になります。
与えられた緯度のbit列が、この2つの範囲のどちらに属するかは、bit列の1bit目が表しています。
1bit目は"1"ですので、大きい方の範囲である"0から90"の範囲の緯度であることが絞り込まれます。
次に、"0から90"の範囲を2分割します。2分割すると、"0から45"と"45から90"の二つの範囲になります。
2bit目は"0"ですので、小さい方の範囲である"0から45"の範囲の緯度であることが絞り込まれます。
この要領で、bit列の全てのbitに対して絞り込みを繰り返します。次のようなイメージです。
| bit | max | mid | min | val |
|---|---|---|---|---|
| 1 | -90.000 | 0.000 | 90.000 | 45.000 |
| 0 | 0.000 | 45.000 | 90.000 | 22.500 |
| 1 | 0.000 | 22.500 | 45.000 | 33.750 |
| 1 | 22.500 | 33.750 | 45.000 | 39.375 |
| 1 | 33.750 | 39.375 | 45.000 | 42.188 |
| 1 | 39.375 | 42.188 | 45.000 | 43.594 |
| 0 | 42.188 | 43.594 | 45.000 | 42.891 |
| 1 | 42.188 | 42.891 | 43.594 | 43.242 |
| 0 | 42.891 | 43.242 | 43.594 | 43.066 |
| 0 | 42.891 | 43.066 | 43.242 | 42.979 |
| 1 | 42.891 | 42.979 | 43.066 | 43.022 |
| 1 | 42.979 | 43.022 | 43.066 | 43.044 |
| 0 | 43.022 | 43.044 | 43.066 | 43.033 |
| 0 | 43.022 | 43.033 | 43.044 | 43.028 |
| 0 | 43.022 | 43.028 | 43.033 | 43.025 |
最終的に、緯度は北緯43.025と算出されました。範囲は、"北緯43.022から北緯43.028"であることがわかります。
同じ要領で、経度のbit列に対しても"-180から180"を開始範囲として絞り込むこと経度が算出できます。
GeoHashをエンコード/デコードするScalaのライブラリ
で、書いてみました。
結構やっつけでエラーチェックとかしてないです。
object GeoHash{ val base32 = "0123456789bcdefghjkmnpqrstuvwxyz" def encode( longtitude:Double, latitude:Double, range:Double) = { def asBit( d:Double,max:Double,min:Double ) : List[Boolean] = { val mid = ( max + min ) / 2 var res = ( d >= mid ) val (m,n) = if( res ) (max,mid) else (mid,min) if( Math.abs( m - n ) <= range ) res :: Nil else res :: asBit( d ,m ,n ) } def asBase32( xs:List[Boolean] ):String = { base32( (0.0 /: xs.reverse.zipWithIndex){ case( n,(b,i) ) => if( b ) n + Math.pow( 2, i ) else n } toInt ).toString } def encodeBits( xs:List[Boolean] ):String = xs match{ case Nil => "" case _ => val (h,t) = xs.splitAt(5) asBase32(h) + encodeBits( t ) } val bits = asBit(longtitude , 180,-180 ). zipAll( asBit( latitude, 90, -90 ), false, false ). flatMap{ case (a,b) => a::b::Nil } encodeBits( bits ).reverse.dropWhile( '0' == ).reverse.mkString } def decode( geohash:String ):((Double,Double),(Double,Double)) = { def toBitList( s:String ) = s.toLowerCase.flatMap{ c => ("00000" + base32.indexOf(c).toBinaryString ). reverse.take(5).reverse.map('1' == ) } toList def split( l:List[Boolean] ):(List[Boolean],List[Boolean]) ={ l match{ case Nil => (Nil,Nil) case x::Nil => ( x::Nil,Nil) case x::y::zs => val (xs,ys) =split( zs );( x::xs,y::ys) } } def dehash( xs:List[Boolean], min:Double, max:Double ):(Double,Double) = { ((min,max) /: xs ){ case ((min,max) ,b) => if( b )( (min + max )/2 , max ) else ( min,(min + max )/ 2 ) } } val ( xs ,ys ) = split( toBitList( geohash ) ) ( dehash( xs, -180,180 ) , dehash( ys ,-90,90) ) } }
Scala Hack-a-thon #2(初心者向けハンズオンor発火村) やります!
1回目の発火村が終わったばかりですが、Scala Hack-a-thon #2 を開催します。
参加希望の方は、ATNDで申し込み登録してくださいね☆
参加お待ちしております!!
Scala Hack-a-thon #2
■なにやるの?
・Scalaの初心者向けのハンズオン
なんらかのテーマにそって、Scalaのコードを書きながらチュートリアルします。Scalaの言語仕様をある程度網羅して覚えてもらう内容を考えてます。
・発火村
ある程度Scalaが出来る人は、勝手にコード書いて周りの人と情報交換してください。こっちはゆるふわ系で。
今回は、いくつかのテーマを設定してグループ分けしようと思います。「こんなテーマでやって欲しい!」という要望があればコメントなどで、言ってください。
チューターも募集しています。
LTもやろうかと思うんで、やりたい人はコメントなどで連絡ください。
■会話
リアルでもしゃべって構わないんですよ?ついったーもほどほどにね!
■日時
2010年2月20日(土) 10:00 開場 19:00終了
■会場
オラクル青山センター 13F （東京都港区北青山2-5-8）
http://www.google.co.jp/maps?q=35.6712183,139.7186712(東京都港区北青山2-5-8)&z=17
電源、無線LANあります!
■定員
70名
■懇親会
やる予定です。場所未定。懇親会参加希望の方は、参加登録の際にアンケートで出欠を登録してください。
■用意するもの
・ノートPC(必須)
・Scalaの処理系(2.7以降。2.7.5が好ましい)がインストールされたノートPC
・ScalaのAPIドキュメントをダウンロードしておくと便利
・なんらかのScalaの書籍があるといいかも?
■お問い合わせ
メール(helmettomoあっとgmail.com)またはついった(http://twitter.com/yuroyoro)
はてなスーパーPre記法がScalaに対応したらしいのでEchoServerのソース貼ってみる
はてなスーパーPre記法がScalaに対応したらしいのでEchoServerのソース貼ってみます。
いちおう、Scala hack-a-thonの資料にも反映済み。
yuroyoro/scala-hackathon · GitHub
Dropbox - 404
普通のServerSocket版と、NIOノンブロッキングチャネル版の2種類書いてみましたが、ヒドいソースなんで添削希望ですだれかボスケテ。
ServerSocket版
import scala.actors.Actor import scala.actors.Actor._ import java.io._ import java.net.{ServerSocket, Socket } object EchoServer{ def main( args:Array[String] ) = { EchoActor.start() EchoActor ! Start( args.first.toInt ) } } case class Start( port:Int ) case class Wait( serverSocket:ServerSocket ) case class Accept( socket:Socket ) object EchoActor extends Actor { def act() = { loop{ react { case Start( port ) => { val serverSocket = new ServerSocket( port ) println( "EchoServeが起動しました。port=%d".format( port ) ) EchoActor ! Wait( serverSocket ) } case Wait( serverSocket ) => { val socket = serverSocket.accept val acceptActor = new AcceptActor acceptActor.start() acceptActor! Accept( socket ) EchoActor ! Wait( serverSocket ) } } } } } class AcceptActor extends Actor { def act() = { react { case Accept( socket ) => { val address = socket.getInetAddress println( address + ":[接続しました]" ) val in = new BufferedReader( new InputStreamReader(socket.getInputStream ) ) val out = new PrintWriter( socket.getOutputStream, true) val s = in.readLine println( "%s:%s".format( address , s ) ) out.println( s ) out.close in.close socket.close println( address + ":[切断しました]" ) } } } }
NIO ノンブロッキングチャネル版
import scala.actors.Actor import scala.actors.Actor._ import scala.collection.jcl.Conversions._ import java.net.InetSocketAddress import java.nio.ByteBuffer import java.nio.channels.{ SelectionKey, Selector, ServerSocketChannel, SocketChannel } import java.nio.charset.Charset object EchoServerNIO{ def main( args:Array[String] ){ EchoActor.start() EchoActor ! Start( args.first.toInt ) } } case class Select() case class Start( port:Int ) case class Accept( key:SelectionKey ) case class Read( key:SelectionKey ) object EchoActor extends Actor { val BUF_SIZE = 1024 lazy val selector = Selector.open lazy val serverChannel = ServerSocketChannel.open def act() = { loop { react { case Start( port ) => { serverChannel.configureBlocking(false) serverChannel.socket.bind( new InetSocketAddress( port ) ) serverChannel.register(selector, SelectionKey.OP_ACCEPT ) println( "EchoServeが起動しました。port=%d".format( port ) ) EchoActor ! Select } case Select => { selector.select selector.selectedKeys.foreach{ key => if( key.isAcceptable ){ EchoActor ! Accept( key ) } else if( key.isReadable ){ EchoActor ! Read( key ) } } EchoActor ! Select } case Accept( key ) => { val socket = key.channel.asInstanceOf[ServerSocketChannel] socket.accept match { case null => case channel => { val remoteAddress = channel.socket.getRemoteSocketAddress.toString(); println(remoteAddress + ":[接続しました]" ) channel.configureBlocking(false) channel.register(selector, SelectionKey.OP_READ); } } } case Read( key ) => { val channel = key.channel.asInstanceOf[SocketChannel] val buf = ByteBuffer.allocate(BUF_SIZE) val charset = Charset.forName("UTF-8") val remoteAddress = channel.socket.getRemoteSocketAddress.toString(); def close = { channel.close() println( remoteAddress + ":[切断しました]" ) } channel.read( buf ) match { case -1 => close case 0 => case x => { buf.flip println( "%s:%s".format( remoteAddress, charset.decode(buf).toString )) buf.flip channel.write( buf ) close } } } } } } }
