Komplexität der Raumdichte und Sequenzialität

Question

Ich suche einige Standardterminologie, Metriken und/oder Anwendungen der Berücksichtigung der Dichte und Sequenzialität von Algorithmen.

Wenn wir Algorithmen messen, neigen wir dazu, der Big-oh-Notation wie $ O (n) $ zu geben, und normalerweise messen wir die Zeitkomplexität. Etwas seltener, obwohl immer noch oft, werden wir auch die Raumkomplexität eines Algorithmus messen.

Angesichts der aktuellen Computersysteme spielt jedoch die Speicherdichte und die Sequenz, in der er zugegriffen wird, eine wichtige Rolle bei der praktischen Leistung des Algorithmus. In der Tat gibt es Szenarien, in denen eine Zeitkomplexitätsalgortihm von $ o ( log n) $ mit dispergierender Zufallsspeicherzugriff langsamer sein kann als ein $ O (n) $ -Algorithmus mit dichter sequentieller Speicherzugriff. Ich habe diese Aspekte noch nicht gesehen, die in der formalen Theorie behandelt wurden. Sicher muss es existieren und ich bin hier nur unwissend.

Was sind die Standardmetriken, Begriffe und Ansätze für diese Raumdichte und Zugriffs -Sequenzialität?

Answer 1

Es gibt einige Modelle, die die Anzahl der Speicherübertragungen berücksichtigen, die ein Algorithmus überträgt. Einer der erfolgreichsten ist das Cache-ideal Frigo et al., Cache-obliven Algorithmen, 1999. Es basiert auf dem von Aggarwal und Vitter eingeführten externen Speichermodell, der Eingabe-/Ausgangskomplexität der Sortierung und verwandten Probleme, 1988. Die Notizen von Demaine Geben Sie einen schönen, lesbaren Überblick über das Modell und einige der Algorithmen und Datenstrukturen. Alternativ lesen Sie das Kapitel über Cache-obliven Datenstrukturen im Handbuch mit Datenstrukturen und Anwendungen. Wenn Sie Videos bevorzugen, deckt Demaine alle Grundlagen ab und vielleicht sogar mehr auf der MIT Einführung in Algorithmen Vorträge.

Das Modell nimmt keine Kenntnis der Anzahl der Ebenen in der Speicherhierarchie an. Darüber hinaus sind keine Parameter wie Cache-Linienlänge oder Cache-Größe zu konfigurieren. Eine Eigenschaft ist, dass ein Algorithmus im Cache-ideal-Modell optimal funktioniert, er in jeder Speicherhierarchie von $ k $ -level optimal funktioniert. Darüber hinaus werden Algorithmen, die im Modell optimal funktionieren, als Cache-obliven bezeichnet. Sie bieten die Vorteile von Einfachheit, Robustheit und Portabilität gegenüber den von Cache-bewährten Algorithmen, deren Ressourcennutzung explizit verwaltet werden muss.

Das Ideal-Cache-Modell verfügt über zwei Komplexitätsmaßnahmen. Der erste ist die Arbeitskomplexität, dh die herkömmliche Laufzeit eines Algorithmus im RAM -Modell. Der zweite stammt aus dem externen Speichermodell, das ist die Anzahl der Speichertransfers. Das Ideal-Cache-Modell modifiziert das externe Speichermodell jedoch auf einige Arten. Es verfügt über eine optimale Strategie für Blockersatz, automatischer Austausch und vollständige Assoziativität. Alle diese Annahmen werden durch eine Sammlung von Reduktion von Frigo et al.

Algorithmen und Datenstrukturen werden dann im Modell analysiert. Betrachten Sie beispielsweise die klassische binäre Suche. Die Laufzeit führt zu einem Wiederauftreten

$$ t (n) = t (n/2) + o (1). $$

In Anbetracht des Rekursionsbaums führt jede Stufe einen $ log n $ faktor zu, der die Lösung von $ theta ( log n) $ ergibt. Bei der Analyse von Algorithmen im RAM -Modell nehmen wir häufig den Basisfall von $ t (1) = o (1) $ für unsere Rezidive an. Im Cache-Ideal-Modell lassen wir jedoch häufig den Algorithmus das Problem auf den Weg trennen, betrachten jedoch den Punkt, an dem das Problem entweder zum Cache passt oder in $ o (b) $ Anzahl der Speicherblöcke passt. Tatsächlich können wir unsere Analyse hier verbessern, indem wir einen stärkeren Basisfall von $ t (o (b)) = O (1) $ verwenden. Damit entspricht die klassische binäre Suche $ theta ( log n - log b) $ Memory Transfers. Darüber hinaus ist die klassische binäre Suche nicht Optimal das in Cache-ideale Modell. Es sind cleverere Möglichkeiten erforderlich, um die optimale $ theta ( log_b n) $ gebunden zu erreichen.

Ich denke, der Erfolg des Modells beruht auf der Tatsache, dass es einfach ist, mit ihm zu arbeiten, und es funktioniert auch in der Praxis, was bedeutet, dass es ziemlich effektiv war, die Kosten eines Algorithmus für reale Systeme vorherzusagen. Es gibt viele Cache-obliven Algorithmen und Datenstrukturen. Zum Beispiel haben wir Cache-obliven Algorithmen für viele Probleme in der Rechengeometrie, das Scannen dynamischer Sets, Bioinformatik, Schablonenberechnungen, lineare Algebra, Suffix-Array-Konstruktion und für einige grundlegende Graphenprobleme unter Verwendung von Cache-obliven Prioritätskräften. Die wichtigsten Techniken, die effektiv sind, sind lineares Scannen von Speicher und Divide-and-Conquer.

In der Praxis war die allgemeine Schlussfolgerung so, dass Cache-obliven Algorithmen häufig RAM-Algorithmen übertreffen. Die von Cache-bewussten Algorithmen sind jedoch normalerweise noch schneller, da sie auf eine bestimmte Problemgröße und Speicherhierarchie abgestimmt sind. Für ein schönes Beispiel siehe Ladner et al., Ein Vergleich von Cache -Awes- und Cache, die unvergessliche statische Suchbäume unter Verwendung von Programminstrumenten, 2002.