地图迭代足够随机用于随机选择密钥？ [英] Is map iteration sufficiently random for randomly selecting keys?

问题描述

我可以依靠地图的随机迭代顺序在Web应用程序中实现随机配对客户端吗？我已经试过四处寻找，但似乎无法找到这种随机性是多么随意的细分。

算法看起来像这样：

  var clients map [客户端] struct {} 
 $ b func PairClient（c客户端）（客户端，错误）{
 for m：= range clients {
 if m！= c {
 return m，nil 
} 
} 
 return nil，fmt.Errorf（lobby：客户数量不足）
} 
  

如果> 1000连接客户端，还是应该维护一个单独的客户端片段并从中随机选择？

解决方案

尽管它说是随机的随机化）（规范，博客， hashmap来源，另一个博客，

为什么？因为我们喜欢地图是快速的，而更好的随机分布往往需要更多的计算和/或更大的延迟。妥协必须作出。而且因为其目的不是为范围提供的质量混洗功能，而仅仅是为了防止开发人员依赖稳定的迭代次序（因为即使没有明确的随机化，它也可能改变）。





但是这个分布可能有多好？容易获得品味。我们创建一个10对的地图，并开始迭代很多次。让我们来计算第一个索引（键）的分布：

$ $ $ $ $ $ c $ m：= map [int] int {}
for i：= 0;我< 10; i ++ {
m [i] = i
}

dist：= make（[] int，10）
for i：= 0;我< 100000; i ++ {
for idx：= range m {
dist [idx] ++
break
}
}

fmt.Println（ Distribution：，dist）


输出（在 Go Playground ）：

  Distribution：[25194 24904 6196 6134 6313 6274 6297 6189 6189 6310] 
  

前2个键（ 0 和 1 ）粗略地遇到了 4倍的可能性。

你可以说它对于真实（甚至是好）是随机的很不好，但那不是重点。提供不同的迭代顺序已经足够了（重要的是：速度很快）。

Can I rely on the random iteration order of maps to implement a random "pairing" of clients in a web application? I've tried looking around but can't seem to find a breakdown of how random this randomness is.

The algorithm would look something like:

var clients map[Client]struct{}

func PairClient(c Client) (Client, error) {
    for m := range clients {
        if m != c {
            return m, nil
        }
    }
    return nil, fmt.Errorf("lobby: insufficient number of clients")
}

Would this be sufficient when there are >1000 connected clients, or should I maintain a separate slice of clients and randomly select from that?

解决方案

Even though it said to be random (randomized) (spec, blog, hashmap source, another blog, SO), the distribution is far from being perfect.

Why? Because we like maps being fast, and better random distribution tends to require more computation and/or bigger delays. A compromise had to be made. And because the intention is not to provide a quality "shuffle" functionality by for range, but only to prevent developers relying on stable iteration order (because it could change even without explicit randomization).

But "how good" may this distribution be? Easy to get a "taste". Let's create a map of 10 pairs, and start iterating over it lot of times. And let's count the distribution of the very first index (key):

m := map[int]int{}
for i := 0; i < 10; i++ {
    m[i] = i
}

dist := make([]int, 10)
for i := 0; i < 100000; i++ {
    for idx := range m {
        dist[idx]++
        break
    }
}

fmt.Println("Distribution:", dist)

Output (try it on the Go Playground):

Distribution: [25194 24904 6196 6134 6313 6274 6297 6189 6189 6310]

The first 2 keys (0 and 1) were roughly encountered 4 times more than the rest which had roughly the same probability.

You can tell it's pretty bad for being true (or even good) random, but that's not the point. It's good enough to provide varying iteration order (and importantly: it's fast).

这篇关于地图迭代足够随机用于随机选择密钥？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！