有效地计算每个组和子组的最小值

Question

想象一下，我们从一些人群中随机抽取了一个样本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引入另一个分配变量di，这将指示从中采样yi的子组(以及按概率采样的子组)。有int -m个子组，所以di e {0, .., m-1}。然后(zi=j, di=s)表示观察值yi已经从组j和子组s中提取出来。

我如何有效地计算{i:zi=j, di=s}上的最小yjs_min，因为我必须在每次迭代中这样做？即yi上的最小值，使得zi=j和带有j=0, ..k-1和s=0,..,m-1的di=s

如果能像这样做，那就太好了。

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]];  
    }
}

但显然这是不可能的！所以有什么好主意吗？

干杯，卡洛斯

Answer 1

看起来您正在尝试做一些像Fisher精确测试或排列测试之类的事情。如果是这样的话，您可以尝试使用像R这样的统计软件包，它是为完成这类工作而设计的，并且很可能已经内置了最有效的算法。

除此之外，据我所知，你将样本分成n个子组(y)，然后每个子组又分成k个子组。你想找出每个子群的最小元素。

一种相当有效的解决方案是:创建n*k个唯一标识符和一个映射，该映射指示它们中的每一个对应于哪个子组。然后，随机分配这些数字(使用相同的分布)到您的样本观察值(就像以前一样)。使用有效的就地排序(就像使用正确选择的枢轴的快速排序)来按标识符对样本进行排序，以便具有相同标识符的所有元素都存储在连续的内存块中。这需要对数线性时间，所以它应该非常快。

然后，您只需按顺序遍历数组，并找到每个唯一标识符的最小元素。这应该需要线性时间和n*k额外空间。

希望这能有所帮助。