Set.pop()不是随机的吗? [英] Set.pop() isn't random?

问题描述

从 Python文档，"set.pop( )从s中删除并返回任意元素.在生成一些随机数据以测试程序时，我注意到此pop()函数的奇怪行为.这是我的代码(python 2.7.3):

From the python docs, "set.pop() remove and return an arbitrary element from s". While generating some random data to test a program, I noticed strange behavior of this pop() function. Here is my code (python 2.7.3):

testCases = 10
numberRange = 500

poppedValues = []
greaterPercentages = []

for i in range (testCases):
    s = Set()

    """ inserting 100 random values in the set, in the range [0, numberRange) """
    for j in range (100):
        s.add(random.randrange(numberRange)) 

    poppedValue = s.pop()
    greaterCount = 0

    """ counting how many numbers in the set are smaller then the popped value """
    for number in s:
        if poppedValue > number:
            greaterCount += 1

    poppedValues.append(poppedValue)
    greaterPercentages.append(float(greaterCount) / len(s) * 100)

for poppedValue in poppedValues:
    print poppedValue, '\t',

print

for percentage in greaterPercentages:
    print "{:2.2f}".format(percentage), '\t',

我在这里做的是

1. 在集合s中插入一些随机值，其中每个元素都在[0，numberRange)范围内
2. 从集合中弹出一个元素(根据文档，它应该是随机的)
3. 计算集合中有多少元素小于弹出值

1. Inserting some random values in the set s where each element is in the range [0, numberRange)
2. Pop an element from the set (according to the docs, it should be a random one)
3. Counting how many elements in the set are smaller then the popped value

我希望弹出的值应该是随机数，并且集合中大约50％的数字将大于弹出的值.但是，似乎pop()几乎总是返回集合中最低的数字.这是numberRange = 500的结果.第一行表示弹出元素的值.第二行是小于弹出值的元素所占的百分比.

I expected that the popped value should be a random one and about 50% of the numbers in the set will be greater then the popped value. But seems that pop() almost always returns the lowest number in the set. Here are the result for numberRange = 500. First row denotes the values of the popped element. Second row is the percentage of elements which are smaller then the popped value.

9   0   3   1   409     0   1   2   4   0   
0 % 0 % 0 % 0 % 87 %    0 % 0 % 0 % 0 % 0 %

我用不同的numberRange值进行了此测试.对于设置元素的较低值，似乎pop()几乎总是返回最低元素.但是对于更高的值，它将返回一个随机元素.对于numberRange = 1000，结果为:

I've conducted this test with different values of numberRange. It seems that for lower values of the set elements, pop() almost always returns the lowest element. But for higher values it returns a random element. For numberRange = 1000, the result is:

518     3586    3594    4103    2560    3087    4095    3079    3076    1622    
7 %     72 %    73 %    84 %    54 %    51 %    79 %    63 %    67 %    32 %

我认为这是非常随机的.为什么会有这种奇怪的行为?我在做错什么吗?

which I think is pretty random. Why this strange behavior? Am I doing something wrong?

编辑:感谢大家的回答和评论，似乎任意"表示不能保证它是随机的".

EDIT: Thanks for everyone's answer and comment, seems that by "arbitrarily", it isn't guaranteed that it will be "random".

推荐答案

这是一个实现细节-set被实现为HashMap(类似于dict，但没有用于值的插槽)，set.pop删除了HashMap中的第一个条目，并且int s的哈希值是相同的int.

It's an implementation detail - set is implemented as a HashMap (similar to dict but without a slot for a value), set.pop removes the first entry in the HashMap, and an ints hash value is the same int.

结合起来，这意味着您的set(由哈希值排序)实际上也由条目 modulo hashtable size 排序；在您的情况下，这应该接近自然排序，因为您只插入较小范围内的数字-如果从randrange(10**10)而不是randrange(500)中获取随机数，则应该会看到不同的行为.另外，根据您的插入顺序，由于哈希冲突，您可以从原始哈希顺序中获得一些值.

Combined, this means that your set, which is ordered by the hash values, is actually ordered by the entries modulo hashtable size as well; this should be close to natural ordering in your case as you are only inserting numbers from a small range - if you take random numbers from randrange(10**10) instead of randrange(500) you should see a different behaviour. Also, depending on your insertion order, you can get some values out of their original hashing order due to hash collisions.

这篇关于Set.pop()不是随机的吗?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！