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

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

但显然这是不可能的!!!那么请问有什么想法吗？

干杯， 卡洛斯

Answer 1

看起来您正在尝试执行 Fisher 精确检验或排列检验之类的操作。如果是这样，您可以尝试使用像 R 这样的统计包，它专为执行此类操作而设计，并且可能已经内置了最高效的算法。

除此之外，据我了解，您将样本分成 n 个子组 (y)，然后将每个子组分成 k 个子组。您想找到每个子子组的最小元素。

一个相当有效的解决方案是:创建 n*k 个唯一标识符，以及一个映射，指示每个标识符对应于哪个子子组。然后，将这些数字(使用相同的分布)随机分配给您的样本观察结果(就像您之前一样)。使用有效的现场排序(例如具有正确选择的枢轴的QuickSort)通过标识符对样本进行排序，以便所有具有相同标识符的元素都存储在连续的内存块中。这需要对数线性时间，因此应该非常快。

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

希望对您有所帮助。