-1 
typedef std::map<uint16_t, uint32_t> TSrcMap;
TPSrcMap sp;
TSrcMap::iterator its;
/*Code to populate the array_start.*/

/*Code to populate the array_end.*/

typedef struct port_count
{
        uint32_t port_number;
        uint32_t port_count;
}port_count_t;

port_count_t pcount[5];
memset(pcount,0,sizeof(pcount));
size_t structs_len = sizeof(pcount)/sizeof(port_count_t);
for(its = stcp.begin(); its != stcp.end();its++)
{
      if(pcount[smallest_index].port_count < (*its).second)
      {
            pcount[smallest_index].port_count = (*its).second;
            pcount[smallest_index].port_number = (*its).first;
#ifdef USEQSORT
            qsort(pcount, structs_len, sizeof(port_count_t), struct_cmp_by_port_count);
#else
            std::sort(pcount,(pcount+structs_len),cmp_by_port_count);
#endif
      }
}


#ifdef USEQSORT
/* qsort struct comparision function compare port frequency*/
int struct_cmp_by_port_count(const void *a, const void *b)
{
        port_count_t *ia = (port_count_t *)a;
        port_count_t *ib = (port_count_t *)b;
        return (ia->port_count - ib->port_count);
}
#else
/* qsort struct comparision function compare port frequency*/
int cmp_by_port_count(const port_count_t& a, const port_count_t& b)
{
        return (a.port_count < b.port_count);
}
#endif

我有一个大的std :: map结构，它将port_count映射到port_number。我必须根据port_count找到最大的5个元素。（其中key是port_number）。我上面给出了一个解析循环，它调用排序算法（ qsort 或 std::sort) 在大小为 5 的数组上。这是实现这一目标的最有效方法吗？就排序函数的调用次数而言。就计算效率而言，有更好的方法吗？我还尝试了 qsort 和 std::sort ，它们的性能似乎都差不多。这是因为我正在排序的数组的大小太小而无法产生重大影响。我试图理解这个算法就其复杂性而言。任何想法将不胜感激。

4

6 回答 6

2

从最初为空的结果双端队列开始，并将在算法期间保持排序：

  1. 遍历元素。
  2. 对于当前元素：
    • 将其插入到生成的双端队列中的正确位置，以便保留顺序。
    • 如果生成的双端队列包含超过 5 个元素，则删除最小元素。由于双端队列已排序，因此它始终是第一个元素（或最后一个，取决于排序“方向”）。

最后，生成的双端队列包含（最多）5 个最大的元素。这本质上是 O(n) 算法。

除了双端队列，您可以使用带有降序元素的向量并从末尾删除，甚至可以使用链表（尽管指针追逐对性能没有好处）。

或者，您可以简单地创建额外的地图，即原始地图的“反向”（即价值现在是键，反之亦然）并始终向两者添加元素。这样，替代地图将始终在其末端附近包含 5 个最大的元素。

于 2012-04-24T01:40:19.703 回答
2

你为什么要排序？你让它变得比它需要的更复杂。

创建一个包含 5 个元素的树 - 这是您最大的 5 个元素。（使用 std::set）只需循环内容，每次找到大于树中最小数字的数字时，将其添加到树中并删除任何溢出（前 5 个中的数字一次，不再存在)

这是我在记事本中用两分钟写的东西，没有编译保证：

#include <set>
#include <iostream>

using namespace std;

int main(int argc, char **argv)
{
    int unordered[] = {7, 12, 11, 19, 88, 42, 3, 1, 22};

    set<int> biggest5;
    int smallest = -1;

    for(int i = 0; i < sizeof(unordered)/sizeof(int); ++i)
    {
        if (unordered[i] >= smallest)
        {
            biggest5.insert(unordered[i]);

            if(biggest5.size() > 5)
                biggest5.erase(biggest5.begin());

            smallest = *biggest5.begin();
        }
    }

    //All done
    cout << "Set: ";
    for (set<int>::reverse_iterator i = biggest5.rbegin(); i != biggest5.rend(); ++i)
    {
        cout << *i << " ";
    }
    cout << endl;

    return 0;
}

这应该打印

Set: 88 42 22 19 12

您还可以在遍历后修剪biggest5集合以获得最佳性能，但会消耗更多内存。

于 2012-04-24T01:41:18.993 回答
2

你应该研究一下我最喜欢但经常被忽视的 STL 算法之一：( nth_elementref )。它对O(N)中的数据进行部分排序排序，使得枢轴（第 n 个元素）大于一侧的所有元素而小于另一侧的所有元素. 对于大输入，与快速排序相比的加速可能非常显着。

编辑：如果你想对某个范围进行排序，例如 5 个最大的元素，你可以使用partial_sort（ref）：

std::partial_sort(large_container.begin(), large_container.begin() + 5, large_container.end(), comparison_function);

将在O(n + 5*log(5))中对 large_container 进行部分排序，使得前五个元素是 large_container 降序排列的最大元素（或升序排列的最小元素，具体取决于比较函数）。这可能会替换上面代码的重要部分。

于 2012-04-24T01:45:59.837 回答
1

我认为 5 元素数组可能足够小，可以手动处理，通过将最小元素与地图中的每个项目进行比较并相应地调整数组，因此无需调用排序函数。如果需要维护更大的数组，堆可能是更好的选择。

于 2012-04-24T01:36:21.977 回答
1

我想到的另一个解决方案是使用 priority_queue，考虑到您正在寻找的是具有更高优先级的元素，这很有意义。

    #include <queue>

    int main(){
       priority_queue<int> q;
       int a[] = {7, 12, 11, 19, 88, 42, 3, 1, 22};
       for(int i=0;i<sizeof(a)/sizeof(int);i++){
                q.push(a[i]);
       }
       for(int i=0;i<5;i++){
         cout<<q.top()<<endl;
         q.pop();
       }
       return 0;
    }

请注意，priority_queue 内部实现为堆，pop_heap 以对数时间运行

于 2012-04-24T15:40:32.147 回答
1

std::sort 最有可能使用 QuickSort，或者至少是 QuickSort 的一种变体，称为 IntroSort，当递归太深时，它会“退化”为 HeapSort。所以两者都将在 O(nlogn) 时间内运行。因此，您选择哪一个并不重要（如果您自己的快速排序正确实施）。

于 2012-04-24T01:34:06.597 回答