c++ - 在未排序的对数组中查找 K UNIQUE 最大元素

Question

这就是场景。我有一个名为 gallery 的未排序数组(非常大)，其中包含成对的模板 ( std::vector<uint8_t> ) 及其关联的 ID ( std::string)。

我有一个函数，我在其中提供了一个模板并且必须返回 k 的 ID我图库中最相似的模板(我使用余弦相似度来生成模板之间的相似度分数)。

我考虑过使用 this post 中讨论的堆. 但是，问题在于图库可以包含属于单个 ID 的多个不同模板。在我的函数中，我必须返回 k 唯一 ID。

对于上下文，我正在做一个面部识别应用程序。我可以在我的图库中拥有属于一个人的多个不同模板(该人使用多个不同的图像在图库中注册，因此多个模板属于他们的 ID)。搜索功能应返回 k与提供的模板最相似的人(因此不会多次返回相同的 ID)。

希望在 C++ 中有一个高效的算法。

编辑:为我提出的堆解决方案剪下代码(没有正确处理重复项)

    std::priority_queue<std::pair<double, std::string>, std::vector<std::pair<double, std::string> >, std::greater<> > queue;


    for(const auto& templPair : m_gallery) {
        try{
            double similairty = computeSimilarityScore(templPair.templ, idTemplateDeserial);

            if (queue.size() < candidateListLength) {
                queue.push(std::pair<double, std::string>(similairty, templPair.id));
            } else if (queue.top().first < similairty) {
                queue.pop();
                queue.push(std::pair<double, std::string>(similairty, templPair.id));
            }
        } catch(...) {
            std::cout << "Unable to compute similarity\n";
            continue;
        }
    }
// CandidateListLength number of IDs with the highest scores will be in queue

下面是一个示例，希望对您有所帮助。为了简单起见，我假设已经为模板计算了相似度分数。

模板一:相似度得分:0.4，ID:Cyrus

模板2:相似度得分:0.5，ID:James

模板3:相似度得分:0.9，ID:Bob

模板4:相似度得分:0.8，ID:Cyrus

模板5:相似度得分:0.7，ID:Vanessa

模板6:相似度得分:0.3，ID:Ariana

获取前3个评分模板的ID会返回[Bob, Cyrus, Vanessa]

Answer 1

使用 std::set 结构(平衡 BST)代替堆。它还按顺序排列元素，让您找到插入的最大和最小元素。此外，它在使用插入函数时会自动检测重复项并忽略它，因此其中的每个元素始终是唯一的。复杂度完全相同(但由于常数较大，速度稍慢)。

编辑:我可能没有正确理解这个问题。据我所知，您可以拥有多个具有不同值的元素，这些元素应被视为重复元素。

我会做什么:

1. 用对(模板值，ID)做一个集合

2. 制作一个映射，其中键是 ID，值是集合中当前模板的模板值。

3. 如果要添加新模板:

   • 如果它的 ID 在 map 中 - 您找到了重复项。如果它的值比映射中与ID配对的值差，则什么都不做，否则从集合中删除一对(旧值，ID)并插入(新值，ID)，将映射中的值更改为新值.
   • 如果它不在 map 中，只需将它添加到 map 和集合中。
4. 当集合中的项目太多时，只需从集合和 map 中删除最差的一个即可。