私が抱えている問題は、null モデル作成のためのスワップ アルゴリズムを実装するために、マトリックス内のスワップ可能な要素を見つける効率的な方法を見つけようとすることです。
マトリックスは 0 と 1 で構成され、マトリックスの行と列の合計が同じままになるように要素を列間で切り替えることができるという考え方です。
たとえば、次のマトリックスがあるとします。
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
r1 と r2 の列 c2 と c4 はそれぞれ、合計が変更されないように交換できます。
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
偏りが生じないように、これはすべてランダムに行う必要があります。
うまくいく解決策が1つあります。行と 2 つの列をランダムに選択します。それらが 10 または 01 のパターンを生成する場合、別の行をランダムに選択し、同じ列をチェックして、逆のパターンを生成するかどうかを確認します。どちらかが失敗した場合は、最初からやり直して新しい要素を選択します。
この方法は機能しますが、正しいパターンに「ヒット」するのは約 10% の確率です。大規模なマトリックスまたは行に 1 がほとんどないマトリックスでは、「行方不明」に多くの時間を無駄にします。マトリックス内の要素を選択するよりインテリジェントな方法が必要であると考えましたが、それでもランダムに行います。
作業メソッドのコードは次のとおりです。
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)
}
}
これを処理するより効率的な方法は、使用できない行 (すべて 1 または 0) を削除してから、要素をランダムに選択することだと考えました。そこから、同じ値を持つ行の列を除外し、残りの列から選択することができました。
最初の行と列が選択されたら、必要なパターンを提供できない行を除外し、残りの行から選択します。
これはほとんどの場合機能しますが、対処方法がわからない問題は、選択できる列または行がない場合にどうなるかということです。必要なパターンを見つけようとして無限にループしたくありません。選択する行または列の空のリストを取得した場合、最初からやり直す方法が必要です。
これまでのところ、そのような作業を行っているコード (空のリストを取得するまで) は次のとおりです。
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))
}
再帰的な方法は間違っていて、ここでは実際には機能しないと思います。また、私は本当にセル選択の速度を改善しようとしているので、アイデアや提案は大歓迎です.
編集：
私はこれでもう少し遊ぶ機会があり、別の解決策を考え出しましたが、マトリックス内のセルをランダムに選択するよりもはるかに高速ではないようです。また、ランダム化されていると見なすには、行列を約 30000 回連続して交換する必要があり、テストごとに 5000 個のランダム行列を生成する必要があることを付け加えておく必要があります。の重要な。
現在の解決策（ランダムなセル選択以外は次のとおりです。
- 行列からランダムに 2 行を選択します
- ある行を別の行から減算し、それを配列に入れます
- 新しい配列に 1 と -1 の両方が含まれている場合は、スワップできます
減算のロジックは次のようになります。
0 1 0 0
- 1 0 0 1
---------------
-1 1 0 -1
これを行うメソッドは次のようになります。
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
}
行列の行減算は次のようになります。
def subRows(a: Array[Int], b: Array[Int]): Array[Int] = (a, b).zipped.map(_ - _)
実際のスワップは次のようになります。
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
}
これは、試行されたスワップに対して80％から90％の成功を収めているという点で、以前よりもはるかにうまく機能します（ランダムなセル選択では約10％しかありませんでした）... ランダム化された1000を生成するのにまだ約2.5分かかります行列。
速度を改善する方法についてのアイデアはありますか?