プログラマのつれづれなるままにプログラマのつれづれなるままに音宮志久が思ったことなどをネタにします。プログラムネタ・数学ネタがメインです。ソートアルゴリズムをマルチスレッドでソートアルゴリズムをマルチスレッドでコメントを残す唐突ですが、何となく気になったのでやってみました。ただの話題作りとも言います。アルゴリズムのレベルでマルチスレッド化できるソートアルゴリズムを考えるよく使用される(あるいははサンプルなどで登場する)ソートアルゴリズムとしては以下の物があります。バブルソート選択ソート挿入ソートシェルソートクイックソートヒープソートマージソートこの中でマルチスレッド化が出来る物と出来ない物を考えてみたいと思います。マルチスレッド化するため必要な条件としてはソート時にメモリ空間が競合しないことになります。常に全域を調べていくソート法ではマルチスレッド化が出来ないですね。ちなみに、普通にどのソート法であったとしてもソート対象領域をいくつかに分けるそれぞれに対してソートを適応(これはマルチスレッド化可能)完了した領域を併合する(マージソートの併合と同じ)と言う方法でマルチスレッド化をはかることは出来ますが・・・。言うわけで分類をしてみるとマルチスレッド化が出来るシェルソートクイックソートマージソートマルチスレッド化が出来ないバブルソート選択ソート挿入ソートヒープソートとなります。・・・あっていますよね?どうやってマルチスレッド化する?マルチスレッド化可能な各アルゴリズムで、どの部分がマルチスレッド化可能かは、アルゴリズムの流れを見て見れば分かります。分割した領域それぞれに1.および2.を再度行う(これはマルチスレッド化可能)なお、対象の領域が狭すぎる場合は領域分割ではなく別のソート法を適応する場合が一般的(この場合、ソート法は挿入ソートが主に使われる)マージソート対象のデータ列の領域を分割する分割された領域がある程度より小さくなった段階で適当なソートを行う(データ数が1(ソートしない)でも可。非マルチスレッドのアルゴリズムとマルチスレッド化したアルゴリズムで時間をとった結果を示してみます。データは32bit符号あり乱数を2^26(67108864)個でテストしています。各ソートに与えるデータは同一のデータを与えてあります。マルチスレッド数は私のPCのCPUコア数でもある4を指定してあります。STLの結果を参考として書いてあります。STLはマルチスレッド化できませんのでそのままです。sec)マルチスレッド化でそれなりに高速になっているのが分かると思います。QuickSortの伸び率が3倍前後とかなりいい結果ですね。この結果には微妙なトリックがマルチスレッド化するときに問題になるのが「タスクの大きさをどれくらいにするか」という物です。タスクが小さくなりすぎるとマルチスレッド化したときにタスクの発行やスレッドの管理に時間を使ってしまい、速度が落ちてしまう、と言う現象がおこります。今回のように整数のソートだと比較と代入がかなり早く行われるのであまりに少ないデータ数までタスクとして発行してしまうととんでもないことになります。その結果を示すためにちょっとグラフを作ってみました。QuickSortとMergeSortをマルチスレッドタスクとして発行する数を変えてテストした物です。縦軸はソートが完了するまでにかかった時間(秒)、横軸はタスクを発行する分割限界数です。グラフよりクイックソートの場合、2^12個~2^22個くらいのデータまででソートタスクを発行すると速度がよいマージソートの場合、2048個くらいのデータまででマージタスクを発行すると速度がよいどちらも512個より少ない数でもタスクを発行してしまうと極端に実行効率が悪くなるこの辺はデータ数、CPUの各コア演算速度、CPUの有効演算コア数によって変わるので参考データですが、やはりあまりに細かく分割すると良くないことは確認できました。いっても、簡単なソートくらいでマルチスレッド処理は普通使わないよね・・・まあ、こんなものでマルチスレッド化する意味があるとすればせいぜいデータベースのソートくらいですか・・・。ゲームなどで少量のデータをソートするくらいなら普通にやるのが正しいですしね・・・。最後にコードを無用だと思いますが何となく示してみます。乱数処理やスレッドプールは自分で作ってくださいね。MergeSortは面倒だったので2の累乗専用となっています。コメントをキャンセルメールアドレスが公開されることはありません。志久プログラムネタや思いついたり世間で話題になっている数学ネタを解説したりしています。プログラマとしては今年度(つまり2020年3月)までの復帰となるか、完全復帰となるか、別の仕事に戻るかは運と実力次第。ちなみに教育系のプログラムでもOKです。アクセスカウンタアクセス数:スポンサーリンク。