More than 5 years have passed since last update.

Distributed Code Jam（DCJ）のすすめ

Last updated at 2017-07-06Posted at 2017-06-12

Googleが2015年からDistributed Code Jamという分散コンピューティングのプログラミングコンテストを開催している。最大100台のノードを使って問題を解く。ビッグデータとかGPGPUがもてはやされている昨今では実用的だし、普段の競技プログラミングとは一風変わっていて面白い。ちょっととっつきづらいところがあるので、解説を書いた。

参加方法

普通のGoogle Code Jamは誰でも参加できるけれど、いかにGoogleといえども計算機資源に限りがあるのか、Google Code Jamで一定の成績を取った人しか参加できない。2015年はRound 3進出（Round 2で500位以内）、2016年と2017年はRound 2進出（3回開催されるRound 1のどれかで1000位以内）だった。

賞品

Round 1で500位以内でTシャツ。GCJでTシャツを獲得していても1枚だけ。GCJでTシャツを獲得した人の分のTシャツが繰り下がることはない（たぶん）。Round 2の上位20位で本戦進出。本戦3位以内で賞金。1位ならば1万ドル！

GCJのRound 1を突破した人が、GCJ Round 2とDCJ Round 1に進めて、Tシャツを獲得できる順位は、それぞれ、1000人と500人。この条件を見るとDCJでTシャツを獲得するほうが難しそうだが、DCJのほうが後だからGCJでTシャツを獲得して満足するのか、面倒だからか参加しない人が多く、DCJのほうが大分楽にTシャツを獲得できる印象がある。この記事によって参加する人が増えたらTシャツ獲得が難しくなりそうだけど、来年からはGCJでTシャツを獲得するぞ💪という決意でこの記事を書いている。

詳細

最初の箇条書きを翻訳。

Distributed Code Jamでは、出力ではなくコードを提出し、サーバーでコンパイルと実行が行われる
提出したコードは複数のコンピュータ（ノード）で実行される。ノード間での通信にはmessageライブラリを使う。問題文に別の記載が無い限り、各ノードは最大1000個のメッセージを送信でき、メッセージのサイズの合計は8MB以内。合計サイズの指定にかかわらず、個々のメッセージのサイズは8MBを超えてはいけない。ノードAからノードBに送ったメッセージが読まれる前に、ノードAからノードBに追加のメッセージを送ることはできない
標準入力は読んではいけない。入力は各問題で指定されたライブラリの関数で提供される。各ノードの入力は同じ（訳注：「ノードが故障している」とか言って、ノードによって入力が異なる問題もある）。C++を使用する場合、 #include "problem_name.h" としてライブラリをinclude/importする必要がある。Javaを使用する場合、入力は自動的にimportされる
ちょうど1個のノードが正しい答えを標準出力に書く。他のノードは何も出力してはいけない
Small datasetにコードを提出した場合、2分後にacceptされたかどうかの結果が得られる。この間に他の提出を投稿することはできないから気をつけて（他の問題にコードを提出することはできる）
Large datasetにコードを提出した場合、10分経過すれば、再提出することができる。（コンテスト終了後に）最後に提出されたコードがジャッジに使用される
全てのノードは問題で与えられた制限時間内に（終了コード0で）終了しなければならない

ローカルテスト環境の構築

コンテスト前にこの作業は必須。いちいちコードを提出して確認するわけにはいかない。

の後半に詳細が書かれている。

私はWindowsを使用している。Windows版のローカルテストツールも提供されているかと思いきや、MinGW用だった。Linuxを用意したほうが何かと楽だと思う。VirtualBoxで仮想マシンを作って、UbuntuとVirtualBoxのGuest Additionをインストールして、フォルダ共有機能でDCJのコードを置いているフォルダを共有した。

をダウンロードして、

$ mkdir test_tool
$ tar -jxvf dcj_linux.tar.bz -C test_tool/

で解凍。

$ alias dcj={unpack_directory}/dcj.sh

として dcj で実行できるようにする。 alias に指定したコマンドがそのまま使用されるので、 {unpack_directory} は絶対パスで指定したほうが良い。ログインする度に alias するのが面倒なら、 .bashrc にも書いておくと良いかも。

テスト用に、

をダウンロードして、 #include <sum_all.h> を消して、↓のコードを書き加える（これは書き方のサンプルで、実行して確認するためのものではないのか、sum_all.hが見つからない）。

long long GetN() {return 1000LL;}
long long GetNumber(long long i) {return i;}

$ dcj build --source sum_all_example.cpp
$ dcj run --executable sum_all_example --nodes 10

を実行して、 499500 という答えが出力されればOK。

をダウンロードして、拡張子を .h に書き換え（どう見てもヘッダファイルなので、拡張子が .cpp なのはミスだと思う）、ソースコードと同じディレクトリに置いておくと、手元の環境でコードを書くときにmessageライブラリの関数の補完が効いて楽。

messageライブラリ

関数	説明
int NumberOfNodes()	ノード数の取得。問題文にも書かれている
int MyNodeId()	自分のIDを取得。 `0` ～ `NumberOfNodes()-1`
void PutChar(int target, char value) void PutInt(int target, int value) void PutLL(int target, long long value)	`value` を `target` 向けの送信バッファに積む
void Send(int target)	積んだメッセージを `target` に送信
int Receive(int source)	`source` からのメッセージを受信
char GetChar(int source) int GetInt(int source) long long GetLL(int source)	`source` 用の受信バッファから値を読み出す

使用例

ノード0で、

PutChar(3, 'a');
PutInt(3, 1);
PutLL(3, 1000000000000LL);
Send(3);

を実行すると、ノード3では

Receive(0);
char c = GetChar(3);  // 'a'
int i = GetInt(3);  // 1
long long ll = GetLL(3);  // 1000000000000LL

としてメッセージを受信できる。もしノード3で Receive(0) を実行した時点で、ノード0で Send(3) が実行されていなければ、 Receive(0) はメッセージを受信するまで待つので、タイミングに気を使う必要は無い。

ヘッダファイルのコメントを読むと、 Receive(-1) で任意のノードからメッセージを受信できるらしいけど、使う機会は無さそう。

おそらく、メッセージの送信回数の上限（1000回）は、 Put??? の実行回数ではなく、 Send(target) の実行回数。

コードの書き方

最初はどこから手を付けて良いか分からない。基本的には、1個のノードで実行する場合の解法を考えて、処理する部分を上手いこと分割すれば良い。たいていの問題は、各ノードが自分の担当範囲を処理してノード0に送信し、ノード0が結果を集計するという方針で行けるはず。サンプルのall_sum_example.cppでは剰余で担当範囲を分けているけれど、処理は前後の値に依存することが多いので、1個のノードがまとまった区間を担当するようにした方が良い。ノード0が自分で自分にメッセージを送信し、他のノードからのものと同様に受信するということができるので、処理のときにノード0を特別扱いする必要は無い。特別扱いしないほうが処理が簡潔になるはず。

2017年のRound 1のB問題pancakesを例に、実際に解いてみる。

問題概要

円形のテーブルに D 人の客がいて、時計回りに 0 から D-1 の番号が付いている。各客は自分の番号のパンケーキが食べたい。あなたは、 D 枚のパンケーキを持っていて、テーブルを時計回りにグルグル回ってパンケーキを配っていく。ただし、パンケーキは上から順番にしか取れない。テーブルを何周すればパンケーキを配り終えられるか？

1個のノードで実行する場合の解法

1, 3, 10 のようにパンケーキの番号が単調に増えているならば、1周する間に全部配ることができる。 9, 1 のように番号が減っていたら1周しないと 1 には戻れない。結局、スタックの中で番号が減少している箇所を数えれば良い。コードで書くとこんな感じ。

long long n = GetStackSize();
long long answer = 0LL;
long long prev = -1LL;
for (long long i=0; i<n; i++)
{
    long long t = GetStackItem(i);
    if (t < prev)
        c++;
    prev = t;
}
cout<<answer<<endl;

担当範囲の分割

この問題では単にスタックをノードごとに分割すれば良い。この分割がちょっと面倒で、しっかり n が小さいテストケースも含まれているらしい。下手な分け方をすると、 n がノード数より小さいときに落ちる。余分なノードには何も処理をさせないなどの手もあると思うが、私は最初に次のようなコードを書いている。

long long N  = NumberOfNodes();
long long ID = MyNodeId();

long long n = GetStackSize();
long long w = (n+N-1)/N;
long long l = ID*w;
long long r = min(ID*w+w, n);

各ノードが [l, r) を処理する。あとは、 l>=r の場合（自分が担当する部分が無い場合）に正しく動くようにすれば良い。このときに、後の集計に影響を与えない結果（この問題ならば、「番号が減少する箇所は0個」）を返しておくと、集計のコードが簡潔になる。

本番のときに提出した解答

#include "message.h"
#include "pancakes.h"
#include <iostream>
#include <algorithm>

using namespace std;

int main() {
    long long N  = NumberOfNodes();
    long long ID = MyNodeId();

    long long n = GetStackSize();
    long long w = (n+N-1)/N;
    long long l = ID*w;
    long long r = min(ID*w+w, n);

    long long c = 0LL;
    long long prev = 0<=l-1 && l-1<n ? GetStackItem(l-1) : -1LL;
    for (long long i=l; i<r; i++)
    {
        long long t = GetStackItem(i);
        if (t < prev)
            c++;
        prev = t;
    }

    PutLL(0, c);
    Send(0);

    if (ID==0)
    {
        long long ans = 1LL;
        for (int i=0; i<N; i++)
        {
            Receive(i);
            ans += GetLL(i);
        }
        cout<<ans<<endl;
    }

  return 0;
}

戦略

Largeをいかに通すか

スコアボードを見れば分かるように、上位の人でもlargeをポロポロ落とす。Largeを確実に通せれば強い。

オーバーフロー

多数のノードで処理されるので、普段の感覚では int に収まるものが収まらないことがある。入力用の関数の返値も long long なので、変数は全部 long long で良いのではなかろうか。

Memory Limit Exceeded

各ノードのメモリがしょぼい。問題によって変わるが、たいてい128MB。ノードに分割して処理をする問題なのだから、各ノードの処理も最初に入力を全部読み込む必要が無いことがほとんど。まずは、 vector<> などを使わずに、定数領域のオンラインで計算することを考えると良い。

Time Limit Exceeded

普段のコンテストで入力サイズに対して線形の処理が間に合わないことはない。一方でDCJでは入力サイズが1ノードでは処理できないほどに大きい。うっかり、自分の担当する範囲のサイズではなく、全体の入力サイズに依存する処理を書いてしまうと落ちる。提出前に全てのループ範囲を確認するべき。ここを間違えていても、smallなら通ってしまうのでタチが悪い。

Smallについて

Smallは10ノードで実行されるが、入力サイズは1ノードでも計算が間に合う程度。また、分散処理をしないなら割と簡単に解ける問題が多い。なので、1個のノードで解く解法を、さっさと提出してしまうという手がある。点数は小さいものの、どんなに提出時間で差が付いていても点数で勝っていれば上位なので、意義は大きい。とはいえ、どうせlargeまで通せるならばsmallだけを通すために掛けた時間が無駄になるので悩ましい……。

Smallは一度正解した後でも、再提出ができる。この場合、提出したコードが正解でも不正解でも、提出時間や誤答ペナルティなどへの影響は一切無い。先にsmallだけ通した場合はlarge用の解答をsmallに再提出するべき。2分待つ必要があるので、自信があるならば、先にlargeに提出してからsmallに提出し、もし間違っていたらlargeに再提出という順番でも良いかもしれない。

You get articles that match your needs
You can efficiently read back useful information
You can use dark theme

What you can do with signing up