2009-12-19 ソートの速度を決める要因についてメモ 雑記 開発 思いつく限りの要因をあげてみる。 データ内容 個別比較が必要かどうか 比較にかかる時間 比較の分割性 比較の並列度 データ 要素数 読み込みにかかる時間 読み込みの並列度 交換にかかる時間 交換の並列度 ワーキングメモリ 要素数 再帰段数 読み込みにかかる時間 読み込みの並列度 書き込みにかかる時間 書き込みの並列度 初期状態 どの程度ソートされているか 事前にソートの程度を知っているか 具体例は。 スパゲティソート 個別に比較する必要がない。比較にかかる時間は定数。並列度は要素数と同じ。 辞書順ソート、多倍長数値のソート 個別に比較する必要がない。比較にかかる時間が各データ長Nに比例する。比較をN段階に分割できる。並列度は要素数と同じ。 データベース上のソート 通常、要素数は非常に大きい。読み込みにかかる時間も大きい。交換にかかる時間も大きいが、読み込みより小さい。並列度は実装に大きく依存し、それなりに高いものが多い。 〆。 通常はソートの計算量の指標として個別比較の回数を用いる。もちろんこれは大抵の場合に適切だが、交換よりも読み書きで律速される条件も多い。読み書きは特にハードウェアへの依存が大きく、同一アルゴリズムでも実装によって効率が大きく変わってくる。身近な例としてキャッシュヒット率があるだろう。
