Rコードの最適化例：クイックソート
をテンプレートにして作成
[
トップ
] [
新規
|
一覧
|
検索
|
最終更新
|
ヘルプ
]
開始行:
SIZE(20){COLOR(magenta){Rコードの最適化例：クイックソート...
「工学のためのデータサイエンス入門」215-216頁の例、再帰的...
# オリジナルコード(注：少し編集。なお本の中の i0 <- samp...
quick <-
function(data){
n <- length(data)
if (n <= 1) return(data) # 以下二行は例外処理(これは...
if (n == 2) {if (data[1] < data[2]) return(data) els...
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 <- ...
}
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 によるコード(少し編集)、「データによるプログ...
# ほれぼれする見事なコード(さすが S 言語の開発者！)
# 上のコードの for loop をベクトルの添字操作で隠す(高速...
# 条件 length(x) <= 1 を length(x) == 1 にしてはいけませ...
# x[x < fence] は x の要素の内で値が fennce 未満のもの全...
# x[x == fence] は x の要素の内で値が丁度 fennce のもの...
# x[x == fence] を 単に fence としては絶対いけません(タ...
# x[x > fence] は x の要素の内で値が fence を越えるもの(...
# ベクトルに numeric(0) を連結しても変わらないことを利用...
quicksort <-
function (x) {
if (length(x) <= 1) return(x)
if (length(x) == 2) {if (x[1] <= x[2]) return(x) els...
fence = sample(x,1) # 添字を使わず x の要素を直接無...
return( c(quicksort(x[x < fence]), x[x == fence], qu...
}
# 最悪ケースで比較
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)) # もちろん組み込み関数...
[1] 0.01 0.00 0.03 0.00 0.00
終了行:
SIZE(20){COLOR(magenta){Rコードの最適化例：クイックソート...
「工学のためのデータサイエンス入門」215-216頁の例、再帰的...
# オリジナルコード(注：少し編集。なお本の中の i0 <- samp...
quick <-
function(data){
n <- length(data)
if (n <= 1) return(data) # 以下二行は例外処理(これは...
if (n == 2) {if (data[1] < data[2]) return(data) els...
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 <- ...
}
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 によるコード(少し編集)、「データによるプログ...
# ほれぼれする見事なコード(さすが S 言語の開発者！)
# 上のコードの for loop をベクトルの添字操作で隠す(高速...
# 条件 length(x) <= 1 を length(x) == 1 にしてはいけませ...
# x[x < fence] は x の要素の内で値が fennce 未満のもの全...
# x[x == fence] は x の要素の内で値が丁度 fennce のもの...
# x[x == fence] を 単に fence としては絶対いけません(タ...
# x[x > fence] は x の要素の内で値が fence を越えるもの(...
# ベクトルに numeric(0) を連結しても変わらないことを利用...
quicksort <-
function (x) {
if (length(x) <= 1) return(x)
if (length(x) == 2) {if (x[1] <= x[2]) return(x) els...
fence = sample(x,1) # 添字を使わず x の要素を直接無...
return( c(quicksort(x[x < fence]), x[x == fence], qu...
}
# 最悪ケースで比較
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)) # もちろん組み込み関数...
[1] 0.01 0.00 0.03 0.00 0.00
ページ名:
![[RjpWiki]](image/../Rlogo.png "[RjpWiki]")
