Kompres matriks yang jarang

18

Kompres matriks jarang menggunakan baris jarang Terkompresi (format CSR, CRS, atau Yale) .

Ini semua adalah bentuk kompresi yang sama (abaikan Yale baru).

Input mungkin berupa struktur data 2d (daftar daftar, dll): mis

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

Dan outputnya harus tiga struktur data 1d (daftar dll), yang menunjukkan output A, IAdan JA, misalnya

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

Prosesnya dijelaskan oleh wikipedia:

  • Array A memiliki panjang NNZ dan menampung semua entri bukan-nol dari M dalam urutan kiri-ke-kanan atas-ke-bawah ("baris-utama").

  • Array IA memiliki panjang m + 1. Ini didefinisikan oleh definisi rekursif ini:

    • IA [0] = 0 IA [i] = IA [i - 1] + + (jumlah elemen bukan nol pada baris ke-1 (i - 1) dalam matriks asli)

    • Dengan demikian, elemen m pertama dari IA menyimpan indeks menjadi A dari elemen bukan nol pertama di setiap baris M, dan elemen terakhir IA [m] menyimpan NNZ, jumlah elemen dalam A, yang dapat juga dianggap sebagai indeks dalam A dari elemen pertama dari baris phantom tepat di luar ujung matriks M. Nilai-nilai dari baris ke-i dari matriks asli dibaca dari elemen A [IA [i]] ke A [IA [i + 1] - 1] (inklusif pada kedua ujungnya), yaitu dari awal satu baris ke indeks terakhir tepat sebelum awal berikutnya. [5]

    • Array ketiga, JA, berisi indeks kolom dalam M dari setiap elemen A dan karenanya panjang NNZ juga.

Jika bahasa Anda tidak mendukung struktur data aktual, input dan output mungkin berupa teks.

Uji kasus

Input 1: 

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

Output 1:

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

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

Output 2:

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

Input 3:

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

Output 3:

[ ]
[ 0 0 0 0 ]
[ ]

Input 4:

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

Keluaran 4:

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

Input 5: 

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

Output 5:

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

Asumsikan input dapat berisi bilangan real, Anda tidak perlu mempertimbangkan simbol matematika atau representasi eksponensial (mis. 5.000 tidak akan pernah dimasukkan sebagai 5e3). Anda tidak perlu untuk menangani inf, -inf, NaNatau lainnya 'pseudo-nomor'. Anda dapat menampilkan representasi nomor yang berbeda (5.000 dapat berupa output sebagai 5e3 jika Anda memilihnya).

Mencetak:

Ini adalah kode-golf , byte terkecil yang menang.

Papan peringkat

Berikut ini adalah Stack Snippet untuk menghasilkan leaderboard biasa dan gambaran umum pemenang berdasarkan bahasa.

Untuk memastikan bahwa jawaban Anda muncul, silakan mulai jawaban Anda dengan tajuk utama, menggunakan templat Penurunan harga berikut:

# Language Name, N bytes

di mana Nukuran kiriman Anda. Jika Anda meningkatkan skor Anda, Anda dapat menyimpan skor lama di headline, dengan mencoretnya. Contohnya:

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

Jika Anda ingin memasukkan beberapa angka dalam tajuk Anda (mis. Karena skor Anda adalah jumlah dari dua file atau Anda ingin membuat daftar hukuman penterjemah secara terpisah), pastikan bahwa skor sebenarnya adalah angka terakhir di tajuk:

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

Anda juga dapat membuat tautan nama bahasa yang kemudian akan muncul di cuplikan papan peringkat:

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

Tampilkan cuplikan kode

code-golf number array-manipulation matrix Pureferret
sumber
Bisakah indeks berbasis 1 digunakan untuk baris terakhir?
Leo
@ Leo untuk JA? Tidak.
Pureferret
1
Bukankah IA[0] = 0sama sekali tidak perlu? Ini hanya perlu didefinisikan IA[i] = IA[i − 1]..., namun kita dapat dengan mudah menyatakan bahwa jika i-1 < 0menggunakan 0. Artinya, IA [0] selalu sama dengan 0, karenanya dapat dikompresi (ya, saya menyadari bahwa ini adalah kritik terhadap algoritma, bukan tantangan ini).
Draco18s
Akankah kita memiliki tantangan terbalik juga?
Adám
1
Rapi! Tidak pernah mengalami salah satu format sebelumnya, tapi saya senang melihat orang lain melihat itu sebelumnya (saya seharusnya bukan tipe orang yang melihat optimasi sepele dalam algoritma yang lama ini).
Draco18s

Jawaban:

6

MATL , 19 byte

!3#f!Dx0Gg!XsYshDq!

Input digunakan ;sebagai pemisah baris.

Cobalah online! Atau verifikasi semua kasus uji: 1 , 2 , 3 , 4 , 5 .

Penjelasan

!     % 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
sumber
3

Haskell, 87 byte

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

Cobalah online!

Bagaimana itu bekerja:

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
sumber
2

Jelly , 24 byte

n0S€0;;\S€,T€Ẏ$’$
Ẏḟ0W;Ç

Cobalah online!

Erik the Outgolfer
sumber
2

APL (Dyalog) , 31 28 karakter atau 36 33 byte *

Membutuhkan ⎕IO←0pengindeksan berbasis nol. I / O adalah daftar daftar.

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

Cobalah online!

{... } fungsi anonim di mana argumen diwakili oleh ⍵

 (... )(... )(... ) kembalikan daftar tiga hal:

  ⍵≠0 Boolean di mana argumen berbeda dari 0
  ⍸¨ d dari daftar tersebut untuk setiap sub-daftar
  ∊ ϵ nlist (rata) untuk digabungkan menjadi satu daftar

  ⍵~¨0 menghilangkan angka nol dari masing-masing sub-daftar argumen
  d← toko yang sebagai d
  ≢¨  penghitungan masing-masing
  +\ jumlah kumulatif
  0, tambahkan nol

  ∊d ϵ daftar (ratakan) d untuk digabung menjadi satu daftar

  

* Untuk berjalan di Dyalog Classic, cukup ganti ⍸dengan ⎕U2378.

Adm
sumber
Bagus, saya tidak mengerti format inputnya? f 4 4⍴dan kemudian nilainya?
Pureferret
@ Pureferret the Code mendefinisikan fungsi f. Masukan ini benar-benar sebuah REPL, yang menyerukan fhasil 4 4⍴…yang r eshapes data menjadi 4 × 4 matriks.
Adám
1
Rho untuk r eshapes. Saya mengerti!
Pureferret
1
@ Pureferret Saya telah memperbarui Coba online! tautan ke show case yang lebih baik.
Adám
2

PHP , 107 byte

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

Cobalah online!

PHP , 109 byte

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

Cobalah online!

Jörg Hülsermann
sumber
Apakah ini membutuhkan angka untuk menjadi string?
Pureferret
1
@ Pureferret Setiap Input dalam PHP adalah string atau array string. Saya belum memasukkan inputnya jadi jika Anda ingin outputnya murni diganti $x[]=$v dengan$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]

Input adalah array angka 2D dan output array [A, IA, JA].

Dijelaskan

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

Tes

Tampilkan cuplikan kode

Justin Mariner
sumber
1

Python 2 , 115 byte

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

Cobalah online!

Output adalah [A, JA, IA]

ovs
sumber
1

Perl 6 , 84 byte

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

Cobalah online!

Argumen matriks tunggal dalam $_.

  • .flatmap(*.grep(+*)) memilih elemen bukan nol dari seluruh matriks.
  • [\+] .map(+*.grep(+*))adalah pengurangan segitiga dari jumlah elemen di setiap baris (yang disebut beberapa bahasa scan). (0,|...)menambahkan nol ke daftar itu.
  • .flat.kvmenghasilkan daftar semua elemen matriks yang diindeks. .flatmap: { $^a % .[0] xx ?$^b }peta datar di atas modulus setiap indeks dengan jumlah kolom dalam array ( .[0], jumlah elemen di baris pertama), direplikasi oleh elemen itu sendiri, ditafsirkan sebagai boolean. Yaitu, elemen bukan nol direplikasi sekali, dan elemen nol direplikasi nol kali (yaitu, dihapus).
Sean
sumber
1

Python + SciPy, 79 byte

Saya kira built-in tidak dilarang

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

Menerima input dalam format [[0, 0, 0, 0],[5, 8, 0, 0],[0, 0, 3, 0],[0, 6, 0, 0]]

Karl Napf
sumber
1

Japt , 31 27 byte

Mengambil input sebagai array array dan mengembalikan array array.

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

Mengujinya ( -Qmenandai untuk tujuan visualisasi saja)

Penjelasan

Input array secara implisit U.
[[1,1,1],[1,1,1],[1,1,1]]

Uc f

Untuk sub pertama = -array, kami meratakan ( c) Udan kemudian menyaring ( f), menghapus elemen falsey (yaitu, 0s)
[1,1,1,1,1,1,1,1,1]

U®         Ã

Kita akan membangun 2 sub-array lainnya secara bersamaan, dengan memetakan U.

£     Ã

Kami memetakan setiap elemen (sub-array) di U

X©

Xadalah elemen saat ini dari sub-array saat ini dan ©logis AND ( &&) jadi, jika Xtidak benar (bukan nol) bagian selanjutnya tidak akan dieksekusi.

NpY

Di Japt, Nadalah array yang berisi semua input jadi di sini, jika Xbenar, kami mendorong ( p) indeks ( Y) dari elemen saat ini ke N.
[[[1,1,1],[1,1,1],[1,1,1]],0,1,2,0,1,2,0,1,2]

Zè

Kembali ke peta array utama dan, untuk setiap elemen ( Z), kami mendapatkan jumlah elemen dalam sub-array yang benar (bukan nol).
[3,3,3]

å+

Secara kumulatif kurangi larik ini dengan menjumlahkan.
[3,6,9]

iT

Sisipkan ( i) 0 pada indeks 0 untuk menyelesaikan sub-larik kedua.
[0,3,6,9]

NÅ

Untuk sub-array terakhir, kita cukup mengiris Ndari elemen 1.
[0,1,2,0,1,2,0,1,2]

Shaggy
sumber
Saya hanya menjalankan contoh-contoh lain dan berhasil
Pureferret