読者です 読者をやめる 読者になる 読者になる

DISTRICT 37

なにか

Pythonによるアルゴリズムクイックリファレンス:選択ソート

Python

選択ソート

これも力技の一種。曰く、整列アルゴリズムの中で最も性能が悪いので詳しく述べるのはやめるとの事。確かにこれに関して割いたページ数は2ページ(半ページ2枚なので実質1ページ)と扱いが小さい不遇なアルゴリズム

未ソート分の中から最小値を探し、それを先頭のデータと交換するという処理。数列がどんな状態であろうと最後まで同じ処理を繰り返すので性能が悪いというのがわかる。

## benchmarker:         release 4.0.1 (for python)
## python version:      2.7.6
## python compiler:     GCC 4.8.2
## python platform:     Linux-3.13.0-48-generic-i686-with-Ubuntu-14.04-trusty
## python executable:   /usr/bin/python
## cpu model:           Intel(R) Core(TM) i5-4310U CPU @ 2.00GHz  # 2497.120 MHz
## parameters:          loop=1000, cycle=1, extra=0

##                        real    (total    = user    + sys)
default             hello
    0.0443    0.0500    0.0500    0.0000
insertion               0.3179    0.3200    0.3200    0.0000
median                  0.3209    0.3200    0.3200    0.0000
quick                   0.1730    0.1700    0.1700    0.0000
select                  0.2465    0.2500    0.2500    0.0000

## Ranking                real
default                 0.0443  (100.0) ********************
quick                   0.1730  ( 25.6) *****
select                  0.2465  ( 18.0) ****
insertion               0.3179  ( 13.9) ***
median                  0.3209  ( 13.8) ***

## Matrix                 real    [01]    [02]    [03]    [04]    [05]
[01] default            0.0443   100.0   390.3   556.2   717.1   723.9
[02] quick              0.1730    25.6   100.0   142.5   183.7   185.5
[03] select             0.2465    18.0    70.2   100.0   128.9   130.2
[04] insertion          0.3179    13.9    54.4    77.6   100.0   100.9
[05] median             0.3209    13.8    53.9    76.8    99.1   100.0

おや?挿入ソートとか中央値ソートよりもベンチマーク出てるぞ?誰だ性能が悪いといったのは。1から100までの数列でテストしているので、これを1000までと延ばしたらどうだろうと試してみたが、やっぱり結果は中央値や挿入ソートよりも出る。 という事はこれまで書いたコードに何処かムダがあるのか?それともこのテストケースだから性能が出るのか?アルゴリズムって奥が深い。

アルゴリズムクイックリファレンス

アルゴリズムクイックリファレンス