Project Eulerで用いた数学知識
オイラーにちなんだ数学的なプログラミングの問題が出題されるサイト、Project Euler。 大体の問題は、greedy にやっても解けるんですが、適切な数学的知識を用いると時間計算量のオーダーが劇的に変わってきます。 そこで、１００問目まではラップトップで１秒以内（もちろん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 の問題に関してさえも）まだ完全ではないんですが、暇を見つけて少しずつ更新していきます。
約数
素因数分解
素数
置換
分割数
フィボナッチ数列
ピタゴラス数
平方数
順序集合
数列
方程式
分数
少数
数値解析
グラフ探索
これまでに解いた問題は以下のとおり。
Unicodeの拡張領域の文字を一文字とカウントする
ScalaやJavaは拡張領域の文字をサロゲートペアで表すので、文字数をカウントしたいときに単純に文字列のサイズを取ると実際の文字数とずれてしまう。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]
コードポイント www.wikiwand.com
UTF-8のはずのテキストの処理中に MalformedInputException で落ちる場合の対処
Spark用sbtプロジェクトの設定
プロジェクトセットアップ
build.sbtに以下のコードを書いて、sbt update
ソースを書く
ビルド
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に無視したい文字列を書く。
参考文献：
