Angenommen, ich habe zwei sehr große Listen {a1, a2, ...} und {b1, b2, ...}, wobei alle ai und bj große Sparse-Arrays sind. Aus Gründen der Speichereffizienz speichere ich jede Liste als ein einziges kompaktes Array.
Nun möchte ich eine Funktion f für alle möglichen Paare von ai und bj berechnen, wobei jedes Ergebnis f [ai, bj] wieder ein spärliches Array ist. All diese sparse Arrays haben übrigens die gleichen Dimensionen.
Während
%Vor%gibt das gewünschte Ergebnis zurück (im Prinzip) scheint übermäßig viel Speicher zu verbrauchen. Nicht zuletzt, weil der Rückgabewert eine Liste von Sparse-Arrays ist, während ein umfassendes Sparse-Array in meinen interessanten Fällen viel effizienter ausfällt.
Gibt es eine effiziente Alternative zur obigen Verwendung von Outer ?
Genaueres Beispiel:
%Vor% usw. Nicht nur die rohen Zwischenergebnisse von Outer (Listen von Sparse-Arrays) sind extrem ineffizient, auch Outer scheint bei der eigentlichen Berechnung viel zu viel Speicher zu verbrauchen.
Ich werde eine Lösung vorschlagen, die ziemlich komplex ist, aber es erlaubt, dass man während der Berechnung nur etwa doppelt so viel Speicher verwendet, wie zum Speichern des Endergebnisses als SparseArray benötigt wird. Der Preis dafür ist eine viel langsamere Ausführung.
Hier ist der Code. Erstens, eine leicht modifizierte (um höherdimensionale Sparse-Arrays zu adressieren) Sparse-Array-Konstruktion - Dekonstruktions-API, entnommen aus diese Antwort :
%Vor%Die folgenden Funktionen erzeugen Iteratoren. Iteratoren sind eine gute Möglichkeit, den Iterationsprozess zu kapseln.
%Vor% Beachten Sie, dass ich die obige Funktion mehr Speicher hätte verwenden können - effizient und nicht Outer darin verwenden, aber für unsere Zwecke wird dies nicht die Hauptsorge sein.
Hier ist eine spezialisiertere Version, die Interaktoren für Paare von zweidimensionalen Indizes erzeugt.
%Vor%So funktioniert das:
%Vor%Wir können dies auch verwenden, um Batch-Ergebnisse zu erhalten:
%Vor%, und wir werden diese zweite Form verwenden.
Diese Funktion erstellt iterativ ein SparseArray -Objekt, indem sie Datenbrocken (auch in SparseArray form) erhält und zusammenfügt. Es ist im Grunde genommen Code in diese Antwort, verpackt in ein Funktion. Er akzeptiert das Codeteil, das für die Erzeugung des nächsten Datenblocks verwendet wurde, und zwar in Hold (ich könnte alternativ HoldAll machen)
Diese Funktion ist die Hauptfunktion, die alles zusammenfasst:
%Vor% Hier erzeugen wir zuerst den Iterator, der uns auf Nachfrage Teile der Indexpaarliste liefert, die zum Extrahieren der Elemente verwendet wird (auch SparseArrays ). Beachten Sie, dass wir in der Regel mehr als ein Paar Elemente aus zwei großen Inputs SparseArray -s gleichzeitig extrahieren, um den Code zu beschleunigen. Wie viele Paare gleichzeitig verarbeitet werden, hängt vom optionalen Parameter chunkSize ab, der standardmäßig 100 lautet. Wir konstruieren dann den Code, um diese Elemente zu verarbeiten und setzen das Ergebnis wieder in SparseArray , wo wir eine Hilfsfunktion wrapperF verwenden. Die Verwendung von Iteratoren war nicht absolut notwendig (könnte stattdessen Reap - Sow wie bei anderen Antworten verwenden), erlaubte mir jedoch, die Logik der Iteration von der Logik der generischen Akkumulation von Sparse-Arrays zu entkoppeln.
Zuerst bereiten wir große Sparse-Arrays vor und testen unsere Funktionalität:
%Vor%Jetzt machen wir die Power Tests
%Vor% Für dieses spezielle Beispiel ist die vorgeschlagene Methode 5-mal mehr speichereffizient als die direkte Verwendung von Outer , aber etwa 15 mal langsamer. Ich musste den chunksize -Parameter anpassen (Standard ist 100 , aber für das obige habe ich 2000 verwendet, um die optimale Kombination aus Geschwindigkeit und Speicher zu erhalten). Meine Methode verwendet nur als Spitzenwert doppelt so viel Speicher wie zum Speichern des Endergebnisses benötigt wird. Der Grad der Speicherersparnis im Vergleich zur Outer - basierten Methode hängt von den fraglichen Arrays ab.
Wenn lst1 und lst2 Ihre Listen sind,
erledigt den Job und ist möglicherweise speichereffizienter. Auf der anderen Seite vielleicht nicht. Nasser hat recht, ein explizites Beispiel wäre sinnvoll.
BEARBEITEN: Verwenden von Nassers zufällig generierten Arrays und für len=200 , MaxMemoryUsed[] bedeutet, dass dieses Formular 170 MB benötigt, während das Outer Formular in der Frage 435 MB benötigt.
Mit Ihrem Beispiel list data glaube ich, dass Sie die Möglichkeit finden, Append zu SparseArray ziemlich hilfreich zu finden.
Ich brauche Rest , um den ersten Null-gefüllten Tensor im Ergebnis zu löschen. Das zweite Argument des Seeds SparseArray muss die Dimensionen jedes Ihrer Elemente mit einem Präfix 1 sein. Möglicherweise müssen Sie explizit einen Hintergrund für den Seed SparseArray angeben, um die Leistung zu optimieren.
Tags und Links wolfram-mathematica outer-join sparse-array