Author wbolster
Recipients wbolster
Date 2017-07-12.13:15:30
SpamBayes Score -1.0
Marked as misclassified Yes
Message-id <1499865331.17.0.239728084792.issue30907@psf.upfronthosting.co.za>
In-reply-to
Content
when comparing instances of the built-in container types (dict, list, and others) python assumes that "identity implies equality". this is documented (and assumed) behaviour:


"In enforcing reflexivity of elements, the comparison of collections assumes that for a collection element x, x == x is always true. Based on that assumption, element identity is compared first, and element comparison is performed only for distinct elements."

https://docs.python.org/3/reference/expressions.html#value-comparisons

because of this, various operations such as rich comparison of lists can be sped up by checking for identity first, and only falling back to (possibly) much slower rich comparisons on container elements when two elements are not identical (i.e. id(a) == id(b)).

because identity implies equality, comparing a container instance to itself is guaranteed to be true.

currently, comparing a list to itself takes O(n) time, which can be measured easily:

>>> x = list(range(1000))
>>> %timeit x == x
2.95 µs ± 19.2 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

>>> y = list(range(100000))
>>> %timeit y == y
293 µs ± 3.35 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

the second example is 100 times as slow.

i will shortly submit a few pull request to make "compare to self" run in O(1) time instead for a few of the built-in containers.
History
Date User Action Args
2017-07-12 13:15:31wbolstersetrecipients: + wbolster
2017-07-12 13:15:31wbolstersetmessageid: <1499865331.17.0.239728084792.issue30907@psf.upfronthosting.co.za>
2017-07-12 13:15:31wbolsterlinkissue30907 messages
2017-07-12 13:15:30wbolstercreate