Komprimiere eine dünne Matrix

18

Komprimieren Sie eine Sparse-Matrix mit Compressed Sparse Row (CSR-, CRS- oder Yale-Format) .

Hierbei handelt es sich alle um dieselbe Form der Komprimierung (ignorieren Sie New Yale).

Die Eingabe kann eine beliebige 2D-Datenstruktur sein (Liste der Listen usw.): z

[[0 0 0 0],
 [5 8 0 0],
 [0 0 3 0],
 [0 6 0 0]]

Und die Ausgabe sollte drei 1d Datenstrukturen (Liste usw.) sein, dass die Ausgänge bezeichnen A, IAund JAzum Beispiel

[5, 8, 3, 6]
[0, 0, 2, 3, 4]
[0, 1, 2, 1,]

Der Prozess wird von Wikipedia beschrieben:

  • Das Array A hat die Länge NNZ und enthält alle Nicht-Null-Einträge von M in der Reihenfolge von links nach rechts von oben nach unten ("Zeilenmajor").

  • Das Array IA hat die Länge m + 1. Es wird durch diese rekursive Definition definiert:

    • IA [0] = 0 IA [i] = IA [i - 1] + (Anzahl der Nicht-Null-Elemente in der (i - 1) -ten Zeile in der ursprünglichen Matrix)

    • Somit speichern die ersten m Elemente von IA den Index in A des ersten Nicht-Null-Elements in jeder Reihe von M, und das letzte Element IA [m] speichert NNZ, die Anzahl der Elemente in A, die auch als das Element A angesehen werden kann Index in A des ersten Elements einer Phantomzeile direkt hinter dem Ende der Matrix M. Die Werte der i-ten Zeile der ursprünglichen Matrix werden aus den Elementen A [IA [i]] bis A [IA [i + gelesen 1] - 1] (einschließlich an beiden Enden), dh vom Beginn einer Zeile bis zum letzten Index kurz vor dem Beginn der nächsten. [5]

    • Das dritte Array JA enthält den Spaltenindex in M ​​jedes Elements von A und hat daher auch die Länge NNZ.

Wenn Ihre Sprache keine tatsächlichen Datenstrukturen unterstützt, können Ein- und Ausgaben Text sein.

Testfälle

Eingang 1: 

[[0 0 0 0],
 [5 8 0 0],
 [0 0 3 0],
 [0 6 0 0]]

Ausgang 1:

[ 5, 8, 3, 6 ]
[ 0, 0, 2, 3, 4 ]
[ 0, 1, 2, 1, ]

Eingang 2

[[10 20 0 0 0 0],
 [0 30 0 40 0 0],
 [0 0 50 60 70 0],
 [0 0 0 0 0 80]]

Ausgang 2:

[ 10 20 30 40 50 60 70 80 ]
[  0  2  4  7  8 ]
[  0  1  1  3  2  3  4  5 ]

Eingang 3:

[[0 0 0],
 [0 0 0],
 [0 0 0]]

Ausgang 3:

[ ]
[ 0 0 0 0 ]
[ ]

Eingang 4:

[[1 1 1],
 [1 1 1],
 [1 1 1]]

Ausgang 4:

[ 1 1 1 1 1 1 1 1 1 ]
[ 0 3 6 9 ]
[ 0 1 2 0 1 2 0 1 2 ]

Eingang 5: 

[[0 0 0 0],
 [5 -9 0 0],
 [0 0 0.3 0],
 [0 -400 0 0]]

Ausgang 5:

[ 5, -9, 0.3, -400 ]
[ 0, 0, 2, 3, 4 ]
[ 0, 1, 2, 1, ]

Angenommen, Eingaben können eine reelle Zahl enthalten, Sie müssen keine mathematischen Symbole oder Exponentialdarstellungen berücksichtigen (z. B. werden 5.000 niemals als 5e3 eingegeben). Sie werden nicht behandeln müssen inf, -inf, NaNoder andere ‚pseudo-Zahlen‘. Sie können eine andere Darstellung der Zahl ausgeben (5.000 können als 5e3 ausgegeben werden, wenn Sie dies wünschen).

Wertung:

Dies ist ein Code-Golf , der mit den wenigsten Bytes gewinnt.

Bestenlisten

Hier ist ein Stack-Snippet, um sowohl eine reguläre Rangliste als auch eine Übersicht der Gewinner nach Sprache zu generieren.

Um sicherzustellen, dass Ihre Antwort angezeigt wird, beginnen Sie Ihre Antwort mit einer Überschrift. Verwenden Sie dazu die folgende Markdown-Vorlage:

# Language Name, N bytes

Wo Nist die Größe Ihres Beitrags? Wenn Sie Ihren Score zu verbessern, Sie können alte Rechnungen in der Überschrift halten, indem man sich durch das Anschlagen. Zum Beispiel:

# Ruby, <s>104</s> <s>101</s> 96 bytes

Wenn Sie mehrere Zahlen in Ihre Kopfzeile aufnehmen möchten (z. B. weil Ihre Punktzahl die Summe von zwei Dateien ist oder wenn Sie die Strafen für Interpreter-Flags separat auflisten möchten), stellen Sie sicher, dass die tatsächliche Punktzahl die letzte Zahl in der Kopfzeile ist:

# Perl, 43 + 2 (-p flag) = 45 bytes

Sie können den Namen der Sprache auch als Link festlegen, der dann im Leaderboard-Snippet angezeigt wird:

# [><>](http://esolangs.org/wiki/Fish), 121 bytes

Code-Snippet anzeigen

code-golf number array-manipulation matrix Pureferret
quelle
Könnten 1-basierte Indizes für die letzte Zeile verwendet werden?
Leo
@Leo für JA? Nein
Pureferret
1
Ist das nicht IA[0] = 0völlig unnötig? Es muss nur definiert werden IA[i] = IA[i − 1]..., aber wir können einfach angeben, dass, wenn i-1 < 00 verwendet wird, IA [0] immer gleich 0 ist, daher kann es komprimiert werden (ja, ich erkenne, dass dies eine Kritik des Algorithmus ist, nicht diese Herausforderung).
Draco18s
Werden wir auch die umgekehrte Herausforderung haben?
Adám
1
Ordentlich! Hatte noch nie eines dieser Formate gesehen, aber ich bin froh zu sehen, dass das schon jemand anderes gesehen hat (ich sollte nicht die Art von Person sein, die triviale Optimierungen in so alten Algorithmen entdeckt).
Draco18s

Antworten:

6

MATL , 19 Bytes

!3#f!Dx0Gg!XsYshDq!

Eingabe dient ;als Zeilentrennzeichen.

Probieren Sie es online! Oder überprüfen Sie alle Testfälle: 1 , 2 , 3 , 4 , 5 .

Erläuterung

!     % Implicit input. Transpose
3#f   % 3-output version of find: it takes all nonzero values and pushes
      % their column indices, row indices, and values, as column vectors
!     % Transpose into a row vector
D     % Display (and pop) vector of values
x     % Delete vector of row values
0     % Push 0
G     % Push input
g     % Convert to logical: nonzeros become 1
!     % Transpose
Xs    % Sum of columns. Gives a row vector
Ys    % Cumulative sum
h     % Prepend the 0 that's below on the stack
D     % Display (and pop) that vector
q     % Subtract 1 from the vector of row indices
!     % Transpose into a row vector. Implicitly display
Luis Mendo
quelle
3

Haskell, 87 Bytes

f s|a<-filter(/=0)<$>s=(id=<<a,scanl(+)0$length<$>a,s>>= \t->[i|(i,e)<-zip[0..]t,e/=0])

Probieren Sie es online!

Wie es funktioniert:

a<-filter(/=0)<$>s           -- let a be the list of lists with all 0 removed]
                             -- e.g. [[1,0,0],[0,3,4]] -> [[1],[3,4]]

                             -- return a triple of

id=<<a                       -- a concatenated into a single list -> A 

scanl(+)0$length<$>a         -- partial sums of the length of the sublists of a
                             -- strating with an additional 0 -> IA

s>>=                         -- map the lambda over the sublists of s and concatenate
                             -- into a single list
   \t->[i|(i,e)<-zip[0..]t,e/=0]  -- the indices of the non-zero elements -> JA
nimi
quelle
2

APL (Dyalog) , 31 28 Zeichen oder 36 33 Byte *

Erfordert eine nullbasierte ⎕IO←0Indizierung. I / O ist eine Liste von Listen.

{(∊d)(0,+\≢¨d←⍵~¨0)(∊⍸¨⍵≠0)}

Probieren Sie es online!

{… } Anonyme Funktion, bei der das Argument durch ⍵ dargestellt wird

 (... )(... )(... ) eine Liste von drei Dingen:

  ⍵≠0 Boolean , wo die Argumentation unterscheidet sich von 0
  ⍸¨ ɩ ndices von denen für jede Unterliste
  ∊ ε nlist (Flatten) in einzelne Liste kombinieren

  ⍵~¨0 Entfernen Nullen von jeder Unterliste des Arguments
  d← speichern , die als d
  ≢¨  jeweils tally
  +\ kumulative Summe
  0, eine Null voranstellen

  ∊d ϵ nlist (Abflachen) d , um eine einzelne Liste zu erstellen

  

* Um in Dyalog klassisch laufen, einfach ersetzen ⍸mit ⎕U2378.

Adam
quelle
Schön, ich verstehe das Eingabeformat aber nicht? f 4 4⍴und dann die werte?
Pureferret
@Pureferret der Code definiert die Funktion f. Der Eingang ist wirklich ein REPL, die Anrufe fauf dem Ergebnis 4 4⍴…die r die Daten in eine 4 × 4 - Matrix eshapes.
Adám
1
Rho for r eshapes. Ich verstehe es!
Pureferret
1
@Pureferret Ich habe den Online- Test aktualisiert ! Link zur besseren Darstellung von Testfällen.
Adám
2

PHP , 107 Bytes

<?for($y=[$c=0];$r=$_GET[+$l++];)foreach($r as$k=>$v)!$v?:[$x[]=$v,$z[]=$k,$y[$l]=++$c];var_dump($x,$y,$z);

Probieren Sie es online!

PHP , 109 Bytes

<?$y=[$c=0];foreach($_GET as$r){foreach($r as$k=>$v)if($v){$x[]=$v;$z[]=$k;$c++;}$y[]=$c;}var_dump($x,$y,$z);

Probieren Sie es online!

Jörg Hülsermann
quelle
Müssen die Zahlen Zeichenketten sein?
Pureferret
1
@Pureferret Jede Eingabe in PHP ist eine Zeichenfolge oder ein Array von Zeichenfolgen. Ich habe nicht den Eingang gegossen so , wenn Sie möchten , dass die Ausgabe rein int zu ersetzen ist $x[]=$v mit$x[]=+$v
Jörg Hülsermann
2

JavaScript (ES6), 117 Byte

a=>[a.map((b,i)=>(b=b.filter((x,c)=>x&&o.push(c)),m[i+1]=m[i]+b.length,b),m=[0],o=[]).reduce((x,y)=>x.concat(y)),m,o]

Eingabe ist ein 2D-Array von Zahlen und Ausgabe ist ein Array von [A, IA, JA].

Erklärt

a=>[
    a.map((b,i) => (                                // map each matrix row
            b = b.filter((x,c) => x                 // filter to only non-zero elements
                && o.push(c)                        // and add this index to JA
            )
            m[i+1] = m[i] + b.length,               // set next value of IA
            b                                       // and return filtered row
        ),
        m=[0],o=[]                          // initialize IA (m) and JA (o)
    ).reduce((x,y) => x.concat(y)),                 // flatten the non-zero matrix
m,o]                                                // append IA and JA

Tests

Code-Snippet anzeigen

Justin Mariner
quelle
1

Python 2 , 115 Bytes

lambda m:zip(*[[v,i]for k in m for i,v in enumerate(k)if v])+[reduce(lambda a,b:a+[len(b)-b.count(0)+a[-1]],m,[0])]

Probieren Sie es online!

Ausgabe ist [A, JA, IA]

ovs
quelle
1

Perl 6 , 84 Bytes

{.flatmap(*.grep(+*)),(0,|[\+] .map(+*.grep(+*))),.flat.kv.flatmap:{$^a%.[0]xx?$^b}}

Probieren Sie es online!

Das Einmatrixargument ist in $_.

  • .flatmap(*.grep(+*)) Wählt die Nicht-Null-Elemente der gesamten Matrix aus.
  • [\+] .map(+*.grep(+*))ist die dreieckige Reduzierung der Anzahl der Elemente in jeder Zeile (die einige Sprachen nennen scan). (0,|...)Stellt dieser Liste eine Null voran.
  • .flat.kvErzeugt eine indizierte Liste aller Elemente der Matrix. .flatmap: { $^a % .[0] xx ?$^b }Flatmaps über den Modul jedes Indexes durch die Anzahl der Spalten im Array ( .[0]die Anzahl der Elemente in der ersten Zeile), die vom Element selbst repliziert und als Boolescher Wert interpretiert werden. Das heißt, Elemente ungleich Null werden einmal repliziert, und Elemente ungleich Null werden nullmal repliziert (dh entfernt).
Sean
quelle
1

Python + SciPy, 79 Bytes

ich denke, eingebaute waren nicht verboten

from scipy.sparse import*
A=csr_matrix(input())
print A.data,A.indptr,A.indices

Akzeptiert Eingaben im Format [[0, 0, 0, 0],[5, 8, 0, 0],[0, 0, 3, 0],[0, 6, 0, 0]]

Karl Napf
quelle
1

Japt , 31 27 Bytes

Nimmt Eingaben als Array von Arrays und gibt ein Array von Arrays zurück.

[Uc f U®£X©NpYÃZèÃå+ iT NÅ]

Test it ( -QFlag nur zu Visualisierungszwecken)

Erläuterung

Implizite Eingabe eines Arrays U.
[[1,1,1],[1,1,1],[1,1,1]]

Uc f

Für das erste sub = -Array wird es abgeflacht ( c) Uund dann gefiltert ( f), wobei alle falschen Elemente (dh Nullen) entfernt werden.
[1,1,1,1,1,1,1,1,1]

U®         Ã

Wir werden die anderen 2 Sub-Arrays gleichzeitig erstellen, indem wir sie überlagern U.

£     Ã

Wir bilden jedes Element (Subarray) in ab U

X©

Xist das aktuelle Element des aktuellen Sub-Arrays und ©ist logisch AND ( &&). Wenn dies Xnicht der Fall ist (nicht Null), wird der nächste Teil nicht ausgeführt.

NpY

In Japt gibt Nes ein Array, das alle Eingaben enthält. Wenn dies der XFall ist, verschieben wir ( p) den Index ( Y) des aktuellen Elements nach N.
[[[1,1,1],[1,1,1],[1,1,1]],0,1,2,0,1,2,0,1,2]

Zè

Zurück zur Karte des Hauptarrays und für jedes Element ( Z) erhalten wir die Anzahl der Elemente in diesem Unterarray, die wahr sind (nicht Null).
[3,3,3]

å+

Reduzieren Sie dieses Array kumulativ durch Summieren.
[3,6,9]

iT

Fügen Sie ( i) 0 am Index 0 ein, um das zweite Unterarray zu vervollständigen.
[0,3,6,9]

NÅ

Für das letzte Unterarray schneiden wir einfach Nvom 1. Element.
[0,1,2,0,1,2,0,1,2]

Zottelig
quelle
Ich habe nur die anderen Beispiele ausgeführt und es funktioniert
Pureferret