Cogito ergo sum

常々思うこと。

 

この世界は、私の認識によって成り立っている。

 

私が認識できないもの、すなわち知覚できないもの、知識として得られない有象無象は

そこに存在していないことと何一つ変わらない。

 

私は、私の死後の世界を認識することはできない。

その時、私という自我が失われることを、知識として身につけているからだ。

したがって、私の死後の世界は、私にとって存在しないものである。

 

ゆえに、私が死ぬことはない。

永遠に生き続けねばならないのだ。

 

 

何処に矛盾があるだろうか。

C++: How to Get Per-Core CPU Usage in Mac

C++: Mac環境でコア単位のCPU使用率を測定する

 

環境

• OS X: 10.9

 

コード

#include <stdio.h>
#include <unistd.h>
#include <mach/mach_host.h>
#include <mach/processor_info.h>
#include <iostream>

using namespace std;

class CpuUsage {
 public:
  CpuUsage(int core): core_(core) {
    prev = updated_ticks_(core);
  }

  float get() {
    Ticks t = updated_ticks_(core_);
    unsigned long long int used = t.used() - prev.used();
    unsigned long long int total = t.total() - prev.total();
    prev = t;
    return (float)used / (float)total * 100.0f;
  }

 private:
  struct Ticks {
    unsigned long long int usertime;
    unsigned long long int nicetime;
    unsigned long long int systemtime;
    unsigned long long int idletime;

    unsigned long long int used() { return usertime + nicetime + systemtime; }
    unsigned long long int total() { return usertime + nicetime + systemtime + idletime; }
  } prev;

  int core_;

  Ticks updated_ticks_(int core) {
    unsigned int cpu_count;
    processor_cpu_load_info_t cpu_load;
    mach_msg_type_number_t cpu_msg_count;

    int rc =  host_processor_info(
      mach_host_self( ),
      PROCESSOR_CPU_LOAD_INFO,
      &cpu_count,
      (processor_info_array_t *) &cpu_load,
      &cpu_msg_count
    );
    if (rc != 0) {
      printf("Error: failed to scan processor info (rc=%d)\n", rc);
      exit(1);
    }

    if (core < 0 || cpu_count <= core) {
      printf("Error: invalid core number: %d\n", core);
      exit(1);
    }
    unsigned long long int usertime = cpu_load[core].cpu_ticks[CPU_STATE_USER];
    unsigned long long int nicetime = cpu_load[core].cpu_ticks[CPU_STATE_NICE];
    unsigned long long int systemtime = cpu_load[core].cpu_ticks[CPU_STATE_SYSTEM];
    unsigned long long int idletime = cpu_load[core].cpu_ticks[CPU_STATE_IDLE];

    Ticks t = {usertime, nicetime, systemtime, idletime};
    return t;
  }

};

int main() {
  CpuUsage a(0), b(1), c(2), d(3);
  sleep(1);
  printf("%6.2f, %6.2f, %6.2f, %6.2f\n", a.get(), b.get(), c.get(), d.get());
  sleep(1);
  printf("%6.2f, %6.2f, %6.2f, %6.2f\n", a.get(), b.get(), c.get(), d.get());
  sleep(1);
  printf("%6.2f, %6.2f, %6.2f, %6.2f\n", a.get(), b.get(), c.get(), d.get());
  return 0;
}

(need improvement)

 

実行例

 78.00,  72.73,  85.00,  72.00
 78.00,  57.00,  72.00,  56.57
 82.00,  83.00,  90.00,  88.00

 

 

References

• htop-osx/ProcessList.c at master · max-horvath/htop-osx

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 を追加する。

  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 という名前のファイルはその内容が全て結合される。

  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 程度しかないので、含めておいたとしてもそんなに気にならないと思う。

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

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 を使ってみる。

 

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$ が小さい前提なので問題ない。

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...

単に

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 を手で計算して与えた。

? 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

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))

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

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

Scala: How to Merge Two Maps with Summing Values

Scala: Map の値を加算しながらマージする

 

Scalaz を使うとシンプル。

sbt 設定例

libraryDependencies += "org.scalaz" %% "scalaz-core" % "7.0.6"

実行例

scala> import scalaz.Scalaz._
import scalaz.Scalaz._

scala> Map('a -> 10, 'b -> 20, 'c -> 30) |+| Map('a -> 5, 'c -> 7, 'd -> 9)
res0: scala.collection.immutable.Map[Symbol,Int] = Map('a -> 15, 'c -> 37, 'd -> 9, 'b -> 20)

引き算をするなら、こんな感じだろうか。

scala> Map('a -> 10, 'b -> 20, 'c -> 30) |+| Map('a -> 5, 'c -> 7, 'd -> 9).mapValues(-_)
res1: scala.collection.immutable.Map[Symbol,Int] = Map('a -> 5, 'c -> 23, 'd -> -9, 'b -> 20)

 

 

References

• Nimrod's Tech Blog » Scala Map Merge