Comprimir uma matriz esparsa

18

Comprima uma matriz esparsa usando a linha esparsa compactada (formato CSR, CRS ou Yale) .

Essas são todas as mesmas formas de compactação (ignore a nova Yale).

A entrada pode ser qualquer estrutura de dados 2D (lista de listas, etc.): por exemplo

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

E a saída deverá ser de três estruturas de dados (lista 1d etc), que denotam as saídas A, IAe JA, por exemplo

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

O processo é descrito pela wikipedia:

  • A matriz A tem o comprimento NNZ e mantém todas as entradas diferentes de zero de M na ordem da esquerda para a direita, de cima para baixo ("linha principal").

  • A matriz IA é de comprimento m + 1. É definida por esta definição recursiva:

    • IA [0] = 0 IA [i] = IA [i - 1] + (número de elementos diferentes de zero na (i - 1) -a linha na matriz original)

    • Assim, os primeiros m elementos de IA armazenam o índice em A do primeiro elemento diferente de zero em cada linha de M, e o último elemento IA [m] armazena NNZ, o número de elementos em A, que também pode ser considerado o índice em A do primeiro elemento de uma linha fantasma logo após o final da matriz M. Os valores da i-ésima linha da matriz original são lidos a partir dos elementos A [IA [i]] a A [IA [i + 1] - 1] (inclusive nos dois extremos), ou seja, do início de uma linha ao último índice, pouco antes do início da próxima. [5]

    • A terceira matriz, JA, contém o índice da coluna em M de cada elemento de A e, portanto, também é de comprimento NNZ.

Se o seu idioma não suportar estruturas de dados reais, entrada e saída podem ser texto.

Casos de teste

Entrada 1: 

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

Saída 1:

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

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

Saída 2:

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

Entrada 3:

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

Saída 3:

[ ]
[ 0 0 0 0 ]
[ ]

Entrada 4:

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

Saída 4:

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

Entrada 5: 

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

Saída 5:

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

Suponha que as entradas possam conter qualquer número real; você não precisa considerar símbolos matemáticos ou representação exponencial (por exemplo, 5.000 nunca serão inseridos como 5e3). Você não vai precisar para lidar com inf, -inf, NaNou quaisquer outros 'pseudo-números'. Você pode emitir uma representação diferente do número (5.000 pode ser emitido como 5e3, se assim desejar).

Pontuação:

Este é um código-golfe , o menor número de bytes vence.

Classificação

Aqui está um snippet de pilha para gerar uma classificação regular e uma visão geral dos vencedores por idioma.

Para garantir que sua resposta seja exibida, inicie-a com um título, usando o seguinte modelo de remarcação:

# Language Name, N bytes

onde Nestá o tamanho do seu envio. Se você melhorar sua pontuação, poderá manter as pontuações antigas no título, identificando-as. Por exemplo:

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

Se você quiser incluir vários números no cabeçalho (por exemplo, porque sua pontuação é a soma de dois arquivos ou você deseja listar as penalidades do sinalizador de intérpretes separadamente), verifique se a pontuação real é o último número no cabeçalho:

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

Você também pode transformar o nome do idioma em um link que será exibido no snippet da tabela de classificação:

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

Mostrar snippet de código

code-golf number array-manipulation matrix Pureferret
fonte
Os índices baseados em 1 poderiam ser usados ​​para a última linha?
Leo
@ Leo para JA? Não.
Pureferret 5/07
1
Não é IA[0] = 0completamente desnecessário? É apenas necessário definir IA[i] = IA[i − 1]..., mas poderíamos simplesmente afirmar que, se i-1 < 0usar 0. Ou seja, IA [0] é sempre igual a 0, portanto, pode ser compactado (sim, eu percebo que isso é uma crítica ao algoritmo, não esse desafio).
precisa saber é o seguinte
Teremos também o desafio inverso?
Adám
1
Arrumado! Não havia encontrado nenhum dos formatos antes, mas fico feliz em ver que alguém já viu isso antes (eu não deveria ser o tipo de pessoa que identifica otimizações triviais em algoritmos tão antigos).
Draco18s

Respostas:

6

MATL , 19 bytes

!3#f!Dx0Gg!XsYshDq!

A entrada é usada ;como separador de linhas.

Experimente online! Ou verifique todos os casos de teste: 1 , 2 , 3 , 4 , 5 .

Explicação

!     % 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
fonte
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])

Experimente online!

Como funciona:

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

APL (Dyalog) , 31 28 caracteres ou 36 33 bytes *

Requer ⎕IO←0indexação baseada em zero. E / S é uma lista de listas.

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

Experimente online!

{… } Função anônima em que o argumento é representado por ⍵

 (... )(... )(... ) retornar uma lista de três coisas:

  ⍵≠0 Booleano onde o argumento difere de 0
  ⍸¨ d ndices daqueles para cada sublist
  ∊ ϵ nlist (flatten) para combinar em uma lista única

  ⍵~¨0 remover zeros de cada sub-lista de argumento a
  d← loja que como d
  ≢¨  contagem cada
  +\ soma cumulativa
  0, preceder um zero

  ∊d ε nlist (flatten) d para combinar em lista única

  

* Para executar no Dyalog Classic, basta substituir ⍸por ⎕U2378.

Adão
fonte
Bom, eu não entendo o formato de entrada? f 4 4⍴e então os valores?
Pureferret 5/07
@Pureferret o código define a função f. A entrada é realmente um REPL, que chama fsobre o resultado de 4 4⍴…que r eshapes os dados em uma matriz 4 × 4.
Adám
1
Rho para r eshapes. Entendi!
Pureferret 5/07
1
@Pureferret Atualizei o Experimente online! link para mostrar melhor os casos de teste.
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);

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

Experimente online!

Jörg Hülsermann
fonte
Isso precisa que os números sejam cadeias de caracteres?
Pureferret 5/07
1
@Pureferret Qualquer entrada no PHP é uma string ou uma matriz de strings. Eu não projetei a entrada, portanto, se você deseja que a saída seja puramente int, substitua-a $x[]=$v por$x[]=+$v
Jörg Hülsermann
2

JavaScript (ES6), 117 bytes

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]

A entrada é uma matriz 2D de números e a saída é uma matriz de [A, IA, JA].

Explicado

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

Testes

Mostrar snippet de código

Justin Mariner
fonte
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])]

Experimente online!

Saída é [A, JA, IA]

ovs
fonte
1

Perl 6 , 84 bytes

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

Experimente online!

O argumento de matriz única está em $_.

  • .flatmap(*.grep(+*)) seleciona os elementos diferentes de zero de toda a matriz.
  • [\+] .map(+*.grep(+*))é a redução triangular do número de elementos em cada linha (que alguns idiomas chamam scan). (0,|...)acrescenta um zero a essa lista.
  • .flat.kvproduz uma lista indexada de todos os elementos da matriz. .flatmap: { $^a % .[0] xx ?$^b }mapeia o módulo de cada índice pelo número de colunas na matriz ( .[0]o número de elementos na primeira linha), replicado pelo próprio elemento, interpretado como booleano. Ou seja, elementos diferentes de zero são replicados uma vez e zero elementos são replicados zero vezes (ou seja, removidos).
Sean
fonte
1

Python + SciPy, 79 bytes

Eu acho que embutidos não eram proibidos

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

Aceita entrada no formato [[0, 0, 0, 0],[5, 8, 0, 0],[0, 0, 3, 0],[0, 6, 0, 0]]

Karl Napf
fonte
1

Japonês , 31 27 bytes

Recebe a entrada como uma matriz de matrizes e retorna uma matriz de matrizes.

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

Teste ( -Qsinalize apenas para fins de visualização)

Explicação

Entrada implícita da matriz U.
[[1,1,1],[1,1,1],[1,1,1]]

Uc f

Para o primeiro sub = -array, aplainamos ( c) Ue depois filtramos ( f), removendo quaisquer elementos falsey (ou seja, 0s)
[1,1,1,1,1,1,1,1,1]

U®         Ã

Vamos construir as outras duas sub-matrizes ao mesmo tempo, mapeando U.

£     Ã

Mapeamos sobre cada elemento (sub-matriz) em U

X©

Xé o elemento atual do subconjunto atual e ©é lógico AND ( &&), portanto, se Xnão for verdade (não zero), a próxima parte não será executada.

NpY

Em Japt, Né uma matriz que contém todas as entradas; portanto, se Xfor verdade, pressionamos ( p) o índice ( Y) do elemento atual para N.
[[[1,1,1],[1,1,1],[1,1,1]],0,1,2,0,1,2,0,1,2]

Zè

De volta ao mapa da matriz principal e, para cada elemento ( Z), obtemos a contagem de elementos nessa sub-matriz que são verdadeiros (não zero).
[3,3,3]

å+

Reduza cumulativamente essa matriz somando.
[3,6,9]

iT

Insira ( i) 0 no índice 0 para concluir a segunda sub-matriz.
[0,3,6,9]

NÅ

Para o subconjunto final, simplesmente cortamos No primeiro elemento.
[0,1,2,0,1,2,0,1,2]

Shaggy
fonte
Eu corri os outros exemplos embora e ele funciona
Pureferret