Scala-версия алгоритма обмена для нулевых моделей
Проблема, с которой я столкнулся, заключается в попытке найти эффективный способ поиска заменяемых элементов в матрице, чтобы реализовать алгоритм подкачки для создания нулевой модели.
Матрица состоит из 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
каждый столбец c2 и c4 в r1 и r2 можно поменять местами таким образом, чтобы итоговые значения не были изменены, т.е.
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
Все это должно быть сделано случайным образом, чтобы не вносить никакого смещения.
У меня есть одно решение, которое работает. Я случайным образом выбираю строку и два столбца. Если они дают шаблон 10 или 01, тогда я случайным образом выбираю другую строку и проверяю те же столбцы, чтобы увидеть, дают ли они противоположный шаблон. Если любой из них не удается, я начинаю заново и выбираю новый элемент.
Этот метод работает, но я только "ударил" правильные паттерны примерно в 10% случаев. В большой матрице или в одной с несколькими единицами в строках я теряю много времени, "пропуская". Я подумал, что должен быть более разумный способ выбора элементов в матрице, но все же делать это случайным образом.
Код для рабочего метода:
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 случайных матриц для каждого теста, для которого у меня есть как минимум еще 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% при случайном выборе ячеек), однако... это все еще занимает около 2,5 минут, чтобы сгенерировать 1000 рандомизированных матрицы.
Любые идеи о том, как улучшить скорость?
1 ответ
Я собираюсь предположить, что матрицы большие, поэтому порядок хранения (размер матрицы в квадрате) нежизнеспособен (по соображениям скорости или памяти).
Если у вас есть разреженная матрица, вы можете ввести индекс каждого 1 в каждом столбце в наборе (здесь я покажу компактный способ сделать что-то, но вы можете использовать циклы while для скорости):
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)
Теперь для каждого столбца более поздний столбец содержит совместимые пары (хотя бы одну) тогда и только тогда, когда только следующие два набора непусты:
def xorish(a: Set[Int], b: Set[Int]) = (a--b, b--a)
Таким образом, ответ будет включать вычисление этих наборов и тестирование, являются ли они оба непустыми.
Теперь вопрос в том, что вы подразумеваете под "выборкой случайно". Случайная выборка одиночных 1,0 пар - это не то же самое, что случайная выборка возможных свопов. Чтобы увидеть это, рассмотрим следующее:
1 0 1 0
1 0 1 0
1 0 1 0
0 1 1 0
0 1 1 0
0 1 0 1
Два столбца слева имеют девять возможных перестановок. У двух справа есть только пять возможных обменов. Но если вы ищете (1,0) паттернов, вы будете выбирать только три раза слева против пяти справа; если вы ищете (1,0) или (0,1), вы выберете шесть и шесть, что снова искажает вероятности. Единственный способ исправить это - либо не быть умным, а случайным образом сделать выборку во второй раз (что в первом случае сработает с помощью полезного свопа в 3/5 времени, тогда как во втором - только в 1/5), или чтобы в основном вычислить каждую возможную пару для обмена (или, по крайней мере, сколько пар существует) и выбрать из этого предопределенного набора.
Если мы хотим сделать последнее, отметим, что для каждой пары неидентичных столбцов мы можем вычислить два набора, между которыми нужно поменяться, и мы знаем, что размеры и продукт - это общее количество возможностей. Чтобы не создавать все возможности, мы можем создать
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 }
а затем посчитайте, сколько их:
val cuml = poss.map{ case (_,_,a,b) => a.size*b.size }.scanLeft(0)(_ + _).toArray
Теперь, чтобы выбрать случайное число, мы выбираем число от 0 до cuml.last и выбираем, что это за корзина и какой элемент в корзине:
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)
)
}
Это заканчивается возвращением (c1,c2,r1,r2) выбран случайным образом.
Теперь, когда у вас есть координаты, вы можете создать новую матрицу по своему усмотрению. (Наиболее эффективным является, вероятно, сделать обмен записями на месте, а затем вернуться назад, когда вы захотите повторить попытку.)
Обратите внимание, что это имеет смысл только для большого количества независимых свопов из одной и той же исходной матрицы. Если вместо этого вы хотите сделать это итеративно и сохранить независимость, вам, вероятно, лучше всего делать это случайным образом, если только матрицы не очень разрежены, и в этот момент стоит просто хранить матрицы в некотором стандартном формате разреженных матриц (т. Е. По ненулевому индексу записей) и манипулирование ими (возможно, с изменяемыми наборами и стратегией обновления, так как последствия одного обмена ограничены примерно n из записей в n*n матрица).