Was die Wahl der Datenstruktur kostet

from collections.abc import Hashable


def find_duplicates(items: list[Hashable]) -> list[Hashable]:
    """Items that occur more than once, each listed once, in order of their second occurrence."""
    seen = []
    reported = []
    duplicates = []
    for item in items:
        if item in seen:
            if item not in reported:
                reported.append(item)
                duplicates.append(item)
        else:
            seen.append(item)
    return duplicates

from main import find_duplicates


class Key:
    """Eine int-Hülle, die zählt, wie oft Python sie vergleicht."""

    comparisons = 0

    def __init__(self, n):
        self.n = n

    def __eq__(self, other):
        Key.comparisons += 1
        return isinstance(other, Key) and self.n == other.n

    def __hash__(self):
        return hash(self.n)

    def __repr__(self):
        return f"Key({self.n})"


def test_duplicates():
    """3 und 1 wiederholen sich: [3, 1], jedes einmal"""
    got = find_duplicates([3, 1, 3, 2, 1, 3])
    assert got == [3, 1], f"Ergebnis {got!r}, erwartet [3, 1]"


def test_no_duplicates():
    """Verschiedene Elemente ergeben eine leere Liste"""
    got = find_duplicates(["a", "b", "c"])
    assert got == [], f"Ergebnis {got!r}, erwartet []"


def test_comparisons():
    """400 verschiedene Schlüssel brauchen fast keine ==-Vergleiche"""
    items = [Key(i) for i in range(400)] + [Key(7)]
    Key.comparisons = 0
    got = find_duplicates(items)
    assert [k.n for k in got] == [7], f"Ergebnis {got!r}, erwartet [Key(7)]"
    assert Key.comparisons < 50, f"find_duplicates machte {Key.comparisons} ==-Vergleiche; eine Liste wird Element für Element durchsucht, eine Menge nicht"

class History:
    """The last `size` events, oldest first."""

    def __init__(self, size: int) -> None:
        self.size = size
        self.events: list[str] = []

    def add(self, event: str) -> None:
        self.events.append(event)
        if len(self.events) > self.size:
            self.events.pop(0)  # shifts every other event

    def oldest(self) -> str:
        return self.events[0]

    def recent(self) -> list[str]:
        return list(self.events)

from collections import deque

from main import History


def test_keeps_last_three():
    """Mit size 3 bleiben nach a bis e nur c, d und e"""
    h = History(3)
    for event in "abcde":
        h.add(event)
    assert h.recent() == ["c", "d", "e"], f"recent() lieferte {h.recent()!r}, erwartet ['c', 'd', 'e']"


def test_oldest():
    """oldest() ist das erste noch gespeicherte Ereignis"""
    h = History(2)
    for event in ["login", "view", "logout"]:
        h.add(event)
    assert h.oldest() == "view", f"oldest() lieferte {h.oldest()!r}, erwartet 'view'"


def test_uses_bounded_deque():
    """events ist eine deque mit maxlen gleich size"""
    h = History(4)
    ok = isinstance(h.events, deque) and h.events.maxlen == 4
    assert ok, f"events ist {h.events!r}; erwartet deque(maxlen=4), die das älteste Element in konstanter Zeit verwirft"


def test_recent_is_a_copy():
    """recent() liefert eine neue Liste, nicht den internen Speicher"""
    h = History(2)
    h.add("a")
    h.recent().append("x")
    assert h.recent() == ["a"], f"eine Änderung an der Liste von recent() hat den Verlauf geändert: {h.recent()!r}"