version scala de l'algorithme d'échange pour les modèles nuls

Question

Le problème que je rencontre est d'essayer de trouver un moyen efficace de trouver des éléments permutables dans une matrice afin de mettre en œuvre un algorithme de permutation pour la création de modèles nuls.

La matrice est constituée de 0 et de 1 et l'idée est que les éléments peuvent être échangés entre les colonnes de sorte que les totaux des lignes et des colonnes de la matrice restent les mêmes.

Par exemple, étant donné la matrice suivante :

   c1 c2 c3 c4
r1  0  1  0  0 = 1
r2  1  0  0  1 = 2
r3  0  0  0  0 = 0
r4  1  1  1  1 = 4
   ------------
    2  2  1  2

les colonnes c2 et c4 de r1 et r2 peuvent chacune être permutées de manière à ce que les totaux ne soient pas modifiés, c'est-à-dire :

   c1 c2 c3 c4
r1  0  0  0  1 = 1
r2  1  1  0  0 = 2
r3  0  0  0  0 = 0
r4  1  1  1  1 = 4
   ------------
    2  2  1  2

Tout cela doit être fait de manière aléatoire afin de ne pas introduire de biais.

J'ai une solution qui fonctionne. Je choisis au hasard une ligne et deux colonnes. Si elles produisent un motif 10 ou 01, je sélectionne au hasard une autre ligne et je vérifie les mêmes colonnes pour voir si elles produisent le motif opposé. Si l'un ou l'autre échoue, je recommence et je sélectionne un nouvel élément.

Cette méthode fonctionne mais je ne "trouve" les bons modèles que dans 10 % des cas. Dans une grande matrice ou dans une matrice avec peu de 1 dans les rangées, je perds beaucoup de temps à "manquer". Je me suis dit qu'il devait y avoir une manière plus intelligente de choisir les éléments de la matrice tout en continuant à le faire de manière aléatoire.

Le code de la méthode de travail est le suivant :

def isSwappable(matrix: Matrix): Tuple2[Tuple2[Int, Int], Tuple2[Int, Int]] = {
  val indices = getRowAndColIndices(matrix)

  (matrix(indices._1._1)(indices._2._1), matrix(indices._1._1)(indices._2._2)) match {
    case (1, 0) => {
      if (matrix(indices._1._2)(indices._2._1) == 0 & matrix(indices._1._2)(indices._2._2) == 1) {
        indices
      }
      else {
        isSwappable(matrix)
      }
    }
    case (0, 1) => {
      if (matrix(indices._1._2)(indices._2._1) == 1 & matrix(indices._1._2)(indices._2._2) == 0) {
        indices
      }
      else {
        isSwappable(matrix)
      }
    }
    case _ => {
      isSwappable(matrix)
    }
  }
}

def getRowAndColIndices(matrix: Matrix): Tuple2[Tuple2[Int, Int], Tuple2[Int, Int]] = {
  (getNextIndex(rnd.nextInt(matrix.size), matrix.size), getNextIndex(rnd.nextInt(matrix(0).size), matrix(0).size))
}

def getNextIndex(i: Int, constraint: Int): Tuple2[Int, Int] = {
  val newIndex = rnd.nextInt(constraint)
  newIndex match {
    case `i` => getNextIndex(i, constraint)
    case _ => (i, newIndex)
  }
}

J'ai pensé qu'une manière plus efficace de gérer cela était de supprimer toutes les lignes qui ne pouvaient pas être utilisées (tous les 1 ou 0) et de choisir ensuite un élément au hasard. À partir de là, je pourrais filtrer toutes les colonnes de la ligne qui ont la même valeur et choisir parmi les colonnes restantes.

Une fois que la première ligne et la première colonne sont choisies, je filtre les lignes qui ne peuvent pas fournir le modèle requis et je choisis ensuite parmi les lignes restantes.

Cela fonctionne en grande partie, mais le problème que je ne parviens pas à résoudre est le suivant : que se passe-t-il lorsqu'il n'y a pas de colonnes ou de lignes à choisir ? Je ne veux pas tourner en boucle à l'infini pour essayer de trouver le motif dont j'ai besoin et j'ai besoin d'un moyen de recommencer si j'obtiens une liste vide de lignes ou de colonnes à choisir.

Le code que j'ai jusqu'à présent et qui fonctionne à peu près (jusqu'à ce que j'obtienne une liste vide) est le suivant :

def getInformativeRowIndices(matrix: Matrix) = (
  matrix
    .zipWithIndex
    .filter(_._1.distinct.size > 1)
    .map(_._2)
    .toList
  )

def getRowsWithOppositeValueInColumn(col: Int, value: Int, matrix: Matrix) = (
  matrix
    .zipWithIndex
    .filter(_._1(col) != value)
    .map(_._2)
    .toList
  )

def getColsWithOppositeValueInSameRow(row: Int, value: Int, matrix: Matrix) = (
  matrix(row)
    .zipWithIndex
    .filter(_._1 != value)
    .map(_._2)
    .toList
  )

def process(matrix: Matrix): Tuple2[Tuple2[Int, Int], Tuple2[Int, Int]] = {
  val row1Indices = getInformativeRowIndices(matrix)
  if (row1Indices.isEmpty) sys.error("No informative rows")

  val row1 = row1Indices(rnd.nextInt(row1Indices.size))
  val col1 = rnd.nextInt(matrix(0).size)
  val colIndices = getColsWithOppositeValueInSameRow(row1, matrix(row1)(col1), matrix)
  if (colIndices.isEmpty) process(matrix)
  val col2 = colIndices(rnd.nextInt(colIndices.size))
  val row2Indices = getRowsWithOppositeValueInColumn(col1, matrix(row1)(col1), matrix)
    .intersect(getRowsWithOppositeValueInColumn(col2, matrix(row1)(col2), matrix))
  println(row2Indices)
  if (row2Indices.isEmpty) process(matrix)

  val row2 = row2Indices(rnd.nextInt(row2Indices.size))
  ((row1, row2), (col1, col2))
}

Je pense que les méthodes récursives sont mauvaises et ne fonctionnent pas vraiment ici. De plus, j'essaie simplement d'améliorer la vitesse de sélection des cellules. Toute idée ou suggestion serait donc la bienvenue.

EDIT :

J'ai eu l'occasion de jouer un peu plus avec cela et j'ai trouvé une autre solution, mais elle ne semble pas beaucoup plus rapide que de choisir au hasard des cellules dans la matrice. Je dois également ajouter que la matrice doit être échangée environ 30000 fois de suite pour qu'elle soit considérée comme aléatoire et que je dois générer 5000 matrices aléatoires pour chaque test, dont au moins 5000 autres à faire, donc les performances sont importantes.

La solution actuelle (outre la sélection aléatoire des cellules) est :

1. Sélectionnez aléatoirement 2 lignes de la matrice.
2. Soustraire une ligne de l'autre et la mettre dans un tableau.
3. si le nouveau tableau contient à la fois un 1 et un -1, alors nous pouvons permuter

La logique de la soustraction ressemble à ceci :

  0  1  0  0
- 1  0  0  1
---------------
 -1  1  0 -1

La méthode qui fait cela ressemble à ceci :

 def findSwaps(matrix: Matrix, iterations: Int): Boolean = {
   var result = false

   val mtxLength = matrix.length

   val row1 = rnd.nextInt(mtxLength)
   val row2 = getNextIndex(row1, mtxLength)

   val difference = subRows(matrix(row1), matrix(row2))

   if (difference.min == -1 & difference.max == 1) {
     val zeroOne = difference.zipWithIndex.filter(_._1 == -1).map(_._2)
     val oneZero = difference.zipWithIndex.filter(_._1 == 1).map(_._2)

     val col1 = zeroOne(rnd.nextInt(zeroOne.length))
     val col2 = oneZero(rnd.nextInt(oneZero.length))

     swap(matrix, row1, row2, col1, col2)
     result = true
   }
   result
 }

La soustraction des lignes de la matrice ressemble à ceci :

 def subRows(a: Array[Int], b: Array[Int]): Array[Int] = (a, b).zipped.map(_ - _)

Et l'échange réel ressemble à ça :

 def swap(matrix: Matrix, row1: Int, row2: Int, col1: Int, col2: Int) = {

   val temp = (matrix(row1)(col1), matrix(row1)(col2))
   matrix(row1)(col1) = matrix(row2)(col1)
   matrix(row1)(col2) = matrix(row2)(col2)

   matrix(row2)(col1) = temp._1
   matrix(row2)(col2) = temp._2
   matrix
 }

Cela fonctionne beaucoup mieux qu'avant, car j'obtiens entre 80 et 90 % de réussite pour une tentative d'échange (il n'y en avait que 10 % avec la sélection aléatoire des cellules), mais... il faut toujours environ 2,5 minutes pour générer 1000 matrices aléatoires.

Des idées sur la façon d'améliorer la vitesse ?

Answer 1

Je vais supposer que les matrices sont grandes de sorte que le stockage de l'ordre de (taille de la matrice au carré) n'est pas viable (pour des raisons de vitesse ou de mémoire).

Si vous avez une matrice éparse, vous pouvez entrer l'index de chaque 1 dans chaque colonne d'un ensemble (ici, je montre la façon compacte de faire les choses, mais vous pouvez souhaiter itérer avec des boucles while pour plus de rapidité) :

val mtx = Array(Array(0,1,0,0),Array(1,0,0,1),Array(0,0,0,0),Array(1,1,1,1))
val cols = mtx.transpose.map(x => x.zipWithIndex.filter(_._1==1).map(_._2).toSet)

Maintenant, pour chaque colonne, une colonne ultérieure contient des paires compatibles (au moins une) si et seulement si les deux ensembles suivants sont non vides :

def xorish(a: Set[Int], b: Set[Int]) = (a--b, b--a)

La réponse consistera donc à calculer ces ensembles et à vérifier s'ils sont tous deux non vides.

La question est maintenant de savoir ce que vous entendez par "échantillonnage aléatoire". Échantillonner au hasard solo 1,0 paire est ce n'est pas la même chose qu'un échantillonnage aléatoire des échanges possibles . Pour s'en convaincre, il suffit de considérer ce qui suit :

1 0       1 0
1 0       1 0
1 0       1 0
0 1       1 0
0 1       1 0
0 1       0 1

Les deux colonnes de gauche comportent neuf échanges possibles. Les deux colonnes de droite n'ont que cinq échanges possibles. Mais si vous cherchez des motifs (1,0), vous n'échantillonnerez que trois fois à gauche contre cinq à droite ; si vous cherchez soit (1,0) soit (0,1), vous échantillonnerez six et six, ce qui fausse à nouveau les probabilités. La seule façon de résoudre ce problème est soit de no faire preuve d'intelligence et procéder à un deuxième échantillonnage aléatoire (qui, dans le premier cas, donnera lieu à un échange utilisable dans 3/5 des cas, mais seulement dans 1/5 des cas dans le second), ou calculer toutes les paires possibles pour l'échange (ou au moins le nombre de paires existantes) et choisir dans cet ensemble prédéfini.

Si nous voulons faire ce dernier point, nous notons que pour chaque paire de colonnes non identiques, nous pouvons calculer les deux ensembles à échanger entre eux, et nous connaissons les tailles et le produit est le nombre total de possibilités. Afin d'éviter d'instancier toutes les possibilités, nous pouvons créer

val poss = {
  for (i<-cols.indices; j <- (i+1) until cols.length) yield 
    (i, j, (cols(i)--cols(j)).toArray, (cols(j)--cols(i)).toArray)
}.filter{ case (_,_,a,b) => a.length>0 && b.length>0 }

et ensuite compter combien il y en a :

val cuml = poss.map{ case (_,_,a,b) => a.size*b.size }.scanLeft(0)(_ + _).toArray

Maintenant, pour choisir un nombre au hasard, nous choisissons un nombre entre 0 et cuml.last et nous choisissons de quel seau il s'agit et quel élément du seau :

def pickItem(cuml: Array[Int], poss: Seq[(Int,Int,Array[Int],Array[Int])]) = {
  val n = util.Random.nextInt(cuml.last)
  val k = {
    val i = java.util.Arrays.binarySearch(cuml,n)
    if (i<0) -i-2 else i
  }
  val j = n - cuml(k)
  val bucket = poss(k)
  (
    bucket._1, bucket._2, 
    bucket._3(j % bucket._3.size), bucket._4(j / bucket._3.size)
  )
}

Cela revient à dire (c1,c2,r1,r2) choisis au hasard.

Maintenant que vous avez les coordonnées, vous pouvez créer la nouvelle matrice comme vous le souhaitez. (Le plus efficace est probablement de faire une permutation sur place des entrées, puis de refaire la permutation lorsque vous voulez réessayer).

Notez que cela n'est utile que pour un grand nombre d'échanges indépendants. à partir de la même matrice de départ . Si vous voulez plutôt effectuer cette opération de manière itérative et maintenir l'indépendance, il est probablement préférable de le faire de manière aléatoire, à moins que les matrices soient extrêmement sparse, auquel cas il vaut la peine de simplement stocker les matrices dans un format standard de matrice sparse (c'est-à-dire par index des entrées non nulles) et de faire vos manipulations sur celles-ci (probablement avec des ensembles mutables et une stratégie de mise à jour, puisque les conséquences d'un simple swap sont limitées à environ n des entrées dans un n*n matrice).