сравнивая векторы в большом наборе данных

Question

У меня есть двумерный вектор целочисленного типа, который содержит большое количество векторов (т.е. 18000 и выше), и в этом пуле имеется значительное количество повторяющихся векторов. Я хочу обнаружить похожие векторы и удалить один из них. В настоящее время я сравниваю каждый вектор со всем пулом, используя следующую функцию: `

bool compareVectors(vector<int> a, vector<int> b)
{
    if (a.size() != b.size())
    {
        return false;
    }
    sort(a.begin(), a.end());
    sort(b.begin(), b.end());
    return (a == b);
}

Но это неэффективно делает процесс, вероятно, из-за большого количества сравнений, которые я делаю. Есть ли возможные эффективные способы сделать это?

Answer 1

Подготовка:

1. Сначала рассортируйте ваши векторы по ведрам в соответствии с размером.
2. Контейнеры с одним вектором означают, что вектор является уникальным, выводится и удаляется.
3. сортировка всех оставшихся векторов в оставшихся сегментах

начать с i = 0

Рекурсивный алгоритм:

для каждого ведра:

1. сортирует векторы в сегменты в соответствии с v. (I)
2. Buckets только с одним вектором означает, что вектор уникален, выведите и удалите
3. входить в каждое ведро с i = i + 1

Answer 2

Создайте set или unordered_set из канонизированных (здесь, отсортированных) версий ваших (под) векторов. Затем вы можете найти все дубликаты за O ( mn log m log n ) времени, где m и n - внешние и внутренние измерения ваших данных соответственно.

Возможно, вы захотите использовать отображение, скажем, для хранения индекса первого представителя каждого класса эквивалентности. Вы можете использовать reserve для удаления журнала m из времени выполнения unordered_set.