Shulou(Shulou.com)06/01 Report--

This article mainly introduces the Python implementation of x in range (y) how fast the relevant knowledge, the content is detailed and easy to understand, the operation is simple and fast, with a certain reference value, I believe that you can read this Python implementation of x in range (y) how fast the article will be rewarded, let's take a look at it.

Picture: unsplash.com

How fast can the expression 1000000000000000 in range (1000000000000001) be executed in Python?

The simplest and rudest way to judge whether an element x exists in the set y is to iterate and compare it with one value at a time. If there is a value z equal to x in the set, true is returned, and its time complexity is O (n). The theoretical time complexity of hashing algorithm is O (1), and the time complexity of binary search is O (log n). Which algorithm will Python use to implement it?

Let's do an experiment first:

# python2

Timeit.timeit ('1000000000 in range (0P.10000000000.10)', number=1)

5.50357640805305

Timeit.timeit ('1000000000 in xrange (0P.10000000000.10)', number=1)

2.3025200839183526

# python3

Import timeit

Timeit.timeit ('1000000000 in range (0P.10000000000.10)', number=1)

4.490355838248402e-06

We all know that the range function in python2 returns a list object that loads all the elements into memory at once, so when the first expression is executed, the system suddenly feels very stuttered, and it takes more than 5 seconds.

The range function in xrange and python3 is similar, returning an iterator object, but their execution results are surprisingly different. The third expression takes nearly 0 seconds, so why is the xrange in python2 so different from the range function in python3? To understand the mystery, we need to understand how the in operation is performed. According to the rules of the Python document in:

If the class implements the _ _ contains__ () method, then x in y also returns true as long as y.destroy containers _ (x) returns true, and vice versa.

The _ _ contains__ () method is not implemented, but the _ _ iter__ () method is implemented, so true is returned if there is a value of zroomroomx during the iteration, otherwise it is false.

If neither of the above methods is implemented, take a look at the _ _ getitem__ () method. If there is an index I that makes xroomy [I], it returns true, otherwise it returns false.

Now that we understand the rules of in, let's take a look at what methods xrange provides:

Dir (xrange)

['_ class__','__getitem__','_ _ hash__','_ _ init__'

'_ _ iter__',' _ _ len__','_ _ new__',.]

Yes, the xrange function only implements _ _ getitem__ and _ _ iter__, to determine whether x needs to be compared iteratively in y, that is, the time complexity of xrange is O (n).

Let's take a look at the methods of python3's range:

Dir (range)

['_ class__','_ _ contains__','_ _ getitem__','_ _ iter__'

'count', 'index',' start', 'step',' stop',.]

Range provides a lot more attributes than xrange, implementing not only _ _ getitem__ and _ _ iter__, but also _ _ contains__, so it calls the _ _ contains__ method first. In addition, it provides three properties, start, stop, and step. So why on earth does it execute so fast? Let's see how the contains method is implemented.

In Python3, _ _ contains__ does not iterate and compare value by value, but uses this logic:

First check if x is between start and stop: start

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.