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))) # 以下3行も似たようなことをしていて気になる
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コード最適化のコツと実例集]] に戻る~
「工学のためのデータサイエンス入門」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))) # 以下3行も似たようなことをしていて気になる
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
ページ名: