如何在映射中随机洗牌值

Question

我有一个std::map，键和值都是整数。现在我想随机洗牌，让键随机指向不同的值。我试过random_shuffle，但它不编译。请注意，我并没有试图打乱键，这对地图来说没有意义。我正在尝试随机化这些值。

我可以把值压入一个向量，打乱，然后复制回来。有没有更好的办法?

Answer 1

您可以按下vector中的所有键，洗牌vector并使用它来交换map中的值。

下面是一个例子:

#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <random>
#include <ctime>
using namespace std;
int myrandom (int i) { return std::rand()%i;}
int main ()
{
    srand(time(0));
    map<int,string> m;
    vector<int> v;
    for(int i=0; i<10; i++)
        m.insert(pair<int,string>(i,("v"+to_string(i))));
    for(auto i: m)
    {
        cout << i.first << ":" << i.second << endl;
        v.push_back(i.first);
    }
    random_shuffle(v.begin(), v.end(),myrandom);
    vector<int>::iterator it=v.begin();
    cout << endl;
    for(auto& i:m)
    {
        string ts=i.second;
        i.second=m[*it];
        m[*it]=ts;
        it++;
    }
    for(auto i: m)
    {
        cout << i.first << ":" << i.second << endl;
    }
    return 0;
}

Answer 2

您的建议的复杂性是O(N)(副本和洗牌都具有线性复杂性)，这似乎是最优的(查看较少的元素将在洗牌中引入非随机性)。

如果你想重复洗牌你的数据，你可以维护一个类型为<Key, size_t>(即众所周知的间接级别)的映射，索引到std::vector<Value>，然后只是重复洗牌向量。这样可以节省所有的复制，以换取O(N)空间开销。如果Value类型本身是昂贵的，那么您有一个额外的vector<size_t>索引到您进行改组的实际数据。

为方便起见，可以将map和vector封装在一个公开shuffle()成员函数的类中。这样的包装器还需要公开底层映射的基本查找/插入/擦除功能。

EDIT:正如@tmyklebu在评论中指出的那样，维护(原始或智能)指向辅助数据的指针可能会导致迭代器失效(例如，当在末尾插入新元素导致vector的容量被调整时)。使用索引代替指针解决了"在末尾插入"的问题。但是，在编写包装器类时，需要确保新键值对的插入不会导致对辅助数据的"中间插入"，因为那样也会使索引失效。一个更健壮的库解决方案是使用Boost。MultiIndex，它专门设计用于允许在数据结构上使用多种类型的视图。

Answer 3

好吧，只使用地图，我认为:为map的每个cell做一个标志数组，随机生成两个整数s.t 0<=i, j <地图大小;交换它们，并将这些单元格标记为交换。遍历所有。>
编辑:该数组是根据map的大小分配的，并且是一个本地数组。

Answer 4

我怀疑…

但是…为什么不写一个有两个向量的类呢?一个排序的std::vector的键和std::random_shuffle d std::vector的值?使用std::lower_bound查找键，并使用std::distance和std::advance获取值。简单!

无需深入思考，这应该具有与std::map相似的复杂性，并且可能具有更好的引用局部性。

一些未测试和未完成的代码让你开始。

template <class Key, class T>
class random_map
{
public:
    T& at(Key const& key);
    void shuffle();
private:
    std::vector<Key> d_keys; // Hold the keys of the *map*; MUST be sorted.
    std::vector<T> d_values;
}
template <class Key, class T>
T& random_map<Key, T>::at(Key const& key)
{
    auto lb = std::lower_bound(d_keys.begin(), d_keys.end(), key);
    if(key < *lb) {
        throw std::out_of_range();
    }
    auto delta = std::difference(d_keys.begin(), lb);
    auto it = std::advance(d_values.begin(), lb);
    return *it;
}
template <class Key, class T>
void random_map<Key, T>::shuffle()
{
    random_shuffle(d_keys.begin(), d_keys.end());
}

Answer 5

如果您想打乱地图的位置，您可以为您的map实现您自己的random_shuffle版本。解决方案仍然需要将密钥放入向量中，下面使用transform:

typedef std::map<int, std::string> map_type;
map_type m;
m[10] = "hello";
m[20] = "world";
m[30] = "!";
std::vector<map_type::key_type> v(m.size());
std::transform(m.begin(), m.end(), v.begin(),
               [](const map_type::value_type &x){
                   return x.first;
               });
srand48(time(0));
auto n = m.size();
for (auto i = n-1; i > 0; --i) {
    map_type::size_type r = drand48() * (i+1);
    std::swap(m[v[i]], m[v[r]]);
}

我使用drand48()/srand48()作为统一的伪随机数生成器，但您可以使用任何最适合您的。

或者，您可以洗牌v，然后重建map，例如:

std::random_shuffle(v.begin(), v.end());
map_type m2 = m;
int i = 0;
for (auto &x : m) {
    x.second = m2[v[i++]];
}

但是，我想说明的是，在映射上实现shuffle并不会过于繁重。

Answer 6

这是我使用c++ 11的std::reference_wrapper的解决方案。

首先，让我们创建一个std::random_shuffle版本来对引用进行洗牌。这是对版本1的一个小修改:使用get方法来获取引用的值。

template< class RandomIt >
void shuffleRefs( RandomIt first, RandomIt last ) {
    typename std::iterator_traits<RandomIt>::difference_type i, n;
    n = last - first;
    for (i = n-1; i > 0; --i) {
        using std::swap;
        swap(first[i].get(), first[std::rand() % (i+1)].get());
    }
}

现在很简单了:

template <class MapType>
void shuffleMap(MapType &map) {
    std::vector<std::reference_wrapper<typename MapType::mapped_type>> v;
    for (auto &el : map) v.push_back(std::ref(el.second));
    shuffleRefs(v.begin(), v.end());
}