合併排序R

Question

我正在自學該書"Introduction to Algorithms" by Cormen et alli.在他們的書中，他們使用的假代碼假設數組是通過指針傳遞的（通過引用）。這不同於R（對象是按值傳遞的），所以我在嘗試儘可能地轉換它們的僞代碼時遇到了一些困難，特別是在涉及遞歸時。大多數情況下，我必須以不同的方式實施。例如，使用合併排序算法，他們定義合併函數（我認爲我已經正確翻譯了）和遞歸MergeSort函數（其中直接翻譯爲R不起作用）。

在僞碼合併功能如下，其中：A是一個數組且p，q和r爲索引到所述陣列使得P < q <河該過程假定子陣列A [p：q]和A [q + 1：r]按排序順序排列。它融合了它們形成一個子數組排序代替現有的子陣列[P：R]

Merge(A, p, q, r) 
n1 = q - p + 1 
n2 = r - q 
let L[1...n1+1] and R[1...n2+1] be new arrays 
for i = 1 to n1 
    L[i] = A[p+i-1] 
for j = 1 to n2 
    R[j] = A[q+j] 
L[n1+1] = infinite 
R[n2+1] = infinite 
i=1 
j=1 
for k = p to r 
    if L[i] <= R[j] 
     A[j] = L[i] 
     i = i + 1 
    else 
     A[k] = R[j] 
     j = j + 1 

我已經翻譯成R作爲：

Merge <- function(a, p, q, r){ 
    n1 <- q - p + 1 
    n2 <- r - q 
    L <- numeric(n1+1) 
    R <- numeric(n2+1) 
    for(i in 1:n1){ 
    L[i] <- a[p+i-1] 
    } 
    for(j in 1:n2){ 
    R[j] <- a[q+j] 
    } 
    L[n1+1] <- Inf 
    R[n2+1] <- Inf 
    i=1 
    j=1 
    for(k in p:r){ 
    if(L[i] <= R[j]){ 
     a[k] <- L[i] 
     i <- i +1 
    }else{ 
     a[k] <- R[j] 
     j <- j+1 
    } 
    } 
    a 
} 

它似乎很好地工作。現在

Merge(c(1,3,5, 2,4,6), 1, 3, 6) 
[1] 1 2 3 4 5 6 

的歸併函數在僞代碼定義如下：

MergeSort(A, p, r) 
if p < r 
    q = (p+r)/2 
    MergeSort(A, p, q) 
    MergeSort(A, q+1, r) 
    Merge(A, p, q, r) 

這假定A被參考，並且每一個變化是每遞歸調用，這是不正確的可見傳遞在R.

所以，鑑於上述定義的Merge功能，你將如何實現在R上的MergeSort功能，以獲得正確的結果？ （如果可能是，並且優選但不是必要的，有點類似於僞代碼）

Answer 1

試圖對允許在語言中通過引用的語言編寫的僞代碼進行字面轉換那不支持它是一個可怕的想法。 R的意思並不是要在一個函數內的數組的切片上工作。這不是一個合適的翻譯。該僞代碼應該傳達算法的精神，然後將其轉化爲適當的語言。這裏的歸併精神的一個可能翻譯成R.

mmerge<-function(a,b) { 
    r<-numeric(length(a)+length(b)) 
    ai<-1; bi<-1; j<-1; 
    for(j in 1:length(r)) { 
     if((ai<=length(a) && a[ai]<b[bi]) || bi>length(b)) { 
      r[j] <- a[ai] 
      ai <- ai+1 
     } else { 
      r[j] <- b[bi] 
      bi <- bi+1   
     } 
    } 
    r 
} 
mmergesort<-function(A) { 
    if(length(A)>1) { 
     q <- ceiling(length(A)/2) 
     a <- mmergesort(A[1:q]) 
     b <- mmergesort(A[(q+1):length(A)]) 
     mmerge(a,b) 
    } else { 
     A 
    } 
} 

您可以

x<-c(18, 16, 8, 7, 6, 3, 11, 9, 15, 1) 
mmergesort(x) 

運行在這個版本中的事情是通過更換參考：所有函數返回新值。另外，我們不是傳遞幻燈片索引，而是簡單地將矢量集合起來，並將它們全部傳遞給函數。

當然，由於在中間步驟發生的所有內存重新分配，此版本的性能可能會受到影響。由於該語言的設計原因，在基本R中沒有太多可以做的事情。如果你喜歡，你可以編寫C/C++代碼並通過foreign language interfaces調用它。

如果你想離開你的Merge（並忽略R方式做事情），那麼你可以做...

MergeSort<-function(A, p, r) { 
    if(p < r) { 
     q <- floor((p+r)/2) 
     A <- MergeSort(A, p, q) 
     A <- MergeSort(A, q+1, r) 
     Merge(A, p, q, r) 
    } else { 
     A 
    } 
} 
x <- c(18, 16, 8, 7, 6, 3, 11, 9, 15, 1) 
MergeSort(x, 1, length(x)) 

UPDATE：

包括標準制定線束

m1<-function() { 
    x<-sample(1000, 250); 
    mmergesort(x) 
} 

m2<-function() { 
    x<-sample(1000, 250); 
    MergeSort(x, 1, length(x)) 
} 

microbenchmark(m1(), m2())