→ andrew43: 我覺得瓶頸應該是你的演算法不夠快，倒不是填值的loop 08/30 14:27
→ celestialgod: preallocation 08/30 20:10
→ celestialgod: 還有 你有必要先搞動[跟[[.... 08/30 20:10
→ celestialgod: 懂 08/30 20:10
→ celestialgod: kai_dtw這個函數怎麼實做講出來比較快 08/30 20:11
→ celestialgod: 這個函數可能是最大的瓶頸 08/30 20:11
> -------------------------------------------------------------------------- <
作者: pk790127 (<>) 看板: R_Language
標題: Re: [問題] 兩兩比較運算
時間: Fri Sep 1 14:40:22 2017
※ 引述《pk790127 (<>)》之銘言：
: [問題類型]:
: [軟體熟悉度]:
: 使用者(已經有用R 做過不少作品)
: 算是有學了一陣子,但感覺程式邏輯還是很差
: [問題敘述]:
: [關鍵字]: dtw , 距離矩陣 ,兩兩比較
: 以上 就是我的問題敘述,不曉得有沒有表達清楚
: 基本上就是多層迴圈太慢了,我也正在嘗試使用lapply家族進行運算
: 謝謝~~
回應自己的問題,板友提出我的問題瓶頸不在於矩陣填值的部份,在於我修改的演算法上
實際上,我修改了dtw套件當中的dtw的函式,把權重的概念加進去
我測試了同筆資料用於原始dtw函式與我修改後的dtw(kai_dtw)函式去做運算時間的比較
果真...差了6秒多,問題在於我修改的函式!! (非常感謝兩位版友)
dtw的程式碼如下,我儘截錄我修改的部份,只有增加一個矩陣並做相乘
lm <- NULL
if (is.null(y)) {
if (!is.matrix(x))
stop("Single argument requires a global cost matrix")
lm <- x
}
else if (is.character(dist.method)) {
x <- as.matrix(x)
y <- as.matrix(y)
lm <- proxy::dist(x, y, method = dist.method) #lm x,y 距離矩陣
lm.v<- as.vector(lm) #轉成vector#
weight<-vector() #weight function#
for(i in lm.v){
tmp<-logisticWeight(i,median(lm.v),g)
weight<-c(weight,tmp)
}
lm.v_weight <- lm.v*weight #相乘#
lm<-matrix(lm.v_weight ,length(x),length(y)) #轉回矩陣#
}
else if (is.function(dist.method)) {
stop("Unimplemented")
}
.
.
.
紅色表示我新增的部份,原始程式碼下面還有很多,但我直接省略
在原始function中填入x與y目的是要計算距離矩陣lm
我先將它轉成vector的形式,並且利用logisticWeight函式(自己寫的公式)
並搭配for迴圈逐一的給予Weight(vector的形式),再將lm.v與weight相乘
最後再轉成適當大小矩陣。
簡單來說,原先是矩陣,我運算完(乘上weight)後轉回矩陣,讓它做DTW的運算
logisticWeight函式內容,僅是一般的S形函數
logisticWeight <- function(i,mc,g){
1 / (1 + exp(-g * (i - mc )))
}
我想我應該要優化它賦與權重與相乘的動作,才能達到我降低運算時間的需求
謝謝~
小試了一下,將for loop改成用apply家族,大大改善運算效率
(應該沒有錯吧!?)
weight<-vector() #weight function#
for(i in lm.v){
tmp<-logisticWeight(i,median(lm.v),0.05)
weight<-c(weight,tm)
}
改成
tmp<-sapply(1,function(x){logisticWeight(lm.v,median(lm.v),0.05)})
weight<- as.vector(tmp)
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.116.86.113
※ 文章網址: https://www.ptt.cc/bbs/R_Language/M.1504248024.A.A0B.html
※ 編輯: pk790127 (140.116.86.113), 09/01/2017 16:35:02
→ pk790127: 好像在自問自答...找機會把preallocation研究一下 09/01 18:00
> -------------------------------------------------------------------------- <
作者: celestialgod (天) 看板: R_Language
標題: Re: [問題] 兩兩比較運算
時間: Fri Sep 1 19:15:58 2017
※ 引述《pk790127 (<>)》之銘言：
: ※ 引述《pk790127 (<>)》之銘言：
: : [問題類型]:
: : [軟體熟悉度]:
: : 使用者(已經有用R 做過不少作品)
: : 算是有學了一陣子,但感覺程式邏輯還是很差
: : [問題敘述]:
: : [關鍵字]: dtw , 距離矩陣 ,兩兩比較
: : 以上 就是我的問題敘述,不曉得有沒有表達清楚
: : 基本上就是多層迴圈太慢了,我也正在嘗試使用lapply家族進行運算
: : 謝謝~~
: 回應自己的問題,板友提出我的問題瓶頸不在於矩陣填值的部份,在於我修改的演算法上
: 實際上,我修改了dtw套件當中的dtw的函式,把權重的概念加進去
: 我測試了同筆資料用於原始dtw函式與我修改後的dtw(kai_dtw)函式去做運算時間的比較
: 果真...差了6秒多,問題在於我修改的函式!! (非常感謝兩位版友)
: dtw的程式碼如下,我儘截錄我修改的部份,只有增加一個矩陣並做相乘
: lm <- NULL
: if (is.null(y)) {
: if (!is.matrix(x))
: stop("Single argument requires a global cost matrix")
: lm <- x
: }
: else if (is.character(dist.method)) {
: x <- as.matrix(x)
: y <- as.matrix(y)
: lm <- proxy::dist(x, y, method = dist.method) #lm x,y 距離矩陣
: lm.v<- as.vector(lm) #轉成vector#
: weight<-vector() #weight function#
: for(i in lm.v){
: tmp<-logisticWeight(i,median(lm.v),g)
: weight<-c(weight,tmp)
: }
: lm.v_weight <- lm.v*weight #相乘#
: lm<-matrix(lm.v_weight ,length(x),length(y)) #轉回矩陣#
: }
: else if (is.function(dist.method)) {
: stop("Unimplemented")
: }
: .
: .
: .
: 紅色表示我新增的部份,原始程式碼下面還有很多,但我直接省略
: 在原始function中填入x與y目的是要計算距離矩陣lm
: 我先將它轉成vector的形式,並且利用logisticWeight函式(自己寫的公式)
: 並搭配for迴圈逐一的給予Weight(vector的形式),再將lm.v與weight相乘
: 最後再轉成適當大小矩陣。
: 簡單來說,原先是矩陣,我運算完(乘上weight)後轉回矩陣,讓它做DTW的運算
: logisticWeight函式內容,僅是一般的S形函數
: logisticWeight <- function(i,mc,g){
: 1 / (1 + exp(-g * (i - mc )))
: }
: 我想我應該要優化它賦與權重與相乘的動作,才能達到我降低運算時間的需求
: 謝謝~
: 小試了一下,將for loop改成用apply家族,大大改善運算效率
: (應該沒有錯吧!?)
: weight<-vector() #weight function#
: for(i in lm.v){
: tmp<-logisticWeight(i,median(lm.v),0.05)
: weight<-c(weight,tm)
: }
: 改成
: tmp<-sapply(1,function(x){logisticWeight(lm.v,median(lm.v),0.05)})
: weight<- as.vector(tmp)
其實可以直接改成
lm.v<- as.vector(lm)
lm.v_weight <- sapply(seq_along(lm.v), function(i){
logisticWeight(i, median(lm.v), g)
})
lm.v_weight <- lm.v*weight
...
快就快在sapply會預先配置輸出的vector大小
不然其實weight先給他輸出長度，在用迴圈，速度是一樣的
(詳細可以在板上/preallocation可以找到我的文章)
至於你之前的code可以直接這樣改：
library(dtw)
library(Matrix)
# 產生資料
x <- replicate(10, rnorm(sample(6:10, 1)), simplify = FALSE)
# 直接產生出來要比較的i, j位置，然後用apply餵進去
out <- apply(subset(expand.grid(seq_along(x), seq_along(x)), Var1 > Var2),
1, function(v){
c(v, dtw(x[[v[1]]], x[[v[2]]])$distance)
})
# 把out轉成距離矩陣
output <- as.dist(sparseMatrix(out[1, ], out[2, ], x = out[3, ],
dims = rep(length(x), 2)))
這樣就會很快了(攤手
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 36.235.40.154
※ 文章網址: https://www.ptt.cc/bbs/R_Language/M.1504264562.A.98C.html
※ 編輯: celestialgod (36.235.40.154), 09/01/2017 19:18:16
推 pk790127: 感謝，上篇文我把for轉成apply後就從6秒進步到0.01秒了 09/01 21:27
→ pk790127: （測試資料），會在嘗試本篇的寫法 09/01 21:27