CodeIQ本[Q57:あみだくじの問題]についてのメモ

これまで、コンピュータサイエンスの真ん中の勉強をしてこなかったので、少しずつやってみようかなと思った。とりあえず書店でよさげなCodeIQの「プログラマ脳を鍛える数学パズル」をゲット。謎のプライドが発動し、いきなり上級編の第四章からやってみることに。上級編の最初はQ57、あみだくじの問題。(以下はこの本の出題内容を知らないとわけがわからないと思うので、該当の本を持っていない人は読んでも時間のムダになります。)

「あみだくじをどういう風にコードに落としこむのか」というとっかかりがまったく掴めず脳みそが真っ白になり、「さっぱりわからねぇ…」という状態が10分ほど続く。我ながら笑った。パズル的なものをコードで解いた経験はほぼゼロだったのだが、10年以上プログラミングで食ってきたのでこういうのもチョチョイとできるイメージを持っていた。全然違うよ。

しかし落ち着いてとりあえず書き始めたら何とか1時間くらいで答えを出すことができ、きちんと一発目で正解。初心者らしく、まず「横線を10本引く」パターンについて総当りし、すべてのありえるパターンの結果を列挙。その中から「横線が9本以下でも起こりえるパターン(こちらも総当り)」をすべて消去し、残ったパターンの数が回答になる、という方法。この方法だと計算量が多いらしく、答えが出るまで結構待たされた。

https://github.com/Kanatoko/codeiq_book/blob/master/q57_amida1.java

アルゴリズムそのものとは別に色々とチューニングの余地がありそうだが、とりあえず答えが合っていたので良しとする。続いて別の方法を少し考えてみることに。

最初の方法は非常に原始的で、まず横線を引くパターンをすべて計算し、次にそれぞれの場合にあみだくじの結果がどうなるかを順番に処理するという形。ここで気づいたのは、あみだくじの横線によって2つの数値が入れ替わるということ。いままで感覚としてあみだくじというのは選んだ要素が階段状に降りていくイメージを持っていたのだが、単純に左右が入れ替わると捉えることもできる。

amida1

上記のように、初期状態は「1 2」だが、横線によって「2 1」という状態に変化する。

さらに、別の捉え方をすることもできる。「横線によって、1が右に移動した」と考えるのだ。このとき「1が右に移動し、2が左に移動した」ではなく、「1が右に移動した。2はそのままの位置にいた」つまり「2は動いていないのだが、1が2の右にきた」と考えるのだ。

これにより「あみだくじに横線を追加することで、任意の要素を右に1つ移動させることができる」と考えることができる。ただし、一番右の要素は移動先が存在しないので、移動させることはできない。

また、「左に移動する」という概念は存在しないと考えることができる。左に移動したように見える要素(上図の2)は移動しておらず、あくまでも左にいたもの(1)が右に来たのだ、と考えることで、「2は左に移動したわけではない」と考えることができる。

少し拡張して縦線が4本あるケースを考えてみる。

amida2

上記は3本の横線があるが、これらをすべて「1を右に動かすため」のものであると考える。「2,3,4は動いておらず、1だけが右に移動した」と考える。

このように考えると、上記の縦線4本のあみだくじで言えば

  • 1は右に最大3移動できる
  • 2は右に最大2移動できる
  • 3は右に最大1移動できる
  • 4は移動できない

となる。今回の問題はすべての横線を引いたときにはじめて出現するパターンを求めるものなので、ひたすら右を目指して移動するパターンのみ考えればよい。(横線が縦に連続した場合は元に戻ってしまうわけだが、そういうケースは無視してよいのだ。)

上図は「1234」という文字列を「2341」に変換するための距離が3、のようないわゆる編集距離のような感覚で考えることができる。(1を3回移動させるので距離が3と考える)

今回の出題内容は「縦線が7本・横線が10本」だが、これだと多いので、縦線が4本・横線が5本のケースを例に考える。

横線が5本ということは、いずれかの要素を選び、合計で5回右に移動させることができるということだ。

例えば、1は最大で3移動できるので、とりあえず3移動させるものとしよう。残りの横線は2本だ。2は最大2移動できるので2を2移動させよう。これで合計の5を使いきった。

amida3

赤線は1を移動させている。青線は2を移動させている。3と4は移動していないと考える。

このように考えると横線が5本の場合は下記3パターンがあり得る。

  • 1が3移動、2が2移動(合計5)
  • 1が3移動、2が1移動、3が1移動(合計5)
  • 1が2移動、2が2移動、3が1移動(合計5)

そのため答えは「3通り」になる。

これをコードに落とし込んだのが

https://github.com/Kanatoko/codeiq_book/blob/master/q57_amida2.java

で、こちらは一瞬で処理が終わる。計算量が少なく済むようだ。

この手のネタをやったことがなかったので最初は再帰させることにも気づかずあっぷあっぷしたが、最終的には非常に良い脳みその体操になった。あみだくじと編集距離の関係に気づくなど予想もしていなかった。

Advertisements

Clojure vs Java速度比較

twitterで「ClojureはJavaより遅いから…」とつぶやいたら複数人に「どんなケースか?」のような質問を受けて驚いた。実はちょっとうれしくて、僕としてもClojureが本当に速いならそれに越したことはない。

少しincanterを使ってデータをいじっている感覚だと、メモリ上に載せた数十万行〜100万行くらいのデータについて処理している感じでもJavaよりもっさりした感覚があった。

元々STMが遅かったのが強烈な印象だったのだが、普通にでかいファイルを処理する際にはClojureはどの程度速いのか測ってみることにした。

テスト内容は超シンプルに、100万行のCSVファイルの1カラム目の最大値を求める、というもの。コードは以下。

https://github.com/Kanatoko/cljbench/

Clojureのコードを書くのが数年ぶりなのでインデントとかよくわからなくてキモいコードですみません。何か致命的なミスをしている気もするがとりあえず動いている。

速度を比較した感じ、Clojureで10かかるところがJavaだと4で終わる感じ。60%速い。

2017/12/4 06:55追記

今回は「普段使い」のパフォーマンス的な比較をしたいので、2つのコードとも「なるべく深く考えずに、とりあえず書く状態」を目指している。カリカリに速くした状態ではない。

例えばJava側だったらsplit(正規表現なので遅い)を避けてカンマの位置をindexOfで求めに行く方がずっと速くなると思うが(業務でやっているのサーバのパフォーマンスチューニングはそんなのばっかり)、何をやってるのかわかりにくくなるし、最初のカラムではなく別のカラムを求める場合にコードの変更点が増えるので。でももしかしたらsplitは単純なケースだと速いかも。

Clojure側はできるだけClojureらしいコードにしたい。ClojureのコードにBufferedInputStream…とかJavaのクラスがなるべく出てこないようにしたい。

2017/12/4 07:55追記

添削して頂いたらJava版より1〜2割程度遅いくらいまで速くなった。これだと「Clojureは遅い」という評価は当てはまらない。充分に速いと言える。素晴らしい。

このチューニングが具体的にやっているのは「Javaの関数を直接使うようにした」という点なのが微妙(Clojureの関数とJavaの関数が入り乱れてキモいコードになる)だと感じたが、Clojureの哲学としては「Javaを歓迎」して良いはずなのでこれに慣れていけばいいだけか。

あやぴさんありがとうございました。

 


クラスタリングでアノマリ検知メモ

9月のSecMLでクラスタリングを使ったアノマリ検知をどうやっているか等について話をする関係で少し調べものをしていて見つけたネタをメモしておく。

オライリーのAdvanced analytics with SparkにKMeansでアノマリ検知をする章がある。以前に何となく読んではいたんだけど、結局最終的に何をもってクラスタリング結果と「アノマリかどうか」を結びつけているんだっけ?と思い読みなおした。

Now, we can make an actual anomaly detector. Anomaly detection amounts to measuring a new data point’s distance to its nearest centroid. If this distance exceeds some threshold, it is anomalous.

だそうで、「クラスタの中心からの距離がある閾値を超えたらアノマリだ」というごくシンプルな方法だった。

僕がやっているのはそもそもあるクラスタについては全部アノマリかもしれない、というシチュエーションである。そのため「そのクラスタに所属したらアノマリ」「むしろ中心に近かったら超アノマリ」みたいなことになるのでこの本のケースとは異なるな、とわかった。

メモおしまい。


「正義のハッカー、人工知能で異常検知」の難しさ

ふと脳裏に浮かんだのだが、これは実に難しい。

まず「正義」の定義が難しい。言うまでもなく、常に悪の側も「自分たちこそが正義だ」と主張するだろう。「アメリカこそテロ国家だ」みたいなやつである。正義ってなんだろう…と出だしでいきなりつまづくのである。

次に「ハッカー」。ハッカーではなくクラッカーと呼べ、みたいなのは最近見かけなくなった気がするが、我々は「ハッカー」の定義ではひと悶着せざるをえない。実に関わりたくない用語である。

そして流行りの人工知能。最近は書店に行くと中身のない人工知能本が溢れんばかりに平積みされていて気が滅入る。人工知能学会の中ですら人工知能の定義ができていないらしいので、我々が定義できるはずもない。というかそもそも知能の定義はされているのだろうか?

最後に異常検知。「これは問題ないのでは?」だって?甘いな…

まぁ、たしかに、用語としてはそこそこ定義しやすい。もちろん異常を検知するのだ。

しかし「異常」って何?という話になると、これは「正常ではないケースが異常」となるので、正常を定義する必要が出てくる。

セキュリティの文脈の異常検知(攻撃を見つけたい)だったりサーバのメトリクスの異常検知(主に時系列でCPU使用率等が夜間に突然上昇するようなやつを見つけたい)だったり、人や場面によってそれぞれの「正常」があまりにもバラバラなので、異常検知の意味するところもバラバラになる。

「異常検知に興味があるひと」を集めて議論させても、おそらく何も生まれないだろう。「異常検知」という用語は意味が広すぎるのだ。

まさにカオスである。助けて、正義のハッカー!!

 


PostgreSQLでのSQLインジェクションでシステムコマンド実行

https://www.postgresql.org/docs/9.3/static/sql-copy.html

今朝気づいたが、バージョン9.3以降では、COPYコマンド経由(PROGRAM)で外部コマンドを簡単に起動できる。xp_cmdshellの亡霊が再び…なんちゃって…


セッションIDをCSRFトークンに使うべきでない理由

malaさんも2年程前に書かれているのですが、未だに国内のCSRF対策の解説で「セッションIDをCSRFトークンとして使う」というアイデアが披露されていて辟易します。

喩え話は好きでないですが、「複数のサイトで同じパスワードを使っていたら一箇所から漏洩し、パスワードリスト攻撃を受けた」というのを彷彿します。セッションIDとCSRFトークンは単純に別の値にした方がいいです。

さてこのエントリの本題はここからで、CSRFトークンよりもむしろセッションIDの方です。最近は443番ポートへクロスサイトでリクエストを大量に送らせてそれをキャプチャし、すべてのリクエストに共通して含まれてくるCookie中のセッションIDを解読するBEAST/CRIME系の攻撃が知られるようになりました。

これらは基本的にはTLS/SSLの問題でありそれぞれ個別に対策が存在しているものの、基本的には「セッションIDがずっと同じ値である」という部分、HTTP特有の仕組みを攻撃対象としています。(攻撃対象がBasic認証などの場合はこの限りではないです)

これを受けて「何千もリクエストが勝手に送られている間、セッションIDがずっと同じなのって間抜けだよね?」と考えるのがまともな感覚だと思うのですが、いかがでしょうか。つまりセッションIDがずっと同じであるという実装の常識をそろそろ変えていくべきだと思います。あくまで保険的な対策となると思いますが、今後登場するかもしれないBEAST/CRIMEの発展形を防ぐ可能性が高いと考えます。

一部、セッション固定により「ログインしたタイミングでセッションIDを変える」ということは良く知られており実践されていますが、そもそもセッションIDはコロコロ変えるべきなのです。

さて話はCSRFトークンに戻りますが、セッションIDの値をそのままCSRFトークンとして使ってしまっていると、上記のように「セッションIDを頻繁に変更する」ということができなくなってしまいます。なのでセッションIDの値をCSRFトークンにするのはやめましょう。

「…やめましょう」とか書きましたが、別の件(CSRFトークン インタビューズ)でシェアの高いいくつかのフレームワークについて調べてみたところ、そもそもセッションIDの値をそのままCSRFトークンにしているものをひとつも見つけることができませんでした。もし見つけたら教えてください。

なんか、ガラパゴス的な議論をしていたようで脱力します。


非線形データに普通のKMeansを使う

1,2,2,2,3,3,4,10,10,11,11,11,12,12,12,12,13,13,25,25,26,26,26,27,28,28,29,29,29,29,30,30,30,31

例えば上記のような1次元のデータがある場合を考える。ある小学校のクラスで行われた簡易テストの点数のようなイメージだ。「1点の生徒が1人、2点の生徒が3人・・・31点を取った生徒が1人」という感じである。

nonlinear2

ヒストグラムは上記のようになる。ここで色分けは意図的に行っている。

  • 赤は落ちこぼれ
  • 緑は普通の生徒
  • 黒はよくできるグループ

のように、いわゆるラベル分けを行うことができる。繰り返しになってしつこいが、これは意図的なラベル分けだ。

ここでは3つに分類すると決めており、データは人間から見ると自然に3つに(ヒストグラム上で)別れている。各グループ間は線形分離が可能だ。

このような場合、KMeansクラスタリングでk=3とすると完璧にクラスタリングしてくれる(ことが多い)。「ラベルが3種類だから、k=3とする」というごくありがちなアプローチである。

a <-c(1,2,2,2,3,3,4,10,10,11,11,11,12,12,12,12,13,13,25,25,26,26,26,27,28,28,29,29,29,29,30,30,30,31) 
> kmeans(a,3)
K-means clustering with 3 clusters of sizes 16, 11, 7

Cluster means:
[,1]
1 28.000000
2 11.545455
3 2.428571

Clustering vector:
[1] 3 3 3 3 3 3 3 2 2 2 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

Within cluster sum of squares by cluster:
[1] 56.000000 10.727273 5.714286
(between_SS / total_SS = 98.1 %)

Available components:

[1] "cluster" "centers" "totss" "withinss" "tot.withinss"
[6] "betweenss" "size" "iter" "ifault"

仮に今回のケースが、ラベル有りで上記データが提供されていて、KMeansでモデルを作り、新たなデータを「落ちこぼれ」「普通」「よくできる」のいずれかに分類したいという状況だとする。この場合、データが上記kmeansの実行で得られたクラスタ中心(28, 11.5, 2.4)のどれに一番近いか?を判断するだけで良い。

しかし、ラベルが3種類ではなく、下記の2種類だったらどうなるだろうか。

nonlinear3

ここでラベルが以下の2つであるとする。

  • 緑は「普通でない生徒」
  • 赤は「普通の生徒」

突如、緑に属するデータは非線形な集まりとなってしまう。先ほどと同じようにKMeansでモデルを作り、新たなデータを分類する問題として考える場合、先ほどと同じアプローチで「ラベルが2種類だからk=2でクラスタリングしよう」と思っても当然うまくいかない。

ここで「くそっ、KMeansは非線形データに弱いんだぜ…」と考えてカーネル関数とかそっちに走るのもひとつの手だが、もっと超簡単な方法がある。というかこのブログエントリを先頭から読めば自然に気づくと思うが、「ラベルが2種類だからk=2」というのを「ラベルは2種類だけどk=3でやってみよう」とするだけである。

そして、実際の分類の際には

  • 1つめのクラスタ中心に近ければ「普通でない生徒」
  • 2つめのクラスタ中心に近ければ「普通の生徒」
  • 3つめのクラスタ中心に近ければ「普通でない生徒」

というロジックに従えばOKである。

クラスタリング結果をそのまま分類に使うのではなく、クラスタリング結果にもうひとつだけ処理を追加するだけでよい。クラスタリングはあくまでも数値処理で、人間がそれをうまく解釈してやるだけの話だ。

あまりにも簡単な話なのだが、意外と目にしない(私の探し方が悪いだけかもしれないが)ので、ブログに書いてみた。

2017/11/26追記

オライリーの「Pythonではじめる機械学習」のP.176にまさにこれが載っていたので追記しておく。