time~派生開発、組み込み開発周りのこと。sort)を例にRustのクイックツアーをするのですが、私は本書でバイトニックソートが初見のため理解に時間がかかりました。理解できたので、ブログに備忘録しておきます。計算量がデータの要素数で決まり、常にO(nlogn)。データの要素数が2のべき乗でないといけない。全ての要素数に対応するにはダミーデータ追加などの対応が必要。アルゴリズムはソーティングネットワークのモデルで表され、容易に並列化できる*1。バイトニックソートのアルゴリズム「昇順+降順のバイトニック列」にする。2^n・・・2^0間を昇順(降順)で比較する。高速化プログラミングバイトニック列とは前半と後半が逆の順序で並んでいるデータ列のこと。バイトニックソートの実例16要素を手動ソートしつつ、Rustのデバッガ環境で逐次ソートの状況を確認することでようやく理解できました。その逐次処理をまとめたのが下記の図になります。ソートするデータ:[10,30,11,20,4,330,21,110,12,31,15,22,41,331,220,111]前半8要素を昇順にソートするステップ同じ色でハッチングした要素がスワップした箇所になります。midpointによって比較する要素が決定します。書籍やWebページを読んでも最初は全く理解できませんでした。アルゴリズムの説明文からステップ1が完了して、ステップ2を行うように思うのですが、そうではないことを理解する必要がありました。wikipediaの実装例からわかるのですが、再帰的に関数コールして、最初のスワップ処理は隣の要素との比較になります。そこから2^n乗離れた要素と比較していったり、また2^0乗離れた(つまり、隣)要素と比較したりを繰り返します。そのいったりきたりがイメージしにくかったです。ポイント最初は配列を1/2ずつしていき、隣の要素と比較する。1/2していく時に、前半は昇順、後半は降順にソートするように設定する。結合していくときは、親がコールした順序に従ってソートする。おわりにRustに入門しようとしたら、ソートアルゴリズムの知識不足で1回休みという感じになりました。それでもデバッガ使いつつ、理解するところまで到達できたので良かったです。デバッガが非常に理解の助けになりました。月別アーカイブ検索スターをつけました引用をストックしましたストック一覧を見る閉じる引用するにはまずログインしてくださいログイン閉じる引用をストックできませんでした。再度お試しください閉じる限定公開記事のため引用できません。