パスワードを忘れた? アカウント作成
452383 journal

hixの日記: 配列

日記 by hix
ソートされている配列を作る。
元は、ファイルか何かでこちらはソートされていない。
そうした場合、値を追加する段階からソートしながら配列を形成するやり方と、とりあえず配列を形成しておいてあとでソートを掛けるやり方とでは、後者の方が時間が掛からないようだ。
但し、値の重複を許さないとした場合、これから追加しようとする値を検索して配列に無い値のみを追加する(検索を効率化する為、ソートしながら配列を形成することになる)やり方と、とりあえず全て追加しておいて、ソートを実行し、重複した値を取り除くやり方とでは、前者の方が時間が掛からないようだ。但し、重複がそれほど発生しない場合に於いては逆に後者のほうが時間が掛からない。

配列の形は任意なので、値の追加時の検索はバイナリサーチを、ソートはqsort()を行っている。

値の重複を取り除くには、配列上の隣同士の値を比較した結果が等しいなら配列のその後ろを移動して詰める、という方法を取っている。
ここでは、同じ値が2つを超えて続く場合もあり、重複の度に間を詰めていたのでは効率が悪いので、重複の続きを見てから詰めるようにしている。
また、配列の先頭方向から処理するのではなく、配列の末尾方向から処理したほうが、より効率的である。先頭方向からの処理だと、移動するのは未処理の部分なので、値の重複を抱えたまま移動することになるが、末尾方向からの処理だと、移動するのは処理済の部分で、値の重複が既に取り除かれているので、移動される量がより少なくて済む。
配列の移動は意外とコストが高い。
この議論は賞味期限が切れたので、アーカイブ化されています。 新たにコメントを付けることはできません。
typodupeerror

UNIXはシンプルである。必要なのはそのシンプルさを理解する素質だけである -- Dennis Ritchie

読み込み中...