c++ - 在计算列表中获取前 n 项的最快方法是什么？

Question

我正在处理以下任务:

对于 list1 中的每个项目，找到 list2 中项目的前 n 个最佳匹配项

项目本身相当大(每个大约 1.5 kb)，并且有一个用于比较它们的函数。

到目前为止我一直在做的事情，可以用下面的伪代码来表达:

for every item1 in list1 {
    for every item2 in list2 {
        put index of item2 in index_buffer
        put match(item1,item2) in value_buffer
    }
    sort index_buffer by value_buffer
    put first n of index from index_buffer, value_buffer(index) in result_ buffer 
}

我想知道，有什么更好/更快的方法可以做到这一点。

我使用的语言是c++，框架是Qt。我确信在 matlab 中执行具有相同数据的相同任务的速度要快 4 倍，但事实并非如此。

这里是相关代码:http://pastebin.com/xsWsWzgp

Answer 1

执行第 2 步有一种更快的方法。实际上，您可以将它与第 1 步结合起来。

现在您保留所有结果，对它们进行排序，然后选择前 N 个放入输出缓冲区。您可以做的是创建一个包含 N 个项目的优先级队列，并且只保留到目前为止找到的前 N ​​个。在伪代码中，它看起来像这样:

for every item1 in list1 
{
    create empty priority queue to hold n items
    for every item2 in list2 
    {
        value = match(item1, item2)
        if priorityqueue length < n
            add value and index to priority queue
        else if value > lowest value currently in priority queue
        {
            remove lowest value from priority queue
            add new value and index to priority queue
        }
    }
    add items from priority queue to result buffer
}

查看 STL std::priority_queue .

如果请求的项目数 (n) 比 list2 的长度小得多，那将为您节省很多时间。

正如其他人指出的那样，当项目匹配时从 list2 中删除项目(或以某种方式标记它们)可能是合理的，这样它们就不会再次匹配。当然，除非您想要并期望重复匹配。