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

SIZE(20){COLOR(magenta){Rコードの最適化例：クイックソート}}  [[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

タイムスタンプを変更しない

SIZE(20){COLOR(magenta){Rコードの最適化例：クイックソート}}  [[Rコード最適化のコツと実例集]] に戻る~

テキスト整形のルールを表示する

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

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