65.9K
CodeProject 正在变化。 阅读更多。
Home

C++ 中稀疏集的快速实现。

Mikhail Semenov
starIconstarIconstarIconstarIcon
emptyStarIcon
starIcon

4.93/5 (16投票s)

2015年1月4日

CPOL

9分钟阅读

viewsIcon

47575

downloadIcon

435

本文介绍了整数稀疏集的算法和实现，包括基准测试结果。

引言

在执行其中一项任务时，我遇到了一个简单的问题：找到处理数组索引选择的最佳方法。问题是：如果你想要简单的索引选择，你可能希望在每个元素中添加一个额外的布尔字段或创建一个布尔向量。但是如果这个选择非常稀疏，那么遍历所有元素将会很慢。显然，在这种情况下可以生成一个索引数组。但随后就出现了更新此数组的问题：即使不需要排序数组，通过排序数组进行搜索（以避免元素重复）也会更快。但是将元素插入到排序数组中代价很高。

在本文中，我将介绍整数稀疏集的三个实现，并将它们与现有容器（包括 Boost 动态位集）进行比较。

代码在 Microsoft Visual C++ 14 CTP、GNU C++ 4.9 和 Clang C++ 3.5 中进行了测试。

我们应该考虑哪些容器？

让我们看看我们可能希望考虑的现有容器列表。C++11 [1] 中显而易见的是：std::vector<bool>、std::bitset。由于 std::vector<bool> 内部使用位集合，因此将其与字节集合进行比较是明智的：例如，std::vector<char>。

虽然 std::set<T> 是为各种类型而设计的，而不仅仅是整数，并且效率不高。但考虑它将是合适的。我喜欢它的设计：它提供了一个方便的迭代器，可以遍历“选定”的元素。而且，总的来说，我认为它的方法集合是最合适的。相比之下，std::vector<bool> 提供了一个迭代器，但它遍历所有元素（true 和 false），而不是只遍历“选定”的元素（值为 true 的元素）。std::bitset 容器没有迭代器。还有 Boost 动态位集，它类似于 std::bitset：它没有迭代器，但提供了快速扫描选定元素的方法。

您可能还希望查看 BitMagic 位向量 [3]。我不会在本文中讨论它。

稀疏集容器的建议设计

正如我之前提到的，我认为 std::set<T> 的设计在所提供的方法和迭代器方面是最合适的。提出了以下稀疏集的通用结构：size 和 count 方法的含义与 std::set 容器中的不同；添加了 test 方法。

class generic_sparse_set
{
public:

//----------------------------------
// Types
// ----------------------------------
    typedef ... value_type;
    typedef ... size_type;
    typedef  ... iterator;
    typedef  ... const_iterator;    

///------------------------------------
/// Constructors
///------------------------------------
            
    generic_sparse_set(size_type size); // creating a sparse set with elements in the interval [0,size-1]

    generic_sparse_set(); // creating a sparse set; space is not reserved, requires resize.

///------------------------------------
/// Modifiers
///------------------------------------
    void resize(size_type size); // reserve the space for elements in the interval [0,size-1]

    void swap(generic_sparse_set& s); // swap the contents with another sparse set

    bool insert(value_type i); // insert an element; returns true if a new element is inserted;
                               // returns false if the same element is already in the set.

    void erase(value_type i);  // delete an element by value
   
    void erase(const iterator& it); // optional method; deletes an element by iterator   

    void clear(); // deletes all the elemnts   

///------------------------------------
/// Capacity
///------------------------------------
    size_type size() const; // the length of the interval that the elements can be taken from

    size_type count() const; // the number of elements

///------------------------------------
/// Operations
///------------------------------------
 
    bool test(value_type i) const;  // test if an element is in the set

    bool empty() const; // tests if a set is empty

    const_iterator find(value_type i) const; // optional; finds an iterator for an element

    const_iterator lower_bound(value_type i) const; // optional; returns an iterator pointing to
                                                     //  the first element that is >= i

    const_iterator upper_bound(value_type i) const;  // optional; returns an iterator pointing to
                                                      //  the first element that is > i

///------------------------------------
/// Iterators
///------------------------------------
    const_iterator begin() const; // returns an iterator to the beginning

    const_iterator end() const;   // returns an iterator pointing the past-the-end of the container
};

有些方法被认为是可选的：它们可能效率低下或根本不合适（例如，对无序序列使用 lower_bound）。迭代器和常量迭代器是相同的类：您只能扫描集合中的元素，不能在扫描时更改它们。

提供的稀疏集实现

无序稀疏集

这个容器基于文章 [4]。算法的一个很好的解释在 [5] 中给出。

该实现由两个数组组成（例如，std::vector 容器）：一个是 稀疏 的（指针数组），另一个是 密集（或 D） 的（索引数组）。如果值 v 在集合中，则 sparse[v] == &dense[k]，其中 dense[k] == v。换句话说，*(sparse[v]) == v。但索引 k 不重要。只要 dense[k] = v，索引的值就不重要。

一个包含三个值：1、4 和 5 的示例集如 图 1 所示。

图 1

图片中的蓝色方块是 nullptr 值。注意两个重要的特性：

  • 测试一个值是否存在很容易：sparse[value] != nullptr；
  • 遍历元素也很容易：遍历数组 dense；这是你能得到的最快的迭代。

让我们考虑添加一个额外元素 e 的算法，例如，e=2（图 2）

 

图 2

我们执行 dense.push_back(e)。然后我们执行 sparse[e] = &dense.back();

删除也相当容易。我们想删除元素 k = 1（图 3）。

图 3

当我们处理 dense 数组时，我们总是删除最后一个元素，在这种情况下，它包含 2。但我们需要替换我们尝试删除的值。所以，*(sparse[1]) = dense.back()。这意味着现在：dense[1] == 2。我们必须调整 sparse[2] 中的值：一般来说，我们必须执行

sparse[dense.back()] = sparse[1];

之后，建立所有必要的链接后，我们可以删除元素

dense.erase(dense.end()-1);

sparse[1] = nullptr;

我们现在得到数组的状态如 图 4 所示。

图 4

 

最后一点：尽管我没有考虑对 dense 数组进行排序，但可以对其元素进行排序。必要的 swap(i,j) 算法可以很容易地编写出来

std::swap(sparse[dense[i]],sparse[dense[j]]);

std::swap(dense[i],dense[j]);

使用这个交换，可以很容易地实现排序。

有界集

此实现的功能和速度与 Boost 动态位集非常接近。区别在于提供的方法。基本思想是值以位数组（称之为 bit_array）中的位形式存储，该数组具有某种基本类型。例如，如果基本类型是 32 位整数，为了测试第 i 个元素是否存在，可以编写以下代码：

bool test(value_type i)
{
     return ((bit_array[i >> 5] >> (i & 0x1F)) & 1) != 0;
}

该实现提供了一个迭代器，可以快速跳过零位。

这显然是最紧凑且相当高效的实现。但是使用迭代器遍历元素的速度不如无序稀疏集快。

稀疏集

该容器试图结合上面讨论的两个容器的最佳特性：有界集的效率和紧凑性以及无序稀疏集的快速迭代。基本方法与有界集相同，但迭代器不同。当需要迭代器时，整数向量从位数组中快速构建。优点如下：

  • 如果需要多次（通常超过 5 次）遍历所有现有值，则此类扫描的总时间开始接近无序稀疏集；
  • 即使只有一次扫描，计时也与有界集（或 Boost 动态位集）非常接近；
  • 元素是有序的（与无序稀疏集相反）；
  • 它比无序稀疏集更高效（除了使用迭代器扫描）（生成、可用性测试、删除）。


基准测试

概述

对于基准测试，我主要考虑了以下容器：unordered_sparse_set, sparse_set, bounded_set, boost::dynamic_bitset, std::vector<bool>, std::vector<char>。在某些测试中，我还查看了 std::bitset 和 std::set<unsigned>。但前者在值范围方面相当有限（我查看了 VC++ 2014 和 GCC 4.9），并且通常比 std::vector<bool> 慢。后者则相当慢。我已将它们的测试包含在示例代码中，但我不会过多讨论它们。

考虑了以下测试

  • 从预先存储的随机生成数字创建容器（具有各种密度；密度是可用元素数量与间隔长度的比率；通常以百分比表示）；
  • 随机访问；
  • 重复扫描所有元素（考虑的扫描次数：1、5、20）；
  • 使用预先存储的数字删除元素。

为了确保我们进行同类比较，在每个测试中都重置了数字生成器。

结果是在 Microsoft Visual C++ 14 CTP 编译为 32 位时获得的。

元素的生成

结果如 图 5 所示。测试中使用的最高长度为 50,000,000。

图 5

有界集、std::vector<bool>、稀疏集的时间实际上是相同的。Boost 动态位集也相当接近。无序稀疏集显示出最慢的时间。这是由于其使用的数据结构的大小和添加元素的复杂性。无序稀疏集和 std::vector<char> 都似乎受到缓存问题的影响。

随机访问

所讨论的所有容器的性质都是这样的，随机访问不依赖于元素的数量，而只依赖于所涉及的间隔长度和步数（试验次数）。在 图 6 中，您可以看到在各种间隔长度下进行 10,000,000 步基准测试的结果。

图 6

这里再次，与之前一样，无序稀疏集表现最差，尤其是在长度超过 1,000,000 时，其次是 std::vector<char>。这里的问题只是缓存：随机测试代码非常简单。您可能会注意到，当间隔长度约为 100,000 时，它们的性能实际上与其他容器相同。

你可能会问：我们为什么要考虑无序稀疏集呢？它到目前为止并没有表现出比其他容器更好的性能。我建议你阅读下一节。

扫描所有元素

以下是针对不同间隔长度（图 7）扫描所有 100,000 个元素的基准测试。您可能会发现，除了无序稀疏集之外，大多数容器的速度都取决于密度。无序稀疏集表现最佳。该图还显示了稀疏集在扫描次数增加时的性能差异。

图 7

当扫描重复约 20 次时，稀疏集的性能非常接近无序稀疏集。但即使只扫描一次，稀疏集的性能也与其他位图容器相同（或几乎相同）。您会看到 std::vector<bool> 和 std::vector<char> 都“挣扎”。

随机删除的速度

图 8 显示了使用预先存储的随机生成值集合进行随机删除的速度。

 

图 8

这里，无序稀疏集再次与缓存作斗争，并且必须处理其删除操作的复杂性。

埃拉托斯特尼筛法测试

此测试运行多个独立的 200 个埃拉托斯特尼筛法计算。除了最后一步，即计算给定区间内的素数，它不涉及太多不改变值的扫描。那些在随机访问和删除方面遇到困难的容器显然表现最差。但在这里，我尽可能地包含了 std::bitset 和 std::set<unsigned>。结果如 图 9 所示。

图 9
 

在这里，Boost 动态位集、有界集和稀疏集表现最佳。最差的是 std::set<unsigned>。正如我之前提到的，除非我们处理非常宽泛的值范围，否则此容器不适合存储整数。我惊讶地发现 std::bitset 表现不佳，并且不允许存储许多值。布尔向量表现出相当不错的性能。

包含的测试

包含的测试是不言自明的。您可以进行自己的测量。我注意到在某些测试中，运行之间的计时有时可能会相差 10% 以上。在文件开头有以下几行：

//#define USE_BOOST

#ifdef USE_BOOST

#include "boost\dynamic_bitset\dynamic_bitset.hpp"

#endif

const unsigned steps = 100000000;

const unsigned repeat = 5;

如果您想使用 Boost，可以取消注释 USE_BOOST 定义。steps 常量定义了在随机访问测试中使用的步数（试验次数）。repeat 常量定义了在迭代测试中扫描的次数。 

参考文献

[1]. http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2012/n3337.pdf

[2]. https://boost.ac.cn/

[3]. http://bmagic.sourceforge.net/

[4]. Briggs, P., Torczon, L.: An efficient representation for sparse sets. ACM Letters on Programming Languages and Systems 2(1–4), 59–69 (1993)

[5].http://cp2013.a4cp.org/sites/default/files/uploads/trics2013_submission_3.pdf

 

© . All rights reserved.