Understand the use of filters in one article

PythonThe built-in filter() function is used to filter sequences.

Similar to map(), filter() also accepts a function and a sequence. Different from map(), filter() applies the passed function to each element in turn, and then decides whether to keep or discard the element based on whether the return value is True or False.

For example, in a list, to delete even numbers and keep only odd numbers, you can write like this:

def is_odd(n):
    return n % 2 == 1

list(filter(is_odd, [1, 2, 4, 5, 6, 9, 10, 15]))
# 结果: [1, 5, 9, 15]

To delete empty strings in a sequence, you can write like this:

def not_empty(s):
    return s and s.strip()
    
list(filter(not_empty, ['A', '', 'B', None, 'C', '  ']))
# 结果: ['A', 'B', 'C']

It can be seen that the key to using the high-order function filter() is to correctly implement a "filtering" function.

Note that the filter() function returns an Iterator, which is a lazy sequence, so filter() must be forced to complete the calculation As a result, you need to use the list() function to obtain all results and return list.

Use filter to find prime numbers

One way to calculate prime numbers is the Ehrlich sieve method. Its algorithm is very simple to understand:

First, list all natural numbers starting from 2 and construct a sequence:

2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, ...

Take the first number 2 of the sequence, which must be a prime number, and then use 2 to filter out the multiples of 2 in the sequence:

3,4, 5,6, 7,8, 9,10, 11,12, 13,14, 15,16, 17,18, 19,20, ...

Get new The first number in the sequence is 3, which must be a prime number. Then use 3 to filter out the multiples of 3 in the sequence:

5,6, 7,8,9,10, 11,12, 13,14 ,15,16, 17,18, 19,20, ...

Take the first number 5 of the new sequence, and then use 5 to filter out the multiples of 5 in the sequence:

7,8,9,10, 11,12, 13,14,15,16, 17,18, 19,20, ...

If you continue to sift, you can get all the prime numbers.

To implement this algorithm in Python, you can first construct an odd sequence starting from 3:

def _odd_iter():
    n = 1
    while True:
        n = n + 2
        yield n

Note that this is a generator and an infinite sequence.

Then define a filtering function:

def _not_divisible(n):
    return lambda x: x % n > 0

Finally, define a generator to continuously return the next prime number:

def primes():  
  yield 2   
  it = _odd_iter() # 初始序列   
  while True:    
     n = next(it) # 返回序列的第一个数      
     yield n      
     it = filter(_not_divisible(n), it) # 构造新序列

This generator first returns the first prime number 2, Then, use filter() to continuously generate new filtered sequences.

Since primes() is also an infinite sequence, you need to set a condition for exiting the loop when calling:

# 打印1000以内的素数:
for n in primes():   
   if n < 1000:
        print(n)   
   else:       
          break

Note that Iterator is a sequence of lazy calculations, so we can use Python to express "all Natural numbers", "all prime numbers" and other sequences, and the code is very concise

The above is the detailed content of Understand the use of filters in one article. For more information, please follow other related articles on the PHP Chinese website!