Rコードの最適化例：クイックソート

「工学のためのデータサイエンス入門」215-216頁の例、再帰的関数の例。このコードもアルゴリズムの説明を忠実にコード化したという意味で教育的ですが、いかんせんこのままでは遅過ぎ、大きな x を扱えません。

# オリジナルコード(注：少し編集。なお本の中の i0 <- sample(1, 1:n) は間違いです) 
quick <- 
  function(data){  
    n <- length(data)  
    if (n <= 1) return(data) # 以下二行は例外処理(これは if 文の出番) 
    if (n == 2) {if (data[1] < data[2]) return(data) else return(data[2:1])} 
    i0 <- sample(1:n, 1)  
    s1 <- s2 <- numeric(0)  # 最終長さが未定のベクトルを利用(出来れば避けたい)
    x <- data[-i0]  
    for (i in 1:(n-1)){     # このループが目障り  
      if (x[i] < data[i0]) s1 <- c(s1,x[i]) else  s2 <- c(s2,x[i]) 
    }  
    if (length(s1) == 0) return(c(data[i0], quick(s2))) # 以下３行も似たようなことをしていて気になる 
    if (length(s2) == 0) return(c(quick(s1), data[i0]))  
    return(c(quick(s1), data[i0], quick(s2)))
}

# Chambers によるコード(少し編集)、「データによるプログランミング」森北出版 (2002) 68頁
# ほれぼれする見事なコード(さすが S 言語の開発者！)
# 上のコードの for loop をベクトルの添字操作で隠す(高速化のおまけつき)
# 条件 length(x) <= 1 を length(x) == 1 にしてはいけません (x が空の可能性あり)
# x[x < fence] は x の要素の内で値が fennce 未満のもの全体(numeric(0), i.e. 長さゼロとなる可能性)
# x[x == fence] は x の要素の内で値が丁度 fennce のもの全体
# x[x == fence] を 単に fence としては絶対いけません(タイを含む可能性)
# x[x > fence] は x の要素の内で値が fence を越えるもの(numeric(0), i.e. 長さゼロとなる可能性)
# ベクトルに numeric(0) を連結しても変わらないことを利用して quick() の最後の目障りな三行を一行ですます
quicksort <- 
  function (x) {
    if (length(x) <= 1) return(x)
    if (length(x) == 2) {if (x[1] <= x[2]) return(x) else return(x[2:1])}
    fence = sample(x,1)  # 添字を使わず x の要素を直接無作為に取り出している
    return( c(quicksort(x[x < fence]), x[x == fence], quicksort(x[x > fence])) )
  }

# 最悪ケースで比較
system.time(x <- quick(10000:1))
[1] 5.58 0.02 5.61 0.00 0.00
system.time(x <- quicksort(10000:1))
[1] 0.63 0.00 0.64 0.00 0.00
system.time(x <- sort(100000:1))  # もちろん組み込み関数 sort() を使えば一瞬
[1] 0.01 0.00 0.03 0.00 0.00

Rコードの最適化例：クイックソート

最新の20件