Pop takes values from beginning of sets on ranges enumerated by one consitently. Is this intended?

Question

I'm sorry if this has been asked before, but I can't figure out how this prime sieve uses pop on a set to reliably pull its first/lowest values.

def get_primes(n):
    numbers = set(range(n, 1, -1))
    primes = []
    while numbers:
        p = numbers.pop()
        primes.append(p)
        numbers.difference_update(set(range(p*2, n+1, p)))
    print(primes)
get_primes(input('Primes under:'))

As far as I can tell it seems accurate, which seems to imply that it is consistently popping the smallest (or leftmost) number from the set, numbers , which contradicts my understanding of how sets work (inherently unordered). When trying to use the same methods on ranges enumerated by more than one, I got less predictable results (as originally expected).

I did some testing of my own:

numbers = set(range(15, 1, -1))
p = numbers.pop()
P>: 2
---------------------------------------------------------
numbers = set(range(15, 1, -2))
p = numbers.pop()
P>: 3
---------------------------------------------------------
numbers = set(range(15, 1, -3))
p = numbers.pop()
P>: 9
---------------------------------------------------------
numbers = set(range(15, 4, -1))
p = numbers.pop()
p>: 5
---------------------------------------------------------
numbers = set(range(15, 4, -2))
p = numbers.pop()
p>: 5
---------------------------------------------------------
numbers = set(range(15, 4, -3))
p = numbers.pop()
p>: 9

How is the function above not just pulling composite numbers and appending them to the list of primes? Even when the set it's pulling from is no longer enumerated by just one, it seems to work, not only that, but the list of returned primes looks to be completely ordered on magnitudes of ten thousand (and probably higher) . Is it possible to do repeat this for any sets like the ones I tested?

Thanks in advance.

EDIT: After following some links posted in the question linked for duplicates I discovered that sets are ordered based on a values last three binary digits.

Related, possibly dup: https://stackoverflow.com/questions/10432022/in-python-is-set-pop-deterministic — Robᵩ, Jul 12 '17 at 21:03
I am not sure about the `> 1` incremented ranges bit, but here is an existing answer focused on why integers are not random: https://stackoverflow.com/questions/21017188/set-pop-isnt-random — Farmer Joe, Jul 12 '17 at 21:12
Sets **are** arbitrarily ordered, based on the hash insertion point for the integer. It just so happens that most integers map to a hash that is equal to their value. — Martijn Pieters, Jul 12 '17 at 21:23
@EricDuminil: that's because the OP is not creating a disjoint sequence. — Martijn Pieters, Jul 12 '17 at 21:30
@EricDuminil: Also, look at the resulting set, not just what is popped. `set(range(15, 4, -3))` is `{9, 12, 6, 15}`, so `9` is popped. — Martijn Pieters, Jul 12 '17 at 21:32

Dan · Answer 1 · 2017-07-12T21:21:09.710

0

Sets are indexed by hash so for integers they will be ordered in ascending order since hash(n) == n if n is a positive int between 0 and 2^31-1. I wouldn't rely on this however since the size of the int can vary on different systems and it's really not a supported feature of the set.

edited Jul 12 '17 at 21:21

answered Jul 12 '17 at 21:14

Dan

1,874
1
16
21

only small `int`s hash to themselves – Chris_Rands Jul 12 '17 at 21:15
@Chris_Rands: "small" is relative. `hash(10**18) == 10**18` on my system. You wouldn't want to use this algorithm with 10**18. – Eric Duminil Jul 12 '17 at 21:18
@EricDuminil That's fair, maybe not so small... – Chris_Rands Jul 12 '17 at 21:22
1

@Chris_Rands: no, integers *except for -1* hash to themselves all the way up to `(sys.maxsize // 4) - 1` (because of the way long integers are implemented). – Martijn Pieters Jul 12 '17 at 21:22
Why the downvote? This seems to be the explanation. – Eric Duminil Jul 12 '17 at 21:24
On my OS X system, that means that integers up to `(2^61) - 2` hash to themselves. – Martijn Pieters Jul 12 '17 at 21:25
@MartijnPieters: This fits. To check it : `next(i for i in range(1,1000) if hash(2**i) != 2**i)` – Eric Duminil Jul 12 '17 at 21:26
@MartijnPieters thanks, my definition of *small* a bit unreasonable, why is -1 the exception (it hashes to -2 on my system like -2 does)? – Chris_Rands Jul 12 '17 at 21:26
1

@Chris_Rands: because `-1` is an error condition in C code. You can't return `-1` from a hash function, because that means there was an exception.. – Martijn Pieters Jul 12 '17 at 21:26

Pop takes values from beginning of sets on ranges enumerated by one consitently. Is this intended?

1 Answers1