Python iterators can also be played like this
In the past few days, I basically played around at home, Vientiane Hui, Green Park, Xiaodian Lake, and the wedding banquets of the younger brothers. If you are free, you can watch geek time, play games, and swipe WeChat. The kilometer running is still persisting.
I recently discovered a coup for iterators, and I can’t help but share it with you who love to learn.
For the definition and understanding of iterable objects, iterators, and generators, please refer to the previous article Python Basics Series-Iterable Objects, Iterators and Generators
In short, their relationship can be represented by the following diagram:
Seeing such a picture on Zhihu is more vivid:
Let's do an algorithm problem:
Given the strings s and t, determine whether s is a subsequence of t.
You can think that s and t contain only English lowercase letters. The string t may be very long (length ~= 500,000), and s is a short string (length<=100).
A subsequence of a string is a new string formed by deleting some (or not deleting) characters from the original string without changing the relative position of the remaining characters. (For example, "ace" is a subsequence of "abcde", but "aec" is not).
Source: LeetCode
Link: https://leetcode-cn.com/problems/is-subsequence
To solve this problem, the conventional algorithm is a greedy algorithm. Two pointers Ps and Pt are maintained to point to the beginning of the two strings s and t respectively, and then the string t is scanned all the way. If a character is the same as Ps, then Move the Ps pointer one step forward. When Ps moves out of the last character of the string s, it returns True, otherwise it returns False.
However, this code takes about 10 lines to write down.
If you use iterators and generators, two lines are done:
>>> def is_subseq(s,t):... t =iter(t)...returnall(i in t for i in s)...>>>is_subseq('ace','abcde')
True
>>> is_subseq('aec','abcde')
False
>>>
If you can see through the logic behind the code at a glance, it means that you are already a senior Python engineer. If you are confused, then we will expand the code and look at it step by step:
First, turn the original string into an iterator:
>>> t ='abcde'>>>iter(t)<str_iterator object at 0x7fa7f22c8a60>>>> t =iter(t)>>> t
< str_iterator object at 0x7fa7f229d4c0>
Then iterate through the substrings and determine in turn whether each character is in the above iterator t:
( i in t for i in s)
General mindset: i must be in t, because every character of the string aec exists in the original string abcde.
The good thing is that in this in operation, the in operation determines whether a character is in an iterator, it must be traversed, and traversal is to call the iterator's __next__ method, and return True when it exists, and In the next judgment, continue with __next__ without returning to the starting position to search again. At this point, we can execute next step by step as an experiment: Take s ='aec' and t ='abcdef' as an example:
>>> t ='abcdef'>>> s ='aec'>>> t =iter(t)>>>'a'in t
True
>>> next(t)'b'>>>'e'in t
True
>>> # At this point the pointer has pointed to e, and then call next to return f
>>> next(t)'f'>>>'c'in t #The pointer has pointed to f, and the character c will not appear after f, and it must return false
False
Seeing this, I believe you have already understood that after the in operation returns True, the next time in is judged, it is searched from the position where it ended last time. In other words, in the loop is used to judge whether an element is in an iteration In the device, the iterator will automatically remember the position after the last judgment, which is equivalent to an invisible pointer, which provides great convenience for solving this problem.
The final all function is used to determine whether all the elements of an iterator are True, if so, it returns True, otherwise it returns False.
Python is so magical and elegant. But you must pay attention, try not to use this technique during the interview, because your interviewer may not know the usage of the generator. In terms of this technical knowledge, you are already more proficient than many people in the application of actual work. Up.
Python number seven, do a more satisfactory number seven, learn a Python trick every week, welcome to pay attention.
(Finish)