Kompresuj rzadką matrycę

18

Skompresuj rzadką macierz za pomocą skompresowanego rzadkiego wiersza (format CSR, CRS lub Yale) .

Są to wszystkie te same formy kompresji (zignoruj ​​nowe Yale).

Dane wejściowe mogą być dowolną strukturą danych 2d (lista list itp.): Np

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

I wyjście powinno być trzy 1d struktury danych (lista etc), które oznaczają wyjścia A, IAa JAna przykład

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

Proces jest opisany przez wikipedia:

  • Tablica A ma długość NNZ i przechowuje wszystkie niezerowe wpisy M w kolejności od lewej do prawej od góry do dołu („major-row”).

  • Tablica IA ma długość m + 1. Jest zdefiniowana przez tę rekurencyjną definicję:

    • IA [0] = 0 IA [i] = IA [i - 1] + (liczba niezerowych elementów w (i - 1) -tym rzędzie oryginalnej matrycy)

    • Zatem pierwsze m elementów IA przechowuje indeks w A pierwszego niezerowego elementu w każdym rzędzie M, a ostatni element IA [m] przechowuje NNZ, liczbę elementów w A, którą można również traktować jako indeks w A pierwszego elementu fantomowego rzędu tuż za końcem macierzy M. Wartości i-tego rzędu oryginalnej macierzy odczytywane są z elementów A [IA [i]] do A [IA [i + 1] - 1] (włącznie na obu końcach), tj. Od początku jednego wiersza do ostatniego indeksu tuż przed rozpoczęciem następnego. [5]

    • Trzecia tablica, JA, zawiera indeks kolumny w M każdego elementu A, a zatem ma również długość NNZ.

Jeśli Twój język nie obsługuje faktycznych struktur danych, dane wejściowe i wyjściowe mogą być tekstem.

Przypadki testowe

Wejście 1: 

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

Wyjście 1:

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

Wejście 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]]

Wyjście 2:

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

Wejście 3:

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

Wyjście 3:

[ ]
[ 0 0 0 0 ]
[ ]

Wejście 4:

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

Wyjście 4:

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

Wejście 5: 

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

Wyjście 5:

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

Załóżmy, że dane wejściowe mogą zawierać dowolną liczbę rzeczywistą, nie trzeba brać pod uwagę symboli matematycznych lub wykładniczej reprezentacji (np. 5000 nigdy nie zostanie wpisane jako 5e3). Nie trzeba będzie obsłużyć inf, -inf, NaNlub jakieś inne „pseudo-numbers”. Możesz podać inną reprezentację liczby (5000 może być wyprowadzone jako 5e3, jeśli tak wybierzesz).

Punktacja:

Jest to kod-golf , najmniejsza bajty wygrywa.

Liderów

Oto fragment kodu, który pozwala wygenerować zarówno zwykłą tabelę wyników, jak i przegląd zwycięzców według języka.

Aby upewnić się, że twoja odpowiedź się pojawi, zacznij od nagłówka, korzystając z następującego szablonu Markdown:

# Language Name, N bytes

gdzie Njest rozmiar twojego zgłoszenia. Jeśli poprawić swój wynik, to może zachować stare porachunki w nagłówku, uderzając je przez. Na przykład:

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

Jeśli chcesz umieścić w nagłówku wiele liczb (np. Ponieważ twój wynik jest sumą dwóch plików lub chcesz osobno wymienić kary za flagi tłumacza), upewnij się, że rzeczywisty wynik jest ostatnią liczbą w nagłówku:

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

Możesz także ustawić nazwę języka jako link, który pojawi się we fragmencie tabeli wyników:

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

Pokaż fragment kodu

code-golf number array-manipulation matrix Pureferret
źródło
Czy dla ostatniego rzędu można zastosować indeksy oparte na 1?
Leo
@Leo dla JA? Nie.
Pureferret,
1
Czy nie jest IA[0] = 0całkowicie niepotrzebne? Trzeba tylko zdefiniować IA[i] = IA[i − 1]..., ale moglibyśmy po prostu stwierdzić, że jeśli i-1 < 0użyjemy 0. Oznacza to, że IA [0] jest zawsze równe 0, dlatego można go skompresować (tak, zdaję sobie sprawę, że jest to krytyka algorytmu, nie to wyzwanie).
Draco18s nie ufa już SE 5'17
Czy będziemy mieli również odwrotne wyzwanie?
Adám
1
Schludny! Nie miałem wcześniej żadnego z tych formatów, ale cieszę się, że ktoś widział to wcześniej (nie powinienem być osobą, która dostrzega trywialne optymalizacje w tak starych algorytmach).
Draco18s nie ufa już

Odpowiedzi:

6

MATL , 19 bajtów

!3#f!Dx0Gg!XsYshDq!

Dane wejściowe są używane ;jako separator wierszy.

Wypróbuj online! Lub sprawdź wszystkie przypadki testowe: 1 , 2 , 3 , 4 , 5 .

Wyjaśnienie

!     % 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
źródło
3

Haskell, 87 bajtów

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

Wypróbuj online!

Jak to działa:

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
źródło
2

APL (Dyalog) , 31 28 znaków lub 36 33 bajtów *

Wymaga ⎕IO←0indeksowania zerowego. I / O to lista list.

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

Wypróbuj online!

{… } Anonimowa funkcja, w której argument jest reprezentowany przez ⍵

 (... )(... )(... ) zwróci listę trzech rzeczy:

  ⍵≠0 Boolean, w którym argument różni się od 0
  ⍸¨ d ndices tych dla każdej podlisty
  ∊ ϵ nlist (spłaszcz), aby połączyć w jedną listę

  ⍵~¨0 usunięcie zera z każdego podmenu argumentu
  d← sklepie, a d
  ≢¨  zgadzają każdy
  +\ skumulowana suma
  0, przedrostek zera

  ∊d ε nlist (spłaszczyć) d połączyć w pojedynczej liście

  

* Aby uruchomić w Dyalog Classic, po prostu zastąpić ⍸z ⎕U2378.

Adám
źródło
Fajnie, ale nie rozumiem formatu wejściowego? f 4 4⍴a następnie wartości?
Pureferret,
@Pureferret Kod definiuje funkcję f. Wejście jest naprawdę REPL, który wywołuje fw wyniku 4 4⍴…której R eshapes danych do 4 x 4 matrycy.
Adám
1
Rho dla r eshapes. Rozumiem!
Pureferret,
1
@Pureferret Zaktualizowałem wersję Wypróbuj online! link do lepszego pokazania przypadków testowych.
Adám
2

PHP , 107 bajtów

<?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);

Wypróbuj online!

PHP , 109 bajtów

<?$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);

Wypróbuj online!

Jörg Hülsermann
źródło
Czy to wymaga ciągów liczb?
Pureferret,
1
@Pureferret Wszelkie dane wejściowe w PHP to ciąg znaków lub tablica ciągów znaków. Nie lanego wejście więc jeśli chcesz, że wyjście jest czysto int zastąpić $x[]=$v z$x[]=+$v
Jörg Hülsermann
2

JavaScript (ES6), 117 bajtów

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]

Dane wejściowe to tablica liczb 2D, a dane wyjściowe to tablica [A, IA, JA].

Wyjaśniono

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

Testy

Pokaż fragment kodu

Justin Mariner
źródło
1

Python 2 , 115 bajtów

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])]

Wypróbuj online!

Dane wyjściowe to [A, JA, IA]

ovs
źródło
1

Perl 6 , 84 bajtów

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

Wypróbuj online!

Argument pojedynczej macierzy jest w $_.

  • .flatmap(*.grep(+*)) wybiera niezerowe elementy całej macierzy.
  • [\+] .map(+*.grep(+*))to trójkątna redukcja liczby elementów w każdym rzędzie (którą nazywają niektóre języki scan). (0,|...)wstawia zero na tę listę.
  • .flat.kvtworzy indeksowaną listę wszystkich elementów macierzy. .flatmap: { $^a % .[0] xx ?$^b }płaskie mapy nad modułem każdego indeksu według liczby kolumn w tablicy ( .[0]liczba elementów w pierwszym rzędzie), zreplikowanych przez sam element, interpretowanych jako wartość logiczna. Oznacza to, że niezerowe elementy są replikowane jeden raz, a elementy zerowe są replikowane zero razy (tj. Usuwane).
Sean
źródło
1

Python + SciPy, 79 bajtów

Myślę, że wbudowane nie były zabronione

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

Akceptuje dane wejściowe w formacie [[0, 0, 0, 0],[5, 8, 0, 0],[0, 0, 3, 0],[0, 6, 0, 0]]

Karl Napf
źródło
1

Japt , 31 27 bajtów

Pobiera dane wejściowe jako tablicę tablic i zwraca tablicę tablic.

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

Przetestuj ( -Qflaga tylko do celów wizualizacji)

Wyjaśnienie

Domniemane wejście tablicy U.
[[1,1,1],[1,1,1],[1,1,1]]

Uc f

Dla pierwszego sub = -array spłaszczamy ( c), Ua następnie filtrujemy ( f), usuwając wszelkie elementy falsey (tj. 0s)
[1,1,1,1,1,1,1,1,1]

U®         Ã

Zamierzamy zbudować pozostałe 2 pod-tablice w tym samym czasie, odwzorowując U.

£     Ã

Mapujemy każdy element (pod-tablicę) w U

X©

Xjest bieżącym elementem bieżącej podtablicy i ©jest logiczne AND ( &&), więc jeśli Xnie jest to prawda (nie zero), następna część nie zostanie wykonana.

NpY

W Japt Njest tablica zawierająca wszystkie dane wejściowe, więc tutaj, jeśli Xto prawda, wypychamy ( p) indeks ( Y) bieżącego elementu do N.
[[[1,1,1],[1,1,1],[1,1,1]],0,1,2,0,1,2,0,1,2]

Zè

Wracając do mapy głównej tablicy i dla każdego elementu ( Z) otrzymujemy liczbę elementów w tej pod-tablicy, które są prawdziwe (nie zero).
[3,3,3]

å+

Łącznie zmniejsz tę tablicę, sumując.
[3,6,9]

iT

Wstaw ( i) 0 o indeksie 0, aby uzupełnić drugą pod-macierz.
[0,3,6,9]

NÅ

W końcowej pod-macierzy po prostu wycinamy Npierwszy element.
[0,1,2,0,1,2,0,1,2]

Kudłaty
źródło
Po prostu
przejrzałem