Scala: Tackling with sbt-assembly

Scala: sbt-assembly を使う

Scala プロジェクト全体の jar ファイルを作るツールは色々あるが
ここ最近は sbt-assembly がデファクトスタンダードの座を確立したという感が強い。

導入

• project/assembly.sbt の作成
  

  README に従い、以下の内容をのファイルを project/assembly.sbt として保存する。

  addSbtPlugin("com.eed3si9n" % "sbt-assembly" % "0.11.2")

• Build.scala の編集
  

  build.sbt ではなく project/Build.scala に sbt の設定を書く場合の例。
  インポート文を以下のように書き、Project の settings に assemblySettings を追加する。

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46

  import sbt._ import sbt.Keys._ import sbtassembly.Plugin._ import AssemblyKeys._   object Build extends Build {   lazy val buildSettings = Seq(     organization := "your.organization",     version := "0.1.0",     scalaVersion := "2.11.2",     scalacOptions ++= Seq(       "-encoding", "utf-8",       "-target:jvm-1.7",       "-deprecation",       "-unchecked",       "-Xlint",       "-feature"     ),     javacOptions ++= Seq(       "-encoding", "utf-8",       "-source", "1.7",       "-target", "1.7"     )   )     lazy val dependencySettings = Seq(     resolvers ++= Seq(       // your resolvers     ),     libraryDependencies ++= Seq(       // your library dependencies     )   )     // configure prompt to show current project   override lazy val settings = super.settings :+ {     shellPrompt := { s => s"${Project.extract(s).currentProject.id}> " }   }     lazy val root = Project(     id = "projectname",     base = file("."),     settings = super.settings ++ buildSettings ++       dependencySettings ++ assemblySettings   ) }

  プロンプト文字列を変える設定は、spray/Build.scala at master · spray/spray から拝借した。

実行

sbt プロンプトの中で assembly と打つだけ。

projectname> assembly

OS のシェルから実行する場合は

$ sbt assembly

target/scala-X.X/projectname-assembly-X.X.X.jar が作成される。

jar ファイルの実行例

$ java $JAVA_OPTIONS -jar target/scala-X.X/projectname-assembly-X.X.X.jar

 

コンフリクトの解決

sbt-assembly に限らないが、jar 作成にあたって大半の時間は「依存関係スパゲッティ」との格闘に奪われる。

application.conf

例えば、複数プロジェクトでそれぞれ別の application.conf を利用している場合、デフォルトでは以下のようなエラーが出る。

java.lang.RuntimeException: deduplicate: different file contents found in the following: application.conf application.conf         at sbtassembly.Plugin$Assembly$.sbtassembly$Plugin$Assembly$$applyStrategy$1(Plugin.scala:253)         at sbtassembly.Plugin$Assembly$$anonfun$15.apply(Plugin.scala:270)         at sbtassembly.Plugin$Assembly$$anonfun$15.apply(Plugin.scala:267)   *snip*   [error] (projectname/*:assembly) deduplicate: different file contents found in the following: [error] application.conf [error] application.conf

この場合、適切な mergeStrategy を作りこむ必要がある。

例えば、以下のように。
MergeStrategy.concat を指定すれば、application.conf という名前のファイルはその内容が全て結合される。

1 2 3 4 5 6 7 8 9 10 11 12 13 14

lazy val assemblyAdditionalSettings = Seq(   mergeStrategy in assembly ~= { (old) => {     case "application.conf" => MergeStrategy.concat     case x => old(x)   }   } )   lazy val root = Project(   id = "projectname",   base = file("."),   settings = super.settings ++ buildSettings ++     dependencySettings ++ assemblySettings ++ assemblyAdditionalSettings )

同様のファイルが複数あるなら、以下のように指定すればよい。

case "application.conf" | "settings.conf" => MergeStrategy.concat

 

slf4j + logback

例えば、libraryDependencies に以下のように記述すると、assembly 実行時に class ファイルのコンフリクトが発生する。

"ch.qos.logback" % "logback-classic" % "1.1.2", "org.slf4j" % "slf4j-simple" % "1.7.7", "org.slf4j" % "slf4j-api" % "1.7.7", "org.slf4j" % "slf4j-ext" % "1.7.7",

[error] (projectname/*:assembly) deduplicate: different file contents found in the following: [error] /Users/xxxxxx/.ivy2/cache/ch.qos.logback/logback-classic/jars/logback-classic-1.1.2.jar:org/slf4j/impl/StaticLoggerBinder.class [error] /Users/xxxxxx/.ivy2/cache/org.slf4j/slf4j-simple/jars/slf4j-simple-1.7.7.jar:org/slf4j/impl/StaticLoggerBinder.class

• そもそも、必要なライブラリは何かを確認
  

  上記の例の場合、そもそも logback-classic と slf4j-simple を両方使っているのが間違い。
  slf4j-simple の記述を消せばよい。 => 参考

• 依存ライブラリの除外設定
  

  複数のライブラリが、バージョンの異なる同じライブラリに依存している場合、libraryDependencies に exclude を指定する。

  Exclude specific transitive deps

  libraryDependencies ++= Seq(   ("org.apache.spark" %% "spark-core" % "0.8.0-incubating").     exclude("org.mortbay.jetty", "servlet-api").     exclude("commons-beanutils", "commons-beanutils-core").     exclude("commons-collections", "commons-collections").     exclude("commons-collections", "commons-collections").     exclude("com.esotericsoftware.minlog", "minlog") )

• それでもダメなら、mergeStrategy に手を付ける
  

  パスに対してパターンマッチを適用し、適切なマージ方法を設定。

  Merge Strategy

  mergeStrategy in assembly <   {     case PathList("javax", "servlet", xs @ _*)         => MergeStrategy.first     case PathList(ps @ _*) if ps.last endsWith ".html" => MergeStrategy.first     case "application.conf" => MergeStrategy.concat     case "unwanted.txt"     => MergeStrategy.discard     case x => old(x)   } }

 

その他の便利設定

テスト中は assembly を無効に

test in assembly := {}

エントリポイントの指定

明示したほうが可読性が上がりそう。

mainClass in assembly := Some("your.app.Boot")

scala-library を含めない

jar ファイルをダイエットさせたい場合。

assemblyOption in assembly ~= { _.copy(includeScala = false) }

ただ scala-library.jar 自体は 6MB 程度しかないので、含めておいたとしてもそんなに気にならないと思う。

最終的にはこのような形になった。

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56

import sbt._ import sbt.Keys._ import sbtassembly.Plugin._ import AssemblyKeys._    object Build extends Build {   lazy val buildSettings = Seq(     organization := "your.organization",     version := "0.1.0",     scalaVersion := "2.11.2",     scalacOptions ++= Seq(       "-encoding", "utf-8",       "-target:jvm-1.7",       "-deprecation",       "-unchecked",       "-Xlint",       "-feature"     ),     javacOptions ++= Seq(       "-encoding", "utf-8",       "-source", "1.7",       "-target", "1.7"     )   )      lazy val dependencySettings = Seq(     resolvers ++= Seq(       // your resolvers     ),     libraryDependencies ++= Seq(       // your library dependencies     )   )     lazy val assemblyAdditionalSettings = Seq(     test in assembly := {},     mainClass in assembly := Some("your.app.Boot"),     mergeStrategy in assembly ~= { (old) => {       case "application.conf" => MergeStrategy.concat       case x => old(x)     }     }   )     // configure prompt to show current project   override lazy val settings = super.settings :+ {     shellPrompt := { s => s"${Project.extract(s).currentProject.id}> " }   }      lazy val root = Project(     id = "projectname",     base = file("."),     settings = super.settings ++ buildSettings ++       dependencySettings ++ assemblySettings ++ assemblyAdditionalSettings   ) }

Top N Sorter in Scala

Scala: トップNソートの実装

 

比較可能な大きな集合 $M$ に対して上位 $N$ 件のソート結果を取得したい。

この局面では一般にヒープソートが有効なので、PriorityQueue を使ってみる。

 

1 2 3 4 5 6 7 8 9 10 11 12

import scala.collection.mutable.PriorityQueue   class TopNSorter[A](n: Int)(ord: Ordering[A]) {   private[this] val data = PriorityQueue()(ord.reverse)     def insert(item: A): Unit = {     data += item     if (data.size > n) data.dequeue   }     def result(): Seq[A] = data.dequeueAll.reverse }

insert は $O(\log N)$ になるはず。(要素の追加は $O(\log N)$, サイズ取得と先頭要素へのアクセスは$O(1)$)
$M$ 件挿入すれば $O(M\log N)$。
result は $O(N)$ だが、$N$ が小さい前提なので問題ない。

1 2 3 4 5 6 7

scala> val x = new TopNSorter[Int](100)(Ordering.Int) x: TopNSorter[Int] = TopNSorter@520f1862   scala> (1 to 10000000) foreach x.insert   scala> x.result res1: Seq[Int] = Vector(10000000, 9999999, 9999998, 9999997, 9999996, 9999995, 9999994, 9999993, 9999992, 9999991, 9999990, 9999989, 9999988, 9999987, 9999986, 9999985, 9999984, 9999983, 9999982, 9999981, 9999980, 9999979, 9999978, 9999977, 9999976, 9999975, 9999974, 9999973, 9999972, 9999971, 9999970, 9999969, 9999968, 9999967, 9999966, 9999965, 9999964, 9999963, 9999962, 9999961, 9999960, 9999959, 9999958, 9999957, 9999956, 9999955, 9999954, 9999953, 9999952, 9999951, 9999950, 9999949, 9999948, 9999947, 9999946, 9999945, 9999944, 9999943, 9999942, 9999941, 9999940, 9999939, 9999938, 9999937, 9999936, 9999935, 9999934, 9999933, 9999932, 9999931, 9999930, 9999929, 9999928, 9999927, 9999926, 9999925, 9999924, 9999923, 9999922, 9999921, 9999920, 9999919, 9999918, 9999917, 9999916, 9999915...

単に

1	scala> (1 to 10000000).sorted.reverse.take(100)

とするよりはずっと速い。

もう少しスマートに書けそうなものだけど。。。

IVA Reading: Chapter 02, Section 06 Exercises

IVA読書会 chap02-sect06 宿題

 

No.5

lex順序でS多項式を求める計算問題。

RECAP

$$S(f, g) = \frac{x^\gamma}{{\scriptstyle \text{LT}}(f)}\cdot f - \frac{x^\gamma}{{\scriptstyle \text{LT}}(g)}\cdot g$$
where $$x^\gamma = \text{LCM}({\scriptstyle \text{LM}}(f), {\scriptstyle \text{LM}}(g))$$

計算には PARI/GP を利用。
ただ Leading Term を返す関数が見つからなかったので、LM, LC を手で計算して与えた。

1 2 3 4 5 6 7 8 9 10

? spol(f, g, lm_f, lm_g, lc_f, lc_g) = lcm(lm_f, lm_g)/(lm_f * lc_f) * f - lcm(lm_f, lm_g)/(lm_g * lc_g) * g %11 = (f,g,lm_f,lm_g,lc_f,lc_g)->lcm(lm_f,lm_g)/(lm_f*lc_f)*f-lcm(lm_f,lm_g)/(lm_g*lc_g)*g ? spol(4*x^2*z - 7*y^2, x*y*z^2 + 3*x*z^4, x^2*z, x*y*z^2, 4, 1) %12 = -3*z^4*x^2 - 7/4*z*y^3 ? spol(x^4*y - z^2, 3*x*z^2 - y, x^4*y, x*z^2, 1, 3) %18 = 1/3*y^2*x^3 - z^4 ? spol(x^7*y^2*z + 2*i*x*y*z, 2*x^7*y^2*z + 4, x^7*y^2*z, x^7*y^2*z, 1, 2) %17 = 2*i*z*y*x - 2 ? spol(x*y + z^3, z^2 - 3*z, x*y, z^2, 1, 1) %15 = 3*z*y*x + z^5

a.
$\begin {eqnarray*} S(4x^2z - 7y^2, xyz^2 + 3xz^4) &=& \frac{x^2yz^2}{4x^2z}\cdot (4x^2z - 7y^2) - \frac{x^2yz^2}{xyz^2}\cdot (xyz^2 + 3xz^4)\\ &=& \frac{1}{4}yz \cdot (4x^2z - 7y^2) - x \cdot (xyz^2 + 3xz^4) \\ &=& x^2yz^2 - \frac{7}{4}y^3z - x^2yz^2 - 3x^2z^4 \\ &=& -3x^2z^4-\frac{7}{4}y^3z \end {eqnarray*}$

以下、途中式は省略。

b.
$S(x^4y - z^2, 3xz^2 - y) = \frac{1}{3}x^3y^2 - z^4$

c.
$S(x^7y^2z + 2ixyz, 2x^7y^2z + 4) = 2ixyz - 2$

d.
$S(xy+z^3, z^2-3z) = 3xyz + z^5$

 

No.11




左辺を変形

$$\begin {eqnarray*} S(x^\alpha f, x^\beta g) &=& \frac{\text{LCM}({\scriptstyle \text{LM}}(x^\alpha f), {\scriptstyle \text{LM}}(x^\beta g))}{{\scriptstyle \text{LT}}(x^\alpha f)}\cdot x^\alpha f - \frac{\text{LCM}({\scriptstyle \text{LM}}(x^\alpha f), {\scriptstyle \text{LM}}(x^\beta g))}{{\scriptstyle \text{LT}}(x^\beta g)}\cdot x^\beta g \\ &=& \frac{\text{LCM}(x^\alpha {\scriptstyle \text{LM}}(f), x^\beta {\scriptstyle \text{LM}}(g))}{x^\alpha {\scriptstyle \text{LT}}(f)}\cdot x^\alpha f - \frac{\text{LCM}(x^\alpha {\scriptstyle \text{LM}}(f), x^\beta {\scriptstyle \text{LM}}(g))}{x^\beta {\scriptstyle \text{LT}}(g)}\cdot x^\beta g \\ &=& \frac{\text{LCM}(x^\alpha {\scriptstyle \text{LM}}(f), x^\beta {\scriptstyle \text{LM}}(g))}{{\scriptstyle \text{LT}}(f)}\cdot f - \frac{\text{LCM}(x^\alpha {\scriptstyle \text{LM}}(f), x^\beta {\scriptstyle \text{LM}}(g))}{{\scriptstyle \text{LT}}(g)}\cdot g \end {eqnarray*}$$

右辺を変形

$$\begin {eqnarray*} x^\gamma S(f,g) &=& x^\gamma \cdot \Bigl(\frac{\text{LCM}({\scriptstyle \text{LM}}(f), {\scriptstyle \text{LM}}(g))}{{\scriptstyle \text{LT}}(f)}\cdot f - \frac{\text{LCM}({\scriptstyle \text{LM}}(f), {\scriptstyle \text{LM}}(g))}{{\scriptstyle \text{LT}}(g)}\cdot g\Bigr) \\ &=& \frac{\text{LCM}(x^\alpha {\scriptstyle \text{LM}}(f), x^\beta {\scriptstyle \text{LM}}(g))}{\text{LCM}({\scriptstyle \text{LM}}(f), {\scriptstyle \text{LM}}(g))} \cdot \Bigl(\frac{\text{LCM}({\scriptstyle \text{LM}}(f), {\scriptstyle \text{LM}}(g))}{{\scriptstyle \text{LT}}(f)}\cdot f - \frac{\text{LCM}({\scriptstyle \text{LM}}(f), {\scriptstyle \text{LM}}(g))}{{\scriptstyle \text{LT}}(g)}\cdot g\Bigr) \\ &=& \text{LCM}(x^\alpha {\scriptstyle \text{LM}}(f), x^\beta {\scriptstyle \text{LM}}(g)) \cdot \Bigl(\frac{1}{{\scriptstyle \text{LT}}(f)}\cdot f - \frac{1}{{\scriptstyle \text{LT}}(g)}\cdot g\Bigr) \\ &=& \frac{\text{LCM}(x^\alpha {\scriptstyle \text{LM}}(f), x^\beta {\scriptstyle \text{LM}}(g))}{{\scriptstyle \text{LT}}(f)}\cdot f - \frac{\text{LCM}(x^\alpha {\scriptstyle \text{LM}}(f), x^\beta {\scriptstyle \text{LM}}(g))}{{\scriptstyle \text{LT}}(g)}\cdot g \end {eqnarray*}$$

したがって、$S(x^\alpha f, x^\beta g) = x^\gamma S(f,g)$

□

 

また、
$\text{LCM}(x^\alpha {\scriptstyle \text{LM}}(f), x^\beta {\scriptstyle \text{LM}}(g)) = \text{LCM}({\scriptstyle \text{LM}}(x^\alpha f), {\scriptstyle \text{LM}}(x^\beta g))$
${\scriptstyle \text{LM}}(f) \mid {\scriptstyle \text{LM}}(x^\alpha f)$
${\scriptstyle \text{LM}}(g) \mid {\scriptstyle \text{LM}}(x^\alpha g)$
より、
$\text{LCM}({\scriptstyle \text{LM}}(f), {\scriptstyle \text{LM}}(g)) \mid \text{LCM}(x^\alpha {\scriptstyle \text{LM}}(f), x^\beta {\scriptstyle \text{LM}}(g))$

$x^\alpha$, $x^\beta$, ${\scriptstyle \text{LM}}(f)$, ${\scriptstyle \text{LM}}(g)$ はいずれも単項式であるから、$x^\gamma$ もまた単項式である。

How to Make a Transpose of 2D-Array in Scala

Scala: 2次元配列を転置する方法

 

要素数 $M \times N$ の 2次元配列 $A$ に対して、$A_{ij} = B_{ji} \, (1 \le i \le M,\, 1 \le j \le N)$ となるような
$N \times M$ の2次元配列 $B=A^T$ を作成したい。

Scala の Array クラスには、そのものズバリ transpose というメソッドがある。

• Scala Standard Library 2.11.2 - Array - Scala Standard Library 2.11.2 - scala.Array

1 2 3 4 5

scala> val a = Array(Array(1,2,3),Array(4,5,6),Array(7,8,9),Array(10,11,12)) a: Array[Array[Int]] = Array(Array(1, 2, 3), Array(4, 5, 6), Array(7, 8, 9), Array(10, 11, 12))   scala> a.transpose res0: Array[Array[Int]] = Array(Array(1, 4, 7, 10), Array(2, 5, 8, 11), Array(3, 6, 9, 12))

これを利用すれば、文字列を区切って縦に結合するような処理もシンプルに記述できる。

1 2 3 4 5 6 7 8 9 10 11 12

scala> val s = """      | abc 123      | def 456      | """ s: String = " abc 123 def 456 "   scala> s.split('\n').withFilter(!_.isEmpty).map(_.split("[ ]+")).transpose map (_.mkString) res1: Array[String] = Array(abcdef, 123456)

　

　

References

• Matrix transposition - Rosetta Code