Speicher-effiziente Sortierung auf einer Spalte einer Matrix

Question

Ich habe eine große Matrix und ich möchte sortperm auf jede Spalte dieser Matrix anwenden. Die naive Sache zu tun ist

order = sortperm(X[:,j]) 

, die eine Kopie macht. Das scheint wie eine Schande, so dass ich dachte, ich würde versuchen, eine SubArray:

order = sortperm(sub(X,1:n,j)) 

aber das war noch langsamer. Für ein Lachen habe ich versucht

order = sortperm(1:n,by=i->X[i,j]) 

aber natürlich war das schrecklich. Was ist der schnellste Weg, dies zu tun? Hier

ist einige Benchmark-Code:

getperm1(X,n,j) = sortperm(X[:,j]) 
getperm2(X,n,j) = sortperm(sub(X,1:n,j)) 
getperm3(X,n) = mapslices(sortperm, X, 1) 
n = 1000000 
X = rand(n, 10) 
for f in [getperm1, getperm2] 
    println(f) 
    for it in 1:5 
     gc() 
     @time f(X,n,5) 
    end 
end 
for f in [getperm3] 
    println(f) 
    for it in 1:5 
     gc() 
     @time getperm3(X,n) 
    end 
end 

Ergebnisse:

getperm1 
elapsed time: 0.258576164 seconds (23247944 bytes allocated) 
elapsed time: 0.141448346 seconds (16000208 bytes allocated) 
elapsed time: 0.137306078 seconds (16000208 bytes allocated) 
elapsed time: 0.137385171 seconds (16000208 bytes allocated) 
elapsed time: 0.139137529 seconds (16000208 bytes allocated) 
getperm2 
elapsed time: 0.433251141 seconds (11832620 bytes allocated) 
elapsed time: 0.33970986 seconds (8000624 bytes allocated) 
elapsed time: 0.339840795 seconds (8000624 bytes allocated) 
elapsed time: 0.342436716 seconds (8000624 bytes allocated) 
elapsed time: 0.342867431 seconds (8000624 bytes allocated) 
getperm3 
elapsed time: 1.766020534 seconds (257397404 bytes allocated, 1.55% gc time) 
elapsed time: 1.43763525 seconds (240007488 bytes allocated, 1.85% gc time) 
elapsed time: 1.41373546 seconds (240007488 bytes allocated, 1.82% gc time) 
elapsed time: 1.42215519 seconds (240007488 bytes allocated, 1.83% gc time) 
elapsed time: 1.419174037 seconds (240007488 bytes allocated, 1.83% gc time) 

Wo die mapslices Version 10x die getperm1 Version, wie man erwarten würde.

Es lohnt sich darauf hinzuweisen, dass die Option copy + sortperm auf meiner Maschine nicht viel langsamer ist als nur ein sortperm auf einem Vektor gleicher Länge, aber keine Speicherzuweisung ist notwendig, also wäre es nett um es zu vermeiden.

Answer 1

Sie können die Leistung von Sub-Arrays in einigen sehr speziellen Fällen schlagen (wie eine kontinuierliche Ansicht eines Array nehmen) mit Zeiger Magie:

function colview(X::Matrix,j::Int) 
    n = size(X,1) 
    offset = 1+n*(j-1) # The linear start position 
    checkbounds(X, offset+n-1) 
    pointer_to_array(pointer(X, offset), (n,)) 
end 

getperm4(X,n,j) = sortperm(colview(X,j)) 

Die Funktion colview wird wieder ein vollwertiges Array, dass die Aktien seine Daten mit dem Original X. Beachten Sie, dass dies eine schreckliche Idee ist, da das zurückgegebene Array Daten referenziert, die Julia nur über X verfolgt. Dies bedeutet, dass, wenn X außerhalb des Geltungsbereichs vor der Spalte "view" Datenzugriff mit einem segfault abstürzt.

Mit Ergebnisse:

getperm1 
elapsed time: 0.317923176 seconds (15 MB allocated) 
elapsed time: 0.252215996 seconds (15 MB allocated) 
elapsed time: 0.215124686 seconds (15 MB allocated) 
elapsed time: 0.210062109 seconds (15 MB allocated) 
elapsed time: 0.213339974 seconds (15 MB allocated) 
getperm2 
elapsed time: 0.509172302 seconds (7 MB allocated) 
elapsed time: 0.509961218 seconds (7 MB allocated) 
elapsed time: 0.506399583 seconds (7 MB allocated) 
elapsed time: 0.512562736 seconds (7 MB allocated) 
elapsed time: 0.506199265 seconds (7 MB allocated) 
getperm4 
elapsed time: 0.225968056 seconds (7 MB allocated) 
elapsed time: 0.220587707 seconds (7 MB allocated) 
elapsed time: 0.219854355 seconds (7 MB allocated) 
elapsed time: 0.226289377 seconds (7 MB allocated) 
elapsed time: 0.220391515 seconds (7 MB allocated) 

Ich habe in nicht sieht, warum die Leistung ist mit Subarray schlechter, aber es kann einfach von einem zusätzlichen Pointer-Dereference auf jedem Speicherzugriff sein. Es ist sehr bemerkenswert, wie wenig die Zuteilung tatsächlich in der Zeit kostet - getperm1's Timings sind variabler, aber es schlägt immer noch getperm4! Ich denke, dass dies auf einige zusätzliche Zeiger Mathe in Array interne Implementierung mit gemeinsamen Daten zurückzuführen ist. Es gibt auch ein paar verrückte Caching-Verhalten ... Getperm1 wird deutlich schneller bei wiederholten Läufen.