Comprimir una matriz dispersa

18

Comprima una matriz dispersa utilizando la fila dispersa comprimida (formato CSR, CRS o Yale) .

Estas son todas la misma forma de compresión (ignore el nuevo Yale).

La entrada puede ser cualquier estructura de datos 2D (lista de listas, etc.): por ejemplo

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

Y la salida debe ser de tres estructuras de datos (lista 1d, etc), que denotan las salidas A, IAy JA, por ejemplo,

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

El proceso es descrito por wikipedia:

  • La matriz A tiene una longitud NNZ y contiene todas las entradas distintas de cero de M en orden de izquierda a derecha de arriba a abajo ("fila mayor").

  • La matriz IA tiene una longitud m + 1. Se define mediante esta definición recursiva:

    • IA [0] = 0 IA [i] = IA [i - 1] + (número de elementos distintos de cero en la fila (i - 1) en la matriz original)

    • Por lo tanto, los primeros m elementos de IA almacenan el índice en A del primer elemento distinto de cero en cada fila de M, y el último elemento IA [m] almacena NNZ, el número de elementos en A, que también puede considerarse como el índice en A del primer elemento de una fila fantasma justo más allá del final de la matriz M. Los valores de la fila i-ésima de la matriz original se leen desde los elementos A [IA [i]] a A [IA [i + 1] - 1] (inclusive en ambos extremos), es decir, desde el inicio de una fila hasta el último índice justo antes del inicio de la siguiente. [5]

    • La tercera matriz, JA, contiene el índice de columna en M de cada elemento de A y, por lo tanto, también tiene una longitud NNZ.

Si su idioma no admite estructuras de datos reales, la entrada y la salida pueden ser texto.

Casos de prueba

Entrada 1: 

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

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

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

Salida 3:

[ ]
[ 0 0 0 0 ]
[ ]

Entrada 4:

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

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

Salida 5:

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

Suponga que las entradas pueden contener cualquier número real, no necesita considerar símbolos matemáticos o representación exponencial (por ejemplo, 5,000 nunca se ingresarán como 5e3). Usted no tendrá que manejar inf, -inf, NaNo cualquier otro 'pseudo-números'. Puede generar una representación diferente del número (5,000 se pueden generar como 5e3 si así lo desea).

Puntuación:

Este es un código de golf , menos bytes gana.

Tablas de clasificación

Aquí hay un fragmento de pila para generar una tabla de clasificación regular y una descripción general de los ganadores por idioma.

Para asegurarse de que su respuesta se muestre, comience con un título, usando la siguiente plantilla de Markdown:

# Language Name, N bytes

¿Dónde Nestá el tamaño de su envío? Si mejora su puntuación, se puede mantener viejas cuentas en el título, golpeándolos a través. Por ejemplo:

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

Si desea incluir varios números en su encabezado (por ejemplo, porque su puntaje es la suma de dos archivos o desea enumerar las penalizaciones de la bandera del intérprete por separado), asegúrese de que el puntaje real sea el último número en el encabezado:

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

También puede hacer que el nombre del idioma sea un enlace que luego aparecerá en el fragmento de la tabla de clasificación:

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

Mostrar fragmento de código

code-golf number array-manipulation matrix Pureferret
fuente
¿Se podrían usar índices basados ​​en 1 para la última fila?
Leo
@Leo para JA? No.
Pureferret
1
¿No es IA[0] = 0completamente innecesario? Solo es necesario definir IA[i] = IA[i − 1]..., sin embargo, podríamos simplemente decir que si se i-1 < 0usa 0. Es decir, IA [0] siempre es igual a 0, por lo tanto, se puede comprimir (sí, me doy cuenta de que esto es una crítica del algoritmo, No este desafío).
Draco18s
¿Tendremos el desafío inverso también?
Adám
1
¡Ordenado! No me había encontrado en ninguno de los formatos antes, pero me alegra ver que alguien más lo haya visto antes (no debería ser el tipo de persona que detecta optimizaciones triviales en algoritmos tan antiguos).
Draco18s

Respuestas:

6

MATL , 19 bytes

!3#f!Dx0Gg!XsYshDq!

La entrada se usa ;como separador de filas.

Pruébalo en línea! O verifique todos los casos de prueba: 1 , 2 , 3 , 4 , 5 .

Explicación

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

Pruébalo en línea!

Cómo 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
fuente
2

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

Requiere ⎕IO←0para indexación basada en cero. I / O es una lista de listas.

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

Pruébalo en línea!

{... } función anónima donde el argumento está representado por ⍵

 (... )(... )(... ) devuelve una lista de tres cosas:

  ⍵≠0 Booleano donde el argumento difiere de 0
  ⍸¨ ɩ ndices de aquellos para cada sublista
  ∊ ϵ nlist (flatten) para combinar en una sola lista

  ⍵~¨0 eliminar los ceros de cada sub-lista del argumento
  d← tienda que como d
  ≢¨  recuento de cada
  +\ suma acumulada
  0, anteponer un cero

  ∊d ε nlist (aplanar) d de combinar en una sola lista

  

* Para ejecutar en Dyalog Classic, simplemente reemplácelo ⍸con ⎕U2378.

Adán
fuente
Bien, ¿no entiendo el formato de entrada? f 4 4⍴y luego los valores?
Pureferret
@Pureferret el Código define la función f. La entrada es realmente un REPL, que llama fen el resultado de 4 4⍴…la cual r eshapes los datos en una matriz de 4 × 4.
Adám
1
Rho para r eshapes. ¡Lo entiendo!
Pureferret
1
@Pureferret He actualizado el ¡ Pruébelo en línea! enlace para mostrar mejor los casos de prueba.
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);

Pruébalo en línea!

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

Pruébalo en línea!

Jörg Hülsermann
fuente
¿Esto necesita que los números sean cadenas?
Pureferret
1
@Pureferret Cualquier entrada en PHP es una cadena o una matriz de cadenas. No he emitido la entrada, así que si desea que la salida sea puramente int, reemplácela $x[]=$v con$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]

La entrada es una matriz 2D de números y la salida es una 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

Pruebas

Mostrar fragmento de código

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

Pruébalo en línea!

La salida es [A, JA, IA]

ovs
fuente
1

Perl 6 , 84 bytes

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

Pruébalo en línea!

El argumento de matriz única está en $_.

  • .flatmap(*.grep(+*)) selecciona los elementos distintos de cero de toda la matriz.
  • [\+] .map(+*.grep(+*))es la reducción triangular del número de elementos en cada fila (que algunos idiomas llaman scan). (0,|...)antepone un cero a esa lista.
  • .flat.kvproduce una lista indexada de todos los elementos de la matriz. .flatmap: { $^a % .[0] xx ?$^b }mapas planos sobre el módulo de cada índice por el número de columnas en la matriz ( .[0], el número de elementos en la primera fila), replicado por el elemento mismo, interpretado como un booleano. Es decir, los elementos distintos de cero se replican una vez, y los elementos cero se replican cero veces (es decir, se eliminan).
Sean
fuente
1

Python + SciPy, 79 bytes

Supongo que las incorporaciones no estaban prohibidas

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

Acepta entradas en el formato [[0, 0, 0, 0],[5, 8, 0, 0],[0, 0, 3, 0],[0, 6, 0, 0]]

Karl Napf
fuente
1

Japt , 31 27 bytes

Toma datos como una matriz de matrices y devuelve una matriz de matrices.

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

Pruébalo ( -Qmarca solo con fines de visualización)

Explicación

Entrada implícita de la matriz U.
[[1,1,1],[1,1,1],[1,1,1]]

Uc f

Para el primer sub = -array, aplanamos ( c) Uy luego lo filtramos ( f), eliminando cualquier elemento falsey (es decir, 0s)
[1,1,1,1,1,1,1,1,1]

U®         Ã

Vamos a construir los otros 2 sub-arrays al mismo tiempo, mapeando U.

£     Ã

Mapeamos sobre cada elemento (sub-matriz) en U

X©

Xes el elemento actual del subarreglo actual y ©es lógico AND ( &&), por lo tanto, si Xno es verdadero (no cero), la siguiente parte no se ejecutará.

NpY

En Japt, Nes una matriz que contiene todas las entradas, por lo que aquí, si Xes verdad, empujamos ( p) el índice ( Y) del elemento actual a N.
[[[1,1,1],[1,1,1],[1,1,1]],0,1,2,0,1,2,0,1,2]

Zè

Volviendo al mapa de la matriz principal y, para cada elemento ( Z), obtenemos el recuento de elementos en esa sub-matriz que son verdaderos (no cero).
[3,3,3]

å+

Reduzca acumulativamente esta matriz sumando.
[3,6,9]

iT

Inserte ( i) 0 en el índice 0 para completar la segunda sub-matriz.
[0,3,6,9]

NÅ

Para la submatriz final, simplemente cortamos Ndel primer elemento.
[0,1,2,0,1,2,0,1,2]

Lanudo
fuente
Sin embargo, acabo de ejecutar los otros ejemplos y funciona
Pureferret