Method Shuffle

catboost/libs/data/objects_grouping.cpp:191–257

TObjectsGroupingSubset NCB::Shuffle(
    TObjectsGroupingPtr objectsGrouping,
    ui32 permuteBlockSize,
    TRestorableFastRng64* rand
) {
    const ui32 objectCount = objectsGrouping->GetObjectCount();

    TIndexedSubset<ui32> indices;
    indices.yresize(objectCount);

    if (objectsGrouping->IsTrivial()) {
        if (permuteBlockSize == 1) {
            CreateShuffledIndices(objectCount, rand, &indices);
        } else {
            const ui32 blocksCount = (objectCount + permuteBlockSize - 1) / permuteBlockSize;
            TVector<ui32> blockedPermute;
            CreateShuffledIndices(blocksCount, rand, &blockedPermute);

            ui32 currentIdx = 0;
            for (ui32 i = 0; i < blocksCount; ++i) {
                const ui32 blockStartIdx = blockedPermute[i] * permuteBlockSize;
                const ui32 blockEndIndx = Min(blockStartIdx + permuteBlockSize, objectCount);
                for (ui32 j = blockStartIdx; j < blockEndIndx; ++j) {
                    indices[currentIdx + j - blockStartIdx] = j;
                }
                currentIdx += blockEndIndx - blockStartIdx;
            }
        }
        return TObjectsGroupingSubset(
            objectsGrouping,
            TArraySubsetIndexing<ui32>(std::move(indices)),
            EObjectsOrder::RandomShuffled
        );
    } else {
        CB_ENSURE_INTERNAL(permuteBlockSize == 1, "permuteBlockSize must be 1 if groups are present");

        TIndexedSubset<ui32> groupPermute;
        CreateShuffledIndices(objectsGrouping->GetGroupCount(), rand, &groupPermute);

        const TConstArrayRef<TGroupBounds> srcGroupsBounds = objectsGrouping->GetNonTrivialGroups();

        TVector<TGroupBounds> dstGroupBounds;
        dstGroupBounds.yresize(objectsGrouping->GetGroupCount());

        ui32 idxInResult = 0;
        for (ui32 queryIdx = 0; queryIdx < (ui32)groupPermute.size(); queryIdx++) {
            TGroupBounds srcGroupBounds = srcGroupsBounds[groupPermute[queryIdx]];
            ui32 initialStart = srcGroupBounds.Begin;
            ui32 resultStart = idxInResult;
            ui32 size = srcGroupBounds.GetSize();
            dstGroupBounds[queryIdx] = TGroupBounds(idxInResult, idxInResult + size);
            for (ui32 doc = 0; doc < size; doc++) {
                indices[resultStart + doc] = initialStart + doc;
            }
            Shuffle(indices.begin() + resultStart, indices.begin() + resultStart + size, *rand);
            idxInResult += size;
        }