16

我见过有人提到可以在 O(1) 时间内从 unordered_set 中获取随机元素。我试图这样做：

std::unordered_set<TestObject*> test_set;

//fill with data

size_t index = rand() % test_set.size();
const TestObject* test = *(test_set.begin() + index);

但是，unordered_set 迭代器不支持带整数的 +。 begin可以给定一个 size_t 参数，但它是一个桶的索引而不是一个元素。随机挑选一个桶然后随机挑选其中的一个元素将导致非常不平衡的随机分布。

正确的 O(1) 随机访问的秘诀是什么？如果重要的话，这是在 VC++ 2010 中。

4

4 回答 4

7

我相信您误解了“随机访问”的含义，因为在您所指的那些情况下使用了它。

“随机访问”与随机性没有任何关系。这意味着“随机”访问一个元素，即访问容器中任何位置的任何元素。直接访问元素，例如 withstd::vector::operator[]是随机访问，但遍历容器不是。

将此与 RAM 进行比较，RAM 是“随机存取存储器”的缩写。

于 2012-10-06T16:11:30.413 回答
7

std::unordered_set在数组的意义上没有 O(1) 随机访问。可以根据键在 O(1) 中访问元素，但不可能找到第 k 个元素。

尽管如此，这是一种从std::unordered_map（或者std::unordered_set如果键具有可变字段）获得具有均匀分布的随机元素的方法。我在对 SO question Data Structure(s) Allow For Alteration Through Iteration and Random Selection From Subset (C++)的回答中提出了类似的技术。

这个想法是std::unordered_set用一个可变索引值将每个条目补充到指向unordered_set. 向量的大小是 的大小unordered_set。每次将新元素插入到 中时unordered_set，指向该元素的指针都会被push_back-ed 到向量中。每次从 unordered_set 中删除一个元素时，向量中的相应条目位于 O(1) 中，并与back()向量的元素交换。先前元素的索引back()被修改，现在指向它在向量中的新位置。最后，旧条目pop_back()-ed来自向量。

这个向量正好指向unordered_set. 从均匀分布的组合结构中选择一个随机元素需要 O(1)。在组合结构中添加或删除元素需要 O(1)。

注意：只要元素存在，指向元素的指针（与迭代器不同）就保证保持有效。

这应该是这样的： 集合中的三个元素

对于擦除元素 c：

  1. 交换元素 c_index 和 a_index 并修复指向它们的指针：
  2. pop_back 最后一个元素，也就是向量中的 element_c。
  3. unordered_set从.中删除 c

随机化是微不足道的——只需从向量中随机选择一个元素。

编辑：这是一个部分代码，可以从 unordered_set 返回均匀分布的随机元素。我不得不做一些与上面的解释稍有不同的事情，因为 unordered_set 中没有可靠的索引（或迭代器）。无法将迭代器保存到 unordered_set 中的原因是它的元素不时被重新散列，从而使过程中的所有迭代器无效。因此，这个解决方案不是使用稳定的索引，而是简单地使用指向永远不会重新分配的对象的指针：

#include <unordered_set>
#include <functional>
#include <vector>
#include <memory>
#include <random>


template <class T>
class RandomUnorderedSet
{
private:
   struct Entry {
       Entry(const T & data_in, unsigned index_in_vector_in)
       : data(data_in), index_in_vector(index_in_vector_in) 
       {}
       T data;
       unsigned index_in_vector;
   };
   struct PtrEntryHash {
       auto operator()(const std::unique_ptr<Entry> & entry) const 
       { 
           return std::hash<T>()(entry->data);
       }
   };
   struct PtrEntryEqual {
       bool operator()(const std::unique_ptr<Entry> & a, 
                       const std::unique_ptr<Entry> & b ) const 
       { 
           return a->data == b->data;
       }
   };
public:
   bool insert(const T & element)
   {
       auto entry_ptr = std::make_unique<Entry>(element, m_entry_vector.size());
       if (m_entry_set.count(entry_ptr) > 0)
          return false;
       m_entry_vector.push_back(entry_ptr.get());
       try {
            m_entry_set.insert(std::move(entry_ptr));
       } catch(...) {
           m_entry_vector.pop_back();
           throw;
       }
       return true;
   }

   // Return the number of elements removed
   int erase(const T & element)
   {
       auto it = m_entry_set.find(element);
       if (it == m_entry_set.end())
          return 0;
       auto swap_with = it->index_in_vector;
       if (swap_with < m_entry_vector.size() - 1) {
           m_entry_vector.back()->index_in_vector = swap_with;
           m_entry_vector[swap_with] = m_entry_vector.back();
       }
       m_entry_set.erase(it);
       m_entry_vector.pop_back();
       return 1;
   }
   template <typename RandomGenerator>
   const T & random_element(RandomGenerator & r)
   {
       std::uniform_int_distribution<> dis(0, m_entry_vector.size() - 1);
       return m_entry_vector[dis(r)]->data;

   }

private:
   std::unordered_set<std::unique_ptr<Entry>, PtrEntryHash, PtrEntryEqual> 
        m_entry_set;
   std::vector<Entry*> m_entry_vector;
};

笔记：

  • 这个实现只是一个框架，可能会添加额外的操作。
  • 如果这是一个库类，那么最好把它做成一个合适的容器，有一个迭代器类型，它隐藏了实现细节，有begin()和end()调用，还有一个更好的返回类型insert()。
于 2018-08-22T19:27:58.763 回答
6

std::unordered_set不要提供随机访问迭代器。我想这是 stl 设计者的一个选择，给 stl 实现者更多的自由……底层结构必须支持 O(1) 插入和删除，但不必支持随机访问。例如，unordered_set即使不可能为这样的底层容器编写随机访问迭代器，您也可以将符合 stl 的代码编写为双向链表。

即使第一个元素是随机的，也无法获得完全随机的元素，因为元素在底层容器中按哈希排序的方式是确定性的......并且在我正在研究的算法中，使用第一个元素会使结果产生很大的偏差。

如果你可以在 O(1) 中构建一个随机 value_type 元素，我可以想到一个“hack”......这是这个想法：

  1. 检查无序集是否为空（如果是，则没有希望）
  2. 生成一个随机 value_type 元素
  3. 如果已经在无序集中，则返回它，否则插入它
  4. 获取it此元素的迭代器
  5. 获取随机元素*(it++)（如果*it是最后一个元素，则获取第一个元素）
  6. 删除您插入的元素并返回 (5) 中的值

所有这些操作都是 O(1)。你可以很容易地实现我给出的伪代码并对其进行模板化。

注意：第 5 步虽然很奇怪，但也很重要......因为例如，如果你得到随机元素it++（it--如果it是最后一个迭代器），那么第一个元素的概率将比其他元素小两倍（不是微不足道，但想想它...）。如果你不关心你的分布，那没关系，你可以得到最前面的元素。

于 2015-07-20T17:27:59.433 回答
1

我用 buck_count() 和 cbegin(n) 方法写了一个解决方案，随机选择一个桶，然后在桶中随机选择一个元素。

两个问题： - 这不是恒定时间（更糟糕的情况是有很多空桶和一个桶中有很多元素） - 概率分布是倾斜的

我认为随机查看元素的唯一方法是维护一个提供随机访问迭代器的单独容器。

#include <random>
#include <iostream>
#include <unordered_set>
#include <unordered_map>
#include <cassert>

using namespace std;

ranlux24_base randomEngine(5);

int rand_int(int from, int to)
{
    assert(from <= to);

    return uniform_int_distribution<int>(from, to)(randomEngine);
}

int random_peek(const unordered_set<int> & container)
{
    assert(container.size() > 0);

    auto b_count = container.bucket_count();
    auto b_idx = rand_int(0, b_count - 1);
    size_t b_size = 0;

    for (int i = 0; i < b_count; ++i)
    {
        b_size = container.bucket_size(b_idx);
        if (b_size > 0)
            break;

        b_idx = (b_idx + 1) % b_count;
    }

    auto idx = rand_int(0, b_size - 1);

    auto it = container.cbegin(b_idx);

    for (int i = 0; i < idx; ++i)
    {
        it++;
    }

    return *it;
}

int main()
{
    unordered_set<int> set;

    for (int i = 0; i < 1000; ++i)
    {
        set.insert(rand_int(0, 100000));
    }

    unordered_map<int,int> distribution;

    const int N = 1000000;
    for (int i = 0; i < N; ++i)
    {
        int n = random_peek(set);
        distribution[n]++;
    }

    int min = N;
    int max = 0;

    for (auto & [n,count]: distribution)
    {
        if (count > max)
            max = count;
        if (count < min)
            min = count;
    }

    cout << "Max=" << max << ", Min=" << min << "\n";
    return 0;
}
于 2017-11-15T10:39:29.567 回答