ta7uw’s gist

競プロとかサーバーサイド開発について書いてます

Gradle のビルドタスクに Protocol Buffers から Java ソースファイルを生成するタスクを組み込む

はじめに

Protocol Buffers ( 以下、protobuf ) で定義されたスキーマ ( .proto ファイル) を protoc コマンドによってコンパイルすることで JavaC++Python、Go などのクラスや構造体を生成できます。Java のクラスを生成した場合、 lombok で生成されるような 、getter、setter、builder メソッドが自動生成され、また protobuf はシリアライズ形式であるように serialize、deserialize の API も提供されます。Java 以外の言語にもおいても同様の機能は提供されます。

protobuf のスキーマは可読性が高く、言語のデータ型から独立して型を定義できるところがいいと思います。また、シリアライズ形式としての protobuf はシリアライズ・デシリアライズが高速でメモリの使用を抑えることができ、データ量も少なくなるので通信にも向いていると言われています。アプリケーションが分割され複数のサービス間で通信を行うことが多い現在では protobuf が役に立つ機会も多いのではないでしょうか。

protobuf はスキーマ定義から実際の利用まで幅広くカバーできており、いくつかの場面で有用ですが、protoc コマンドを都度実行するのは実際の開発においてはやや手間がかかり、めんどうです。

一般的な開発では Gradle のようなツールを使いビルドを自動化していると思います。protobuf においても Gradle の plugin が提供されており、ビルドスクリプトに protobuf のコンパイル作業を組み込むことができます。protobuf のコンパイルJavaソースコードコンパイルする流れに組み込むことで扱いやすいツールになると思います。

build script

実際に Gradle のビルドスクリプト ( build.gradle.kts ) を書いていきます。以下では Kotlin DSL でビルドスクリプトを記述します。

まずはじめに protobuf の Gradle plugin を追加します。

plugins {
    id("com.google.protobuf") version "0.8.11"
}

続いて protobuf 用の設定です。

sourceSets {
    main {
        proto {
            srcDir("src/main/proto")
        }
    }
}

dependencies {
    implementation("com.google.protobuf:protobuf-java:3.11.1")
}

protobuf {
    // Configure the protoc executable
    protoc {
        // Download from repositories
        artifact = "com.google.protobuf:protoc:3.11.1"
    }

    generatedFilesBaseDir = "$projectDir/src"

    generateProtoTasks {
        ofSourceSet("main").forEach {
            it.doFirst {
                delete("$generatedFilesBaseDir/main/java")
            }
        }
    }
}

簡単に説明すると、src/main/proto 以下の .proto ファイルから src/main/javaJava クラスを生成するようなスクリプトになっています。protoc コマンドに使うコンパイラは直接リポジトリからダウンロードすることで可搬性をもたせています。

IntelliJ で利用する場合は idea plugin を追加し、以下の記述を加えるといいです。

idea {
    module {
        generatedSourceDirs.add(file("src/main/java"))
        sourceDirs.add(file("src/main/java"))
    }
}

これで準備は完了しました。Gradle の assemble task を実行すると protobuf 関連のコンパイルタスクも組み込まれます。

コード生成

実際に protobuf のスキーマ定義から コード生成までを試します。 以下の proto ファイル ( Base.proto )を使います。

syntax = "proto3";

package com.examples;

import "google/protobuf/timestamp.proto";

message User {
    string name = 1;
    string email = 2;
    google.protobuf.Timestamp createdAt = 3;
}

このスキーマから Java ソースファイルを生成してJava 側から呼び出してみます。
Gradle の multi module 構成で別の module から呼び出してみます。

呼び出す側の module に protobuf module を追加します。

dependencies {
    implementation(project(":protobuf"))
    implementation("com.google.protobuf:protobuf-java:3.11.1")
}

実際の Java からは以下のように操作できます。

public class ApiApplication {
    public static void main(String[] args) throws Exception {
        var user = Base.User.newBuilder()
                .setName("taro")
                .setEmail("xxx@example.com")
                .setCreatedAt(Timestamp.newBuilder()
                        .setSeconds(1000000)
                        .build())
                .build();

        // serialize
        var data = user.toByteArray();

        // deserialize
        var content = Base.User.parseFrom(data);

        System.out.println(content.toString());
    }
}

参考

github.com

orElse()とorElseGet()の違い ( Java Optional )

はじめに

orElse()orElseGet()Optional<T> から値を取り出すときに使います。両者とも Optional が空でなければ中身の値を返しますが、Optional が空の場合は orElse(T other)otherorElseGet(Supplier<? extends T> supplier)supplier.get() の結果を返します。

引数の型が違う意外に差異がなさそうに思えますが、挙動に違いがあります。

orElse()

orElse()について。とりあえず、以下のコードを見てみます。

public class Main {
    public static void main(String[] args) {
       var emptyData = Optional.empty();
       var res = emptyData.orElse(createData());
       System.out.println(res);

       System.out.println("-------");

       var data = Optional.of("data");
       var res2 = data.orElse(createData());
       System.out.println(res2);
    }

    public static String createData() {
        System.out.println("call createData");
        return "hello";
    }
}

結果がこちら

call createData
hello
-------
call createData
data

Optional が空かどうかに関係なく createData() が呼び出されていることがわかります。orElse() の引数は Optional が空かどうかに関係なく評価されるということです。

orElseGet()

orElseGet() について。

public class Main {
    public static void main(String[] args) {
       var emptyData = Optional.empty();
       var res = emptyData.orElseGet(() -> createData());
        System.out.println(res);

        System.out.println("-------");

        var data = Optional.of("data");
        var res2 = data.orElseGet(() -> createData());
        System.out.println(res2);
    }

    public static String createData() {
        System.out.println("call createData");
        return "hello";
    }
}

結果がこちら

call createData
hello
-------
data

optional が空の時だけ createData() が呼ばれています。Optional が空の時だけ引数の Supplier<T> が遅延評価されていることがわかります。

おわりに

orElse() は Optional が空かどうかにかかわらず必ず評価されるので、新たにインスタンスを生成する処理や API や DB へのアクセスなどを行う処理を引数にしてしまうとパフォーマンスに大きな影響を与えます。対して orElseGet() は Optional が空の時のみ遅延評価されて呼び出されるので無駄なインスタンス生成やアクセスを防げます。

基本的に orElseGet() を使えばいいと思います。orElse() はすでに代替のインスタンスが存在しているときとかなら使っても良さそうです。

ベルマン–フォード法 ( Bellman-Ford 法 )

ベルマン–フォード法

ベルマン–フォード法は単一始点の最短経路問題を解くためのアルゴリズムです。計算量は  O(  |E|\cdot|V|) (頂点数  |V| 辺数  |E| ) です。計算量を考慮するとダイクストラ法で単一始点の最短経路問題を解く方が高速ですが、ベルマン–フォード法には負閉路の検出が可能で負のコスト辺にも対応可能であるというメリットがあります。

負閉路検出の実装には注意が必要なポイントがあります。 今回は負閉路検出に着目して実装します。ベルマン–フォード法のアルゴリズムについては説明しないです。

負閉路検出

負閉路検出を  |V| 回目のループでも更新かあるかどうかで判定すると、始点から終点までの経路に含まれない閉路 も検出してまいます。負閉路検出の際は以下のどちらの負閉路を検出したいのか注意します。

  • 始点から到達できる負閉路
  • 始点から到達できる負閉路であって、閉路から終点へ到達できる負閉路

前者は、 |V| 回目のループで更新かあるかどうかで判定することができます。後者は次のように判定を行います。

  • 負閉路検出用配列を用意して、 |V| 回のループを行い、更新があった箇所の配列の値を true に更新し他の頂点へ伝播させる

  • 終点の負閉路検出用配列の値が true のとき始点から終点までの経路に負閉路が含まれる

上記の内容を踏まえてベルマン–フォード法を実装します。

実装

struct edge {
    int from, to;
    ll cost;
};

class BellmanFord {
    int V;
    int E;
    vector<edge> edges;
    vector<ll> dist;
    vector<bool> negative;

public:
    BellmanFord(int v, int e) : V(v), E(e), negative(v) {
        dist.resize(V, INF);
    }

    void add_edge(int from, int to, ll cost) {
        edges.push_back({from, to, cost});
    }

    ll get_total_cost(int v) {
        return dist[v];
    }

    // v に到達するまでに負ループがあるかを検出する
    bool is_negative(int v) {
        return negative[v];
    }

    // ベルマンフォード法の実行・全辺の負閉路を検出 trueを返す時に負閉路を含む
    bool exec() {
        bool updated = false;
        dist[0] = 0;
        for (int i = 0; i < V; ++i) {
            for (int j = 0; j < E; ++j) {
                edge edge = edges[j];
                if (dist[edge.from] != INF && dist[edge.to] > dist[edge.from] + edge.cost) {
                    dist[edge.to] = dist[edge.from] + edge.cost;
                    if (i == V - 1) updated = true;
                }
            }
        }

        for (int i = 0; i < V; ++i) {
            for (int j = 0; j < E; ++j) {
                edge edge = edges[j];
                if (dist[edge.from] != INF && dist[edge.to] > dist[edge.from] + edge.cost) {
                    negative[edge.to] = true;
                }
                if (negative[edge.from]) {
                    negative[edge.to] = true;
                }
            }
        }
        return updated;
    }
};

ベルマン–フォード法を扱う問題

Segment Tree ( セグ木 )

Segment Tree

Segment Tree ( 以下セグ木 ) は区間を扱うのが得意なデータ構造です。 区間に対する操作を  O(  \log N ) で実現します。 詳しくは以下の資料を見るといいです( てきとう )。

www.slideshare.net

まとめるとセグ木は

  • 各ノードにどのようなデータをもたせるか
  • どのような操作でノードのデータを更新するか
  • 区間からデータを取り出す際にどのような操作を行うか

によって様々な機能が実現できる応用力が高いデータ構造です。

今回は以上の3つのポイントを柔軟に変更できるセグ木のライブラリを書きます( 遅延評価しない通常のセグ木を対象にします )。

実装

コードはまとめて最後に貼ります。各処理でやっていることをざっくり書いていきます。

初期化

初期化する際には以下を行います。

  • セグメント木のサイズを決定 ( 管理するデータのサイズ 以上になる最小の 2 冪 )
  • データの単位元の取得
  • 更新処理の取得 (  updater )
  • 区間操作処理の取得 (  operation )

 updater  operation にはラムダ式を使って実行したい操作を渡します。

更新  update(i, x)

  •  i 番目のデータに  x を与えて  updater の処理を実行
  • 更新したノードの親ノードのデータを operation で更新

区間クエリ  query(a, b)

  •  a,  b の他に今対象としているノード  k, ノード  k が管理する区間  [ l, r ) も引数にもつ
  • 区間  [ a, b ) にノードが管理する区間完全  [ l, r ) が含まれるまで子ノードに分割していく

ライブラリ

以下がセグ木のライブラリです。

template<class T>
class SegmentTree {

public:
    /**
     * @param N size
     * @param e identity element
     * @param operation operation for query
     * @param updater operation for update
     */
    SegmentTree(size_t N, T e, function<T(T, T)> operation, function<T(T, T)> updater)
            : e(e), operation(std::move(operation)), updater(move(updater)) {
        n = 1;
        while (n < N) {
            n *= 2;
        }
        data = vector<T>(2 * n - 1, e);
    }

    /**
     * iの値をxに更新
     * @param i index ( 0-indexed )
     * @param x  value
     */
    void update(int i, T x) {
        i += n - 1;
        data[i] = updater(data[i], x);
        while (i > 0) {
            i = (i - 1) / 2;
            data[i] = operation(data[i * 2 + 1], data[i * 2 + 2]);
        }
    }

    /**
     * [a, b)の区間でクエリを実行
     */
    T query(int a, int b) {
        return query(a, b, 0, 0, n);
    }

    /**
     * 添字でアクセス
     * @param i index ( 0-indexed )
     */
    T operator[](int i) {
        return data[i + n - 1];
    }

private:
    int n;
    vector<T> data;
    T e;
    function<T(T, T)> operation;
    function<T(T, T)> updater;

    T query(int a, int b, int k, int l, int r) {
        // 交差しない
        if (r <= a || b <= l) return e;
        // 区間 [a, b) に l, r が含まれる
        if (a <= l && r <= b) return data[k];
        // 左の子
        T c1 = query(a, b, 2 * k + 1, l, (l + r) / 2);
        // 右の子
        T c2 = query(a, b, 2 * k + 2, (l + r) / 2, r);
        return operation(c1, c2);
    }
};

verified

セグ木で解くことができる問題 (随時追加)

参考

ローリングハッシュ( Rolling Hash )

ローリングハッシュ

ローリングハッシュでは文字列をハッシュ (ある大きな整数のひとつ)として扱います。文字列  S に対してハッシュテーブルを  O( N ) であらかじめ求めておくことで、文字列  S区間  [l, r)ハッシュ値 O( 1 ) で返すことを実現します。 また、文字列の一致判定や最長共通接頭辞 (Longest Common Prefix) の長さを求めることを高速に行うことができます。

実装

ローリングハッシュのC++での実装です。 ハッシュの衝突には注意が必要です。

class RollingHash {
    static const ll base1 = 1009;
    static const ll base2 = 2009;
    static const ll mod1 = 1000000007;
    static const ll mod2 = 1000000009;
    vector<ll> hash1, hash2, pow1, pow2;

public:
    RollingHash(const string &S) {
        int n = (int) S.size();
        hash1.assign(n + 1, 0);
        hash2.assign(n + 1, 0);
        pow1.assign(n + 1, 1);
        pow2.assign(n + 1, 1);
        for (int i = 0; i < n; ++i) {
            hash1[i + 1] = (hash1[i] * base1 + S[i]) % mod1;
            hash2[i + 1] = (hash2[i] * base2 + S[i]) % mod2;
            pow1[i + 1] = (pow1[i] * base1) % mod1;
            pow2[i + 1] = (pow2[i] * base2) % mod2;
        }
    }

    /**
     * S の [l, r) のハッシュ値を返す
     * O(1)
     */
    inline pair<ll, ll> get(int l, int r) const {
        ll res1 = hash1[r] - hash1[l] * pow1[r - l] % mod1;
        if (res1 < 0) res1 += mod1;
        ll res2 = hash2[r] - hash2[l] * pow2[r - l] % mod2;
        if (res2 < 0) res2 += mod2;
        return make_pair(res1, res2);
    }

    /**
     * S のハッシュ値を返す
     * O(1)
     */
    inline pair<ll, ll> hash() const {
        return get(0, (int) hash1.size() - 1);
    }

    /**
     * LCP (Longest Common Prefix)
     * O( log N )
     */
    inline int getLCP(int a, int b) const {
        int len = min((int) hash1.size() - a, (int) hash1.size() - b);
        int low = 0, high = len;
        while (high - low > 1) {
            int mid = (low + high) >> 1;
            if (get(a, a + mid) != get(b, b + mid)) high = mid;
            else low = mid;
        }
        return low;
    }

    /**
     * hash h1 と 長さ h2_len の文字列の hash h2 を結合
     */
    pair<ll, ll> concat(pair<ll, ll> h1, pair<ll, ll> h2, int h2_len) {
        return make_pair((h1.first * pow1[h2_len] + h2.first) % mod1, (h1.second * pow2[h2_len] + h2.second) % mod2);
    }
};

ローリングハッシュを扱う問題

参考

最小全域木 (クラスカル法・プリム法)

最小全域木

無向グラフが与えられた時に、その部分グラフで任意の 2 頂点のを連結するような木を全域木と言います。また、辺にコストがある場合、使われる辺のコストを最小にする木を最小全域木と言います。最小全域木を求めるアルゴリズムとしてクラスカル法とプリム法と呼ばれるアルゴリズムがあります。今回はこれらをC++で実装しました。

クラスカル (Kruskal) 法

  • 計算量:  O(   E \log V ) (頂点数  |V|・辺の個数  |E|)
  • 辺をコストが小さい順にみていき、閉路ができなければ追加するという貪欲法
  • 閉路判定には UnionFind を使って、辺を追加する前にすでに連結成分に属しているかを判定する

冗長なので UnionFind の実装は省略してあります。

template<typename T>
struct edge {
    int from, to;
    T cost;
};

template<typename T>
T kruskal(vector<edge<T>> &edges, int V) {
    sort(edges.begin(), edges.end(), [](const edge<T> &a, const edge<T> &b) {
        return a.cost < b.cost;
    });
    UnionFind unionFind(V);
    T res = 0;
    for (edge<T> &e: edges) {
        if (unionFind.unit(e.to, e.from)) {
            res += e.cost;
        }
    }
    return res;
}

プリム (Prim) 法

  • 計算量:  O(   E \log V ) (頂点数  |V|・辺の個数  |E|)
  • 始点を選んで、最小全域木に属する辺を貪欲に追加していく
  • プライオリティーキューを使って最小コストの辺を貪欲に選んでいくと計算量を抑えられる(ダイクストラに似ている)
  • 疎グラフで有効
template<typename T>
struct edge {
    int from, to;
    T cost;
};

template<typename T>
T prim(vector<vector<edge<T>>> &edges, int V) {
    using Pi = pair<T, int>;

    T res = 0;
    vector<bool> used(V, false);
    priority_queue<Pi, vector<Pi>, greater<>> priorityQueue;
    priorityQueue.emplace(0, 0);
    while (!priorityQueue.empty()) {
        Pi p = priorityQueue.top();
        priorityQueue.pop();
        if (used[p.second]) continue;
        used[p.second] = true;
        res += p.first;
        for (edge<T> &e : edges[p.second]) {
            if (!used[e.to]) priorityQueue.push({e.cost, e.to});
        }
    }
    return res;
}

最小全域木を扱う問題

参考

  • 蟻本

二部グラフ判定

二部グラフ

二部グラフとは頂点集合を二つに分割したときに、それぞれの集合内の頂点同士を結ぶ辺が存在しないグラフのことです。ある頂点を選択したとき、その頂点に隣接する頂点は別の集合に属することになります。二部グラフであることと奇数長サイクルを含まないことは同値であり、問題の考察ポイントとなることが多いです。

二部グラフ判定

二部グラフ判定を行うコードです。C++で実装しています。 グラフが連結ならば以下のコード一度で二部グラフ判定を行うことができますが、連結でない場合はすべての頂点において探索する必要があることに注意が必要です。

using Graph = vector<vector<ll>>;
int colors[100005];
bool is_bipartite_graph(const Graph &graph, int v, int c) {
    colors[v] = c;
    for (int u: graph[v]) {
        if (colors[u] == c) {
            return false;
        }
        if (colors[u] == 0 && !is_bipartite_graph(graph, u, -c)) {
            return false;
        }
    }
    return true;
}

二部グラフ判定を扱う問題

二部グラフ判定が重要なポイントになる問題です

Binary Indexed Tree ( BIT )

Binary Indexed Tree

Binary Indexed Tree (以下、BIT) は以下を実現するデータ構造です。

  •  sum(i) :
    累積和  a_1 +  a_2 +  a_3 + ... +  a_i O(  \log N )で計算
  •  add(i, x) :
     i  x が与えたれたとき  a_i  x を加算することを  O(  \log N ) で行う
  • 素数  N に対してサイズ  N の配列を持つ

実装方法

累積和  sum(i)

 i までの和を求めるには  i から  0 まで、 i から最後の  1 ビットを減算しながら、 i の場所の値を加算していく。 i の最後の  1 ビットは i & -i と書く

値の更新  add(i, x)

 i の値に  x を加えるためには、 i から  N まで  i に最後の  1 ビットを加算しながら、 i の場所の値に  x を加算していく

ライブラリ

以下は C++ の BITのライブラリです。

template<typename T>
class BinaryIndexedTree {
    int N;
    vector<T> data;
public:
    BinaryIndexedTree(int N) : N(N) {
        data.resize(N + 1, 0);
    }

    T sum(int k) {
        T res = 0;
        for (; k > 0; k -= k & -k) {
            res += data[k];
        }
        return res;
    }

    void add(int k, T x) {
        for (; k <= N; k += k & -k) {
            data[k] += x;
        }
    }

    /**
     * v1 + v2 + ⋯ + vx ≧ W となる最小の 𝑥 を求める
     */
    int lowerBound(int w) {
        if (w <= 0) return 0;
        int x = 0;
        int k = 1;
        while (k * 2 <= N) k *= 2;
        for (; k > 0; k /= 2) {
            if (x + k <= N && data[x + k] < w) {
                w -= data[x + k];
                x += k;
            }
        }
        return x + 1;
    }
};

ライブラリの動作確認に以下の問題が使えます。

AOJ: Range Sum Query

応用

二分探索の搭載

上記のライブラリの中にもありますが、二分探索を使って累積和が  w 以上となる最小の  x を求めるができます。 二分木の枝分かれに従い二分探索することで実現できます。

二次元配列のBIT

 H×W の二次元配列に BIT を適用して累積和と値の更新を高速に行うことができます。要素数  W の BIT を  H 個つくり BIT が BIT をつようにして管理します。

  •  add(h, w, x) :
     V_hw に値  x を加える
  •  sum(h, w) :
     (1, 1) から  (h, w) までの範囲の累積和を求める
  •  sum(h1, w1, h2, w2) :
    左上の座標  (h1, w1) , 右下の座標  (h2, w2) に含まれる値の累積和を求める

以下が 2 次元BIT のライブラリです。

template<typename T>
class BinaryIndexedTree2D {
    int H;
    int W;
    vector<vector<T> > data2d;
public:
    BinaryIndexedTree2D(int H, int W) : H(H), W(W) {
        data2d.resize(H + 1, vector<T>(W + 1, 0));
    }

    T sum(int h, int w) {
        T res = 0;
        for (int i = h; i > 0; i -= i & -i) {
            for (int j = w; j > 0; j -= j & -j) {
                res += data2d[i][j];
            }
        }
        return res;
    }

    /**
     * 左上の座標(h1, w1), 右下の座標(h2, w2) に含まれる値の累積和
     */
    T sum(int h1, int w1, int h2, int w2) {
        return sum(h2, w2) - sum(h1 - 1, w2) - sum(h2, w1 - 1) + sum(h1 - 1, w1 - 1);
    }

    void add(int h, int w, ll x) {
        for (int i = h; i <= H; i += i & -i) {
            for (int j = w; j <= W; j += j & -j) {
                data2d[i][j] += x;
            }
        }
    }
};

ライブラリの動作確認に以下の問題が使えます。

AOJ: Taiyaki-Master and Eater

BITで解くことができる問題

見つけ次第更新していきます。

参考