Python: how does the generator and filter work in the codes gene

ghz 14hours ago ⋅ 5 views

Python: how does the generator and filter work in the codes generating prime list with filter()

Note: This question is different with using filter and generator to generator endless prime number in python although both of them are related to Python code finding all the prime numbers up to a given limit.

The core codes are actually very simple, but it's hard for me to understand how it works. That's the reason I add some debug prints.

def _odd_number_generator():
    x = 1
    while True:
        x += 2
        print('    _odd_number_generator, x=', x)
        yield x

def _not_divisible(n):
    def func(x):
        print("      filter calling on x:", x, ", n:", n)
        return x % n > 0
    return func


def _primes():
    yield 2                                 # return first prime: 2
    odd_numbers = _odd_number_generator()   
    print("  in _primes, #a:  odd_numbers=", odd_numbers)
    while True:
        print("  in _primes, #b:         before next(filter) odd_numbers=", odd_numbers)

        # I know this line calling _odd_number_generator and _not_divisible, 
        # but how it works
        n = next(odd_numbers)   

        print("  in _primes, #c:         begin yield n:", n)
        yield n
        print("  in _primes, #d: n=", n, ", after yield  odd_numbers=", odd_numbers)
        odd_numbers = filter(_not_divisible(n), odd_numbers)    
        print("  in _primes, #e: n=", n, ", after filter odd_numbers=", odd_numbers)


def print_prime_numbes():
    for n in _primes():                                          
        print("  in print_prime_numbes, n = ", n)
        if n < 30:
            print(n)
            print()
            print("print_prime_numbes, begin next loop: n=", n)
        else:
            break

def test_print_prime_numbes():
    print("test_output_triangles() >>>")
    print_prime_numbes()

The answer in using filter and generator to generator endless prime number in python is very helpful to understand the chained iterator. But still, I get problem to understand how the _odd_number_generator and _not_divisible is being called when handling the number 25.

For example, here is a piece of outputs when running:

print_prime_numbes, begin next loop: n= 23
  in _primes, #d: n= 23 , after yield  odd_numbers= <filter object at 0x000002B0E02366D8>
  in _primes, #e: n= 23 , after filter odd_numbers= <filter object at 0x000002B0E0236F98>
  in _primes, #b:         before next(filter) odd_numbers= <filter object at 0x000002B0E0236F98>
    _odd_number_generator, x= 25
      filter calling on x: 25 , n: 3
      filter calling on x: 25 , n: 5
    _odd_number_generator, x= 27
      filter calling on x: 27 , n: 3
    _odd_number_generator, x= 29
      filter calling on x: 29 , n: 3
      filter calling on x: 29 , n: 5
      filter calling on x: 29 , n: 7
      filter calling on x: 29 , n: 11
      filter calling on x: 29 , n: 13
      filter calling on x: 29 , n: 17
      filter calling on x: 29 , n: 19
      filter calling on x: 29 , n: 23
  in _primes, #c:         begin yield n: 29
  in print_prime_numbes, n =  29
29

Here, because 25 is divisible, next number, 27, is being generated. I want to know what makes the calling to generate 27?

[Edited]

After yield 23, and go to next loop, the odd_numbers should be something like this: filter(_not_divisible(23),filter(_not_divisible(19) ...filter(_not_divisible(7),filter(_not_divisible(5),filter(_not_divisible(5),filter(_not_divisible(3), _odd_generator())).

When running "yield n", the next number 25, is being generated and check the divisibility, and _not_divisible return False. Here, looks like the 'yield' will run next on _odd_generator() and check if the new number can be divided by 3,4,5,..23 until it gets a prime. But I want to know the mechanism here in details.

Answer

The mechanism you're observing involves the interplay between generators and filters, as well as how filtering works in Python when it's applied to an iterator. Let's break it down step by step, focusing on the core elements:

Key Concepts

  1. Generators (yield): The function _odd_number_generator is a generator that yields odd numbers one by one, starting from 3 (after the first yield of 2).

  2. Filter: The filter() function takes a function and an iterable and returns a filter object, which is an iterator that only yields elements of the iterable for which the function returns True.

  3. Chaining of filters: When you chain filter calls, they are not immediately executed. Instead, they create an iterator that lazily evaluates the condition when you ask for the next item.

Your Example Walkthrough

At each step, the main focus is on how the numbers are filtered through the _not_divisible(n) function and how the yield of the prime numbers happens in the _primes() function.

Let’s break down the code with the key part being this:

    odd_numbers = filter(_not_divisible(n), odd_numbers)

This line filters out numbers from odd_numbers that are divisible by n. However, because filter only produces the next value when asked for it (lazy evaluation), the filter itself doesn't execute until next(odd_numbers) is called.

Now, let’s focus on the specific part of the output you're asking about, when 25 is encountered.

What Happens After Yielding 23?

After yielding 23 from _primes(), you then proceed to the next loop iteration. Let's walk through what happens:

Step 1: The Next Number from the Generator

  • odd_numbers = filter(_not_divisible(23), odd_numbers) is set up.
  • odd_numbers is now a filter object, meaning it will lazily evaluate each number to check if it's divisible by 23.
  • When you call next(odd_numbers), Python will try to fetch the next odd number from the filtered sequence.

Step 2: The First Iteration with next(odd_numbers) (Generating 25)

  • The filter is applied to the odd numbers generated by _odd_number_generator(). The first odd number from the generator is 25.
  • Now, the filter _not_divisible(23) is applied to 25:
    • The _not_divisible(23) function is a closure that takes a number n and returns a function that checks if a given number x is not divisible by n.
    • It is called with x = 25 and n = 23, and the check 25 % 23 > 0 returns True because 25 is not divisible by 23. Therefore, 25 passes this filter.

Step 3: Moving to the Next Odd Number (Generating 27)

  • The next number generated by _odd_number_generator() is 27.
  • Again, the filter _not_divisible(23) is applied to 27:
    • The _not_divisible(23) function checks if 27 % 23 > 0. This is True, so 27 is not divisible by 23 and is allowed to pass through the filter.

Step 4: Continuing the Filtering Process with Other Primes

  • Next, you proceed to check divisibility against the next primes:
    • _not_divisible(19) is called, and the check is done for each number (27, 29, etc.).
    • The filter keeps checking if each number is divisible by any of the primes found so far (3, 5, 7, 11, etc.).
    • Numbers that are divisible by any prime are discarded, while numbers that aren't are allowed to continue.

Step 5: Generating 29 (Prime)

  • Eventually, the next number that passes all the divisibility checks is 29, and it is yielded as the next prime.

Detailed Explanation of What's Happening with 25

To clarify what’s happening when 25 is generated:

  1. First, _odd_number_generator() generates the number 25.

  2. Then, the number 25 is passed through a series of filters.

    • First, it’s checked for divisibility by 23.
      • The _not_divisible(23) function returns True, because 25 % 23 != 0. Therefore, 25 is allowed.
    • Next, it’s checked for divisibility by 19, 17, and so on (other primes previously encountered).
      • For each prime, the _not_divisible() filter is applied. The checks for divisibility by 5 and 3 fail (since 25 is divisible by 5), and the filter() for these primes will return False for 25.
      • This means 25 is discarded by the filter and not passed to the next loop.

  3. After 25 is discarded, the generator moves on to 27, and the same process is applied.

  4. Eventually, 29 is generated, passes all the filters, and is yielded as the next prime.

Conclusion

The filter function works lazily, meaning the filtering process isn't executed all at once but only when the next item is requested via next(odd_numbers). When 25 is generated, it's checked against all the primes found so far, and because it’s divisible by 5, it gets discarded. The generator then proceeds to the next number, 27, and the filtering process continues.

This lazy evaluation and chaining of filters allow for efficient prime number generation without having to check every odd number upfront. The filters only process numbers as they are needed and discard non-prime numbers immediately, which optimizes the process of finding primes.

#py