こんにちは！TechFULでアルバイトしているあたかです． 今回はk-means法について解説します！
続きを読むやさC#で簡単な非同期処理３ ～async～
こんにちは！魚介類のサバです。 最近、といっても数か月前ですが、C#の非同期処理が必要になって触った機会があったので、忘れないうちに出力したいと思います！
今回は 「async」 を理解することが目的です。 やっと非同期処理のお話ができます！ 親切な解説ができるように努力します！！
※魚介類なので、浅い知識で書いています。ふわふわした解説や、ちょっとした間違いはご了承ください。
非同期な関数
async句を頭につけた関数は、非同期に動くかもしれない関数になり、非同期処理として呼び出すことができます。
int Func() // 同期的に動くメソッド { return 0; } async Task<int> FuncAsync() // Funcを非同期に動くかもしれないメソッドに書き換え { return 0; // 実は中身がこのままでは、実質、同期的にしか動きません… } void dothis() { FuncAsync(); // 一つ目の非同期処理として呼び出す FuncAsync(); // 二つ目の非同期処理として呼び出す FuncAsync(); // 三つ目の非同期処理として呼び出す }
また、一般的に戻り値はTask<>型を使用します。<>内にメソッド内で返したい戻り値の型を指定します。
C#の非同期な関数は、関数名の後ろにAsyncと付けるのが一般化しているようです。（普通、非同期な関数があれば、同期的に動く関数もあり、コーディング方法も違うため、同期的に動く関数とはっきり見分けがつくようにするためという理由でしょうか？）
Taskを戻り値に使用できない場合はvoidを使います。WPFとかがそんな感じです。Taskを戻り値にすることで、非同期処理中の状態や、非同期処理中に起きた例外の処理、非同期処理が終わった後に行いたい処理の記述などができるため、基本的にはTaskを戻り値にしましょう。
ここでは
dothis()を呼び出すと、これを呼び出したスレッドが、3つある、0を返す処理を非同期に処理しなさいと記述したことになります。（実際には0を返すだけの簡単な処理で、小分けに区切る場所もないために同期的に処理されますが…）
非同期処理ってなんぞ？（C#のGUIアプリケーションでの話）
非同期処理＝並行処理 ( 同期処理＝非並行処理 )
非同期処理は、並列処理と似て、複数の処理を一緒に行ってくれます。ただし、使っているスレッドは一つだけで、複数の処理を小分けにローテーションすることで、同時実行しているように見せかかけてくれるものです。並行処理とも言えますね！
非同期処理と、並列処理の違いをしっかり覚えてください！
- 並列処理 : スレッドを複数個使って、それぞれのスレッドに別々の仕事をしてもらう。各スレッドは同期的に処理をする。
- 非同期処理（GUI）：1つのスレッドを使って、複数の処理を小分けにローテーションすることで、同時に実行しているように見せかける。（並行処理）
同期処理はある処理が完全に終わったら、次の処理を行うという動作で複数の処理を行うことを指します。そのため、非同期という言葉を使うのは、一つの処理を何個にも小分けにすることで、他の処理を行う片手間で処理を実行できる点が、同期処理とは異なるからだと考えています。
GUIアプリケーションとCUIアプリケーション
C#は、CUIアプリケーションの場合、非同期処理をスレッドにこだわることなく、動的に切り替えて実行するようになります。つまり、その時点で暇にしているスレッドに、非同期処理を順次割り当てていくため、一つのスレッドでローテーションするかもしれませんし、別々のスレッドをたらいまわしするように処理していくのかもしれないということです。これはGUIアプリケーションが、描画用スレッドという特殊なスレッドを持つために、スレッドを区別する必要ができてしまったためです。別段CUIが変態とかGUIが悪いとかそういうわけではありません。
CUIアプリケーションの例
- VisualStudioの新規プロジェクトにある、「コンソールアプリ」で作られたもの
GUIアプリケーションの例
まとめ
並列処理
別々のスレッドそれぞれに、仕事を割り当てて実行してもらう。（ここでは小分けにしていないため各スレッドは同期処理。もちろん各スレッドが非同期な場合もある。）
非同期処理（GUI）
一つのスレッドに処理を複数個渡し、小分けにしながら、ローテーションして処理する。（並行処理）資源の排他制御などを考えなくていい。
非同期処理（CUI）
複数個ある処理を小分けしたうえで、複数のスレッドで共有しながら、小分けする前の順番を守って処理する。（並行処理をマルチスレッドで分担して処理）動的に処理スレッドへの割り当て方が決まる高度（or汚い?
）な並列処理。
非同期処理（GUI+CUI）
≒並行処理。処理を小分けにして実行し、同時に処理を進めているように見せかけることができる。ただし、小分けにした処理の一つが終わらなければそのスレッドはロックされたりするし、小分けにされた処理の進み具合やスレッドが暇にしている度合いによって進み具合が違うため、コードが実行されるタイミングはある程度制御できても基本的に不定。
最後に
並列処理と非同期処理の違いを理解しましょう！
Task.Run()はマルチスレッド処理（並列処理）で、Asyncは非同期処理（並行処理）です。同じコード内でよく使われるものですが、全くの別物だということを理解してください。
加えて、GUIでの非同期処理（並行処理）と、CUIでの非同期処理をする際の動きを理解しましょう！
またこれらの挙動は、あくまでC#の場合ですので注意してください。
次は Async とセットで出てくる await についての解説です。
運営会社 / サービス
444株式会社
TechFUL
条件を指定してソートする (C++)
こんにちは！TechFUL でアルバイトをしている ia7ck です。
今回は、C++ で条件を指定したソートを行う方法について説明します。
シンプルな条件で並び替える
C++ の algorithm ヘッダに含まれている std::sort を使うと配列や std::vector を要素の昇順にソートしてくれます。たとえば
[6, 2, 5, 3, 8, 7]
という配列を
[2, 3, 5, 6, 7, 8]
と並び替えてくれます。
上の配列を降順にソートしたいときはどうしたらいいのでしょう。この場合は配列の要素を逆順にする std::reverse を使って、
- 配列を昇順にソートする (
std::sortを使う) - ソートした配列を逆順にする (
std::reverseを使う)
とすれば降順に並び替えられた配列
[8, 7, 6, 5, 3, 2]
が得られます。
複雑な条件で並び替える
さて、あなたは の倍数がとても好きだとします。なので配列をソートしたときに
の倍数はその他の数より前に来てほしいです。ただし
の倍数同士や
で割り切れない数同士は昇順に並べます。つまり、配列
[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 |
番目に成績の良い生徒の出席番号は
なので答えは
です。
以上の考察からこの問題は
- 出席番号・テストの点数の情報から、生徒を成績の良い順に並べる
- 前から K 番目の生徒の出席番号を見る
とすれば解けることが分かりました。1.の部分で条件を指定したソートを行う必要があります。比較関数を用いたソートは
bool cmp(const T &a, const T &b)
という形式を持つ関数を std::sort の第3引数に与えればいいです。関数の返り値は
aがbより (ソート後の配列で) 前に来てほしいなら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ならばlhsがrhsより前に来てほしいです。したがってこのときはtrueを返します。- 逆に
lhs.score < rhs.scoreならばlhsはrhsより後ろに来てほしいので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::sort と std::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問目を解いてみましょう。問題を再掲します。
整数値の配列が与えられる。
の倍数とその他の数では
上の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株式会社
TechFUL
ワーシャルフロイド 入門
こんにちは！ganariyaです。
今回はグラフ理論のアルゴリズム、「ワーシャルフロイド」についてです。
実世界において、グラフ理論はあらゆるところで利用されます。
例えば、インターネットにおける通信パスや、JRなどの電車の経路パス探索です。
これらはグラフ理論を発展させて、実務的に使用しているものです。
グラフ理論は殆ど、駅などをノード、道路などをエッジとして扱い、点と線が結ばれたものとして扱われます。
グラフのキホン（1）グラフ概要編やグラフのキホン（2）表現方法と探索編の記事を読むとグラフの基礎が身につくと思います。
そして、グラフ理論で扱われる大きなジャンルの一つには、最短経路問題というものがあります。
これは、与えられたグラフの2つのノード間の最小のコストの経路を見つけるというものです。
例えば、以下のようなグラフがあったとします。
以上のようなグラフで、始点から終点
までの最短経路を求めたいです。
これは以下のようになります。
以上のように、通っていくと、最短経路のコストは15となり、これが最小のコストとなります。
このように、最短経路を求めるアルゴリズムはいくつかありますが、今日はそのうちの一つである「ワーシャルフロイド」を掘り下げてみたいと思います！
続きを読む