有效計算每個組和小組的最小值

想象一下，我們從一些人口中抽取了一個隨機樣本y1, y2, ...,yn，所以double y[]和int n是已知的。我們的人羣中有一些羣體，但我們並不確切知道在某個特定羣體上分配了哪些觀察結果。因此，對於每個yi，我們引入一個分配變量zi，告知我們已從中繪製了哪個組yi。現在我們假設有int k組，所以zi e {0, .., k-1} for all i。現在爲我需要迭代我的算法的組進行推理，幾次說50,000或100,000。在每次迭代中，我們將概率地將每個觀察分配給某個組，因此我的分配數組int z[]將會改變。在這種情況下，要計算每組中的觀察次數，最小值很容易;有效計算每個組和小組的最小值

int nj[k], yj_min[k]; 

/* initializing the variables at each iteration */ 
for(j=0; j<k; j++){ 
    nj[j]=0; 
    yj_min[j]=y[n]; /* y[] are ordered so y[n] is the maximum*/ 
} 

for(i=0; i<n; i++){ 
    nj[z[i]] = nj[z[i]] + 1; 
    if(yj_min[z[i]]) < y[z[i]]){ 
     yj_min[z[i]] = y[z[i]]; 
    } 
}

但如果我們引入對於每個觀測義，將指示從哪個yi已採樣的子組（以及概率性地取樣）進一步分配變量二。有int m個子組，所以di e {0, .., m-1}。然後(zi=j, di=s)指示觀察yi已經從組j和子組s得出。

我該如何計算EFFICIENTLY，因爲我必須在每次迭代中執行此操作，最小yjs_min高於{i:zi=j, di=s}？即最小過yi這樣zi=j和di=s與j=0, ..k-1和s=0,..,m-1

這將是巨大的像做

for(i=0; i<n; i++){ 
    njs[z[i]][d[i]] = njs[z[i]][d[i]] + 1; 
    if(yjs_min[z[i]][d[i]]) < y[z[i]][d[i]]){ 
     yjs_min[z[i]][d[i]] = y[z[i]][d[i]]; 
    } 
}

，但顯然這是不可能的！那麼請有什麼想法？

乾杯，卡洛斯

來源

2011-04-16 Carlos

您能否提供一些示例數據和輸出，以便我們可以更好地感受您正在嘗試做什麼？謝謝。 – erisco 2011-04-16 19:30:31

根據我的理解，''''''''''''''''''''''''''''值'n'值，所以如何使用'y [z [i]]'？ – steabert 2011-04-16 22:29:29

它看起來就像你試圖做一些像Fisher精確檢驗或置換檢驗。如果是這樣，你可以嘗試使用像R這樣的統計軟件包，該軟件包可以完成這種功能，並且可能已經內置了最高效的算法。除此之外，據我所知，您將樣本分爲n個子羣（y），然後將這些子羣中的每個子羣劃分爲k個子羣組。您想要查找每個子子組的最小元素。

一個合理有效的解決方案是：創建n * k個唯一標識符，以及一個映射表明每個子分組對應哪個子分組。然後，隨機將這些數字（使用相同的分佈）分配給您的樣本觀察值（就像您以前那樣）。使用高效的就地排序（如具有正確選擇的透視的快速排序）按標識符排序樣本，以便具有相同標識符的所有元素都存儲在連續的內存塊中。這需要對數線性時間，所以它應該非常快。

然後，您只需要按順序遍歷數組，然後找到每個唯一標識符的最小元素。這應該需要線性時間和n * k額外的空間。

希望有所幫助。

來源

2011-05-20 23:52:08

有效計算每個組和小組的最小值

回答

相關問題