-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

port_countをport_numberにマップする大きなstd::map構造があります。port_countに基づいて最大の5つの要素を見つける必要があります（ここで、keyはport_numberです）。ソートアルゴリズムを呼び出す上記の単一の解析ループがあります（サイズ5の配列でqsortまたはstd::sort）これを実現するための最も効率的な方法ですか？並べ替え関数への呼び出し数の観点から、計算効率の観点から、これを行うためのより良い方法はありますか？また、qsortとstd :: sortの両方を試しましたが、どちらもほぼ同じように機能しているようです。これは、並べ替える配列のサイズが小さすぎて大きな影響を与えられないためです。このアルゴリズムを理解しようとしています。それの複雑さの用語。どんな考えでもいただければ幸いです。

4

6 に答える 6

2

最初は空で、アルゴリズムの期間中はソートされたままになる結果の両端キューから開始します。

  1. 要素をトラバースします。
  2. 現在の要素の場合：
    • 結果の両端キューの正しい場所に挿入して、順序が保持されるようにします。
    • 結果の両端キューに5つを超える要素が含まれている場合は、最小要素を削除します。dequeはソートされているため、これは常に最初の要素です（または、ソートの「方向」によっては最後の要素です）。

最後に、結果の両端キューには（最大）5つの最大要素が含まれます。これは本質的にO（n）アルゴリズムです。

dequeの代わりに、降順の要素を持つベクトルを使用して、最後から削除することも、リンクリストを削除することもできます（ただし、ポインターの追跡はパフォーマンスには決して適していません）。

または、元のマップの「逆」である追加のマップを作成し（つまり、値がキーになり、その逆も同様）、常に両方に要素を追加することもできます。このように、代替マップには常にその終わり近くに5つの最大の要素が含まれます。

于 2012-04-24T01:40:19.703 に答える
2

なぜ並べ替えるのですか？あなたはそれを必要以上に複雑にしている。

5つの要素のツリーを作成します-これは5つの最大の要素です。（std :: setを使用）コンテンツをループするだけで、ツリー内の最小数よりも大きい数を見つけるたびに、それをツリーに追加し、オーバーフローを削除します（上位5に1回の数は、もはや存在しません） ）。

これが私が2分でメモ帳に作成したものです。コンパイルの保証はありません。

#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アルゴリズムの1つを調べる必要があります: nth_element( ref）。クイックソートのO（N log（N））と比較して平均してO（N）のデータを部分的にソートし、ピボット（n番目の要素）が一方のすべての要素よりも大きく、もう一方のすべての要素よりも小さいようにします。 。クイックソートに対するスピードアップは、入力が大きい場合に非常に重要になる可能性があります。

partial_sort編集：特定の範囲を並べ替える場合、たとえば5つの最大の要素を使用する場合は、 （ref）を使用できます。

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

large_containerをO（n + 5 * log（5））で部分的に並べ替え、最初の5つの要素がlarge_containerの降順で最大の要素（または比較関数によっては昇順で最小の要素）になるようにします。これはおそらく、上記のコードの重要な部分を置き換えるでしょう。

于 2012-04-24T01:45:59.837 に答える
1

std :: sortは、QuickSort、または少なくとも再帰が深くなりすぎるとHeapSortに「縮退」するIntroSortと呼ばれるQuickSortのバリエーションを使用する可能性が最も高いです。したがって、両方ともO（nlogn）時間で実行されます。したがって、どちらを選択してもかまいません（独自のクイックソートが適切に実装されている場合）。

于 2012-04-24T01:34:06.597 に答える
1

5要素の配列は、最小の要素をマップ内の各項目と比較し、それに応じて配列を調整することで、手動で処理できるほど小さい可能性があると思います。したがって、並べ替え関数を呼び出す必要はありません。より大きな配列を維持する必要がある場合は、ヒープの方が適している場合があります。

于 2012-04-24T01:36:21.977 に答える
1

私が考えたもう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 に答える