比较大型数据集中的向量

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

从您的（子）向量的规范化（此处为排序）版本构建一个 set 或 unordered_set。然后你可以在 O(mn log m log n 中找到所有重复项) 时间，其中 m 和 n 分别是数据的外部和内部维度。

您可能需要一个映射来存储每个等价项的第一个代表的索引 class。您可以使用 reserve 从 unordered_set 运行时间删除日志 m。

Answer 2

准备工作：

首先根据大小将向量分类到桶中。
只有一个向量的桶意味着向量是唯一的，输出并删除。
对剩余桶中的所有剩余向量进行排序

从 i = 0 开始

递归算法：

每个桶：

根据 v.(i)
只有一个向量的桶意味着向量是唯一的，输出并移除
递归到每个桶中，i=i+1

比较大型数据集中的向量

comparing vectors in a large data set

c++

comparison

vector

large-data