Friday, October 08, 2021

Converting an algorithm to use Pythons' new Structural Pattern Matching

 Python 3.10 is out and browsing what's new, I decided to convert one of my existing routines to use the new Structural Pattern Matching  statement  to try it out.

I used fgrep -c elif,  as part of a long unix command to find my algorithms with a lot of elif statements, and then chose my routine that evaluates Ackermann's function without explicit recursive function calls and with a lot of optimisations.


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
from collections import deque

def ack_ix(m, n):
    "Paddy3118's iterative with optimisations on m"

    stack = deque([])
    stack.extend([m, n])

    while  len(stack) > 1:
        n, m = stack.pop(), stack.pop()

        if   m == 0:
            stack.append(n + 1)
        elif m == 1:
            stack.append(n + 2)
        elif m == 2:
            stack.append(2*n + 3)
        elif m == 3:
            stack.append(2**(n + 3) - 3)
        elif n == 0:
            stack.extend([m-1, 1])
        else:
            stack.extend([m-1, m, n-1])

    return stack[0]

Note that first n, then m is popped off the stack in the first line within the while loop.

Checking the match statement examples PEP-634, I create a match subject expression as a list of first the n then the m value and replace the if statement with case statements covering each of the if conditionals and also assigning to n and m as appropriate, to create:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
def ack_im(m, n):
    "Paddy3118's iterative with optimisations on m using match of lists"

    stack = deque([])
    stack.extend([m, n])

    while  len(stack) > 1:
        match  [stack.pop(), stack.pop()]:
            case [n, 0]:
                stack.append(n + 1)
            case [n, 1]:
                stack.append(n + 2)
            case [n, 2]:
                stack.append(2*n + 3)
            case [n, 3]:
                stack.append(2**(n + 3) - 3)
            case [0, m]:
                stack.extend([m-1, 1])
            case [n, m]:
                stack.extend([m-1, m, n-1])

    return stack[0]

I had thought that it would be more natural to use tuples rather than lists for the subject expressions and case patterns as there are always only two things being matched, so created a third version:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
def ack_imt(m, n):
    "Paddy3118's iterative with optimisations on m using match of tuples"

    stack = deque([])
    stack.extend([m, n])

    while  len(stack) > 1:
        match  (stack.pop(), stack.pop()):
            case (n, 0):
                stack.append(n + 1)
            case (n, 1):
                stack.append(n + 2)
            case (n, 2):
                stack.append(2*n + 3)
            case (n, 3):
                stack.append(2**(n + 3) - 3)
            case (0, m):
                stack.extend([m-1, 1])
            case (n, m):
                stack.extend([m-1, m, n-1])

    return stack[0]


Checks/Timings

if __name__ == "__main__":
    import timeit
    assert (ix := ack_ix(4, 2)) == (im := ack_im(4, 2)) == (im := ack_imt(4, 2)), "Whoops!"
    print(f"Answer has {len(str(ix))} decimal digits")
    n = 100_000
    print(f"Timings for {n:_} repetitions of ack(4, 2)")
    for func in 'ack_ix ack_im ack_imt'.split():
        print(f"  {func+':':8}",
              timeit.timeit(f"{func}(4, 2)",
                            number=n,
                            setup=f"from __main__ import {func}"))

Running the code produces the following output:

Answer has 19729 decimal digits
Timings for 100_000 repetitions of ack(4, 2)
  ack_ix:  15.179398099950049
  ack_im:  15.368259999959264
  ack_imt: 15.472230200015474

 

Personal conclusion

There isn't much difference in runtime between if and match statements. This example only touches on the match statements capabilities, and so seems equally expressive as the if statement variant to me.

at

No comments:

Post a Comment