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
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.