Scala日記

Scalaの備忘録。ときどき研究の話。

Project Eulerで用いた数学知識

オイラーにちなんだ数学的なプログラミングの問題が出題されるサイト、Project Euler。 大体の問題は、greedy にやっても解けるんですが、適切な数学的知識を用いると時間計算量のオーダーが劇的に変わってきます。 そこで、100問目まではラップトップで1秒以内(もちろんScalaです)に解くという縛りを設けてやっていました。 (ただし、幾つかの問題ではこの縛りに違反したまま。 Problem 60: 9,472ms, Problem 78: 2,948ms, Problem 86: 2,125ms, Problem 93: 2,244ms, Problem 95: 3,854ms, Problem 96: 1,184ms)

その際に使った知識(Wikipediaへのリンク)をここにまとめていきます。 このリストは(これまでに解いた Project Euler の問題に関してさえも)まだ完全ではないんですが、暇を見つけて少しずつ更新していきます。

約数

素因数分解

素数

置換

分割数

フィボナッチ数列

ピタゴラス

平方数

順序集合

数列

方程式

分数

少数

数値解析

グラフ探索


これまでに解いた問題は以下のとおり。

f:id:yuimat:20151202152117p:plain

ScalaFX で sorting visualizer を 作る

ScalaGUI を作るときには、JavaFX8 compatible な ScalaFX というライブラリが使えるが、参考資料が非常に少ない。練習がてらに ScalaFX で ソーティングアルゴリズムを可視化・可聴化するプログラムを作ってみた。

github.com

動いているところ

f:id:yuimat:20151102092057j:plain f:id:yuimat:20151102092100j:plain

このプログラムは以下の動画に啓発された。本家と違うのは、音色や音階(スケール)を選んで綺麗なメロディにできること。 Pure Scalaなので、sbtとjreさえ入っていれば動く。

www.youtube.com

ついでに迷路生成・探索も実装してみた。興味のある方は是非どうぞ。

f:id:yuimat:20151102092549j:plain f:id:yuimat:20151102092553j:plain

Unicodeの拡張領域の文字を一文字とカウントする

ScalaJavaは拡張領域の文字をサロゲートペアで表すので、文字数をカウントしたいときに単純に文字列のサイズを取ると実際の文字数とずれてしまう。Java 1.5からはUnicodeコードポイント を数えるメソッドが追加されているので、これを使えば正確に文字数をカウントできる。

以下、地球の絵文字を例に取って説明。

scala> val earth = "\uD83C\uDF0D"
earth: String = 🌍
scala> println(earth, earth.length)
(🌍,2)
scala> earth.codePointCount(0, earth.length)
res20: Int = 1

ちなみに、

Python

% ipython
In [1]: print u"\U0001F30D", len(u"\U0001F30D")
🌍 2

% ipython3
In [1]:  print(u"\U0001F30D", len(u"\U0001F30D"))
🌍 1

Ruby

% pry
[1] pry(main)> p ["\u{1F30D}", "\u{1F30D}".size]
["🌍", 1]
  1. コードポイント www.wikiwand.com

  2. サロゲートペア www.wikiwand.com

UTF-8のはずのテキストの処理中に MalformedInputException で落ちる場合の対処

Webなどから取ってきた巨大な文書ファイルを処理するとき、UTF-8エンコーディングで処理したはずだったのに、中間処理に使った言語の仕様なのか処理ミスなのか、とにかく何らかの理由があって、Scalaで読み込む際に MalformedInputException が発生してしまうことがある。文字コード周りに問題があるらしいが、みんなが使っているファイルだし、1ファイルあたり圧縮済みで数十GBだし、作り直したくないな、という込み入った状況のときには以下のようにコーデックの設定でなんとかできる。

gist.github.com

Spark用sbtプロジェクトの設定

プロジェクトセットアップ

build.sbtに以下のコードを書いて、sbt update

gist.github.com

ソースを書く

gist.github.com

ビルド
sbt package
実行
spark-submit \
  --class SampleApp \
  --master yarn-cluster \
  --num-executors 8 \
  target/scala-2.10/(your project)_2.10-1.0.jar

xmlファイルをstdinから読み込む

import scala.xml.parsing.ConstructingParser

val doc = ConstructingParser.fromSource(Source.stdin, preserveWS = true).document()

sbtで実行するときにstdoutにsbtのログを出さないようにする

sbt経由でプログラムを実行すると

[info] Loading project definition from...
[info] Set current project to ...
[info] Running ...

[success] Total time: 3 s, completed 2015/07/...

などが「標準出力」に出てしまって、出力をリダイレクトして処理しにくい。

そこで、

sbt --error 'set showSuccess := false'  'set outputStrategy := Some(StdoutOutput)' run

や、

sbt --error 'set showSuccess := false'  'set outputStrategy := Some(StdoutOutput)' 'runMain MainClass'

などとすると、これらを沈黙させることができる。 もちろん、これらをbuild.sbt等に直書きしておけば常に沈黙を保てる。

それでもなお

Loading ...

などが残る場合は、以下の sbt-extraをインストールして、.sbtignoreに無視したい文字列を書く。

github.com

参考文献:

  1. stackoverflow.com