Эффективно рассчитать минимум по каждой группе и подгруппе

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

, но если мы введем дополнительную переменную распределения di для каждого наблюдения yi, которая укажет подгруппу, из которой yi был отобран (также отобран вероятностно).Есть подгруппы int m, поэтому di e {0, .., m-1}.Тогда (zi=j, di=s) указывает, что наблюдение yi было взято из группы j и подгруппы s.

Как я могу рассчитать ЭФФЕКТИВНО, так как я должен делать это на каждой итерации, минимум 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]];  
    }
}

, но, очевидно, этоневозможно!!!Так что, пожалуйста, какие-нибудь идеи?

Приветствия, Карлос

Answer 1

Похоже, вы пытаетесь сделать что-то вроде точного теста Фишера или теста перестановки. Если это так, вы можете попробовать использовать статистический пакет, такой как R, который предназначен для такого рода вещей, и, вероятно, в него уже встроены самые эффективные алгоритмы.

Кроме того, насколько я понимаю, вы разбиваете выборку на n подгрупп (y), а затем каждую из этих подгрупп на k подгрупп. Вы хотите найти минимальный элемент каждой подгруппы.

Одно достаточно эффективное решение: создайте n * k уникальных идентификаторов и карту, которая указывает, какой подгруппе соответствует каждый из них. Затем случайным образом распределите эти числа (используя то же распределение) для ваших выборочных наблюдений (как вы делали это раньше). Используйте эффективную сортировку на месте (например, быструю сортировку с правильно выбранной сводкой), чтобы отсортировать выборку по идентификатору, чтобы все элементы с одинаковым идентификатором сохранялись в непрерывном блоке памяти. Это занимает логарифмическое время, поэтому оно должно быть очень быстрым.

Тогда вам просто нужно пройтись по массиву по порядку и найти минимальный элемент для каждого уникального идентификатора. Это должно занять линейное время и n * k дополнительного пробела.

Надеюсь, это поможет.