なんとな～くしあわせ？の日記

「そしてそれゆえ、知識そのものが力である」 (Nam et ipsa scientia potestas est.) 〜 フランシス・ベーコン

Neo4jでグラフアルゴリズム

AOJ アルゴリズム

前から調べようと思っていたNeo4jの勉強会に行ってきた。
jp-neo4j-usersgroup.connpass.com

グラフアルゴリズム

AOJ - 深さ優先探索

データセットの用意

入力例 2
6
1 2 2 3
2 2 3 4
3 1 5
4 1 6
5 1 6
6 0

  • こんな感じか？
    • たぶん書き方が冗長になっている気がする
CREATE (g:Graph { u:1, k:2 });
CREATE (g:Graph { u:2, k:2 });
CREATE (g:Graph { u:3, k:1 });
CREATE (g:Graph { u:4, k:1 });
CREATE (g:Graph { u:5, k:1 });
CREATE (g:Graph { u:6, k:0 });

MATCH (s:Graph) WHERE s.u = 1
MATCH (d:Graph) WHERE d.u = 2
CREATE (s)-[:DIRECTED]->(d);

MATCH (s:Graph) WHERE s.u = 1
MATCH (d:Graph) WHERE d.u = 3
CREATE (s)-[:DIRECTED]->(d);

MATCH (s:Graph) WHERE s.u = 2
MATCH (d:Graph) WHERE d.u = 3
CREATE (s)-[:DIRECTED]->(d);

MATCH (s:Graph) WHERE s.u = 2
MATCH (d:Graph) WHERE d.u = 4
CREATE (s)-[:DIRECTED]->(d);

MATCH (s:Graph) WHERE s.u = 3
MATCH (d:Graph) WHERE d.u = 5
CREATE (s)-[:DIRECTED]->(d);

MATCH (s:Graph) WHERE s.u = 4
MATCH (d:Graph) WHERE d.u = 6
CREATE (s)-[:DIRECTED]->(d);

MATCH (s:Graph) WHERE s.u = 5
MATCH (d:Graph) WHERE d.u = 6
CREATE (s)-[:DIRECTED]->(d);
ビジュアライズ

Neo4j Desktopを使ってビジュアライズしてみる

f:id:panzer-jagdironscrap1:20180802233545p:plain

なにこれ高性能過ぎる・・・

アルゴリズム実装

あとはこれをクエリで距離を測ったりいろいろやりたい。

実装するのはこれ

function 深さ優先探索(v)
    v に訪問済みの印を付ける
    v を処理する
    for each v に接続している頂点 i do
        if i が未訪問 then
            深さ優先探索(i)
  • ノード3から辿れるものを出力
    • これで一応有向グラフをたどることはできてんのかな？
    • もともとプログラム側の疑似コードで for each v に接続している頂点 i do ~ done という処理をやらせているのは、グラフの探索のためであった、Neo4j(GQL)では MATCH (src)-[:DIRECTED*]->(dst) にてその指示が完了しているので、そこを考える必要がなくなっている？あとは、後戻り防止のために訪問済みかどうかチェックが付けられればいいのだけど。*1
MATCH (src)-[:DIRECTED*]->(dst)
WHERE src.u = 3
RETURN dst;

f:id:panzer-jagdironscrap1:20180802235638p:plain

*1:そしてそのような処理はFOREACHでできそう

SoundHound Inc. Programming Contest 2018 - (Ordinary Beauty) 再考

AtCoder アルゴリズム 競技プログラミング

問題は単純なのだが、解法が全然思いつかず。

問題

C - Ordinary Beauty

  • N, M, D が与えられるとき
  • 1 ～ N までの種類の整数を使って
  • サイズMの数列を作ったとき
  • それぞれの隣り合う要素の差がDになるものの合計値を数列の美しさとして定義する

各要素が 1 以上N以下の整数である長さMの数列は全部でN^M通り存在します。 このN^M通りの数列すべてに対して美しさを求めて、それらの平均を出力してください。

n, m, d = 2, 3, 1 のとき、並べ替えのパターンと数列の美しさは

111 = 0 
112 = 1 
121 = 2 
122 = 1 
211 = 1 
212 = 2 
221 = 1 
222 = 0

考えたこと

  • 数列 [ 1, 2, 3 ... n ] から重複を許して m 個選んで並び替えたときの要素m-1個すべて差分を数え上げれば答えが出るな！（死）
  • 上記は考えたのだけど、問題の制約からnもmも10^9まで行くので間違いなく制限時間に間に合わない→解法が思いつかず寝る

方針

以下、解説のリーディング

期待値の線形性を利用して数列の美しさの算出を分解する

隣り合う 2 項は m − 1 通り存在します。

わかる（自明）。サイズmの数列を作るので、間に入るそれぞれの要素の差分はm-1個になるはず。

期待値の線形性から、m − 1 通りそれぞれについて差の絶対値が d である確率を求めて、足し上げれば答えが求まります。

は？なんで（半ギレ）要は数列考える際に、m 個選んで並び替えするということは必要なく隣り合う２つの要素の差を考えてm-1個足し上げると答えになるようです。めちゃくちゃ不思議。期待値の線形性については　和の期待値は期待値の和 | 高校数学の美しい物語　が参考になりました。

リンク先の「期待値の線形性の応用例2」が、そのまま今回の問題に適用できるので解説の画像を作りました。

例

f:id:panzer-jagdironscrap1:20180709114308p:plain

問題

f:id:panzer-jagdironscrap1:20180709115138p:plain

d = 0の場合と d != 0の場合で場合分けする

確率を求める処理を、d = 0の場合と d != 0の場合で場合分けします。これは単にその２通りで計算が変わるからでしょう。

1 から n までの整数のペア (a, b) の差の絶対値が d である確率を求めます。
d = 0 であるとき、条件を満たすペアは (1, 1), . . . ,(n, n) の n 個です。よって、確率は n / n^2 = 1 / n です。

与えられた数1~nまでを使用して同じものを並べるだけなのでn通りあるはず。全体はn^2通りあるので、d = 0の場合の確率は 1 / n。

d != 0 であるとき、条件を満たすペアは
(1, d + 1), . . . ,(n − d, n) と
(d + 1, 1), . . . ,(n, n − d) の
2(n − d) 個です。よって、確率は 2(n−d) / n^2 です。

これも考えてみれば簡単で、1~2のカードを重複を許して２枚並べてその差分が１になるのは(1,2)のときと(2,1)のとき。これを一般化したものとわかる。

解答コード

コード自体は短く、小数点以下の桁数を0埋めしていると正解になった。

lines = $stdin.read
array = lines.split("\n")
N,M,D = array[0].split(" ").map(&:to_i)

ans = if D.zero?
        1.quo(N)
      else
        (2*(N - D)).quo(N**2)
      end

puts "%.10f" % ((M-1)*ans).to_f

Submission #2816342 - SoundHound Inc. Programming Contest 2018 -Masters Tournament-

AWS GlueでSparkのDataframeを使う

PySpark AWS Python

AWS GlueでSparkのDataframeを使う

Glue上のクラス構造

docs.aws.amazon.com

  • 引用

Apache Spark の主要な抽象化の 1 つは SparkSQL DataFrame で、これは R と Pandas にある DataFrame 構造に似ています。DataFrame はテーブルと似ており、機能スタイル (マップ/リデュース/フィルタ/その他) 操作と SQL 操作 (選択、プロジェクト、集計) をサポートしています。
これらの制限に対応するために、AWS Glue により DynamicFrame が導入されました。DynamicFrame は、DataFrame と似ていますが、各レコードが自己記述できるため、最初はスキーマは必要ありません。代わりに、AWS Glue は必要に応じてオンザフライでスキーマを計算し、選択 (または共用) タイプを使用してスキーマの不一致を明示的にエンコードします。これらの不整合を解決して、固定スキーマを必要とするデータストアとデータセットを互換性のあるものにできます。

こう書かれてはいるが、DynamicFrameは少し自由度が低いように感じられる（S3やRDSへの接続が可能なのはいいんだけど）。とは言えDynamicFrameからDataFrameへの変換、そしてその逆が可能であるので、やりたいことは実現できた。

DynamicFrameからDataFrameへの変換

toDF
toDF(options)

# DynamicFrame -> Spark DataFrame
src_s3_df = DynamicFrame.toDF(<元のDynamicFrame>)
  • DynamicRecords を DataFrame フィールドに変換することにより、DynamicFrame を Apache Spark DataFrame に変換します。新しい DataFrame を返します。

DataFrameからDynamicFrameへの変換

fromDF
fromDF(dataframe, glue_ctx, name)

# Spark DataFrame -> DynamicFrame
result_s3 = DynamicFrame.fromDF(<加工したDataFrame>, glueContext, 'result_s3')
  • DataFrame フィールドを DynamicRecord に変換することにより、DataFrame を DynamicFrame に変換します。新しい DynamicFrame を返します。

ここまでをまとめると以下のような感じ

f:id:panzer-jagdironscrap1:20180621180055p:plain

DataFrameを使った処理など

連番作成

最初はrow_number()を使おうとしたのだけど、うまくいかなかったので zipWithIndex を使った。DataFrameに生えているrddを使えばOK。中のデータをいじるときはrddを更新したほうがよさそう。

rdd_indexed = dataframe.rdd.zipWithIndex().map(lambda x: (x[0][0],x[0][1],x[1]+1))
df = rdd_indexed.toDF(['id','score','rowNum'])
df.show()

カラムの追加、リネーム

withColumn, withColumnRenamedというものがDataFrameに生えているのでそれを使う。表形式のデータを変更したい場合はDataFrameに生えているメソッドでだいたい解決しそう。

.withColumn(lit('固定値'))
.withColumnRenamed('from', 'to')

あとはこの調子でデータを変形してDynamicFrameに戻せばまた連携できる