When does grep -v succeed?

昨日、簡単なシェルスクリプトを書いていたとき、「grepはマッチする行が1行でもあれば真を返すのであった。はて、grep -vの戻り値はどういう条件で真になるんだろう? また、grep -v -e a -e bなどといったように、条件が複数指定されているときはどうなるのだろう?」と悩んでしまいました。

調べた結果、「grepに-vフラグが指定されているときは、マッチしない行が一行でもあると真を返す」ようです。そこからの結論として、「grepは、-vフラグの指定の有無に関わらず、表示される行がある場合に真を返す」ということになります。

...とここまで時間をかけて検証をしたのですが、マニュアルにきちんと記載されていることに気づきました。マニュアルは機会があるごとに積極的に読まないと結局損をしますね。

EXIT STATUS
     The grep utility exits with one of the following values:

     0     One or more lines were selected.
     1     No lines were selected.
     >1    An error occurred.

Idiom: Passing reverse iterator to a constructor

文字列\(s\)から反転した文字列\(t\)を作成するとき、これまではコピーして反転という処理をしていました。

  std::string s("string");

            :

  std::string t(s);

  std::reverse(ALL(t)); // tの内容は"gnirts"となる

今日なんとなくこの実装を見て目から鱗が落ちました。コンストラクタにリバースイテレータを渡してしまえばいいんですね。この発想はなかった。

  std::string s("string");

  std::string t(s.rbegin(), s.rend());  // tの内容は元々"gnirts"となる!

「何かを反転したもの」を得たいことはよくあるのでこの手法はこれから活躍しそうです。

Using std::multiset instead of std::priority_queue

std::multisetをstd::priority_queueの代わりに使う実装例を目にしました。std::priority_queueは重いと言われているし、std::multisetのほうが性能がよいのであれば使う価値があるな...と考えて計測してみたところstd::priority_queueよりも3倍重く少しがっかり。まあ知見は得られたのでよしとします。

以下は検証に使った実装です。こちらはstd::priority_queueを使ったもので、数値の小さいものをキューに残そうとします。値が重複していても大丈夫です。

  int N = 1000000, M = 100, K = 1000;

  std::priority_queue<int> pq;

  for (int i = 0; i < N; i ++) {        // N回
    int size = rand() % M;
    
    for (int j = 0; j < size; j ++)     // [0, M)個のランダムな値を追加して
      pq.push(rand());

    while (pq.size() > K)               // キューがK個になるまで大きな数値を取り除く
      pq.pop();                         // (つまり、小さな数値を最大K個残す)
  }

std::multiset版はこちらです。数値の小さいものを残すために値の正負を反転しています(std::multiset::removeがリバースイテレータを取れればいいのですが、そういうものではないようです)。

  std::multiset<int> set;

  for (int i = 0; i < N; i ++) {
    int size = rand() % M;
    
    for (int j = 0; j < size; j ++)
      set.insert(- rand());

    while (set.size() > K)
      set.erase(std::begin(set));
  }

それでもstd::multisetを使う利点があるとすれば、要素を取り出すことなく反復できるところでしょうか(std::priority_queueは取り出す必要があります)。

  // 要素を(結果、降順で)表示する

  for (const auto& i : set)
    std::cerr << - i << std::endl;

Visualizing Rank on Union-Find Tree

縮約を伴ったUnion-Find木は高速に動作することで知られています。以下は蟻本からの抜粋です。

// 木の根を求める
int find(int x) {
  if (par[x] == x) {
    return x;
  } else {
    return par[x] = find(par[x]);
  }
}

// xとyの属する集合を併合
void unite(int x, int y) {
  x = find(x);
  y = find(y);
  if (x == y) return;

  if (rank[x] < rank[y]) {
    par[x] = y;
  } else {
    par[y] = x;
    if (rank[x] == rank[y]) rank[x]++;
  }
}

木の根を求める際、同時に縮約を行い、また併合の際にはランクを使って木の高さに偏りが発生するのを抑えます。

同時に蟻本には以下のように注記がなされています。

縮約を行って木の高さが変化しても、簡単のため rank を変えることは考えません。

ランクの概念や制限も大体理解しているつもりでしたのでライブラリにほぼ写経した実装を押し込み、習得したものとしていました。ですが、先日参加したコンテストこの実装を見て、憧れの念が生まれました。ランクを使いこなしている。そう感じたからです。

早速蟻本の実装を見直しました。理解していたつもりがスラスラと読めない...後からでも正確にイメージできるように作図することにしました。

  • 木のランクが異なる場合、ランクの小さい木の根からランクの大きい木の根に辺を張る

例えば以下のxとyの頂点を併合することを考えます。頂点の右の数値はランクを表しています。xのランクは1、yのランクは2です。そのため、右のように辺を張ります。

f:id:agw:20180623094352p:plain

\(\mathit{rank}_x < \mathit{rank}_y\)ですので、\(\mathit{rank}_x + 1 \le \mathit{rank}_y\)が常に成り立ちます。ですので、yのランクを更新する必要はありません。

同様に木のランクが異なる場合の例です。

f:id:agw:20180623094401p:plain

  • 木のランクが同じ場合、片方の木の根から他の木の根に辺を張る。そのとき、辺を張られるほうの木のランクを1つ増やす

以下の例でもxとyの頂点を併合することを考えています。双方の木のランクは同じですので、この場合はxからyに辺を張ってみることにしましょう。ランクは2になります。

f:id:agw:20180623094446p:plain

ランクが同じときの辺の張りかたも統一しておくとよいでしょう。ここでは蟻本を見習って、「根のインデックスが大きいものから小さいものに辺を張る」ことにしましょう。これに習うと上の例は以下のようになります。

f:id:agw:20180623094501p:plain

さて、併合時に縮約が起きる様子も見てみましょう。以下は、多少作為的ですが、蟻本の実装ではこうはならない、という例です。今回はzとaを併合します。

zの根を求める際に縮約が発生します(中央の図)。aの根はaですので縮約は発生しません。結果的に、xとaを併合します。

f:id:agw:20180623094510p:plain

さて、どこが作為的なのでしょうか? 実はこれ、縮約された木のランクを意図的に操作しているのです。これまで行儀のいい場合のみ図示してきましたが、蟻本の実装では縮約の際にランクを操作しません。そのため、実際には以下のようになります。

f:id:agw:20180623094521p:plain

併合時に参照されるランクは根のものだけであることに注意してください。言い換えると、一回子供になってしまった頂点のランクはもう気にする必要はありません。少々乱暴ですが、縮約は根の参照の効率を改善するためだけに行われていると言ってもいいでしょう。

蟻本の例には以下のような縮約の例が掲載されています。具体的にはeをfindするとこのような縮約が発生します。

f:id:agw:20180623094531p:plain

蟻本の図にはランクが示されていません。そのため、図からこのようなことが起こっていると捉えてしまっている人は少なくないかもしれません。

f:id:agw:20180623094614p:plain

また、木の中腹の頂点をfindすると以下のような縮約が発生します。これはcをfindした例です。

f:id:agw:20180623094628p:plain

最後に、ここまでの図にはランクが2の木が出てきていました。では実際にランク2の木はどのように作ることがができるでしょう? ランクを2にするには、ランク1の木が二つないといけません(おそらく、今まで説明に使ったx、y、zの3頂点からなる木は作れないように思います)。

f:id:agw:20180623094641p:plain

Idiom: Partial Sorting

書庫から久しぶりに取り出したEffective STLをパラパラめくっていて、std::partial_sortのうまい用法を学びました(第31項「ソートの選択肢を知っておこう」)。昇順に整列して初めから20番目の要素までの合計を取りたいときにはstd::sortを使うより、std::partial_sortを使ったほうが効率的であるようです。

std::vector<int> a;

// ...aを更新する

std::partial_sort(std::begin(a),
                  std::begin(a) + 20,
                  std::end  (a));

int sum = std::accumulate(std::begin(a), std::begin(a) + 20, 0);

イテレータを3つ取る関数には苦手意識がありましたが、この用法は覚えやすいですし、手軽な定数倍高速化として重宝するかもしれません。計算量は面白く、

$$ O({}(\mathrm{last} - \mathrm{first})\log(\mathrm{middle} - \mathrm{first}){}) $$

だそうです。線形の項が配列全体の要素数なので劇的に計算量が減るわけではなさそうですが、以下のように一定の効果は期待できそうです。

$$ \begin{array}{cccc} \mathrm{first} & \mathrm{middle} & \mathrm{last} & \text{Complexity}\\ \hline 0 & 10 & 1000 & 1000 \times 3.322\\ 0 & 100 & 1000 & 1000 \times 6.644\\ 0 & 500 & 1000 & 1000 \times 8.966\\ 0 & 1000 & 1000 & 1000 \times 9.966\\ \end{array} $$

よしよし、一つ賢くなったぞ...と喜んでいたのも束の間、合計を取りたいのであればstd::nth_elementで十分であることに気づきました。std::nth_elementはstd::partial_sortと書式がほとんど一緒ですが、std::partial_sortが先頭から20要素までに上位20個の要素を整列して格納するのに比べ、先頭から20要素までに上位20個の要素を格納する、とのこと。

std::vector<int> a;

// ...aを更新する

std::nth_element(std::begin(a),
                 std::begin(a) + 20,
                 std::end  (a));

int sum = std::accumulate(std::begin(a), std::begin(a) + 20, 0);

(この用途では1)計算量はstd::parital_sortに比べとても効率的で、\(O(\mathrm{last} - \mathrm{first})\)だそうです。\(\log\)が落ちてしまうんですね。


  1. C++17から追加されたstd::nth_elementの計算量は少々複雑であるようです

Multi-start Breadth First Search

先日参加したコンテストで以下のような問題が出題されました1

シンプルなグラフがある。それぞれの頂点は最大で100個ほどのグループに分けられている。各頂点から各グループの頂点までの最短距離を求めよ。ただし、頂点の最大数は\(10^{5}\)である。

この問題、コンテスト中には全く手が出ませんでした。それぞれの頂点から幅優先探索を行なって任意のグループに属する頂点に出会う度に記録すれば、目的はまあ達成です。ですが、計算量は軽く見積もっても\(O(N^{2})\)。\(10^{10}\)を超えてしまいます。これは駄目です。

また、制約から考えると、\(10^{5} \times 100\)のテーブルを用意して記録していけばよいように思うのですが、うまく埋めていくことができませんでした。

このときは次のように考えていました。

  • 各頂点から幅優先探索を行う。訪れた頂点のグループ情報を得る。そのグループに初めて訪れているなら、距離を最短距離として記録する(全てのグループに出会ったらその頂点に関しての探索は終了する)

さてコンテスト終了後に色々考えても計算量が落とせなかったので他のコンテスタントの実装を読んでみました。皆幅優先探索を実装しているようですが、探索をグループの数分しか行なっていません...はて?

ポイントは以下でした。

  • 幅優先探索の開始点はグループに属する全頂点とする(!)
  • 幅優先探索を行う。先ほどのようにグループ情報を集めるのではなく、開始点のグループ情報を伝搬するようにする

なるほど、これなら計算量も\(O(MN)\)に落とすことができます。「多点開始幅探索」、とでも呼称できそうな技法です。

以下のような盤面を考えてみます。ここで、グループは4色の色として表しています。また、グラフは表示されているよりも広く存在しています。

f:id:agw:20180604152628p:plain:w350:h350

単点開始幅優先探索では以下のように探索を行います。この緑色の頂点はすぐに、青色と紫色の点を見つけることができますが、赤色の頂点にたどり着くまでには3ステップかかっていることが分かります。

f:id:agw:20180604152739p:plain

赤色の頂点にたどり着いた時点で自分が属する色以外の3色の頂点にたどり着いたのでここで探索を打ち切ることはできますが、最悪\(O(N)\)の探索を\(N\)回繰り返さなければならないので、計算量は依然\(O(N^{2})\)と考えたほうがよいでしょう。

では多点開始幅探索を見て見ましょう。探索は以下のようになされているようです。先ほどの単開始点から行う幅優先探索に比べて、ほとんどの頂点をすぐ網羅することも注目しましょう。

f:id:agw:20180604153135p:plain

一回の探索で訪れる頂点の数は単点開始でも多点開始でも\(N\)ですが、探索を全体で\(N\)回(最大\(10^{5}\)回)やらなければいけないか、\(M\)回(最大100回)でいいのかで総合的な計算量は大きく変わります。ぜひ覚えておきたい技法です。


  1. 少し簡潔な問題としています

Idiom: Enumerate ranges that decrease(but not strictly)

コンテストに参加していると、数列の部分的に降順になっている区間を列挙することを求められることがままあるのですが、苦手意識がありました。図でいえば、[4, 9]、[18, 21]、[23, 24]を列挙することです。

f:id:agw:20180215092113p:plain

この小問題、自分にはなかなか難しいものでした。特に初めの区間のように、単調に減少しないものを処理しなければならない場合は無駄に複雑な実装をして時間を浪費することが多かったように思います(この問題を見るたびに「隣り合う値から微分を検出すれば書けるのでは?」と考えてしまうのが敗因です)。

今日参加したコンテストでも同じように迷い、しゃくとりを使えば簡潔に書けることにやっと気づきました。

for (int i = 1; i <= N; )
  if (a[i] <= a[i + 1]) {
    i ++;
  }
  else {
    for ( ; i <= N && a[i] >= a[i + 1]; i ++)
      ;

    ranges.emplace_back(i, j);  // 区間はinclusive。[i, j]
  } 

しゃくとり以外に工夫していることといえば、処理を簡潔にするために最初と最後に番兵を入れていることでしょうか(実際には先頭の番兵を\(-\infty\)、最後の番兵は\(\infty\)としています)。

f:id:agw:20180215092108p:plain

隣り合う値から微分を検出しようとしてうまく行かなかったのですが、番兵のアイデアはそのときに微分を確実に取れるように、と思いついたものです(この問題設定だと先頭はなくてもよい)。面白いですね。

これからは迷うことなく書くことができそうです。