найти индексы повторяющихся строк в двумерном массиве

Question

Есть задача найти номер повторяющихся строк в двумерном массиве. Повторяющимися считаются строки, у которых совпадают элементы в определенных позициях (количество таких позиций и сами позиции задаются пользователем, по сути это std::vector<uint16_t> colsToCompare). Мое решение задачи максимально тривиальное (тут просто идея алгоритма больше на псевдокоде):

std::unordered_set<uint32_t> rowsToRemove;
for (int i = start_row; i < end_row; i++) 
{
    for (int j = i + 1; j < end_row; j++)
    {
        bool equal = false;
        for (size_t k = 0; k < colsToCompare.size(); k++) 
        {
            GetCell(i, colsToCompare.at(k), cell1);
            GetCell(j, colsToCompare.at(k), cell2);
            equal = are_cells_equal(cell1, cell2);
            if (!equal)
                break;
        }
        if (equal) 
        {
            rowsToRemove.insert(j);
        }
    }
}

Алгоритм рабочий, но при большом количестве строк (около 1М) он очень медленный. Подскажите, может есть вариант используя какие-нибудь контейнеры stl решить задачу только с одним прохождением по строкам (то есть без цикла j)?

Answer 1

Создаёте сет, хранящий выборки нужных ячеек. Для каждой строки создаёте выборку, и проверяете, есть ли она уже в сете. Если есть - номер в список на удаление, если нет - добавляете в сет

set<tuple чего-то там> csets;
for (int i = start_row; i < end_row; i++) 
    tup = tuple(line[i], colsToCompare);
    if (tup in csets) 
        rowsToRemove.insert(j)
    else
        csets.insert(tup)

БЛОГ НА HUSL

найти индексы повторяющихся строк в двумерном массиве

Ответы (1 шт):