删除重复项和对向量进行排序的最有效方法是什么？

Question

我需要获取一个可能包含很多元素的 C++ 向量，删除重复项并对其进行排序。

我目前有以下代码，但它不起作用。

 vec.erase(
      std::unique(vec.begin(), vec.end()),
      vec.end());
std::sort(vec.begin(), vec.end());

我怎样才能正确地做到这一点？

此外，先删除重复项（类似于上面的代码）还是先执行排序更快？如果我确实先执行排序，是否保证在执行 std::unique 后保持排序？

还是有另一种（可能更有效）的方式来完成这一切？

原文由 Kyle Ryan 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

我同意 R. Pate 和 Todd Gardner 的观点； a std::set 在这里可能是个好主意。即使您无法使用向量，但如果您有足够的重复项，您最好创建一个集合来完成这些繁琐的工作。

让我们比较三种方法：

仅使用向量，排序+唯一

sort( vec.begin(), vec.end() );
vec.erase( unique( vec.begin(), vec.end() ), vec.end() );

转换为设置（手动）

 set<int> s;
unsigned size = vec.size();
for( unsigned i = 0; i < size; ++i ) s.insert( vec[i] );
vec.assign( s.begin(), s.end() );

转换为集合（使用构造函数）

 set<int> s( vec.begin(), vec.end() );
vec.assign( s.begin(), s.end() );

以下是这些随着重复数量的变化而变化的表现：

摘要：当重复的数量足够大时， _转换为集合然后将数据转储回向量实际上更快_。

出于某种原因，手动进行集合转换似乎比使用集合构造函数更快——至少在我使用的玩具随机数据上是这样。

原文由 Nate Kohl 发布，翻译遵循 CC BY-SA 3.0 许可协议

Answer 2

取决于用例。如果您期望少于 100 个正整数唯一值，并且如果您有一个能够支持 avx512f 指令集的 CPU，那么您可以通过使用以每个元素约 15 个时钟周期或每秒 300-5 亿次插入的速率插入元素与小型查找表的简单比较。

下面的实现使用 CPU 寄存器为约 50 个唯一值和 L1 缓存进行约 1000 个唯一值的值查找。对于 L1 缓存版本，每次插入大约需要 160 个时钟周期，这相当于每秒大约 25M 次插入，并且比使用 std::set 慢。对于只有 4 个唯一值，它以每个元素 5.8 个周期的速率插入，高于 500M/s。

 //g++  7.4.0
// time measurement taken from another answer
// valid C99 and C++

#include <stdint.h>  // <cstdint> is preferred in C++, but stdint.h works.

#ifdef _MSC_VER
# include <intrin.h>
#else
# include <x86intrin.h>
#endif

// optional wrapper if you don't want to just use __rdtsc() everywhere
inline
uint64_t readTSC() {
     _mm_lfence();  // optionally wait for earlier insns to retire before reading the clock
    uint64_t tsc = __rdtsc();
     _mm_lfence();  // optionally block later instructions until rdtsc retires
    return tsc;
}

// requires a Nehalem or newer CPU.  Not Core2 or earlier.  IDK when AMD added it.
inline
uint64_t readTSCp() {
    unsigned dummy;
    return __rdtscp(&dummy);  // waits for earlier insns to retire, but allows later to start
}

#include <iostream>

template<int n>
struct FastUnique
{
    public:
    FastUnique()
    {
         it=0;
         for(int i=0;i<n;i++)
             dict[i]=-1;
    }

    void insert(const int val)
    {
        if(!test(dict,val))
            dict[it++]=val;
    }

    const int get(const int index)
    {
        return dict[index];
    }

    const int size()
    {
        return it;
    }

    private:
    int dict[n];
    int it;
    bool test(const int * dict, const int val)
    {
        int c=0;
        for(int i=0;i<n;i++)
            c+=(dict[i]==val);
        return c>0;
    }
};

int main()
{
    std::cout << "Hello, world!\n";
    const int n=500000000;

    FastUnique<64> fastSet;

    auto t= readTSC();

    for(int i=0;i<n;i++)
        fastSet.insert(i&63);

    auto t2=readTSC();

    std::cout<<(t2-t)/(double)n<<"cycles per iteration"<<std::endl;

    for(int i=0;i<fastSet.size();i++)
        std::cout<<fastSet.get(i)<<std::endl;

    return 0;
}

原文由 huseyin tugrul buyukisik 发布，翻译遵循 CC BY-SA 4.0 许可协议