たにしきんぐダム

プログラミングやったりゲームしてます

Coursera の Algorithms on Strings 受けました

Cousera の Algorithms on Strings を受講していて、平日にお昼ご飯食べながらビデオを見たり休日とかに課題をやったりしていたのですが先日完走しました!(講義は4週分なのですが忙しかったり難しかったりで2ヶ月くらいかかってしまった)
お金を払うと課題提出システムみたいなのが使えて提出したプログラムの時間/空間計算量を教えてくれるらしいけど無料でも授業ビデオと資料にはアクセスできた
めちゃくちゃ良かったのでみんなも受講しましょう

www.coursera.org

きっかけはアルバイト先で開催されていたのに参加させてもらったのと、 ISUCON6予選で高速な文字列マッチングアルゴリズムが全く分からず悔しい思いをしたから(正規表現の更新・キャッシュをうまく頑張れば十分な点数は獲得できたみたいですが...)でした。
学んで終わりじゃ多分忘れるから何とか応用とかできたら良い

授業ビデオは例を交えて教えてくれたり定理を証明してくれたりクイズが挟まったり(前半の)先生のテンションが異常に高かったりして楽しかったし分かりやすかったので受講しましょう

文句を言うならWeek4は先生がひたすらスライド数枚で定理と証明を延々と喋ったあとアルゴリズムはこれだよってスライドが何枚か出てきただけだったのはめちゃくちゃ分かりにくかったのでもっと例が欲しかった。Couseraのフォームから意見を送ったりした、評価-1したりした...
(授業ビデオに対して気軽にLike/Dislikeしたり意見を送信できるシステムがあるのは凄く良いですね)


以下は授業メモを清書したもの、ブログ書くつもりで授業受けると他の人も読むのでしっかり整理する必要があって理解が深まるという知見が!
この記事頑張りすぎたので次からはもう少し手を抜きたい

  • ちまちま書いてたらめちゃくちゃ長くなってしまったので読むとしたら辞書的に使うのが良さそう
  • この記事にはプログラムは掲載していません
  • この記事では詳細なアルゴリズムなどは書いていません(調べれば/受講すれば出てくる)、アルゴリズム・データ構造の具体例くらいの気持ち
  • この記事を読んで各アルゴリズムの雰囲気を掴んでもらって、詳しく知りたい場合はCoursera受けてみてください
  • Week1
    • BruteForce
    • Trie
    • Suffix Trie
    • Suffix Tree
  • Week2
  • Week3
    • ShiftingPatterns
    • PrefixFunction
    • Knuth–Morris–Pratt algorithm
  • Week4
    • Construct Suffix Array (Manber & Myers)
    • Construct LCP Array
      • kasai’s Algorithm
    • Suffix Array + LCP Array -> Suffix Tree
  • おわりに
続きを読む

JS知識ほぼ0からTypeScript入門してる

この記事は CAMPHOR- Advent Calendar 2016 23日目の記事です。
JS知識ほぼ0は言い過ぎかもしれないが、いわゆるモダンJSというものには縁遠く、つい最近まで jQuery をブラウザからぽちぽちダウンロードして適当に ajax とか使う人生を送ってまいりました。(当然フレームワークとか使ったことない)

まさしくこの記事みたいな状況

kikuchi1201.hateblo.jp

最近 TypeScript を書く機会があって、開発環境は用意されてるのでなんとなく書けるけど、エコシステムとかいろいろ全くわかってなくてこのまま旧石器時代然としたJavaScriptを書いていてはまずい気がすると思って勉強することにしました。

目標は TypeScript を使ってこんなんを作る、テストも書こうね(こんなのに何をテストするんだ)
この記事では主に環境構築~DOM操作のテストまでをやっていてTypeScriptの文法みたいな話はしません

https://gyazo.com/ac3e0137e71e2ef475c685185fdcd06f

  • npm とか node のバージョンを管理
  • npm でパッケージ管理をする
    • プロジェクトごとにパッケージ管理
  • TypeScript
    • 開発環境
  • tsconfig.json
  • 外部モジュールをTypeScriptから使う
  • 実際にTypeScriptプログラムを書く
  • CommonJS
  • browserify
  • gulp
  • テスト
    • 環境構築
    • HTML断片を読んでDOM操作のテスト
  • npm script からテストなどを呼び出す
  • 感想
  • 参考
続きを読む

WartRemover で Scala を静的解析

この記事は CAMPHOR- Advent Calendar 2016 7日目の記事です。

WartRemoverScala のASTレベルの静的解析ツールで、WartRemover に組み込まれているパターンに加えて、自分で定義したパターンをビルド時に検出することができます。
これを使えばscalacはエラーや警告を出さないけど検出してほしいコーディング規約などをビルド時に検出することができるようになって便利。

github.com

もとから組み込まれてるパターンはGitHubのREADMEに詳しく書かれています。

使ってみる

詳しくは GitHubREADME を参照。

project/plugins.sbt に以下を追記

addSbtPlugin("org.wartremover" % "sbt-wartremover" % wartremoverVersion)

build.sbt に以下を追記

wartremoverErrors ++= Warts.all

これだけでビルド時にビルド対象のscalaプログラムを見て、すべてのパターンにマッチするASTを探索し、マッチしたパターンをエラーとして出力してくれるようになります、簡単ですね。

上の例だとすべてのプログラムに対して、すべてのパターンを検出しますが

  • 特定ファイルは検出対象から外す
  • 一部のパターンのみ/一部のパターンを除いてすべてのパターンを検出
  • あるパターンはエラー、あるパターンは警告を出すようにする

などのことが build.sbt に記述するだけでシュッとできるようになります。
詳しい設定方法はREADMEを(ry

カスタム Wart を作ってみる

ここ を見ると wart rule を自分で追加できるようです。

今回は HOGE_HOGE みたいな全部大文字とアンスコのみの変数名を見つけてみます。
Scala の定数は 公式のscala code styleUpperCamel だよって言われているのですが、僕はよくミスって LIMIT みたいな定数名を作ってしまうし、scalac も scalastyle も warning を出さないからです。(もしかして僕の設定が足りてないだけ?)(まあそこは本題じゃないし)

完成したものはこちら

github.com

WartRemoverはscalaのASTとのマッチングによって検出を行うので、まずは val HOGE = 1 みたいなプログラムがどういう AST になるのか確認しましょう。

scala> import scala.reflect.runtime.universe
import scala.reflect.runtime.universe

scala> universe.showRaw(universe.reify { val HOGE = 1 }.tree)
res1: String = Block(
List(ValDef(Modifiers(), TermName("HOGE"), TypeTree(), Literal(Constant(1)))),
Literal(Constant(())))

なんとなく ValDef(Modifiers(), TermName(), TypeTree(), Litenarl()) にマッチさせてやれば良いことがわかりますね。
(Modifiers には final private みたいな修飾子 が入ります。TypeTree はよく分からない...)

ちなみにScalaのリフレクションを使った構文木へのアクセスは公式ドキュメントが詳しい

概要

よっしゃ、それでは ValDef(Modifiers(), TermName(), TypeTree(), Litenarl()) のうち TermName が全部大文字かアンスコだけな構文木にマッチしてくれるwartを書いていきましょう!
ディレクトリ構成はこんな感じ、LargeValueName.scala は wartルールを記述するプログラム、wartsは別プロジェクトとして管理しています。

.
├── build.sbt
├── project
│   ├── build.properties
│   └── plugins.sbt
├── src/main/scala/Main.scala
└── warts
    └── src/main/scala/LargeValueName.scala

LargeValueName.scala

自分で wart を作るときはだいたい以下のような必要があります。

  • wart object は WartTraverser を継承
  • def apply(u: WartUniverse): u.Traverser のみをメソッドとして持ち
    • WartUniversereflect.api.Universe を内部にもつ
  • apply が返す Traversertraverse(tree: Tree): Unit を override
    • 引数として与えられたASTと、検出したいパターンとのマッチングさせる
package warts

import org.wartremover.{WartTraverser, WartUniverse}

object LargeValueName extends WartTraverser {
  def apply(u: WartUniverse): u.Traverser = {
    import u.universe._

    new Traverser {
      override def traverse(tree: Tree) {
        tree match {
          case t @ ValDef(_, TermName(s), _, _)
            if s.trim.matches("[A-Z_]+") =>
            u.error(tree.pos, s"Value name $s should be upper/lower camel case")
            // 他のwartもチェックするかもしれないので super.traverse を呼ぶ
            super.traverse(tree)
          case _ =>
            super.traverse(tree)
        }
      }
    }
  }
}

build.sbt

それじゃあこれを build.sbt に登録してみます、今回は LargeValueName.scala は sbt のマルチプロジェクトを使ってメインプロジェクトとは別で管理します。

  • wartremoverClasspaths にカスタム wart の classpath を追加
  • wartremoverWarnings += Wart.custom("your.own.wart")

build.sbt はこんな感じ、

val wartremoverVersion = "1.2.1"
val customWartProjectName = "MyWarts"

lazy val commonSettings = Seq(
  scalaVersion := "2.11.8"
)

lazy val root = (project in file(".")).
  settings(commonSettings: _*).
  dependsOn(warts).
  settings(
    name := "wartremoverPlayground",
    version := "1.0",
    // warts project の jar ファイルが欲しい
    // wartremoverClasspaths += 
    //   "file://" + baseDirectory.value + "/warts/target/scala-2.11/mywarts_2.11-1.0.jar",
    wartremoverClasspaths ++= {
       // lazy val warts = ... settings( exportJars := true) と
       // dependsOn(warts) により dependencyClasspath in Compile に上記のjarが追加されてるはず
      (dependencyClasspath in Compile).value.files
        .find(_.name.contains(customWartProjectName.toLowerCase()))
        .map(_.toURI.toString)
        .toList
    },
    wartremoverWarnings += Wart.custom("warts.LargeValueName")
  )

lazy val warts = (project in file("warts")).
  settings(commonSettings: _*).
  settings(
    name := customWartProjectName,
    version := "1.0",
    exportJars := true,
    libraryDependencies ++= Seq(
      "org.wartremover" %% "wartremover" % wartremoverVersion
    )
  )

warts project に移動して jar ファイルをいちいち生成して、頑張ってjarへのpathを渡しても動くのですが大変、自動化したすぎます。

wartremoverClasspaths += "file://" + baseDirectory.value + "/warts/target/scala-2.11/mywarts_2.11-1.0.jar"

この部分で、wartsプロジェクトの生成したjarファイルを見つけています。

wartremoverClasspaths ++= {
  (dependencyClasspath in Compile).value.files
     .find(_.name.contains(customWartProjectName.toLowerCase()))
     .map(_.toURI.toString)
     .toList
}

動かしてみる

Main.scala

package playground

object Main {
  val LIMIT = 1
}

これで sbt compile すると

[warn] /path/to/Main.scala:4: Value name LIMIT should be upper/lower camel case
[warn]   val LIMIT = 1

おお、警告出してくれた!
これを使って、簡単にパターンとして記述できるコーディング規約などは静的解析で検出してくれると良いですね!

明日は id:ryota-ka の「 Vim script でジェネレータを作ったり、遅延評価してみる」です。

参考

Scala関西勉強会でscala.Eitherとscalaz.\/の違いを話してきた

Scala関西勉強会で scala.Eitherscalaz.\/ の違いについて話してきました!
connpass.com

この話題、ブログとか漁ってみると3年前あたりに活発に議論されてる話だった...
僕自身for式の中でパターンマッチさせようとしてハマったものの(僕の検索能力の低さもあるけど)それを解説している記事にぶつかるまで時間がかかってしまったので、これについて解説する記事が一つでも増えると良いなーと思って発表しました。

考え事

\/単位元も定義されてる\/-(Monoid[B].zero)

https://github.com/scalaz/scalaz/blob/series/7.3.x/core/src/main/scala/scalaz/Either.scala#L411-L418

-\/(Monoid[A].zero)じゃないのかーって思ったけど、+++の実装を見てみると確かに\/-(Monoid[B].zero)\/appendについての単位元になってるなぁ@@

https://github.com/scalaz/scalaz/blob/series/7.3.x/core/src/main/scala/scalaz/Either.scala#L230-L238


今回の勉強会、バリュエーション豊かで基礎から応用まで幅広い内容のセッションがあってすごく良かった!
会場提供のエムオーテックス株式会社様、主催の@aa7thさん、@ryu1_okdさん、ありがとうございました!

参考

余談

発表中両手あげてバンザイして全身で\/を表現したりしてた

また参加します!

空間インデックス(R-tree)入門

R-treeとは空間データを効率良く検索するためのインデックス構造。R-tree について調べたのまとめておく。

目次

  • 目次
  • 参考資料
  • ナイーブな例
  • R-tree の概要
  • 参照処理
    • 点検索
    • 範囲検索
  • データの挿入・削除
    • 挿入処理
    • ノードの分割
      • Exhaustive Algorithm
      • Quadratic-Cost Algorithm
      • Linear-Cost Algorithm
    • 削除
    • 更新処理
  • まとめ

参考資料

続きを読む