Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Collection comparison is reflexive, yet does not short circuit. Why?

Tags:

python

In python, the built in collections compare elements with the explicit assumption that they are reflexive:

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.

Logically, this means that for any list L, L == L must be True. Given this, why doesn't the implementation check for identity to short circuit the evaluation?

In [1]: x = list(range(10000000))
In [2]: y = list(range(int(len(x)) // 10))
In [3]: z = [1]

# evaluation time likes O(N)
In [4]: %timeit x == x
10 loops, best of 3: 21.8 ms per loop
In [5]: %timeit y == y
100 loops, best of 3: 2.2 ms per loop
In [6]: %timeit z == z
10000000 loops, best of 3: 36.4 ns per loop

Clearly, child classes could choose to make an identity check, and clearly an identity check would add a very small overhead to every such comparison.

Was a historical decision explicitly made not to make such a check in the built in sequences to avoid this expense?

like image 416
donkopotamus Avatar asked Aug 05 '16 01:08

donkopotamus


1 Answers

While I'm not privy to the developers' thinking, my guess is that they might have felt comparing L == L does not happen often enough to warrant a special check, and moreover, the user can always use (L is L) or (L==L) to build a short-circuiting check himself if he deems that advantageous.

In [128]: %timeit (x is x) or (x == x)
10000000 loops, best of 3: 36.1 ns per loop

In [129]: %timeit (y is y) or (y == y)
10000000 loops, best of 3: 34.8 ns per loop
like image 96
unutbu Avatar answered Oct 21 '22 03:10

unutbu