cafelier@SRM

競技プログラミングのためのD言語 (2/2)

03:22 |

続きです。

foreach文

string[] strs = ["aaa", "bbb", "ccc"];

foreach(s; strs) // strsの要素をループ
   writeln(s);
foreach(i, s; strs) // strsの要素を添え字付きでループ
   writeln(i, ": ", s);
foreach(i; 0..100) // 0から99まで(100は含まない)ループ
   writeln(i);

foreach_reverse(s; strs) // strsの要素を逆順にループ
   writeln(s);
foreach_reverse(i, s; strs) // strsの要素を添え字付きで逆順にループ
   writeln(i, ": ", s);
foreach_reverse(i; 0..100) // 99から0までループ
   writeln(i);

はい。

基本的ではない型・演算

標準ライブラリの std.bigint というモジュールを import すると BigInt 型が使えます。普通に+-*/で演算できます。JavaのprobablePrimeのような格好いいメソッドはありません。

import std.stdio;
import std.bigint;

BigInt factorial(int n) {
   return n>0 ? factorial(n-1) * n : BigInt(1);
}

void main()
{
   writeln(factorial(1000));
}

複素数が言語組み込みの型としてあります。cfloat, cdouble, creal という型名です。std.complexというライブラリ実装に置き換えるという話があったんですがまだ置き換わってないので組み込み型の方を紹介します。

import std.stdio;
import std.math; // 実部 .re と虚部 .im と四則演算以外の関数は std.math で
void main()
{
   creal z = 1+2i;
   z = z*z; // (1+2i)(1+2i) = -3+4i
   writeln(z.re); // -3
   writeln(z.im); // 4
   writeln(conj(z)); // -3+-4i
}

普通の整数や浮動小数点数にもちょっと便利機能があります。

void main()
{
   int x = 3^^4; // 3の4乗 : 81
   int veryLarge = int.max; // intに入る最大値すなわち2147483647
   real inf = real.inf; // IEEE754の∞値
}

競技プログラミング的に言うと、べき乗は3状態あるもののビットじゃないけどビットマスク、っぽいものの計算が楽になったりします。.max や .min や .inf は変数の初期値として埋めておくと役に立つ場面が色々。

詳しくはこちら

• Type: 英語 日本語
• Property: 英語 日本語
• Expression: 英語 日本語
• std.bigint: 英語 日本語
• std.math: 英語 日本語

データ構造：連想配列

std::map<string, int> や java.util.HashMap<String, Integer> のような、あれです。メモ化に使います。

int[string] m;
m["one"] = 1;
m["two"] = 2;
m["three"] = 3;
if( "four" in m ) writeln("hogehoge");
m.remove("three");
writeln(m.length); // 2
foreach(key, value; m)
   { ... }
int[string] point_to_same_as_m = m; // 同じmapを参照
int[string] another = m.dup; // コピーはdupで

そんな感じで ValueType[KeyType] という型として言語組み込みでこの機能を持っています。実装はハッシュ表を使っているので、C++のstd::mapやjavaのTreeMapのような、キーの順序通りに取り出す機能は、この連想配列にはありません。

HashSet相当のものはないので、私は bool[Type] を set としてよく使っています。

詳しくはこちら

Associative Arrays: 英語 日本語

データ構造：その他

std.container

に、BinaryHeap (priority_queue/PriorityQueue) と RedBlackTree (set/TreeSet) があります。私使ったことないので詳しくは知りません...。

詳しくはこちら

std.container: 英語 日本語

データ構造：pair, tuple

std.typecons モジュールに、Tuple!() というテンプレートが用意されています。2つ組や3つ組を作れます。

import std.typecons;

void main()
{
  Tuple!(int, string, real) t = tuple(1, "hello", 3.14); // tuple() 関数はC++のmake_pairみたいなもの、型を省略して構築
  int x = t[0]; // 0番目はint
  string y = t[1]; // 1番目はstring
  t[2] = 2.72; // 2番目はreal
}

DのTupleの良いところは、メンバの名前をfirstやsecondじゃなくて自由に決められるところです。

Tuple!(int, "src", int, "dest") edge = tuple(0, 2);
writeln(edge.src, "-->" edge.dest);

型名が長いなーと思ったら、aliasを使います（C++で言うtypedefです）。

alias Tuple!(real, "x", real, "y", real, "r") Circle;
Circle c = Circle(0.1, 0.2, 0.3);
c.r = 0.4;

詳しくはこちら

std.typecons: 英語 日本語

クラスの書き方・使い方

Tupleでメンバの名前がつけられるとなると、競技プログラミングレベルではclassやstructを定義せずに全部Tupleで済ませてしまうことがかなり多くなるのですが、必要ならばもちろんクラスを作って使うこともできます。クラスの定義、使い方はJavaと同じです。 唯一の注意点としては、コンストラクタの名前は クラス名() ではなく、this() です。あとデフォルトは public です。

詳しくは他のもっと真っ当な解説などを。

無名関数・クロージャ

void sort(int[] arr,  bool delegate(int x, int y) ordered) {
   foreach(i; 0..arr.length)
      foreach(j; i+1..arr.length)
         if( !ordered(i, j) )
            {int tmp=arr[i]; arr[i]=arr[j]; arr[j]=tmp;}
}

void main() {
   int[] weight = [9,3,4,7,1,6,2,8,5];
   int[] arr = [0,1,2,3,4,5,6,7,8];
   sort( arr, (int x, int y){ return weight[x]<weight[y]; } );
}

(int x, int y){ return weight[x]<weight[y]; } の部分が無名の関数です。周りの環境のweightという変数を使うこともできています。この無名関数を変数で受けるには、<b>delegate という型で受けます。構文は上の例のような感じ。

アルゴリズム

C++の<algorithm>ヘッダに相当する物は、Dでは std.algorithm モジュールです。std.range も見ておくと便利です（特に、二分探索系の機能はstd.rangeにあります）。機能としては基本的に <algorithm> をなぞったものが多いですが、よく見るとBoyerMooreとかlevenshteinDistanceなどが紛れ込んでいてちょっと楽しいです。

楽しいかどうかはさておき、std.algorithm を使うにあたって重要なポイントは、Range という概念です。C++ では iterator というものの上にSTLのアルゴリズムがすべて組まれていましたが、D言語では Range の上に全部のアルゴリズムが組まれています。

なにやら難しそうですが、要はぶっちゃけると Range は iterator の begin と end の組と思って下さい。Topcoderなどでも

#define ALL(c) (c).begin(), (c).end()

というけしからんマクロを書いている人をよく見ますが、確かに、この二つは常に組であつかった方が色々と便利なのです。

import std.algorithm;
import std.stdio;

void main()
{
   int[] arr = [1,2,3];
   auto r = find(arr, 2);
   writeln(r); // [2,3]
}

[1,2,3] から 2 を探すと、最初に 2 が現れた位置より後ろ全体を指すRangeが返ります。別の例。count。

import std.algorithm;
import std.stdio;

void main()
{
   int[] arr = [1,2,3];
   writeln( count!((int x){return x>=2;})(arr) ); // 2以上のものの個数。2個。
   writeln( count!("a>=2")(arr) ); // 同じ意味
}

関数を引数にとるタイプのアルゴリズムの場合、アルゴリズム名!(ここ)(range) に関数を渡します。周りの環境の変数をみないのであれば、"a"を引数と思った関数のbodyの文字列を書いても行けたりします。!() は C++ でいうテンプレート引数を渡している部分になります。

普通の配列を操作する＆走査するRangeは要するにただの部分配列ですが、Rangeという概念自体はもっと抽象的なものなので

import std.algorithm;
import std.range;
import std.stdio;

void main()
{
   string[] names = ["taro", "hanako", "toastman"];
   int[] ratings = [3000, 4500, 4000];

   sort( zip(ratings, names) );

   writeln(names);  // ["taro", "toastman", "hanako"]
   writeln(ratings); // [3000, 4000, 4500]
}

二つの配列を並行して走るRangeをzipでその場で作ってそのRangeをsort、とやると元の二つの配列がpairとしての順序でsortされたりします。これは割と経験的に便利です。

別の例。二分探索。

import std.array;
import std.range;

void main()
{
   int[] arr = [1,2,3,4,5];
   auto sorted = assumeSorted(arr);

   int[] lw = array(sorted.lowerBound(3)); // [1,2];
   int[] up = array(sorted.upperBound(3)); // [4,5];
}

Rangeを返値として返す関数の結果は大抵よくわからない謎の型になっていますが、auto で自動的に適切な型で受け取ることができます。あと、そのRangeをこれ以上他のアルゴリズムに渡したりしないので普通の配列にしてください、と思ったらstd.arrayのarray()関数でRangeを何でも配列化できます。

詳しくはこちら

• std.algorithm: 英語 日本語
• std.range: 英語 日本語

スレッド

std.concurrencyのspawnという関数でスレッドを起動してsendとreceiveでやりとりします。最近のマシンは4コアや8コアは持っていたりするので、ローカルで実行する形式のコンテストでは、単純にテストケースを別スレッドで並行に実行するだけで8倍の高速化が達成できたりすることがあります。

import std.stdio;
import std.concurrency;

void compute_square(Tid parent, int n)
{
   send(parent, n, n*n);
}

void main()
{
   // 100個スレッド起動
   foreach(i; 0..100)
      spawn(&compute_square, thisTid, i);

   // 100個返事が来るのを待つ
   int[] results = new int[100];
   foreach(_; 0..100)
      receive( (int i, int result)
      {
         results[i] = result;
      });

   writeln(results);
}

スレッドを起動したりメッセージ通信したりするコードはこれだけです。

詳しくはこちら

• std.concurrentcy: 英語
• std.parallelism: 英語

そして最近はstd.parallelismなどという物もできていました…知らなかった…

まとめ

とりあえず、以上です。

D言語の言語機能の紹介としては、テンプレートとかテンプレートとかテンプレートとか契約とか契約とか契約とか特徴的な部分をごっそり省いているのですが、競技プログラミングでそこまで激しくその辺りの機能を使うことはなかろうということで省いています。「○○と同じです」で済ませた部分も本当は全然同じではなくて、同じ書き方をしたらだいたい同じに動くというだけで、同じでない書き方も色々できて面白いのですが、その辺りは他のまともな解説記事を読んでみてください。ではでは。