Verändert die Vektorisierung die Komplexität?

Ich schrieb einen Code in MATLAB mit der Komplexität O (n^3). Ich entfernte eine der Schleifen und verwendete stattdessen die vektorisierte Form. Als Ergebnis verringerte sich die Laufzeit. Ich verstehe im Allgemeinen die Vektorisierung verbessert die Leistung. Ich bin mir nicht sicher, dass ich angenommen habe, dass die Vektorisierung die Komplexität nicht ändert.Verändert die Vektorisierung die Komplexität?

Ich habe einige Experimente wie folgt:

Als ich die Eingangsgröße um den Faktor 2, um die Laufzeit um etwa einen Faktor von 2,5 (I um etwa den Faktor 8 erwartet) erhöht erhöht.

Jetzt bin ich nicht sicher, ob meine anfängliche Annahme (die die Vektorisierung nicht die Komplexität ändert.) Gültig ist. Hat jemand einen Einblick?

Vielen Dank.

Quelle

2016-10-12 Crimson

Es hängt von der Funktion ab, die Sie verwenden. Zum Beispiel erhöht die Verwendung einer Funktion wie 'bsxfun' die Geschwindigkeit, während es nur eine' for-Schleife' ist, die als 'C++'/'mex'-Datei geschrieben ist. In solchen Fällen glaube ich nicht, dass die Vektorisierung des Codes die Komplexität verändert. – NKN

Danke für Ihre Einsicht. Weißt du, warum die Laufzeit nicht proportional erhöht wird (wenn die Eingabegröße zunimmt)? Als ich für for-Schleife verwendete, war es nahe der erwarteten Zunahme, aber als ich vektorisierte, war es nicht nah. Ich habe MATLAB benutzt. Ich gab nur einen Bereich zum Index (anstatt Spalte) und entfernen Sie die for-Schleife. Http://www.mathworks.com/help/matlab/matlab_prog/vectorization.html – Crimson

@ Crimson Well mit vektorisierten Ansätze, Sie verarbeiten mehr Daten pro Zeitperiode, so gibt es viel mehr Datenübertragungen, die von der Speicherbandbreite, etc. beeinflusst werden können. Also, ich denke nicht, dass es eine lineare Skala wäre. Vectorisierung vs Performance vs Memory ist ein einzigartiges Spiel. Ich bin mit den Komplexitätsdefinitionen allerdings nicht so vertraut. – Divakar

In der sehr allgemeinen Weise denke ich, der Unterschied ist tatsächlich Durchsatz (Latenz) vs Anzahl der Operationen (Komplexität). Wenn Sie einen sehr dedizierten ASIC for you-Algorithmus erstellen würden, müssten Sie n^3 Operationen ausführen. Durch das Vektorisieren sagen Sie, dass einige dieser Operationen unabhängig voneinander parallel ausgeführt werden können. Matlab und aktuelle Prozessoren sind schlauer und können bestimmte Operationen parallel ausführen, z. ein 64-Bit-Prozessor könnte 2-32bit-Summierungen 4-16bit usw.

Denken Sie an zwei Algorithmen sowohl in O (n^3), a, wo jede Operation vollständig unabhängig durchgeführt werden muss (Sie können diesen Algorithmus Vektorisierung) und b das andere, wo sie Serien sein müssen (Sie können es nicht vektorisieren). Spezielle Hardware für jede von diesen würde beide Operationen erfordern. Durch die Verwendung von mehr Hardware/Gates für ein können Sie die Aufgabe in so schnell wie 1 Taktzyklus, während für b mehr Hardware/Gates hilft Ihnen nicht und die Aufgabe dauert n^3 Taktzyklus.

EDIT:

Einige Code die Vektorisierung Geschwindigkeit zu veranschaulichen, obwohl die Komplexität (#operation) erhöhen würde nicht

clear variable; 

Iterations = 100; 
n = 2^20; 
a = randi(100,[1,n]); 
b = randi(100,[1,n]); 

profile on; 
for loop=1:Iterations 
    % Full vector approach 
    vector = a*b.'; 

    % Partial vector approach 
    vector2 = sum(a.*b); 

    % Direct mathematical approach 
    serial = 0; 
    for id=1:n 
     serial = serial + a(id)*b(id); 
    end 
end 
profile viewer;

jetzt hat technisch Matlab einigen zusätzlichen Aufwand pro Betrieb wie Überprüfen, ob die Operation Sinn macht usw., wodurch die for-Schleife erheblich verlangsamt wird. Aber im Allgemeinen ist dies nur ein Beispiel, um einen Trend zu veranschaulichen.

Quelle

2016-10-12 20:36:40 mpaskov

mit dieser Erklärung, wenn ich nicht missverstanden werde, wird die Komplexität abnehmen, da die meisten parallelen Versionen eines Algorithmus weniger komplex sind. – Crimson

Danke für Ihre Antwort. Mit Ihrer Erklärung, wenn ich nicht missverstanden werde, wird die Komplexität abnehmen (da die parallele Version eines Algorithmus normalerweise weniger komplex ist). Im Handbuch zur Vektorisierung habe ich keine Erklärung dafür gesehen, wie man es parallel macht. – Crimson

Die Komplexität bleibt meist gleich, immer noch in O (n^3), aber vielleicht auch mit anderen Vorfaktoren wie bei Andras. Was sich ändern wird ist, dass einige Operationen parallel ausgeführt werden, wodurch die Zeit für die Antwort verringert wird. Wenn es um die Vektorisierung der Komplexität geht, impliziert dies parallele Operationen. Im Allgemeinen bedeutet "Zeit" nicht notwendigerweise Komplexität, sondern eher die Ursache. Besonders mit MATLAB. – mpaskov

Verändert die Vektorisierung die Komplexität?

Antwort

Verwandte Themen