線香を焚きながら

勉強したこと置き場

Jacksonを使って、CSVをJSONに変換する(した)

はじめに

Javaです。
ちょっと前に異動してJava(Spring)を書くことになったので、お勉強を兼ねてメモ。

業務で、CSVデータをElasticsearchに手作業でぶち込むことになり、その方法としてBulk APIが使えるので、 じゃあいっちょCSVJSONに変換するか、となった次第(正確にはJSONデータでは無いが)。

上司に聞いてみると、Jacksonというライブラリが、 Spring Boot でJSONを構築するために使われており、 それ使えばいけるんちゃう?とのことだったので意気揚々と開始する。

やりたいこと

以下の方針で、CSVデータをJSONデータに変換する。

  1. 変換したい対象のデータのPOJOを定義する
  2. CSVデータを読み込んでPOJO(のコレクション)に格納する
  3. POJOJSONデータとして出力する

今回は、変換処理を CommandLineRunner として実装する。

想定する入力・出力サンプルは以下の通り。

  • Input
1,Taro,Hello
2,Jiro,Good morning
3,Saburo,Good afternoon.
  • Output
{"index":{"_index":"test"}}
{"userId":"1","username":"Taro","comment":"Hello"}
{"index":{"_index":"test"}}
{"userId":"2","username":"Jiro","comment":"Good morning"}
{"index":{"_index":"test"}}
{"userId":"3","username":"Saburo","comment":"Good afternoon."}

Bulk API の仕様に沿った形式であり、JSONではない(JSONのオブジェクトが\nで連結されている)。

実装

github.com

特にCSVの読み込み処理の実装に時間が掛かった。 知らないクラスがたくさん出てくるので、それらの関係を紐解きながら適切な実装を探すのは結構大変だ。

ちなみに、今回の処理で重要と思われるクラスは以下(なんでこんなにあるんだ…)。

  • ObjectMapper / CsvMapper
    • データとPOJOを紐づけるための起点となるクラス。ここから、さまざまに派生する。
  • ObjectReader
    • データの読み込み処理を提供するクラス。 ObjectMapper から作られる。
    • 何の変換もなく読み込むだけなら ObjectMapper#read() とかで良さそうだが、 スキーマ構造を詳細に指定したい場合は ObjectMapper#readerFor() から ObjectReader を作って、 with() 等でスキーマを指定する。
    • もしくは、 ObjectMapper#reader()スキーマを食わせてもいけるかも(試してない)。
  • FormatSchera / CsvSchema
    • データのスキーマ構造(CSVならデリミタが何、とかヘッダ行はあるか、とか)を定義する。
    • CsvSchemaFormatSchema インタフェースの実装クラス。
    • スキーマ関連の挙動がまだよくわかっていない。
    • JSONにもスキーマ構造を指定する方法があるはずだが、まだ整理できていない。
  • MappingIterator<T>
    • データがコレクション型として読み込まれる場合。
    • readValues() 等で作って、あとは普通のイテレータとして使用できる。

考慮すべきこと

  1. 今回は、(おそらく最も一般的な)CSVの形式を想定したため、 特に CsvSchera に追加の設定をする必要はなかった(あえてCsvSchemaを定義しているが、不要だったかも)。 実際に使用する際は、 CsvSchema をデータに合わせて変更する必要がある。
  2. null などの値が混入した場合は全く考慮されていないので、こちらも検討が必要。
  3. ソースコード内にPOJOやらファイル名やらベタ打ちしてるので、何とかしたいなあ… (一度しか使われない可能性が高いので、あまりリファクタリングするモチベーションがない)

最後に

JavaでもHaskellみたいに型アノテーションかけるといいなあ。JavaDoc見ながら書いているが、混乱しまくる。

参考

CSVのパーサを書いた

せっかくHaskell使っているのに、パーサライブラリをまともに使ったこと無いな、ってことで書いてみた。 ライブラリは無難に attoparsec を使う。パースした結果、CSVがリストになる。

github.com

CSVの規則は、RFC4180(の日本語訳)を参考に。

CSVファイルの一般的書式 (RFC4180 日本語訳) - アルプス登山の玄関口・笠井家

もともとCSVを平坦なJSONに変換しようとしていたので、パッケージ名が csv2json となっている。 書いてみた感想としては、パーサライブラリに慣れていないことを除けば、大凡平易に書けるなと感じた。

遅延データ構造におけるメモ化再帰を理解する

Introduction

Haskellにおけるメモ化がどんな風に動いているか、ようやくわかってきたのでメモ。

競技プログラミングでよく使用されるアルゴリズムに「動的計画法(DP)」と呼ばれるものがある。 その中では、メモ化(一度計算した値を保存しておいて再び同じ計算をする代わりに保存した値を返すこと)というテクニックが使用されている。

Haskellでも、もちろんメモ化を実装することができる。メモ化について以下のような実装があるようだ。

  1. メモ用のデータ構造として遅延しない(しなくても大丈夫な)データ構造を使用するパターン(今回はMap)。 値を辞書(もしくはテーブル)として保持し、新しいデータだった場合は辞書に追加する(値を追加した新しい辞書を返す)。 github.com

  2. メモ用のデータ構造として遅延するデータ構造を使用するパターン(今回は遅延リスト)。 値を遅延リストの要素として保持し、新しいデータだった場合に初めてリストの要素を計算する。 計算(評価)されたら、今後は評価済の値が使用される。 再帰的な計算を実行する場合は、こちらの方が都合が良さそうである。 qiita.com こちらはメモ化に対応した不動点演算子を使用するバージョン(データ構造は無限の2分木)。 tanakh.hatenablog.com

比較的どのようなことをしているのかがわかりやすいのは1である。 一方、2は少しわかりづらい。 これは、遅延評価によってどのタイミングでデータが更新されるかが不明瞭だからだと思われる。

そこで、遅延評価に基づいた簡約計算を実行してみて、実際にどのように値の更新が行われるのか確認する (実際に計算できるものでも、理屈がわからないと安心して使えないので)。

簡約計算

ここでは、2で出てきた定義をそのまま使用する。

fib :: Int -> Integer
fib 0 = 0
fib 1 = 1
fib n = fibList !! (n - 2) + fibList !! (n - 1)

fibList :: [Integer]
fibList = map fib [0..]

fib 5が、どのように簡約されるのか見よう。 簡単のため、単純な和はすぐに評価されるものとして書く (今回はデータ構造の遅延に着目しているので、これでも問題ない、と思う)。 実際に計算されている様子は、GHCiデバッガを使用して確認することもできる。

fib 5
= fibList !! 3 + fibList !! 4
= fibList !! 3 + (map fib [0..]) !! 4
= fibList !! 3 + ((fib 0):(fib 1):(fib 2):(fib 3):(fib 4):_) !! 4
= fibList !! 3 + fib 4
= fibList !! 3 + (fibList !! 2 + fibList !! 3)
= fibList !! 3 + (fibList !! 2 + ((fib 0):(fib 1):(fib 2):(fib 3):(fib 4):_) !! 3)
= fibList !! 3 + (fibList !! 2 + fib 3)
= fibList !! 3 + (fibList !! 2 + (fibList !! 1 + fibList !! 2))
= fibList !! 3 + (fibList !! 2 + (fibList !! 1 + ((fib 0):(fib 1):(fib 2):(fib 3):(fib 4):_) !! 2))
= fibList !! 3 + (fibList !! 2 + (fibList !! 1 + fib 2))
= fibList !! 3 + (fibList !! 2 + (fibList !! 1 + (fibList !! 0 + fibList !! 1)))
= fibList !! 3 + (fibList !! 2 + (fibList !! 1 + (fibList !! 0 + ((fib 0):(fib 1):(fib 2):(fib 3):(fib 4):_) !! 1)))
= fibList !! 3 + (fibList !! 2 + (fibList !! 1 + (fibList !! 0 + fib 1)))
= fibList !! 3 + (fibList !! 2 + (fibList !! 1 + (fibList !! 0 + 1)))
= fibList !! 3 + (fibList !! 2 + (fibList !! 1 + (((fib 0):1:(fib 2):(fib 3):(fib 4):_) !! 0 + 1)))
= fibList !! 3 + (fibList !! 2 + (fibList !! 1 + (fib 0 + 1)))
= fibList !! 3 + (fibList !! 2 + (fibList !! 1 + (0 + 1)))
= fibList !! 3 + (fibList !! 2 + (fibList !! 1 + 1))
= fibList !! 3 + (fibList !! 2 + ((0:1:1:(fib 3):(fib 4):_) !! 1 + 1))
= fibList !! 3 + (fibList !! 2 + (1 + 1))
= fibList !! 3 + (fibList !! 2 + 2)
= fibList !! 3 + ((0:1:1:2:(fib 4):_) !! 2 + 3)
= fibList !! 3 + (1 + 2)
= fibList !! 3 + 3
= (0:1:1:2:3:_) !! 3 + 3
= 2 + 3
= 5

再帰的に遅延リストが呼ばれているが、このとき一度計算された要素は全てその結果で置き換えられていることがわかる (例えば15行目以降に出てくるfibListの全てについて、その第1要素はサンクではなく評価済の値 (1) となっている)。 上記の結果は、Haskellの評価戦略が遅延評価である事、およびfibListの実体がただ1つである事に拠る (メモ化せずに計算したときfib 1といった計算が大量に発生するのは、計算毎にfib 1の実体が異なっているからである)。

まとめ

上記のように簡約計算を実行してみることで、メモ化の構造(特に遅延データ構造)がどのようにしてメモ化しているのかが理解できる。 また、実際に使うときにどのように値がストアされていくのかを知っておくと、安心して使えそうである。

なお、競技プログラミングでは、こういうメモ化するためのデータ構造には配列(Array)が有力なようで、そのルックアップの計算量はO(1)である。 他方今回記載したメモ化用のデータ構造はMap/リスト/2分木だが、それぞれルックアップに必要な計算量がO(\log n)/O(n)/O(\log n)であり圧倒的に遅い。 配列を使用することを前提にした制限時間になっている以上、上記で検討したメモ化は採用できない。 また、遅延データ構造では問題にならないが、遅延しないデータ構造を使用する場合、 immutableなデータ構造(例えばIArray)だと新しい辞書を返すたびに辞書の再構築が必要となり、こちらもコストが大きい。 そのため代わりに、他の手続き型言語と同様、mutableな配列(MArray / MVector)を使ってメモ化する必要がある。

参考