ビジネスバンクグループ新卒エンジニアのしみきょんこと清水恭子です！ 社会人になって半年くらいが立ち日々奮闘しているしみきょんですが、最近気になっていることがあったので調べてみました。

それは、rubyのsortについてです。 学生時代、ライブラリなどを使用せず地道に選択ソートを書いて実装していたことがあったのですが実務ではそんなことは当然ありません。 今までの自分の実装がどれほど非効率であったか気になったのでrubyのsortを調べて比べてみました。

今回は、0~999のランダムに並べられた数字をソートした計算時間の平均数値(100回)をみてみました。

今まで書いていた選択ソート

  a = (0..999).to_a
  data = a.sample(a.size)
  for n in 0..(data.length-1) do
    min = data[n]
    min_position = n
    for m in (n+1)..(data.length-1) do
      if data[m] < min
        min = data[m]
        min_position = m
      end
    end
    tmp = data[n]
    data[n] = min
    data[min_position] = tmp
  end

結果：約0.037s

続いてrubyのsort

こちらにArrayクラスのsortがあるらしいです。
(https://github.com/ruby/ruby/blob/trunk/array.c)

  a = (0..999).to_a
  data = a.sample(a.size)
  data.sort

結果：約0.000211s

おお、全然違います。
rubyのsortはクイックソートに似たようなものを使用しているようなのでクイックソートも試してみました。

クイックソート

  a = (0..999).to_a
  data = a.sample(a.size)
  def quick_sort(a, left, right)
    return a if left >= right
    pivot = a[((left + right).to_f/2.to_f).ceil]
    i = left
    j = right

    while true
      i += 1 while a[i] < pivot
      j -= 1 while a[j] > pivot
      break if (i >= j)
      a[i], a[j] = a[j], a[i]
      i += 1
      j -= 1
    end
    quick_sort(a, left, i-1)
    quick_sort(a, i, right)
    a
  end
  quick_sort(data, 0, data.size - 1)

結果：約0.000660s

クイックソートでも全然ちがいます。

今まで、いかに非効率な実装をしていたのかとこれを見ると一目瞭然です。

またrubyのsortでも、文字列の並び替えなどといったsort条件が複雑になる場合はsort_byを使用したほうが優れていたりだとか、 sortって普通要素数が計算量に比例しているイメージですが、要素の最大値が計算量を支配している"sleep sort"というsortがあったりだとか、 調べれば調べるほど奥が深いです、、、おもしろいですね

sortと聞くと一見ただの並び替えというイメージがありますがデータの持ち方によってそれにあったsortを選ばないと計算量に差がでてくるので気をつけたいです。

エンジニア募集中！

ビジネスバンクグループではエンジニアを募集中しています。

弊社が採用しているテクノロジや開発環境に興味を持った方は、 ここから是非エントリー を！