Compressez une matrice clairsemée

18

Compressez une matrice clairsemée à l'aide d' une ligne clairsemée compressée (format CSR, CRS ou Yale) .

Ce sont tous la même forme de compression (ignorez le nouveau Yale).

L'entrée peut être n'importe quelle structure de données 2D (liste de listes, etc.): par exemple

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

Et la sortie doit être trois structures de données 1d (liste, etc.), qui désignent les sorties A, IAet JA, par exemple

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

Le processus est décrit par wikipedia:

  • Le tableau A est de longueur NNZ et contient toutes les entrées non nulles de M dans l'ordre de gauche à droite de haut en bas ("row-major").

  • Le tableau IA est de longueur m + 1. Il est défini par cette définition récursive:

    • IA [0] = 0 IA [i] = IA [i - 1] + (nombre d'éléments non nuls sur la (i - 1) -ième ligne de la matrice d'origine)

    • Ainsi, les m premiers éléments de IA stockent l'index dans A du premier élément non nul dans chaque ligne de M, et le dernier élément IA [m] stocke NNZ, le nombre d'éléments dans A, qui peut également être considéré comme le index dans A du premier élément d'une ligne fantôme juste au-delà de la fin de la matrice M. Les valeurs de la i-ème ligne de la matrice d'origine sont lues à partir des éléments A [IA [i]] à A [IA [i + 1] - 1] (inclus aux deux extrémités), c'est-à-dire du début d'une ligne au dernier index juste avant le début de la suivante. [5]

    • Le troisième tableau, JA, contient l'indice de colonne en M de chaque élément de A et est donc également de longueur NNZ.

Si votre langue ne prend pas en charge les structures de données réelles, l'entrée et la sortie peuvent être du texte.

Cas de test

Entrée 1: 

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

Sortie 1:

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

Entrée 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]]

Sortie 2:

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

Entrée 3:

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

Sortie 3:

[ ]
[ 0 0 0 0 ]
[ ]

Entrée 4:

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

Sortie 4:

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

Entrée 5: 

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

Résultat 5:

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

Supposons que les entrées peuvent contenir n'importe quel nombre réel, vous n'avez pas besoin de considérer les symboles mathématiques ou la représentation exponentielle (par exemple, 5000 ne seront jamais entrés comme 5e3). Vous aurez pas besoin de gérer inf, -inf, NaNou tout autre « pseudo-numéros ». Vous pouvez générer une représentation différente du nombre (5 000 peuvent être générés en 5e3 si vous le souhaitez).

Notation:

Il s'agit d'un code-golf , le moins d'octets gagne.

Classements

Voici un extrait de pile pour générer à la fois un classement régulier et un aperçu des gagnants par langue.

Pour vous assurer que votre réponse s'affiche, veuillez commencer votre réponse avec un titre, en utilisant le modèle Markdown suivant:

# Language Name, N bytes

où Nest la taille de votre soumission. Si vous améliorez votre score, vous pouvez conserver les anciens scores dans le titre, en les barrant. Par exemple:

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

Si vous souhaitez inclure plusieurs nombres dans votre en-tête (par exemple, parce que votre score est la somme de deux fichiers ou que vous souhaitez répertorier les pénalités de drapeau d'interprète séparément), assurez-vous que le score réel est le dernier numéro de l'en-tête:

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

Vous pouvez également faire du nom de la langue un lien qui apparaîtra ensuite dans l'extrait de classement:

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

Afficher l'extrait de code

code-golf number array-manipulation matrix Pureferret
la source
Des indices basés sur 1 pourraient-ils être utilisés pour la dernière ligne?
Leo
@Leo pour JA? Non.
Pureferret
1
N'est-ce pas IA[0] = 0complètement inutile? Il suffit de définir IA[i] = IA[i − 1]..., mais nous pourrions simplement dire que si i-1 < 0vous utilisez 0. Autrement dit, IA [0] est toujours égal à 0, il peut donc être compressé (oui, je me rends compte que c'est une critique de l'algorithme, pas ce défi).
Draco18 ne font plus confiance au SE
Aurons-nous aussi le défi inverse?
Adám
1
Soigné! Je n'avais rencontré aucun des deux formats auparavant, mais je suis heureux de voir que quelqu'un d'autre l'a déjà vu auparavant (je ne devrais pas être le genre de personne qui repère des optimisations triviales dans des algorithmes aussi anciens).
Draco18s ne fait plus confiance au SE

Réponses:

6

MATL , 19 octets

!3#f!Dx0Gg!XsYshDq!

L'entrée utilise ;comme séparateur de ligne.

Essayez-le en ligne! Ou vérifiez tous les cas de test: 1 , 2 , 3 , 4 , 5 .

Explication

!     % 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
la source
3

Haskell, 87 octets

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

Essayez-le en ligne!

Comment ça fonctionne:

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
la source
2

APL (Dyalog) , 31 28 caractères ou 36 33 octets *

Requiert ⎕IO←0une indexation à base zéro. I / O est une liste de listes.

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

Essayez-le en ligne!

{… } Fonction anonyme où l'argument est représenté par ⍵

 (... )(... )(... ) retourner une liste de trois choses:

  ⍵≠0 Booléen où l'argument diffère de 0
  ⍸¨ ɩ ndices de ceux de chaque sous-liste
  ∊ ϵ nlist (flatten) à combiner en une seule liste

  ⍵~¨0 supprimer des zéros de chaque sous-liste de l'argument
  d← magasin que d
  ≢¨  tally chaque
  +\ somme cumulative
  0, préfixer un zéro

  ∊d ε nlist (aplatir) d à combiner en liste unique

  

* Pour exécuter dans Dyalog Classic, remplacez simplement ⍸par ⎕U2378.

Adam
la source
Bien, je ne comprends pas le format d'entrée? f 4 4⍴puis les valeurs?
Pureferret
@Pureferret le Code définit la fonction f. L'entrée est vraiment un REPL, qui appelle fsur le résultat de 4 4⍴…laquelle r eshapes les données dans une matrice 4 × 4.
Adám
1
Rho pour r eshapes. J'ai compris!
Pureferret
1
@Pureferret J'ai mis à jour le Essayez-le en ligne! lien pour mieux montrer les cas de test.
Adám
2

PHP , 107 octets

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

Essayez-le en ligne!

PHP , 109 octets

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

Essayez-le en ligne!

Jörg Hülsermann
la source
Faut-il que les nombres soient des chaînes?
Pureferret
1
@Pureferret Toute entrée en PHP est une chaîne ou un tableau de chaînes. Je n'ai pas casté l'entrée donc si vous souhaitez que la sortie soit purement int remplacer $x[]=$v par$x[]=+$v
Jörg Hülsermann
2

JavaScript (ES6), 117 octets

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]

L'entrée est un tableau 2D de nombres et la sortie est un tableau de [A, IA, JA].

Expliqué

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

Les tests

Afficher l'extrait de code

Justin Mariner
la source
1

Python 2 , 115 octets

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

Essayez-le en ligne!

La sortie est [A, JA, IA]

ovs
la source
1

Perl 6 , 84 octets

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

Essayez-le en ligne!

L'argument de matrice unique est dans $_.

  • .flatmap(*.grep(+*)) sélectionne les éléments non nuls de la matrice entière.
  • [\+] .map(+*.grep(+*))est la réduction triangulaire du nombre d'éléments dans chaque ligne (que certaines langues appellent scan). (0,|...)ajoute un zéro à cette liste.
  • .flat.kvproduit une liste indexée de tous les éléments de la matrice. .flatmap: { $^a % .[0] xx ?$^b }flat-maps sur le module de chaque index par le nombre de colonnes du tableau ( .[0], le nombre d'éléments dans la première ligne), répliqué par l'élément lui-même, interprété comme un booléen. Autrement dit, les éléments non nuls sont répliqués une fois et les éléments nuls sont répliqués zéro fois (c'est-à-dire supprimés).
Sean
la source
1

Python + SciPy, 79 octets

je suppose que les éléments intégrés n'étaient pas interdits

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

Accepte les entrées au format [[0, 0, 0, 0],[5, 8, 0, 0],[0, 0, 3, 0],[0, 6, 0, 0]]

Karl Napf
la source
1

Japt , 31 27 octets

Prend l'entrée comme un tableau de tableaux et renvoie un tableau de tableaux.

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

Testez-le ( -Qindicateur à des fins de visualisation uniquement)

Explication

Entrée implicite du tableau U.
[[1,1,1],[1,1,1],[1,1,1]]

Uc f

Pour le premier sous-tableau =, nous l'aplatissons ( c) Upuis le ffiltrons ( ), en supprimant tous les éléments de falsey (c.-à-d., 0s)
[1,1,1,1,1,1,1,1,1]

U®         Ã

Nous allons construire les 2 autres sous-tableaux en même temps, en mappant dessus U.

£     Ã

Nous cartographions chaque élément (sous-tableau) dans U

X©

Xest l'élément courant du sous-tableau courant et ©est un ET logique ( &&) donc, s'il Xn'est pas véridique (pas nul), la partie suivante ne sera pas exécutée.

NpY

Dans Japt, Nest un tableau contenant toutes les entrées donc ici, si Xc'est vrai, nous poussons ( p) l'index ( Y) de l'élément courant vers N.
[[[1,1,1],[1,1,1],[1,1,1]],0,1,2,0,1,2,0,1,2]

Zè

Revenons à la carte du tableau principal et, pour chaque élément ( Z), nous obtenons le nombre d'éléments dans ce sous-tableau qui sont véridiques (et non nuls).
[3,3,3]

å+

Réduisez cumulativement ce tableau en sommant.
[3,6,9]

iT

Insérez ( i) 0 à l'index 0 pour terminer le deuxième sous-tableau.
[0,3,6,9]

NÅ

Pour le sous-tableau final, nous découpons simplement à Npartir du 1er élément.
[0,1,2,0,1,2,0,1,2]

Hirsute
la source
Je viens de lancer les autres exemples et cela fonctionne
Pureferret