17

When I convert a Python 3.8.0 list to a set, the resulting set ordering* is highly structured in a non-trivial way. How is this structure being extracted from the pseudo-random list?

As part of an experiment I am running, I am generating a random set. I was surprised to see that plotting the set suddenly showed unexpected linear structure in the set. So there are two things puzzling me - why does converting to a set result have an ordering* which ends up highlighting this structure; and, to a lesser extent why does the pseudo-random set have this "hidden" structure at all?

The code:

X = [randrange(250) for i in range(30)]
print(X)
print(set(X))

which outputs, for example

[238, 202, 245, 94, 111, 106, 148, 164, 154, 113, 128, 10, 196, 141, 69, 38, 106, 8, 40, 53, 160, 87, 85, 13, 38, 147, 204, 50, 162, 91]

{128, 8, 10, 141, 13, 147, 148, 154, 160, 162, 164, 38, 40, 50, 53, 196, 69, 202, 204, 85, 87, 91, 94, 106, 238, 111, 113, 245}

A plot** of the above list looks fairly random, as expected:

WolframAlpha plot of randomly generated list

whereas plotting the set (as it is ordered in the output) exhibits the structure present in the set:

WolframAlpha plot of set from random list

This behaviour 100% consistent on my machine (more examples below) with the values 250 and 30 used in the above code (the example I used is not cherry picked - it is just the last one I ran). Tuning these values sometimes results in slightly different structure (e.g. a subset of three arithmetic progressions*** instead of two).

Is this reproducible on other people's machines? Of course, that such structure exists seems indicative of a not-so-great pseudo-random number generation, but this does not explain how converting to a set would in some sense 'extract' this structure. As far as I am aware, the there is no formal guarantee that the ordering of a set (when converted from a list) is deterministic (and even if it is, there is no sophisticated ordering being done in the background). So how is this happening?!

(*): I know, sets are unordered collections, but I mean "ordered" in the sense that, when calling the print statement, the set is output in some order which consistently highlights the underlying set structure.

(**): These plots are from Wolfram Alpha. Two more examples are below:

enter image description here

(***): Two plots when changing the range of the random numbers from 250 to 500:

enter image description here

Improve this question

1 Answer 1

Reset to default
18

Basically, this is because of two things:

  • A set in Python is implemented using a hashtable,
  • The hash of an integer is the integer itself.

Therefore, the index that an integer appears in the underlying array will be determined by the integer's value, modulo the length of the underlying array. So, integers will tend to stay in ascending order when you put a contiguous range of them into a set:

>>> list(set(range(10000))) == list(range(10000))
True # this can't be an accident!

If you don't have all of the numbers from a contiguous range, then the "modulo the length of the underlying array" part comes into play:

>>> r = range(0, 50, 4)
>>> set(r)
{0, 32, 4, 36, 8, 40, 12, 44, 16, 48, 20, 24, 28}
>>> sorted(r, key=lambda x: x % 32)
[0, 32, 4, 36, 8, 40, 12, 44, 16, 48, 20, 24, 28]

The sequence is predictable if you know the length of the underlying array, and the (deterministic) algorithm for adding elements. In this case the array's length is 32, because it's initially 8 and is quadrupled while elements are added.

Except for a blip near the end (because the numbers 52 and 56 aren't in the set), the range is divided into two sequences 0, 4, 8, ... and 32, 36, 40, ... which alternate because the hashes, which are the numbers' values themselves, are taken modulo 32 to choose indices in the array. There are collisions; for example, 4 and 36 are equal modulo 32, but 4 was added to the set first so 36 ends up at a different index.

Here's a chart for this sequence. The structure in your charts is just a noisier version, because you generated your numbers randomly rather than from a range with a step.

enter image description here

The number of interleaved sequences will depend on the size of the set in proportion to the length of the range the numbers are sampled from, since that determines how many times the range's length "wraps around" modulo the length of the hashtable's underlying array. Here's an example with three interleaved sequences 0, 6, 12, ..., 66, 72, 78, ... and 36, 42, 48, ...:

>>> set(range(0, 90, 6))
{0, 66, 36, 6, 72, 42, 12, 78, 48, 18, 84, 54, 24, 60, 30}
Improve this answer
Sign up to request clarification or add additional context in comments.

15 Comments

Ah! That explains it (and nice explanation too)!
And of course, this pattern in the plots has nothing to do with underlying structure in the set (we would expect this pattern to arise in the plots with random lists as in my example)... I was just seduced by the unexpected patterns in the plots!
How do you find that 30 is the length of the underlying array?
@MarkSnyder It turns out it's 32, which means there are collisions, but the order is the same as if it was modulo 30.
@MarkSnyder The array will be resized if it gets more than 2/3 full, since a hashtable's performance degrades very significantly if you let the array get full or nearly-full.
|

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.