ZIO 2.0について
この記事はScala Advent Calendar 2021の17日目の記事です。
参考
この記事では下記のサイトから説明、コード、画像を引用しています。
ZIOとは
ZIOは純粋な関数型プログラミングを促進する非同期・並行プログラミング用ライブラリです。 モナドなどを知らなくても、ZIOを使うことで関数型プログラミングを始めることができます。
ZIO 2.0
つい先日ZIO2.0-RC1がリリースされました。 github.com
ZIO2.0では以下の4つの領域で大きな変更が加えられています。
- Performance
- Ergonomics
- Operations
- Streaming
ZIO2.0への移行ガイドはこちらになります。 zio.dev
以下では、上記の中からZIO 2.0での変更点で私が気になった点を取り上げました。
[Performance] 新しいスケジューラー
ZIO2.0ではスケジューラが新しくなりました。 ZIOではfiberという論理的なプロセスの単位で処理が実行されます。アプリケーションは無数のfibterから構成され、スケジューラーはfiberのOSスレッドへの割り当てを制御します。 ZIO 1.xではスケジューラーはグローバルな単一のキューとして実装されていました。
この実装の場合、全てのワーカースレッドが同じキューから取り出すため、多くのワーカースレッドが同時に操作しようとするとパフォーマンスに悪影響を及ぼす可能性がありました。また、グローバルキューを使用するとキャッシュの局所性を損ねパフォーマンスを向上させることができませんでした。
ZIO2.0では以下のようになりました。
各ワーカースレッドごとにローカルのキューを持つことで、グローバルなリソースの競合を排除しキャッシュの局所性を最大化させることができます。しかしながら、それだけでは特定のワーカーにタスクが偏った場合リソースを効率的に使用できない可能性があります。そこで新しいスケジューラーはワーカーが自身のキューにタスクが存在しない場合に他のワーカーからタスクを盗むことができるようになっています。
詳細は以下のブログに記載されているのでご参照ください。 ziverge.com
ちなみにRustのTokioプロジェクトに触発されて開発したようです。
また、関連していそうなPRはこちらです。 github.com
[Ergonomics] Layerが使いやすくなった
fromService*がなくなりtoLayerに統一される
ZIO 1.xでは他のServiceに依存したServiceを作る場合、以下のように書かないといけませんでした。
val live: URLayer[Clock with Console, Logging] = ZLayer.fromServices[Clock.Service, Console.Service, Logging.Service] { (clock: Clock.Service, console: Console.Service) => new Service { override def log(line: String): UIO[Unit] = for { current <- clock.currentDateTime.orDie _ <- console.putStrLn(current.toString + "--" + line).orDie } yield () } }
ZIO 2.0ではtoLayerが導入されボイラープレートを書かなく済むようになります。
case class LoggingLive(console: Console, clock: Clock) extends Logging { override def log(line: String): UIO[Unit] = for { current <- clock.currentDateTime.orDie _ <- console.putStrLn(current.toString + "--" + line).orDie } yield () } object LoggingLive { val layer: URLayer[Console with Clock, Logging] = (LoggingLive(_, _)).toLayer[Logging] }
依存関係の構築が簡単に
ZIO 1.xでは複数のレイヤーを以下のように組み合わせてアプリケーション全体の依存グラフを構築する必要がありました。
val appLayer: URLayer[Any, DocRepo with UserRepo] = (((Console.live >>> Logging.live) ++ Database.live ++ (Console.live >>> Logging.live >>> BlobStorage.live)) >>> DocRepo.live) ++ (((Console.live >>> Logging.live) ++ Database.live) >>> UserRepo.live) val res: ZIO[Any, Nothing, Unit] = myApp.provide(appLayer)
依存関係が大きくなってくると上記をメンテするのが大変でした。また依存関係の宣言に間違いがあった場合、以下のようなメッセージがコンパイル時に出力されるのですが、わかりづらく解決するのが難しかったです。
type mismatch;
found : zio.URLayer[zio.Logging with zio.Database with zio.BlobStorage,zio.DocRepo]
(which expands to) zio.ZLayer[zio.Logging with zio.Database with zio.BlobStorage,Nothing,zio.DocRepo]
required: zio.ZLayer[zio.Database with zio.BlobStorage,?,?]
((Database.live ++ BlobStorage.live) >>> DocRepo.live) ++
ZIO 2.0ではinjectを使用することで自動で依存関係が解決されるようになります！
val res: ZIO[Any, Nothing, Unit] =
myApp.inject(
Console.live,
Logging.live,
Database.live,
BlobStorage.live,
DocRepo.live,
UserRepo.live
)
Module Patternが変わる
ZIO1.xでのModule Patternは以下のようになっていました。
object logging { // Defining the service type by wrapping the service interface with Has[_] data type type Logging = Has[Logging.Service] // Companion object that holds service interface and its live implementation object Logging { trait Service { def log(line: String): UIO[Unit] } // Live implementation of the Logging service val live: ZLayer[Clock with Console, Nothing, Logging] = ZLayer.fromServices[Clock.Service, Console.Service, Logging.Service] { (clock: Clock.Service, console: Console.Service) => new Logging.Service { override def log(line: String): UIO[Unit] = for { current <- clock.currentDateTime.orDie _ <- console.putStrLn(s"$current--$line") } yield () } } } // Accessor Methods def log(line: => String): URIO[Logging, Unit] = ZIO.accessM(_.get.log(line)) }
ZIO 2.0 では Hasが削除され以下のようになります。
// Defining the Service Interface trait Logging { def log(line: String): UIO[Unit] } // Accessor Methods Inside the Companion Object object Logging { def log(line: String): URIO[Logging, Unit] = ZIO.serviceWithZIO(_.log(line)) } // Implementation of the Service Interface case class LoggingLive(console: Console, clock: Clock) extends Logging { override def log(line: String): UIO[Unit] = for { time <- clock.currentDateTime _ <- console.printLine(s"$time--$line").orDie } yield () } // Converting the Service Implementation into the ZLayer object LoggingLive { val layer: URLayer[Console with Clock, Logging] = (LoggingLive(_, _)).toLayer[Logging] }
ZIO1.x系のmoduleパターンについては以前書きましたが、
Hasが削除された結果、覚えることが少なくなりよりシンプルに書けるようになっている気がします。
[Ergonomics] Smart Constructorの導入
ZIO 1.xではZIOのコンストラクタとしてZIO.fromEitherやZIO.fromOptionのような形で、元になるデータ型ごとにメソッドが用意されていました。
ZIO 2.0ではfromだけで様々なデータ型からZIOを生成できるようになっています。
ZIO.from {
println("Entering example")
for {
result1 <- ZIO.from(Future.successful(1))
result2 <- ZIO.from(Right(2))
result3 <- ZIO.from(ZIO.from(3))
result4 <- ZIO.from(Try(4))
} yield result1 + result2 + result3 + result4
}
[Operations] Loggingがビルトインされるようになった
ZIO 2.0 では標準のlogging facadeが提供されるようになりました。 facadeなのでlogbackやlog4jなどのloggingバックエンドはこれまで通り必要となります。
ZIO.logLevel(LogLevel.Warning) {
ZIO.log("The response time exceeded its threshold!")
}
ZIO.logError("File does not exist: ~/var/www/favicon.ico")
今まではLogging Moduleを毎回自作していたので、その手間がなくなりそうです。
まとめ
ZIO 2.0で導入される機能や変更の一部を紹介しました。様々な改善点が盛り込まれていてリリースされるのが待ち遠しいです。 今回は変更点が多すぎてほんの一部しか紹介できなかったので、ぜひマイグレーションガイドを読んでみてください。
ZIOのZLayerについて
この記事はただの集団 Advent Calendar 2020の23日目の記事です。
本記事では、ZIOのDI機能であるZLayerの使い方を説明します。 対象読者はZIOをある程度知っている方を想定しています。 ZIOについて詳しく知らない方はまず公式ページのドキュメントを読むことをお勧めします。
ZIOとは
ZIOは純粋な関数型プログラミングを促進する非同期・並行プログラミング用ライブラリです。 モナドなどを知らなくても、ZIOを使うことで関数型プログラミングを始めることができます。
ZIOには便利なデータ型が複数存在しますが、中心となるのはeffectを表すデータ型であるZIO[-R, +E, +A]です。
このデータ型はの3つの型パラメータを持ちます。
R: Environment Type => 実行に必要な環境の型, Anyの場合は環境を必要としない E: Failure Type => 失敗した時の型, Nothingの場合は失敗しない A: Success Type => 成功した時の型
E,Aに関しては説明不用だと思うので、今回はこのRについて詳しくみていきます。
環境型Rの使い方
題材としてZIOで書かれた以下のプログラムを考えます。 このコードは、公式ドキュメントのものを参考にしています。 https://zio.dev/docs/howto/howto_use_layers#our-first-zio-module
val user2: User = User(UserId(123), "Tommy") val makeUser: ZIO[Logging with UserRepo, DBError, Unit] = for { _ <- ZIO.accessM[Logging](_.get.info(s"inserting user")) _ <- ZIO.accessM[UserRepo](_.get..createUser(user2)) _ <- ZIO.accessM[Logging](_.get.info(s"user inserted")) } yield ()
このプログラムは、最初に処理をはじめることをログに出力し、 つぎに、ユーザをRepositoryに登録します。 最後にログに処理が完了したことを再度出力します。
Logging with UserRepoがmakeUserを実行するために必要な環境の型です。
ここではLoggingやUserRepoは以下のようなメソッドを持つ型だと考えてください。
trait Logging {
def info(s: String): UIO[Unit]
}
trait UserRepo {
def createUser(user: User): IO[DBError, Unit]
}
ZIO.accessMを使うことでeffectの環境にアクセスすることができます。
このプログラムmakeUserを実行するためには、
以下のようにLoggingとUserRepoの実装を提供する必要があります。
val runnable: ZIO[Any, DBError, Unit] = makeUser.provide(new Logging with UserRepo { // なんらかの実装 }) runtime.unsafeRun(runnable)
ZIO.provideによってeffectに環境を提供することで、Rから必要な環境が削除され、環境型がAnyのeffectが生成されます。
こうして作成されたeffectはruntime.unsafeRunで実行できるようになります。
ZIOのバージョンv1.0.0-RC17までは実際にこのようにして、依存性を注入していました。
しかしながら、このアプローチにはいくつかの欠点があります。 まず、環境の一部だけを提供することができません。必要な環境を全て揃えた上でprovideする必要があります。 また、環境の一部を動的に更新することができず、アプリケーションの一部でサービスをカスタマイズしようとするときに苦労します。
これらの問題の解決のために、v1.0.0-RC18ではHasとZLayerという2つの新しいデータ型が導入されました。
ZIO module
HasとZLayerの詳細に入る前に、ZIOで環境を定義する際の典型的なパターンを紹介します。
type UserRepo = Has[UserRepo.Service] object UserRepo { // インタフェース trait Service { def getUser(userId: UserId): IO[DBError, Option[User]] def createUser(user: User): IO[DBError, Unit] } // 実装 val testRepo: ZLayer[Any, Nothing, UserRepo] = ZLayer.succeed(???) // ZIO.accessMを毎回書くのは大変なので、ここでアクセサメソッドを定義しておく def getUser(userId: UserId): ZIO[UserRepo, DBError, Option[User]] = ZIO.accessM(_.get.getUser(userId)) def createUser(user: User): ZIO[UserRepo, DBError, Unit] = ZIO.accessM(_.get.createUser(user)) }
この書き方のパターンをモジュールパターンと呼びます。 モジュールとは、1つの問題のみを扱う機能のグループです。 モジュールの範囲を限定することで、頭の中であまりにも多くの概念を一緒に扱うことなく、 一度に一つのトピックだけに集中することができます。
何かしらの環境を定義する必要がある場合は、まずこのパターンにのっとってインタフェースを定義します。 このパターンさえ覚えておけば、どのようなものでも同じようにアプリケーションの環境として扱えます。
Has
先ほどのコードでHas[UserRepo.Service]というものがありました。
Has[A] は、型 A のサービスに対するeffectの依存性を表現するための型です。
たとえば、RIO[Has[Console.Service], Unit] はこのeffectがConsole.Serviceを必要とすることを表しています。
Hasは++演算子を使用して組み合わせることができます。
val repo: Has[UserRepo.Service] = Has(new UserRepo.Service{}) val logger: Has[Logger.Service] = Has(new Logger.Service{}) val mix: Has[UserRepo.Service] with Has[Logger.Service] = repo ++ logger
先ほどは UserRepo with Loggingとmixinで2つの環境を組み合わせていました。
これでも環境の組み合わせはできていたのに、
なぜtype UserRepo = Has[UserRepo.Service]のような型エイリアスを用いてまでHasを使っているのでしょうか？
Hasが優れているところは、以下のように複数のHasを結合したあとでも、 それぞれの環境を分離して取り出すことができる点です。
// get back the logger service from the mixed value: val log = mix.get[Logger.Service].log("Hello modules!")
これが可能であるということは、型安全に環境の一部を動的に更新することができるということです。
Hasでなぜこのようなことが可能なのかというと、TypeTagを用いているためです。
Hasの定義は以下のようになっています。
https://github.com/zio/zio/blob/master/core/shared/src/main/scala/zio/Has.scala
final class Has[A] private ( private val map: Map[LightTypeTag, scala.Any], private var cache: Map[LightTypeTag, scala.Any] = Map() ) extends Serializable ..
ここでmap: Map[LightTypeTag, scala.Any]でインタフェースと実装のマッピングを保持しています。
他の JVM言語同様に、Scala の型はコンパイル時に消去されますが、
TypeTagを用いることで実行時でも型情報を保持することができます。
Hasを++で結合するということは、単にmapに新しい項目を追加しているということです。
またmapのキーに同じ型を指定することで実装を後から入れ替えることもできます。
余談ですが、ZIOではscala-reflectのTypeTagの代わりに独自実装のizumi-reflectを使用しているようです。 github.com
ZLayer
さて、データ型Hasを見てきましたが、つぎにZLayerについて説明します。
Zlayerは環境Rを作るためのレシピを表すデータ型です。ZLayer[-RIn, +E, +ROut <: Has[_]]という3つの型パラメータを持ちます。
RIn - 構築するために必要な依存関係 (依存関係がない場合は Any になります) E - 作成時に発生する可能性があるエラー(失敗する可能性がない場合はNothing) ROut - 作成される環境の型
つまり、RIn型からRout型を生成する方法を表すデータ型です。 これはJavaやScalaアプリケーションのコンストラクタに似ていて、依存するサービスを受け取り、構築したサービスを返します（コンストラクタベースの依存性注入）。 しかし、コンストラクタとは異なり、ZLayers はいくつかの方法で型安全に構成されたファーストクラスの値であり、1つのサービスだけではなく、多くのサービスを構築することができます。 さらに、データベースに接続し、データベースのスレッドプールを作成し、サービスが不要になったら、スレッドプールを解放し、データベースから切断するといった、リソースの管理も行うことができます。
では、ZLayerの作り方を見ていきます。
まず、RIntがAnyかつ失敗しない場合は、ZLayer.succeedを使うことでZLayerを作成できます。
type UserRepo = Has[UserRepo.Service] object UserRepo { trait Service { def getUser(userId: UserId): IO[DBError, Option[User]] def createUser(user: User): IO[DBError, Unit] } val inMemory: ZLayer[Any, Nothing, UserRepo] = ZLayer.succeed( new Service { def getUser(userId: UserId): IO[DBError, Option[User]] = UIO(???) def createUser(user: User): IO[DBError, Unit] = UIO(???) } ) //accessor methods def getUser(userId: UserId): ZIO[UserRepo, DBError, Option[User]] = ZIO.accessM(_.get.getUser(userId)) def createUser(user: User): ZIO[UserRepo, DBError, Unit] = ZIO.accessM(_.get.createUser(user)) }
つぎに、構築時に他のコンポーネントが必要な場合を見てみます。
type Logging = Has[Logging.Service] object Logging { trait Service { def info(s: String): UIO[Unit] def error(s: String): UIO[Unit] } import zio.console.Console val consoleLogger: ZLayer[Console, Nothing, Logging] = ZLayer.fromFunction( console => new Service { def info(s: String): UIO[Unit] = console.get.putStrLn(s"info - $s") def error(s: String): UIO[Unit] = console.get.putStrLn(s"error - $s") } ) //accessor methods def info(s: String): URIO[Logging, Unit] = ZIO.accessM(_.get.info(s)) def error(s: String): URIO[Logging, Unit] = ZIO.accessM(_.get.error(s)) }
ZLayerの構築方法は以下のように様々な種類があります。 一つ一つの説明は行いませんが、どのメソッドを使うべきかの判断するには各メソッドの実装を見て型から考えていくのが早いと思います。
ZLayer.succeed // or ZIO#asService to create a layer from an existing service ZLayer.succeedMany // to create a layer from a value that's one or more services ZLayer.fromFunction // to create a layer from a function from the requirement to the service ZLayer.fromEffect // to lift a ZIO effect to a layer requiring the effect environment ZLayer.fromAcquireRelease // for a layer based on resource acquisition/release. The idea is the same as ZManaged ZLayer.fromService // to build a layer from a service ZLayer.fromServices // to build a layer from a number of required services ZLayer.identity // to express the requirement for a layer ZIO#toLayer // or ZManaged#toLayer to construct a layer from an effect
最後に、ZLayerの使い方をみていきます。
ZLayerは++メソッドで水平に合成することができます。
val inMemory: ZLayer[Any, Nothing, UserRepo] = UserRepo.inMemory val consoleLogger: ZLayer[Console, Nothing, Logging] = Logging.consoleLogger val horizontal: ZLayer[Console, Nothing, Logging with UserRepo] = Logging.consoleLogger ++ inMemory
これはHasのところで見た形と似ていると思います。
実際にZLayerの++メソッドは内部でHasのunionメソッド、すなわち++メソッドを呼び出しています。
また、ZLayerを縦に合成することもできます。 つまり、1 つのレイヤーの出力を後続のレイヤーの入力として使用して次のレイヤーを構築することができます。
val horizontal: ZLayer[Console, Nothing, Logging with UserRepo] = Logging.consoleLogger ++ inMemory val console: ZLayer[Any, Nothing, Console] = Console.live val fullLayer: ZLayer[Any, Nothing, Logging with UserRepo] = console >>> horizontal makeUser.provideLayer(fullLayer)
このようにZLayerを使うことで、柔軟に環境の構築を行うことができます。 継承ベースの環境組み合わせから、ZLayerを用いて値ベースで環境を組み合わせになったことで柔軟に環境の構築・変更ができるようになりました。
まとめ
ZIOのデータ型であるZLayerを紹介しました。
参考
PlayFramework+GuiceでDIしているときに型クラスインスタンスでインジェクションされたクラスを使用する
PlayFrameworkでGuiceを使ってDIしているときに、 型クラスインスタンスでインジェクションされたクラスを使う方法を調べました。
以下のようなコードがあるとします。
// Factory.scala trait Factory[T] { def create: T } case class Type1() object Type1Factory { implicit object Type1Factory extend Factory[Type1] { override def create: Type1 = Type1() } } case class Type2(value: String) object Type2Factory { implicit object Type2Factory extend Factory[Type2] { // どうやってここに、type2Repositoryを渡せば良い？ override def create: Type2 = type2Repository.load() } }
// UseCase.scala class UseCase @Inject()(type2Repository: Type2Repository) { def create[T: Factory]: T = { // 共通処理 ... implicitly[Factory[T]].create } }
// Controller.scala class Controller @Inject()(usecase: UseCase) { import Factory._ def create1: Type1 = usecase.create() def create2: Type2 = usecase.create() }
Factoryというcreateというメソッドをもつ型クラスがあって、
その型クラスインスタンスとしてType1FactoryとType2Factoryが定義されています。
Type1Factoryはとくに他に依存しないcreateメソッドを持ちますが、
Type2Factoryのcreateメソッドでは、Type2Repositoryを使う必要があります。
Type2Repositoryはインタフェースで、他のところにDBからデータを取得する処理を行うType2RepositoryImplクラスが定義されています。
Type2RepositoryはGuiceでUseCaseクラスにInjectされます。
このとき、DI管理下のType2RepositoryのインスタンスをType2Factoryに渡す方法がわからず、困っていました。
Type2Repositoryが必要なのはType2Factoryだけなので、Factoryのメソッドの引数にType2Repositoryを渡したくありません。
型クラスインスタンスが増え、そのインスタンスが別のRepositoryを要求する場合、引数を追加していかなければならないためです。
良い方法が思いつかなくて悩んでいたところ、Twitterで教えていただきました。
Scalaは値に対して import が可能なので、無理に object に DI する方向よりも、型クラスインスタンスの定義をDI管理化のclass上で定義しておいて、DI した値に対して import して上げるほうが単純なコードにできるかと思います
— がくぞ (@gakuzzzz) February 17, 2020
値に対するimportでうまくいきそうです。以下が、改良版のコードになります。
// UseCase.scala class UseCase @Inject()(type2Repository: Type2Repository) { def create[T: Factory]: T = { // 共通処理 ... implicitly[Factory[T]].create } implicit val type1Factory: Factory[Type1] = new Factory[Type1] { override def create: Type1 = Type1() } implicit val Type2Factory: Factory[Type2] = new Factory[Type2] { override def create: Type2 = type2Repository.load() } }
// Controller.scala class Controller @Inject()(usecase: UseCase) { import usecase._ def create1: Type1 = usecase.create() def create2: Type2 = usecase.create() }
型クラスインスタンスをDI管理下のUseCaseクラスで定義することで、Type2Repositoryを呼び出すことができました。
また、先程はControllerクラスでimport Factory._で型クラスインスタンスをimportしていましたが、
scalaでは値に対してimportできるようなので、インジェクトされたUseCaseインスタンスに対してimportすることでimplicitが解決できるようになります。
社内の検索技術勉強会ふりかえり
これはただの集団 Advent Calendar 2019の16日目の記事です。
昨日はTapanさんのMonixの話でした。
最初はZIOについて書こうと思っていたのですが、 TapanさんのMonixの話と内容がほとんどおなじになってしまったので 社内で行っている検索技術勉強会について書くことにします。
概要
昨年2月頃から社内のエンジニアを中心に始めた勉強会です。 検索技術を勉強する機会を作るためにふわっとはじめました。 週一回お昼休みに集まって、ご飯を食べながら進めています。
メンバー
メンバーは開発チームのエンジニアがだいたい6名ほどで、 それ以外にAIチームの方が1名参加してくれています。 初期はもっと参加者がいましたが、このぐらいの人数で落ち着きました。
内容
はじめに取り組んだのは情報検索の基礎という有名な本です。
タイトルどおり情報検索の基礎を学ぶ上で外せない本です。 特に第1章〜第8章まではポスティングリストやTF-IDFなどの検索技術の基本的な概念・手法がつまっていて非常に勉強になりました。 それ以降の章に関してはどちらかというと機械学習の話になってきたので、 この本を使わずに機械学習に強いメンバーに独自で資料を作ってもらったりしました。 また、機械学習に関しては他の本で学んだほうが効率が良さそうだねということで、 第11章〜第18章は飛ばして読み、逆に第19〜第21章はウェブ検索についての章だったのでしっかり読みました。
この本は一番最初、全員で本を読みながらホワイトボードを使って議論するスタイルで進めていました。 このやり方はしっかり理解ができるという点では良かったのですが、あまりにも進みが遅かったためすぐに変えなければなりませんでした。 その後は、各章ごとに担当を割り振りスライドを作ってもらって発表する形式になり、結果的に進みは良くなりましたが、 自分の担当箇所以外の理解度が低くなってしまった印象があります。 例えば、ジグソー法などでもう少しうまく議論が発生する仕組みを取り入れてみても良かったかもしれません。
余談ですが、この本で学んだことをまとめた同人誌を技術書典7で販売しました。
情報検索の基礎を読み終わったので、現在はランク学習(Learning to Rank)に取り組んでいます。 ランク学習とは機械学習で文書の並びを予測する手法です。
この題材に関しては、なんと昨年のアドベントカレンダーで一人でランク学習についての記事を書かれている方がいたので、 この記事を読みながら少しづつすすめていっています。
また、同じ方が発表されたヤフーにおける機械学習検索ランキングの取り組みの資料も非常に参考になります。
上記の資料をもとに、ランク学習を用いた検索基盤を構築するのが目下の目標です。 情報検索の基礎は良かったのですが、あまり手を動かせておらずアウトプットが少なかったため、今回は モブプログラミングなどでメンバー全員でコードを書きながら進めてみようと思っています。
その後のことについては、やりたいことが多すぎて何をやるか決まっていません。 案としては以下のようなものが上がっています。
- ランク学習の本(Learning to Rank for Information Retrieval)を読む
- SIGIRで採択された論文を読む
- 情報検索のためのユーザインタフェースを読む
まとめ
ふりかえってみると、9ヶ月ほど続いている勉強会になっていました。 まだ検索技術の初歩的な部分しか触れていませんが、 なにより継続することが一番難しいと思うので、これからも続けていければと思います。
Go言語でフレーズ検索を実装してみる
この記事はただの集団 AdventCalendar PtW.2019の6日目の記事です。 昨日はumeneriさんのGKE上にElasticsearchとcerebro環境を構築するでした。
本記事では、Golangを使って検索エンジンのフレーズ検索機能を実装してみます。
フレーズ検索とは
文章の集合からダブルクォートでくくった文字に合致する部分を見つける検索です。
例えば、"エンジニア 東京"で検索するとエンジニア 東京というフレーズに合致するものだけを取得します。
エンジニアや東京だけに合致するものは結果に含みません。
検索エンジンはフレーズ検索を実現するだけでなく、効率的に処理する必要があります。
本記事では、フレーズ検索を行うためのアルゴリズムの実装を行います。
転置インデックス
一般的に、時間がかかるテキストの線形走査を避けるためには、事前に文書をインデックス付します。 ほとんどすべての情報検索エンジンでは、インデックスに転置インデックスを用います。
転置インデックスとは、簡単に言うと「用語とその用語の文書集合内の出現位置のマッピング」です。 転置インデックスは、文書集合内に含まれる用語のリストである辞書と各用語に紐づく出現位置のリストであるポスティングリストから構成されます。
今回は簡単のため、ポスティングリストにはその用語のテキスト集合内での出現位置の配列を持つようにします。 このようにポスティングリストに構造を持たないものをschema-independent-indexと呼びます。
package index // schema independent index type Index struct { Dictionary map[string][]int }
また、Indexを作成するメソッドも追加しておきます。
func NewIndex(dictionary map[string][]int) *Index { index := new(Index) index.Dictionary = dictionary return index }
準備
まず、今回実装する関数の説明をしておきます。 今回は以下の4つの関数を実装します。
next(t string, current int) int- 現在の位置(current)より後ろにある最初の用語tの場所を返す。
prev(t string, current int) int- 現在の位置(current)より前にある最初の用語tの場所を返す。
nextPhrase(phrase []string, current) (int, int)- 現在の位置(current)より後ろにある最初のフレーズ(phrase)の開始位置と終了位置を返す。
allPhrase(phrase []string, current) [][2]int- 現在の位置(current)より後ろにある全てのフレーズの開始位置と終了位置を返す。
アルゴリズムの実装の前にまずテストを書きましょう。
func TestNext(t *testing.T) { index := NewIndex(map[string][]int{ "大阪": {316669, 745434}, "営業": {36898, 137236, 745397, 745419, 1247139}, "エンジニア": {1598, 27555, 745407, 745429, 745451, 745467, 1245276}, "事務": {265197}, }) type test struct { t string current int expected int } testCases := []test{ {"エンジニア", 745429, 745451}, {"大阪", 345678, 745434}, {"エンジニア", 1245276, END_OF_FILE}, {"エンジニア", BEGINNING_OF_FILE, 1598}, {"エンジニア", END_OF_FILE, END_OF_FILE}, } for _, testCase := range testCases { actual := index.next(testCase.t, testCase.current) if actual != testCase.expected { t.Errorf("\n got: %v\n want: %v", actual, testCase.expected) } } } func TestPrev(t *testing.T) { index := NewIndex(map[string][]int{ "大阪": {316669, 745434}, "営業": {36898, 137236, 745397, 745419, 1247139}, "エンジニア": {1598, 27555, 745407, 745429, 745451, 745467, 1245276}, "事務": {265197}, }) type test struct { t string current int expected int } testCases := []test{ {"エンジニア", 745451, 745429}, {"大阪", 456789, 316669}, {"エンジニア", 1598, BEGINNING_OF_FILE}, {"エンジニア", END_OF_FILE, 1245276}, {"エンジニア", BEGINNING_OF_FILE, BEGINNING_OF_FILE}, } for _, testCase := range testCases { actual := index.prev(testCase.t, testCase.current) if actual != testCase.expected { t.Errorf("\n got: %v\n want: %v", actual, testCase.expected) } } } func TestNextPhrase(t *testing.T) { index := NewIndex(map[string][]int{ "東京": {2205, 2268, 745406, 745466, 745501, 1271487}, "エンジニア": {1598, 27555, 745407, 745429, 745451, 745467, 745502, 1245276}, }) type test struct { t []string current int expectedStart int expectedEnd int } testCases := []test{ {[]string{"東京", "エンジニア"}, BEGINNING_OF_FILE, 745406, 745407}, {[]string{"東京", "エンジニア"}, 745500, 745501, 745502}, } for _, testCase := range testCases { u, v := index.nextPhrase(testCase.t, testCase.current) if u != testCase.expectedStart || v != testCase.expectedEnd { t.Errorf("\n got: [%v, %v]\n want: [%v, %v]", u, v, testCase.expectedStart, testCase.expectedEnd) } } } func TestAllPhrase(t *testing.T) { index := NewIndex(map[string][]int{ "東京": {2205, 2268, 745406, 745466, 745501, 1271487}, "エンジニア": {1598, 27555, 745407, 745429, 745451, 745467, 745502, 1245276}, }) type test struct { t []string current int expected [][]int } testCases := []test{ {[]string{"東京", "エンジニア"}, BEGINNING_OF_FILE, [][]int{ {745406, 745407}, {745466, 745467}, {745501, 745502}, }, }, } for _, testCase := range testCases { results := index.allPhrase(testCase.t, testCase.current) for i, result := range results { if result[0] != testCase.expected[i][0] || result[1] != testCase.expected[i][1] { t.Errorf("\n got: %v\n want: %v", result, testCase.expected[i]) } } } }
実装
まず、現在位置の前後に最初に用語が出現する位置を返すnextとprevを実装します。
// next(t, current) returns the position of t's first occurrence after the current position func (index *Index) next(t string, current int) int { if postingList, ok := index.Dictionary[t]; !ok { return END_OF_FILE } else { for _, p := range postingList { if p > current { return p } } return END_OF_FILE } } // prev(t, current) returns the position of t's last occurrence before the current position func (index *Index) prev(t string, current int) int { if postingList, ok := index.Dictionary[t]; !ok { return BEGINNING_OF_FILE } else { for i := len(postingList) - 1; i >= 0; i-- { p := postingList[i] if p < current { return p } } return BEGINNING_OF_FILE } }
単に引数で渡された用語のポスティングリストをたどり、条件に合致するものを返します。 見つからない場合は、ファイルの開始や終了を表す定数(BEGINNING_OF_FILE, END_OF_FILE)を返しています。 簡単のため以下のように定義しておきます。
const (
BEGINNING_OF_FILE = -math.MaxInt32
END_OF_FILE = math.MaxInt32
)
それでは、実際にフレーズ検索を行う部分を実装します。
nextPhraseは現在の位置より後ろにあるフレーズを見つけ、その開始位置uと終了位置vを返す関数です。
func (index *Index) nextPhrase(phrase []string, current int) (int, int) { length := len(phrase) v := current for _, t := range phrase { v = index.next(t, v) } if v == END_OF_FILE { return END_OF_FILE, END_OF_FILE } u := v for i := length - 2; i >= 0; i-- { u = index.prev(phrase[i], u) } if v-u == length-1 { return u, v } else { return index.nextPhrase(phrase, u) } }
この関数は大まかに２つの処理に分けることができます。 まず、はじめに引数で渡された用語のリスト(phrase)の順に用語が出現している箇所を探索します。
v := current
for _, t := range phrase {
v = index.next(t, v)
}
if v == END_OF_FILE {
return END_OF_FILE, END_OF_FILE
}
現在の位置からフレーズに含まれる用語の順にnextを呼び出し、フレーズの最後尾の用語の位置を割り出します。 これにより、フレーズに含まれる用語(t1,t2....,tn)が文書中にこの順で出現していることが明らかになりました。 ここで、文書内にフレーズ内の用語が文書中に順番通り含まれていなければ、そのフレーズは見つからなかったとして探索を終了します。
次に、それらの用語の出現箇所が隣接しているかをチェックします。
u := v
for i := length - 2; i >= 0; i-- {
u = index.prev(phrase[i], u)
}
if v-u == length-1 {
return u, v
} else {
return index.nextPhrase(phrase, u)
}
フレーズ最後尾の用語の位置からフレーズに含まれる用語の逆順にprevを呼び出し、フレーズの開始位置uを特定します。 uが特定できたらu,vの距離を計算し、その長さがフレーズの長さと一致していれば、検索できたのでその位置を返します。 長さが異なっていれば、現在位置を更新して再度nextPhraseを呼び出します。このようにしてフレーズが見つかるまで探索します。
すべてのフレーズを検索するには単にnextPhraseを文書集合の末尾に到達するまで開始位置uを更新しながらforでまわします。
func (index *Index) allPhrase(phrase []string, current int) [][2]int { var results [][2]int var u,v int u = current for u < END_OF_FILE { u, v = index.nextPhrase(phrase, u) if u != END_OF_FILE { results = append(results, [2]int{u, v}) } } return results }
以上が、フレーズ検索の実装になります。
まとめ
全文検索エンジンのフレーズ検索機能をGo言語で実装してみました。 今回実装したnextやprevメソッドはポスティングリストをたどるのに単にループしてしまっていますが、 キャッシュやbinary searchなどを使用して計算量を改善することができます。
参考
Godogの実装を見てみる
この記事はただの集団 Advent Calendar 2018の23日目の記事です。
昨日は hajimeniさんのプログラム上で時間を扱う際に気をつけることでした。
Advent Calendarもいよいよ終りが見えてきました。
本記事では、GolangでATTDを実践するためのツールであるGodogがどのように動いているかを探ってみます。
TL;DR
- Godogはコマンド実行時にファイルを読み込んでテスト用のソースコードを生成し、それをコンパイルしたものを実行している
go/buildやgo/parser、go/astなどのパッケージを活用してソースコードを解析して、対象となるstep関数を見つけ出している
はじめに
GodogとはCucurmberのGolang版です。GithubのCucumberのリポジトリには存在しませんが、 Cucurmberチームの開発メンバーがメンテナンスしているようなので安心して使って良いと思われます。
Godogは以下のような自然言語で書かれたfeatureファイルと、それに対応するstepファイルを記述しgodogコマンドを実行することでテストが実行されます。
Feature: eat godogs
In order to be happy
As a hungry gopher
I need to be able to eat godogs
Scenario: Eat 5 out of 12
Given there are 12 godogs
When I eat 5
Then there should be 7 remaining
package main import ( "github.com/DATA-DOG/godog" ) func thereAreGodogs(arg1 int) error { return godog.ErrPending } func iEat(arg1 int) error { return godog.ErrPending } func thereShouldBeRemaining(arg1 int) error { return godog.ErrPending } func FeatureContext(s *godog.Suite) { s.Step(`^there are (\d+) godogs$`, thereAreGodogs) s.Step(`^I eat (\d+)$`, iEat) s.Step(`^there should be (\d+) remaining$`, thereShouldBeRemaining) }
godogコマンドが実行されたときにどのようにしてこれらのテストが実施されるのでしょうか？ godogコマンドはどのようにしてstepファイルを認識しているのでしょうか？ これらの疑問を解消するため、実際にgodogのコードを見てみることにしました。
Godogの動き
call graphは以下のようになっています。今回着目する箇所は印がついている部分になります。
ちなみに、こちらはgo-callvisを使って出力しました。
main
godogを実行するとはじめに、cmd/godog/main.goのmainが呼び出されます。
https://github.com/DATA-DOG/godog/blob/master/cmd/godog/main.go#L61-L105
package main ... func main() { (省略) status, err := buildAndRun() // ここからスタート if err != nil { fmt.Fprintln(os.Stderr, err) os.Exit(1) } // it might be a case, that status might not be resolved // in some OSes. this is attempt to parse it from stderr if parsedStatus > status { status = parsedStatus } os.Exit(status) }
mainでは、引数のParseなどを行ったあと、同じファイル内のbuildAndRun関数を呼び出しています。
buildAndRun
https://github.com/DATA-DOG/godog/blob/master/cmd/godog/main.go#L17-L59
package main ... var parsedStatus int func buildAndRun() (int, error) { var status int bin, err := filepath.Abs("godog.test") if err != nil { return 1, err } if build.Default.GOOS == "windows" { bin += ".exe" } if err = godog.Build(bin); err != nil { // テストの実行ファイルをビルド return 1, err } defer os.Remove(bin) // 処理が終わったら実行ファイルを削除 cmd := exec.Command(bin, os.Args[1:]...) cmd.Stdout = os.Stdout cmd.Stderr = os.Stderr cmd.Stdin = os.Stdin cmd.Env = os.Environ() if err = cmd.Start(); err != nil { // テストを実行 return status, err } (省略) }
buildAndRunの中で行っていることはgodog.testという実行ファイルをgodog.Buildで生成し、
それをexec.Commandで実行するということです。
どうやら、godogコマンドを実行すると直接テストが走るのではなく、 テスト用の実行ファイルをビルドしそれを実行することで テストが動くという仕組みになっているようです。
では、Buildの中の処理を追っていきます。
Build(前半)
https://github.com/DATA-DOG/godog/blob/master/builder.go#L48-L219
Buildの中で最初に重要なのは以下の部分です。
func Build(bin string) error { abs, err := filepath.Abs(".") // (1) if err != nil { return err } // we allow package to be nil, if godog is run only when // there is a feature file in empty directory pkg := importPackage(abs) // (2) src, anyContexts, err := buildTestMain(pkg) // (3) if err != nil { return err } ... }
はじめに、(1)のfilepah.Abs(".")でカレントディレクトリの絶対パスを取得しています。
次に(2)で、 同じファイル内のimportPackageを呼び出しています。
importPackageではgo/buildパッケージのImportDirメソッドを呼び出すことで、
指定したディレクトリ以下のGoファイルを調べ、goのパッケージ情報を抽出しています。
返り値は以下のような情報を持つPackageの構造体へのポインタです。
https://golang.org/pkg/go/build/#Package
type Package struct { Dir string // directory containing package sources Name string // package name ... // Source files GoFiles []string // .go source files (excluding CgoFiles, TestGoFiles, XTestGoFiles) ... Imports []string // import paths from GoFiles, CgoFiles ImportPos map[string][]token.Position // line information for Imports // Test information TestGoFiles []string // _test.go files in package TestImports []string // import paths from TestGoFiles ... XTestGoFiles []string // _test.go files outside package XTestImports []string // import paths from XTestGoFiles ... }
その後(3)で、抽出したパッケージ情報をbuildTestMain関数の引数として呼び出しています。
buildTestMain(前半)
https://github.com/DATA-DOG/godog/blob/master/builder.go#L272-L303
buildTetMain関数ではtestのmainとなるソースコードを生成します。
ここで生成されたコードがコンパイルされexec.Commandで実行されることでgodogは動いています。
func buildTestMain(pkg *build.Package) ([]byte, bool, error) { var contexts []string var importPath string name := "main" if nil != pkg { ctxs, err := processPackageTestFiles( // (1) pkg.TestGoFiles, pkg.XTestGoFiles, ) if err != nil { return nil, false, err } contexts = ctxs importPath = pkg.ImportPath name = pkg.Name } ... }
buildTetMainの前半で重要なのは(1)の箇所です。
受け取ったパッケージ情報の中から、godog_test.goのようなテストファイル
の名前をprocessPackageTestFilesに渡します。
processPackageTestFiles
https://github.com/DATA-DOG/godog/blob/master/builder.go#L322-L347
processPackageTestFilesでは、受け取ったファイル名を
go/parseのParseFileメソッド
に渡してASTを生成します (1)。
その後、生成したASTをastContextsに渡しメソッド名を抽出します (2)。
// processPackageTestFiles runs through ast of each test // file pack and looks for godog suite contexts to register // on run func processPackageTestFiles(packs ...[]string) ([]string, error) { var ctxs []string fset := token.NewFileSet() for _, pack := range packs { for _, testFile := range pack { node, err := parser.ParseFile(fset, testFile, nil, 0) // (1) if err != nil { return ctxs, err } ctxs = append(ctxs, astContexts(node)...) // (2) } } ... }
astContexts
https://github.com/DATA-DOG/godog/blob/master/ast.go
astContextsでは、受け取ったASTを解析して、
func (*godog.Suite)型の関数が存在していたら、その関数名を返します。
というわけでgodogがどうやって処理する関数を見つけ出しているかは、ここにかかれていました。
func astContexts(f *ast.File) []string { var contexts []string for _, d := range f.Decls { switch fun := d.(type) { case *ast.FuncDecl: for _, param := range fun.Type.Params.List { switch expr := param.Type.(type) { case *ast.StarExpr: switch x := expr.X.(type) { case *ast.Ident: if x.Name == "Suite" { contexts = append(contexts, fun.Name.Name) } case *ast.SelectorExpr: switch t := x.X.(type) { case *ast.Ident: if t.Name == "godog" && x.Sel.Name == "Suite" { contexts = append(contexts, fun.Name.Name) } } } } } } } return contexts }
buildTestMain(後半)
https://github.com/DATA-DOG/godog/blob/master/builder.go#L292-L303
processPackageTestFilesの処理が終わったら、buildTestMainに戻ります。
if nil != pkg {
ctxs, err := processPackageTestFiles(
pkg.TestGoFiles,
pkg.XTestGoFiles,
)
...
data := struct {
Name string
Contexts []string
ImportPath string
}{name, contexts, importPath}
var buf bytes.Buffer
if err := runnerTemplate.Execute(&buf, data); err != nil { // (1)
return nil, len(contexts) > 0, err
}
return buf.Bytes(), len(contexts) > 0, nil
buildTestMainでは、テンプレートにimportPackageやprocessPackageTestFilesで抽出した情報を埋め込み、
testのmainとなるソースコードを生成します。
templateは以下のようになっており、
main関数を持つgoのファイルを生成していることがわかります。
https://github.com/DATA-DOG/godog/blob/master/builder.go#L30-L46
var runnerTemplate = template.Must(template.New("testmain").Parse(`package main import ( "github.com/DATA-DOG/godog" {{if .Contexts}}_test "{{.ImportPath}}"{{end}} "os" ) func main() { status := godog.Run("{{ .Name }}", func (suite *godog.Suite) { os.Setenv("GODOG_TESTED_PACKAGE", "{{.ImportPath}}") {{range .Contexts}} _test.{{ . }}(suite) {{end}} }) os.Exit(status) }`))
実際にgodogのテストを実行するのはgodog.Run()の部分です。
godog.Run()の内部ではこれまでの処理で発見した、ステップ関数の実行を行う処理が書かれています。
ここまでで、ようやくbuildTestMainの処理が完了し、実行すべきtestmainのソースコードが得られました。
Build(後半)
最後にBuild関数で得られたソースコードをコンパイルします。
exec.Command(compiler, args...)(1)やexec.Command(linker, args...)(2)を実行して
コンパイルが行われていることが確認できます。
func Build(bin string) error { (省略) src, anyContexts, err := buildTestMain(pkg) if err != nil { return err } (省略) args = append(args, "-pack", testmain) cmd = exec.Command(compiler, args...) // (1) cmd.Env = os.Environ() out, err = cmd.CombinedOutput() if err != nil { return fmt.Errorf("failed to compile testmain package: %v - output: %s", err, string(out)) } // link test suite executable args = []string{ "-o", bin, "-buildmode=exe", } for _, link := range pkgDirs { args = append(args, "-L", link) } args = append(args, testMainPkgOut) cmd = exec.Command(linker, args...) // (2) cmd.Env = os.Environ() out, err = cmd.CombinedOutput() if err != nil { msg := `failed to link test executable: reason: %s command: %s` return fmt.Errorf(msg, string(out), linker+" '"+strings.Join(args, "' '")+"'") } return nil }
まとめ
Godogがどのように実行されるかを理解するために実装を見てみました。
最初はGodogの使い方を解説する記事にしようとしていたのに、
いつのまにかGodogの内部の処理を追ってしまっていましたが、
go/buildやgo/astなど普段はあまり使わない
パッケージの使い方を知ることができてよかったです。
TDDをやっていて学んだこと
最近、TDDを会社でやっているので、学んだことをまとめておく。
学んだこと
TDDでは、まずテストを書き実行する。するとエラーになるので、すぐさまテストを通るようにコードを実装する。 テストが通るようになったら、リファクタリングをする。そしてまたテストを書く。このようにしてRed->Green->Refactoring繰り返す。
テストを書きRedの状態になったらすぐに、Greenになるようにコードを実装する。その際、コードを一般化して書こうとしないように気をつける。 とにかく一秒でも早くGreenにする。たとえば文字列を返すメソッドで
"a"という文字列が返ってくることをテストで期待する場合は、return "a"だけを実装する。 その後、別のテストを追加し、両方のテストが通るように実装を変更する。設計はrefactoringのフェーズでおこなう。必ずテストがリファクタリングの前後で通っている状態になっているはず。
なにか迷ったらすぐにテストを実行する。答えはテスト結果に書いている。とにかく細かくテストを回す。
テストを何度も実行するので、テストの実行に時間がかかると効率が落ちる。Scalaだとsbtを起動するのに時間がかかるのでsbtは常に起動しておく。
感想
- テストが整備されていないコードで途中からTDDをやるのは辛い、テストを書くのに時間がかかってしまう。
- テンポよくリズムに乗って開発するには、そもそもその言語に習熟している必要がありそう。逆に言語の習熟度が上がるほど効率よく開発できそう。
- TDDが良いと思ったのは、余計なことを考えずに手を動かせるところ。いつも先に設計を考えてしまってコードを書くのに時間がかかってしまっていたが、先にコードを書いてから設計を考えるほうが短い時間で効率的に実装できる気がする。
