Почему функция set.union() работает намного медленнее, чем оператор объединения set "|" в этом коде?
Я пересматривал свое решение https://adventofcode.com/2023/day/16. Вот мой старый код:
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
Если я заменю функцию объединения оператором объединения, например: energized |= new_energized, время работы упадет с 28-30 с до 2-3 с.
Я искал документы, руководства, все, что мог найти; все они говорят мне, что функция объединения и оператор имеют одинаковую производительность, но не отличаются в 10 раз.
На всякий случай я запустил код (обе версии) примерно 10 раз.
Репозиторий доступен по адресу https://github.com/ultinvincible/AdventOfCode_Py.
Разве energized |= new_energized не эквивалентно energized = energized | new_energized?
Людям трудно в это поверить, но минимизация кода действительно помогает найти основную проблему.
Ответы 2
Итак, я нашел проблему:
energized = energized.union(new_energized)
на самом деле не эквивалентно
energized |= new_energized
но эквивалентно
energized = energized | new_energized
Разница в том, что a=a.union(b) и a=a|b создают новый объект set и присваивают его старой ссылке, а a|=b изменяет существующий набор, что и является причиной такого ускорения кода.
Дурак я.
Спасибо @user2357112 за подсказку.
В этом та же разница между использованием mylist.append(x) для добавления в конец списка и использованием mylist = mylist + [x]. Первое представляет собой амортизированное постоянное время, поскольку оно добавляется к концу (если оно не изменяется, поэтому оно амортизирует постоянное время), второе является линейным временем, поскольку вы всегда создаете совершенно новый объект списка. Таким образом, в цикле первое будет линейным, а второе — квадратичным.
Таким образом, использование myset = myset.union(data) в цикле — это классическая ловушка производительности, связанная с использованием алгоритма Художника Шлемиэля.
Вот небольшой скрипт, демонстрирующий это (требуется pandas и 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')
И вот полученный рисунок, который показывает классическое линейное и полиномиальное поведение во времени:
|=— этоupdate, а неunion.|этоunion.