Die Signatur ist die Komplexität

Ob ein Join linear oder quadratisch wird, steht oft nicht in der Schleife. Es steht im Typ der Parameter.

Du sitzt im Profiling. Der Export mit zehntausend Zeilen dauert Minuten. In der Flamme: eine harmlose Join-Methode, tausendmal aufgerufen — und darin masters.Find(m => m.Id == item.MasterId). Niemand hat «böse» optimiert. Die Methode hat von Anfang an eine Liste entgegengenommen. Der Compiler hat Recht. Die Signatur hat die falsche Einladung ausgesprochen.

Dieser Text ist für Entwickler, die wissen, dass Find in einer Schleife teuer ist — und trotzdem in jedem zweiten Projekt wieder List<T> für Nachschläge sehen. Es geht nicht um Big-O aus dem Lehrbuch als Pflichtübung, sondern um API-Design: Welche Collection du in die Signatur schreibst, ist ein Versprechen an jeden zukünftigen Aufrufer (inklusive dir in drei Monaten).

Domäne (vereinfacht): Zeilen (Item) mit Fremdschlüssel (MasterId) an Stammdaten (Master) anbinden — Import, Reporting, Batch-Join. Technik: C#, LINQ, typische Service- und Repository-Grenzen. Die Idee gilt überall, wo «Join» heißt, nicht nur in SQL.

Kurzfassung

1. Review-Regeln verblassen («kein Find in der Schleife»), Signaturen bleiben — der Typ erlaubt die bequemste schlechte Lösung.
2. List<T> verspricht Reihenfolge und lineare Suche; für Lookup nach Id ist das die falsche Abstraktion.
3. IReadOnlyDictionary<TKey, TValue> und IReadOnlySet<T> machen den richtigen Pfad (TryGetValue, Contains) zum Normalfall.
4. Zwei ehrliche Überladungen (Einzelabruf vs. Mengen-Join) verhindern versteckte N×M-Aufrufe in Select.
5. Besserer Briefkopf reicht nicht: Wer intern Values.ToList() baut, betrügt trotz Dictionary-Parameter.

Begriffe

Begriff	Bedeutung
Signatur	Name + Parameter-Typen + Rückgabetyp — der öffentliche Vertrag der Methode.
Unterbestimmung	Parameter-Typ ist breiter als die Absicht (z. B. List statt «nur nachschlagen»).
Lookup / Join	Zu einer Id den passenden Stammsatz finden — ideal O(1) amortisiert, nicht O(n) pro Zeile.
Mengenpfad	Viele Item-Zeilen mit einem vorbereiteten Index (Dictionary, HashSet).
Einzelpfad	Ein Aufruf, evtl. mit Cache oder DB — darf teurer sein, nicht in Select über 10⁴ Zeilen.

Muster 1: Die Liste in der Join-Signatur (Anti-Pattern)

Was der Code tut: Für jede Zeile die Master-Liste durchsuchen.

Was die Signatur verspricht: «Ich darf diese Menge linear durchsuchen.»

// Anti-Pattern: Join modelliert als Suche in einer Liste.
static Row? Join(Item item, List<Master> masters)
{
    var master = masters.Find(m => m.Id == item.MasterId);
    return master is null ? null : Map(item, master);
}

Warum das in Produktion landet: Der Aufrufer hat die Masters schon als Dictionary im Speicher — aber die Signatur nimmt nur List entgegen. Also masters.Values.ToList() einmal … oder schlimmer: die Liste kommt aus der DB ohne Index. In einem foreach über Items wird das O(Anzahl Items × Anzahl Masters).

Gegenbeispiel: Vertrag = Nachschlagen nach Id.

static Row? Join(Item item, IReadOnlyDictionary<string, Master> mastersById)
{
    if (!mastersById.TryGetValue(item.MasterId, out var master))
        return null;

    return Map(item, master);
}

Find ist nicht verboten — es ist unbequem, weil man .Values durchlaufen müsste und damit den Sinn des Parameters zerstört. Das fällt im Review auf. Das fällt dir auf, wenn du den Code nochmal liest.

IReadOnlyDictionary statt Dictionary: Die Methode soll lesen, nicht den Index umbauen. Wer mutieren will, hält das konkrete Dictionary beim Aufrufer und übergibt es als Read-Only-View.

Muster 2: Der Export, der die Liste pro Zeile neu baut

Anti-Pattern: Der Parameter heißt Dictionary — intern wird er wieder zur Liste.

// Anti-Pattern: Dictionary nur als Dekoration.
static Row? Join(Item item, IReadOnlyDictionary<string, Master> mastersById)
{
    var master = mastersById.Values.FirstOrDefault(m => m.Id == item.MasterId);
    return master is null ? null : Map(item, master);
}

Gegenbeispiel: Einmal indexieren, dann nur noch TryGetValue.

// Aufrufer (Mengenpfad): Index einmal bauen.
var mastersById = masters.ToDictionary(m => m.Id, StringComparer.Ordinal);

var rows = items
    .Select(item => Join(item, mastersById))
    .Where(row => row is not null)
    .ToList();

Die Schleife ist noch da — aber der innere Teil ist konstant pro Zeile (Hash-Lookup), nicht linear in der Größe der Master-Liste.

Muster 3: Mitgliedschaft statt Lookup (Contains auf List)

Gleiche Logik, anderes Verb: «Ist diese Id erlaubt?»

// Anti-Pattern: List suggeriert Reihenfolge — Contains ist O(n).
bool IsAllowed(string id, List<string> allowedIds)
    => allowedIds.Contains(id);

Gegenbeispiel:

bool IsAllowed(string id, IReadOnlySet<string> allowedIds)
    => allowedIds.Contains(id);

Für kleine Mengen (zwanzig Ids) ist das egal. Für jeden Request mit tausenden Prüfungen wird die Signatur zum Geländer.

Welcher Typ zu welcher Absicht?

Die Kette IEnumerable → ICollection → IList → List kennt man aus API-Design: weniger Oberfläche, weniger Versuchung. Für Joins und Filter ist diese Tabelle oft hilfreicher:

Was die Methode tun soll	Was sie entgegennehmen sollte
durchlaufen, abbilden	IEnumerable<T>
nachschlagen nach Identität	IReadOnlyDictionary<TKey, TValue>
prüfen, ob etwas vorkommt	IReadOnlySet<T> (oder HashSet<T> wenn der Aufrufer mutiert)
Reihenfolge, Index, Find	IList<T> / List<T>

Wer Nachschlagen auf einer Liste modelliert, lügt nicht — er unterbestimmt. Unterbestimmte Signaturen werden mit der bequemsten Operation gefüllt, die der Typ hergibt. Deshalb verpufft «bitte kein Find in der Schleife» als wiederholter Review-Kommentar, während eine geänderte Signatur Jahre hält.

Muster 4: Eine «flexible» Überladung vs. zwei ehrliche

Anti-Pattern: Ein Mengen-Export ruft den Einzelpfad in Select auf — jeder Treffer sieht billig aus, die Summe nicht.

// Anti-Pattern: N Datenbank- oder Cache-Roundtrips (oder N teure Lookups).
var rows = items.Select(async item => await JoinAsync(item)).ToList();

Gegenbeispiel: Zwei Überladungen, klar getrennt.

// Einzelfall: Cache, DB, Berechtigung — bewusst ein Aufruf.
Task<Row?> JoinAsync(Item item, CancellationToken cancellationToken = default);

// Mengenpfad: Index liegt beim Aufrufer.
Row? Join(Item item, IReadOnlyDictionary<string, Master> mastersById);

Der Export soll Join(item, mastersById) nutzen. JoinAsync in einem Select über tausend Zeilen sieht nach einem Fehler aus — und ist einer. Die Signatur macht den Missbrauch sichtbar, ohne dass du in jedem PR die Big-O-Tafel wiederholen musst.

Was sich nicht in den Typ pressen lässt

Ob n und m mit der Zeit wachsen, steht nicht in der Signatur. Ob zwanzig Einträge linear bleiben dürfen, auch nicht. Der Typ sagt nur:

• diese Methode behauptet nachzuschlagen, oder
• sie behauptet, eine Liste zu durchsuchen.

Das ist ein Geländer, kein Ersatz für Nachdenken. Eine IReadOnlyDictionary, die mit .Values.ToList() beginnt, ist derselbe Betrug wie vorher — nur mit besserem Briefkopf.

Trotzdem: Die meisten quadratischen Joins in Produktionscode entstehen nicht, weil jemand Komplexität falsch berechnet hat. Sie entstehen, weil die Methode eine Liste genommen hat und jemand später Find geschrieben hat, weil es kompiliert hat.

Refactor in kleinen Schritten

1. Hot Path finden — Export, Sync-Job, Schleife über viele Items.
2. Signatur lesen — steht List oder IEnumerable dort, wo nur Id → Master gebraucht wird?
3. Index an der Grenze bauen — ToDictionary / HashSet einmal beim Aufrufer, nicht in der inneren Methode.
4. Überladung trennen — Einzel (JoinAsync) vs. Menge (Join(..., mastersById)).
5. Test mit Größe — nicht nur «funktioniert mit drei Zeilen», sondern bewusst viele Masters + viele Items (Integration oder Benchmark, je nach Risiko).

Fazit

Laufzeitkomplexität lässt sich in C# nicht in die Sprache stanzen. Du kannst sie aber in den Vertrag legen: Der Parameter-Typ ist die Einladung an jeden Aufrufer — und an dich selbst in sechs Monaten.

Wer die Komplexität in die Signatur legt, muss sie nicht in jedem Review neu erklären. Nimm dir beim nächsten Join oder GetById zwei Minuten: Brauche ich Reihenfolge — oder Lookup? Wenn Lookup: Dictionary oder Set in die Signatur, Liste raus.

Die Code-Beispiele sind bewusst verdichtet (fiktive Typnamen Item / Master / Row). Sie sollen Muster trainieren, nicht eine konkrete Codebase 1:1 abbilden.