合并排序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())