實現Bin Fu的近似求和算法

Question

我試圖用真實語言實現Bin Fu'sapproximate sum algorithm 以更好地感受它是如何工作的。

In a nutshell，這是一個有效計算$（1+ε）$ - $ s（x）= \ sum_ {i = 1}^n x_i $的邊界的算法，其中 $ x $是一個已排序的花車矢量。但我必須做錯事，因爲運行該算法會導致一個錯誤 （我也不是很熟悉僞算法語言，並且像數組邊界檢查這樣的東西似乎隱含在此代碼中）。

這是我迄今爲止的非工作代碼，任何提示/問題的幫助將受到歡迎 - 我是語言不可知的，我只是使用R，因爲它是一個索引（算法是1 -index）開源的解釋語言：

ApproxRegion<-function(x,n,b,delta){ 
    if(x[n]<b) return(NULL) 
    if(x[n-1]<b) return(c(n,n)) 
    if(x[1]>=b) reurn(c(1,n)) 
    m1<-2 
    while(x[n-m1**2+1]>=b) m1<-m1**2 
    i<-1 
    m1<-m1 
    r1<-m1 
    while(m1>(1+delta)){ 
     m1<-sqrt(m1) 
     if(x[n-floor(m1*r1)+1]>=b){ 
      r1<-m1*r1 
     } else { 
      r1=r1 
     } 
     i=i+1 
    } 
    return(c(n-floor(r1*m1)+1,n)) 
}  
ApproxSum<-function(x,n,epsilon){ 
    if(x[n]==0) return(0) 
    delta<-3*epsilon/4 
    r1p<-n 
    s<-0 
    i<-1 
    b1<-x[n]/(1+delta) 
    while(b1>=((delta*x[n])/(3*n))){ 
     Ri<-ApproxRegion(x=x,n=r1p,b=b1,delta=delta) 
     r1p<-Ri[1]-1 
     b1<-x[r1p]/(1+delta) 
     s1<-(Ri[2]-Ri[1]+1)*b1 
     s<-s+s1 
     i<-i+1 
    } 
    return(s) 
} 
n<-100; 
x<-sort(runif(n)); 
ApproxSum(x=x,n=length(x),epsilon=1/10); 
sum(x) 

筆者提到了一個C++版本，但我無法在網上找到它（在前面的任何幫助，也將是一件好事）。

Modo：我把問題放在這裏（而不是理論上的CS stackexchange站點），因爲它是關於實現問題的。隨意移動。

EDIT

原始代碼有一個 '毛髮' 退出條件（X [I] = $ - \ infty $對於i $ \當量0 $）。 繼馬丁摩根的建議下，我取代了這個事件通過適當的休息，得到下面的代碼：

ApproxRegion<-function(x,b,delta,n){ 
    if(n<=1)   return(NULL) 
    if(x[n]<b)   return(NULL) 
    if(x[n-1]<b)   return(c(n,n)) 
    if(x[1]>=b)   return(c(1,n)) 
    m<-2 
    xit<-0 
    while(!xit){ 
     if(n-m**2+1<1)  break 
     if(x[n-m**2+1]<b) break 
     m<-m**2 
    } 
    i<-1 
    r<-m 
    while(m>=(1+delta)){ 
     m<-sqrt(m) 
     if(n-floor(m*r)+1>0){ 
      if(x[n-floor(m*r)+1]>=b) r=m*r 
     } 
     i<-i+1  
    } 
    return(c(n-floor(m*r)+1,n)) 
}  
ApproxSum<-function(x,n,epsilon){ 
    if(x[n]==0) return(0) 
    delta=3*epsilon/4 
    rp<-n 
    s<-0 
    i<-1 
    b<-x[n]/(1+delta) 
    while(b>=delta*x[n]/(3*n)){ 
     R<-ApproxRegion(x,b,delta,rp) 
      if(is.null(R)) break 
     if(R[1]<=1) break 
     rp<-R[1]-1 
     b<-x[rp]/(1+delta) 
     si<-(R[2]-R[1]+1)*b 
     s<-s+si 
     i<-i+1 
    } 
    return(s) 
} 

現在，它的工作原理：

n<-100; 
set.seed(123) 
x<-sort(runif(n)); 
ApproxSum(x=x,n=length(x),epsilon=1/10); 
sum(x) 

Answer 1

通過了部分答案的方法...有算法沒有明確處理的邊緣條件。例如，在ApproxRegion中，需要再次保護n = 0（返回值應該爲NULL？）或1（c（n，n）？），否則第一或第二條件x[n] < b,x[n - 1] < b將不按照預期進行評估（例如， 0]返回數字（0））。同樣，循環中的測試必須防範m1**2 > n + 1，否則您將以負數下標。

我認爲在ApproxSum中有類似的問題，特別是當ApproxRegion返回時，例如c(1, 1)（因此r1p == 0，b1 = integer（））。看到更新的實現將會很有趣。