-1

当映射中的键数很大（例如 100000）并且它的每个第二个元素也有很大的元素（例如 100000）时，以下代码的运行时间，并行比较，需要永远。

有没有可能加快比较的方法？我的 CPU 是 Xeon E5450 3.00G 4 核。拉姆很公平。

// There is a map with long as its key and vector<long> as second element, 
//     the vector's elements are increasing sorted.
map<long, vector<long> > = aMap() ;
map<long, vector<long> >::iterator it1 = aMap.begin() ;
map<long, vector<long> >::iterator it2; 

// the code need compare each key's second elements 
for( ; it1 != aMap.end(); it1++ ) {
  it2 = it1; 
  it2++;

  // Parallel comparsion: THE MOST TIME CONSUMING PART
  for( ; it2 != aMap.end(); it2++ ) {
    unsigned long i = 0, j = 0, _union = 0, _inter = 0 ;

    while( i < it1->second.size() && j < it2->second.size() ) {
      if( it1->second[i] < it2->second[j] ) {
        i++; 
      } else if( it1->second[i] > it2->second[j] ) {
        j++; 
      } else {
        i++; j++; _inter++;
      }
    }
    _union = it1->second.size() + it2->second.size() - _inter;

    if ( (double) _inter / _union > THRESH )
      cout << it1->first << " might appears frequently with " << it2->first << endl;
  }
}
4

2 回答 2

2

（这不是一个完整的答案。它只解决了您的部分问题；关于位操作的部分。）

这是一个类，您可以使用它来相当快地计算两个集合之间的交叉点数（交叉点的基数）。

它使用位向量来存储集合，这意味着可能的集合成员的范围必须很小。

#include <cassert>
#include <vector>

class BitVector
{
    // IMPORTANT: U must be unsigned
    // IMPORTANT: use unsigned long long in 64-bit builds.
    typedef unsigned long U;
    static const unsigned UBits = 8 * sizeof(U);

public:
    BitVector (unsigned size)
        : m_bits ((size + UBits - 1) / UBits, 0)
        , m_size (size)
    {
    }

    void set (unsigned bit)
    {
        assert (bit < m_size);
        m_bits[bit / UBits] |= (U)1 << (bit % UBits);
    }

    void clear (unsigned bit)
    {
        assert (bit < m_size);
        m_bits[bit / UBits] &= ~((U)1 << (bit % UBits));
    }

    unsigned countIntersect (BitVector const & that) const
    {
        assert (m_size == that.m_size);

        unsigned ret = 0;
        for (std::vector<U>::const_iterator i = m_bits.cbegin(),
             j = that.m_bits.cbegin(), e = m_bits.cend(), f = that.m_bits.cend();
             i != e && j != f; ++i, ++j)
        {
            U x = *i & *j;

            // Count the number of 1 bits in x and add it to ret
            // There are much better ways than this,
            // e.g. using the POPCNT instruction or intrinsic
            while (x != 0)
            {
                ret += x & 1;
                x >>= 1;
            }
        }

        return ret;
    }

    unsigned countUnion (BitVector const & that) const
    {
        assert (m_size == that.m_size);

        unsigned ret = 0;
        for (std::vector<U>::const_iterator i = m_bits.cbegin(),
             j = that.m_bits.cbegin(), e = m_bits.cend(), f = that.m_bits.cend();
             i != e && j != f; ++i, ++j)
        {
            U x = *i | *j;

            while (x != 0)
            {
                ret += x & 1;
                x >>= 1;
            }
        }

        return ret;
    }

private:
    std::vector<U> m_bits;
    unsigned m_size;
};

这里有一个非常小的测试程序，看看如何使用上面的类。它创建了两个集合（每个集合最多有 100K 个元素），向它们添加一些项目（使用set()成员函数），然后计算它们的交集 10 亿次。它在我的机器上运行不到两秒钟。

#include <iostream>

using namespace std;

int main ()
{
    unsigned const SetSize = 100000;
    BitVector a (SetSize), b (SetSize);

    for (unsigned i = 0; i < SetSize; i += 2) a.set (i);
    for (unsigned i = 0; i < SetSize; i += 3) b.set (i);
    
    unsigned x = a.countIntersect (b);
    cout << x << endl;

    return 0;
}

不要忘记在启用优化的情况下编译它！否则它的表现非常糟糕。

POPCNT

现代处理器有一条指令来计算一个字中设置的位数，称为 POPCNT。这比做上面写的幼稚的事情要快得多（作为旁注，在软件中也有更快的方法，但我不想污染代码。）

无论如何，在 C/C++ 代码中使用 POPCNT 的方法是使用编译器内部或内置的. 在 MSVC 中，您可以使用__popcount()适用于 32 位整数的内在函数。在 GCC 中，您可以使用__builtin_popcountl()32 位整数和__builtin_popcountll()64 位。请注意，由于您的编译器版本、目标体系结构和/或编译开关，这些功能可能不可用。

于 2013-05-31T03:59:56.277 回答
0

也许您想尝试PPL。或者它的一些类似物。我真的不明白你的代码应该做什么，因为它似乎没有任何输出。但是无副作用的代码可以使用 Parallel Patterns Library 等工具有效地并行化。

于 2013-05-31T06:06:24.437 回答