TechFULの中の人

triple-four’s blog

条件を指定してソートする (C++)

こんにちは!TechFUL でアルバイトをしている ia7ck です。

今回は、C++ で条件を指定したソートを行う方法について説明します。

シンプルな条件で並び替える

C++ の algorithm ヘッダに含まれている std::sort を使うと配列や std::vector を要素の昇順にソートしてくれます。たとえば

[6, 2, 5, 3, 8, 7]

という配列を

[2, 3, 5, 6, 7, 8]

と並び替えてくれます。

上の配列を降順にソートしたいときはどうしたらいいのでしょう。この場合は配列の要素を逆順にする std::reverse を使って、

  1. 配列を昇順にソートする (std::sort を使う)
  2. ソートした配列を逆順にする (std::reverse を使う)

とすれば降順に並び替えられた配列

[8, 7, 6, 5, 3, 2]

が得られます。

複雑な条件で並び替える

さて、あなたは 3 の倍数がとても好きだとします。なので配列をソートしたときに 3 の倍数はその他の数より前に来てほしいです。ただし 3 の倍数同士や 3 で割り切れない数同士は昇順に並べます。つまり、配列 [3, 6, 5, 2, 8, 7] を並び替えたあとは次のようになっていてほしいです。

[3, 6, 2, 5, 7, 8]

このような場合にはいくら std::reverse を上手に使っても目的を達成できそうにありません。また、今回のケース専用の関数が C++ に用意されているわけでもありません。

問題を解決する鍵はソート関数の引数にあります。std::sort の第3引数に比較関数を用いてソートの条件を指定してあげることで、好きな順序に並び替えることができます。

std::sort の基本的な使い方

比較関数を用いたソートを行う前に std::sort の基本的な使い方を確認します。要素を昇順にソートするには std::sort の第1引数と第2引数にソートする範囲を指定してあげればいいです。たとえば冒頭の問題のように、与えられた数値を降順にソートするプログラムは以下のようになります。

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

int main() {

  vector<int> values = {6, 2, 5, 3, 8, 7};
  sort(values.begin(), values.end());    // 昇順にソートする
  reverse(values.begin(), values.end()); // 逆順にする

  for (auto val : values) {
    cout << val << " ";
  }
  // 8 7 6 5 3 2
  // が出力される

  return 0;
}

比較関数を用いたソート

次の問題を考えます。

N 人の生徒がいて、それぞれの生徒には出席番号が 1 から N まで振られています。
出席番号 i の生徒のテストの点数は scores[i] でした。
生徒の成績はテストの点数が高いほど良く、同じ点数であれば出席番号が小さいほど良いです。
K 番目に成績の良い生徒の出席番号はいくつですか。

たとえば N=5, K=2, scores=[89, 95, 82, 90, 95] の場合を考えます。生徒たちを成績の良い順に並べると次のようになります。

出席番号 テストの点数
2 95
5 95
4 90
1 89
3 82

2 番目に成績の良い生徒の出席番号は 5 なので答えは 5 です。

以上の考察からこの問題は

  1. 出席番号・テストの点数の情報から、生徒を成績の良い順に並べる
  2. 前から K 番目の生徒の出席番号を見る

とすれば解けることが分かりました。1.の部分で条件を指定したソートを行う必要があります。比較関数を用いたソートは

bool cmp(const T &a, const T &b)

という形式を持つ関数を std::sort の第3引数に与えればいいです。関数の返り値は

  • ab より (ソート後の配列で) 前に来てほしいなら true
  • 後ろに来てほしいなら false

とします。具体的に解答例のプログラムを見てみます。

解答例

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

struct Student {
  int number; // 出席番号
  int score;  // テストの点数
};

bool comp(const Student &lhs, const Student &rhs) { // 比較関数の定義
  if (lhs.score != rhs.score) {
    return lhs.score > rhs.score;   
  } else {
    return lhs.number < rhs.number; 
  }
}

int main() {

  int N, K;
  cin >> N >> K;
  vector<Student> students;
  for (int i = 1; i <= N; i++) {
    int score;
    cin >> score;
    students.push_back(Student{i, score});
  }

  sort(students.begin(), students.end(), comp); // 第3引数に比較関数を与える
  cout << students[K - 1].number << endl;       // 0-indexedに注意
  
  return 0;
}

bool comp(const Student &lhs, const Student &rhs) の部分が比較関数です。

2人の生徒の点数が異なる場合、

  • lhs の点数が rhs の点数より高いならば、つまり、lhs.score > rhs.score ならば lhsrhs より前に来てほしいです。したがってこのときは true を返します。
  • 逆に lhs.score < rhs.score ならば lhsrhs より後ろに来てほしいので false を返します。

2人の生徒の点数が同じ場合も同様に、それぞれの生徒の出席番号を比較して lhs が前に来てほしいなら true を、後ろに来てほしいなら false を返します。

ラムダ式を用いたソート

最後に、ラムダ式を用いたソートを紹介します。

とは言ってもすでに説明した比較関数を用いたソートと根本的な違いはありません。上のプログラムではソート関数 std::sort と比較関数 comp が離れていて少し見づらいと感じたかもしれません。ラムダ式を用いてソート部分を書き直すと次のようになります。

sort(students.begin(), students.end(), [](const Student &lhs, const Student &rhs) {
  if (lhs.score != rhs.score) {
    return lhs.score > rhs.score;
  } else {
    return lhs.number < rhs.number;
  };
});

ちょうどソート関数の途中で比較関数を書いたような格好になっています。ラムダ式を用いる利点の1つは、このようにソート対象となる students とソート基準を定めた比較関数とをひと目で確認できることだと思います。

おわりに

この記事では、C++std::sort による昇順ソート・降順ソートおよび比較関数 (ラムダ式) を用いて条件を指定したソートを行う方法を紹介しました。

比較関数さえ用意してしまえば C++ の高速なソート関数を用いて要素を並び替えることができるため、使いこなせると強い武器になるでしょう。

おまけ

いわゆる "読者への課題" です。今回の内容の復習にもなるかと思いますので挑戦してみてください。

1問目 (易しめ)

std::sort の基本的な使い方」の章では std::sortstd::reverse を使って降順ソートを実現していました。ここでは、std::sort の第3引数に比較関数またはラムダ式を与えることで std::reverse を使わずに降順ソートを実現してみましょう。

解答例 (クリックで展開します)

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

int main() {

  vector<int> values = {6, 2, 5, 3, 8, 7};
  sort(values.begin(), values.end(), [](const int &lhs, const int &rhs) {
    return lhs > rhs; // 大きい数が前に来るようにする
  });

  for (auto val : values) {
    cout << val << " ";
  }
  // 8 7 6 5 3 2
  // が出力される

  return 0;
}

2問目 (やや難しめ)

冒頭に挙げた問題の2問目を解いてみましょう。問題を再掲します。

整数値の配列が与えられる。

  •  3 の倍数とその他の数では  3 の倍数が前に来るようにする。
  •  3 の倍数同士や  3 で割り切れない数同士では値が小さいほうが前に来るようにする。

上の2つの条件を満たすように配列の要素を並び替えよ。

解答例 (クリックで展開します)

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

int main() {

  vector<int> values = {6, 2, 5, 3, 8, 7};
  sort(values.begin(), values.end(), [](const int &lhs, const int &rhs) {
    if (lhs % 3 == 0 and rhs % 3 == 0) {
      return lhs < rhs;    // 3の倍数同士は昇順
    } else if (lhs % 3 != 0 and rhs % 3 != 0) {
      return lhs < rhs;    // 3で割り切れない数同士も昇順
    } else {
      return lhs % 3 == 0; // 3の倍数が前に来るようにする
    }
  });

  for (auto val : values) {
    cout << val << " ";
  }
  // 3 6 2 5 7 8
  // が出力される

  return 0;
}

運営会社 / サービス

444株式会社

triple-four.com

TechFUL

procon.techful.jp

ワーシャルフロイド 入門

こんにちは!ganariyaです。
今回はグラフ理論アルゴリズム、「ワーシャルフロイド」についてです。

実世界において、グラフ理論はあらゆるところで利用されます。
例えば、インターネットにおける通信パスや、JRなどの電車の経路パス探索です。
これらはグラフ理論を発展させて、実務的に使用しているものです。

グラフ理論は殆ど、駅などをノード道路などをエッジとして扱い、点と線が結ばれたものとして扱われます。
グラフのキホン(1)グラフ概要編グラフのキホン(2)表現方法と探索編の記事を読むとグラフの基礎が身につくと思います。

そして、グラフ理論で扱われる大きなジャンルの一つには、最短経路問題というものがあります。
これは、与えられたグラフの2つのノード間の最小のコストの経路を見つけるというものです。

例えば、以下のようなグラフがあったとします。

f:id:ganariya:20190216103745p:plain
グラフ

以上のようなグラフで、始点 Sから終点 Tまでの最短経路を求めたいです。

これは以下のようになります。

f:id:ganariya:20190216104024p:plain
グラフ 最短経路

以上のように、通っていくと、最短経路のコストは15となり、これが最小のコストとなります。

このように、最短経路を求めるアルゴリズムはいくつかありますが、今日はそのうちの一つである「ワーシャルフロイド」を掘り下げてみたいと思います!


続きを読む

Kotlinのnull安全

こんにちは!人生二度目の「肺に穴が空く」、という体験をしたSiiiecです。

入院中、PCに触ることが出来なかったものの、書籍Kotlinイン・アクションが手元にあったためKotlinを学ぶ機会がありました。
そこで感心した部分であるKotlinのnull安全についてまとめてみたいと思います。

続きを読む

やさC#で簡単な非同期処理2 ~Wait()~

こんにちは!魚介類のサバです。 最近、といっても数か月前ですが、C#の非同期処理が必要になって触った機会があったので、忘れないうちに出力したいと思います!

今回は 「Wait()」 を理解することが目的です。
親切な解説ができるように努力します!!

※魚介類なので、浅い知識で書いています。ふわふわした解説や、ちょっとした間違いはご了承ください。

Wait() する

Task.Run の戻り値は Task<> 型です。Task<>型 は Wait() メソッドを持ち、これを使うと、呼び出した別スレッドの処理が終わるまで、呼び出し元のスレッドをハードウェイトさせます。

static void Main(string[] args)
{

    Console.WriteLine("Hi : Main    Thread");

    Task.Run(() =>
    {
        for(int i{}; i < 100; ++i)
            Console.WriteLine("Hi : Another Thread " + i);
    }).Wait();   // 呼び出したスレッドの処理が終わるのをハードウェイト

}
  • ここでは別スレッドに重い処理(forループ100回)をさせ、それが終わるのをメインスレッドがハードウェイトで待っています。

ハードウェイト?

Wait() の中身はこんなイメージです。そのため、別スレッドの処理が終わるまで、呼び出し元のスレッドは全く無意味な処理(ループ文ぐるぐる)を行い続けます。

while( 呼び出した別スレッドが処理を続けているなら ){
}
  • ここで重要なのは、呼び出し元スレッドが、別スレッドの処理が終わるのを全力で待ち続け、それ以外何もできなくなる点です。 スレッドがブロックされた状態などともいい、実質的に呼び出し元スレッドは停止します。

Result に注意

Task.Run() に渡したラムダ式の戻り値を取得するために、Task型の Result プロパティを使用する方法があります。(この前回の記事にサンプルコードもあります。)

triple-four.hatenablog.com

Result は内部で Wait() を呼び出し、ラムダ式の戻り値が決定するまで呼び出し元スレッドをハードウェイトさせてしまいます。そのため、Task.Run() した後、すぐに Result でラムダ式の戻り値を取得しては、非同期処理をする意味が全くなくなります。

Wait() のためだけにこの記事を書くのは手抜きなのでは?

Wait() の理解が重要だと考え記事を分けました。特に、どういう仕組みで別スレッドを待っているか、その間Wait()しているスレッドはなぜ何もできないのかを理解してほしいです!

非同期処理に目覚めたあなたに素敵なプレゼント!

実行スレッドを特定する方法

System.Threading名前空間ThreadクラスのプロパティCurrentThreadのプロパティManagedThreadIdを使うことで、そこを処理しているスレッドのIDを取得することができます。実験の際にとても役に立ちます。

using System.Threading.Tasks;
using System.Threading;

static void Main(string[] args)
{

    Console.WriteLine("Main    Thread ID : " + Thread.CurrentThread.ManagedThreadId);

    Task.Run(() =>
    {
        Console.WriteLine("Another Thread ID : " + Thread.CurrentThread.ManagedThreadId);
    }).Wait();

}
  • 非同期できるならいろいろ試してみたいですよね!そんなあなたにはこちら!これだけで実行スレッドを特定できる ID を取得できます!
  • 実際に非同期になっているのか、どの部分がどのスレッドで処理されているのかはっきりわかります!!

最後に

前回の記事で、「Wait() ってなんだよ!?」と思った方、そうでない方、いずれの方々にも誤解なく理解してもらいたくこの記事を書きました。 次回は非同期処理とメソッドについて書きたいと考えています!

運営会社 / サービス

444株式会社

triple-four.com

TechFUL

procon.techful.jp

再帰関数を分かりやすく解説してみる【入門】

こんにちは!ganariyaです。
最近ほとんど遊んでないので、遊びたいですが遊ぶ相手がいません・・・(かなしい)

さて!(切り替え!)
プログラミング始めたてあるあるなのですが、再帰関数、みなさんどのような印象でしょうか・・・
再帰関数は、プログラミングを始めた頃の最初の関門であり、なかなかイメージし辛く、書きづらい、何をしているのかがよく分からない内容です。

しかし、再帰関数は最初理解するのが難しいですが、一度理解してしまえば応用しやすい概念・テクニックであり、色々なことに応用できます。

今日は、その再帰関数の考え方やどのようなお気持ちで書くのかについて、(出来るだけ)分かりやすく書いてみようと思います。


続きを読む