Why is the "set.union()" function much slower than the set union operator "|" in this code?

I have been revisiting my solution for https://adventofcode.com/2023/day/16. Here is my old code:

from functools import cache
from helper import directions_2d
# [(0, 1), (-1, 0), (0, -1), (1, 0)]


def behavior(drt, tile):
    (row, col) = drt
    match tile:
        case "/":
            return [(-col, -row)]
        case "\\":
            return [(col, row)]
        case "|":
            if row == 0:
                return [(-1, 0), (1, 0)]
        case "-":
            if col == 0:
                return [(0, -1), (0, 1)]
    return [drt]


def run(input_data: str):
    part1 = 0
    part2 = 0
    light_map = [list(s) for s in input_data.splitlines()]
    lengths = (len(light_map), len(light_map[0]))
    starts = []
    for drt in directions_2d():
        dim = 0 if drt[0] == 0 else 1
        for i in range(lengths[dim]):
            start = [0, 0]
            start[dim] = i
            start[1 - dim] = -1 if drt[1 - dim] == 1 else lengths[1 - dim]
            starts.append([(tuple(start), drt)])

    @cache
    def run_line(row, col, drt):
        energized = set()
        (new_row, new_col) = (row, col)
        new_drt_list = [drt]
        while new_drt_list == [drt]:
            (new_row, new_col) = (new_row + drt[0], new_col + drt[1])
            if any(not 0 <= (new_row, new_col)[i] < lengths[i] for i in (0, 1)):
                new_drt_list = []
            else:
                new_drt_list = behavior(drt, light_map[new_row][new_col])
                energized.add((new_row, new_col))
        return new_row, new_col, new_drt_list, energized

    beams: list[tuple[int, int]]
    for beams in starts:
        current_i = 0
        energized = set()
        while current_i < len(beams):
            (row, col), drt = beams[current_i]
            new_row, new_col, new_drt_list, new_energized = run_line(row, col, drt)
            for new_drt in new_drt_list:
                if ((new_row, new_col), new_drt) not in beams:
                    beams.append(((new_row, new_col), new_drt))
            # this line
            energized = energized.union(new_energized)
            current_i += 1

        if beams[0] == ((0, -1), (0, 1)):
            part1 = len(energized)
        part2 = max(part2, len(energized))

    return part1, part2

If I replace the union function with the union operator, like so: energized |= new_energized, the running time drops from 28-30s to 2-3s.

I have searched the docs, guides, everything I can find; they all tell me the union function and operator have similar performance, not different by 10 times.

I ran the code (both versions) about 10 times just to be sure.

The repo is public at https://github.com/ultinvincible/AdventOfCode_Py.

>Solution :

This is he same difference between using mylist.append(x) to add to the end of a list versus using mylist = mylist + [x]. The former is amortized constant time since it adds to the end (unless it resizes, which is why it isamoritized constant time), the latter is linear time, since you are always creating a whole new list object. So in a loop, the former will be linear and the later will be quadratic.

So using myset = myset.union(data) in a loop is the classic performance trap of using Shlemiel the Painter’s algorithm.

Here is a little script to demonstrate this (requires pandas and matplotlib):

import pandas as pd
import matplotlib.pyplot as plt

import timeit

def union_new(n):
    result = set()
    for i in range(n):
        result = result.union({i})

def union_inplace(n):
    result = set()
    for i in range(n):
        result |= {i}

union_new_times = [timeit.timeit(lambda i=i: union_new(i), number=10) for i in N]
union_inplace_times = [timeit.timeit(lambda i=i: union_inplace(i), number=10) for i in N]

df = pd.DataFrame({"union_new":union_new_times, "union_inplace":union_inplace_times}, index=N)
df.plot()
plt.savefig('in-place-vs-new-set.png')

And here is the resulting figure, which shows the classic linear vs polynomial time behavior: