Как заменить строковые операции на побитовые? - PullRequest
Новая
       14

Как заменить строковые операции на побитовые?

0 голосов
/ 29 января 2019

Учитывая, что у меня есть эти поля в Base объекте: 

//these fields have their bits constantly permuted
//and have their values defined to "011233455677..."
//to integers acts like Strings

var ul = 0x011233
var ur = 0x455677
var dl = 0x998bba
var dr = 0xddcffe

И учитывая, что у меня есть этот метод, который обрабатывает эти поля как строковые значения: 

private fun Cubo.isSolved(): Boolean {             
    val solved = Base()

    //function to append "leading zero" to the hex integer
    fun fill(s: String) = if (s.length == 5) "0$s" else s

    //all these fields are declared at the global escope

    //converted ul, ur, dl, dr from solved obj to hex string
    a1 = fill(Integer.toHexString(solved.ul))
    b1 = fill(Integer.toHexString(solved.ur))
    c1 = fill(Integer.toHexString(solved.dl))
    d1 = fill(Integer.toHexString(solved.dr))

    //concats the converteds ul and ur into a new one
    ab1 = a1 + b1
    //concats the converteds dl and dr into a new one
    cd1 = c1 + d1

    //do the same with fields of THIS object
    a2 = fill(Integer.toHexString(this.ul))
    b2 = fill(Integer.toHexString(this.ur))
    c2 = fill(Integer.toHexString(this.dl))
    d2 = fill(Integer.toHexString(this.dr))
    ab2 = a2 + b2
    cd2 = c2 + d2

    //checks if concatenated fields from THIS object exists inside the 
    //duplicated [solved] object fields.
    //This will help me to check if fields from THIS object are 
    //cyclic/circular permutations of the [solved] object.
    return (ab1 + ab1).contains(ab2) && (cd1 + cd1).contains(cd2)
}

Моя цельчтобы знать, как заменить эти операции побитовыми операциями, если поля являются целыми числами?

Я пытаюсь это сделать, потому что мое приложение работает очень медленно, и этот метод снижает производительность, когда его вызывают тысячи раз в цикле,затем понял, что способ улучшить производительность моего приложения может быть с помощью побитовых операций.

И чтобы упростить идею этого метода, он просто использовал, чтобы убедиться, что поле ЭТОГО объекта соответствует полям "«Решено», но это сделано с учетом вероятности циклической перестановки полей тестового объекта.

Ответы [ 2 ]

0 голосов
/ 30 января 2019

Предполагая, что ваше целевое состояние фиксировано и имеет фиксированный размер 12 шестнадцатеричных символов, я бы сделал это немного по-другому.Сначала я рассчитал все повороты solved, а затем проверил их с помощью простых равных.Я не уверен, где имеет смысл хранить это в вашем приложении.В этом коде я передаю это как параметр target. 

class Cubo() {

    var ul: Int = 0x011233
    var ur: Int = 0x455677
    var dl: Int = 0x998bba
    var dr: Int = 0xddcffe

    constructor(ul: Int, ur: Int, dl: Int, dr: Int) : this() {
        this.ul = ul
        this.ur = ur
        this.dl = dl
        this.dr = dr
    }

    fun isSolved(target: TargetState): Boolean {
        return target.checkSolved(this)
    }
}


class TargetState(val uRot: AllRotations, val dRot: AllRotations) {
    constructor(c: Cubo) : this(AllRotations(concat(c.ul, c.ur)), AllRotations(concat(c.dl, c.dr))) {
    }

    fun checkSolved(c: Cubo): Boolean {
        val u = concat(c.ul, c.ur)
        val d = concat(c.dl, c.dr)
        return uRot.contains(u) and dRot.contains(d)
    }

    companion object {
        fun concat(l: Int, r: Int): Long {
            return l.toLong().shl(AllRotations.singleBitsCount).or(r.toLong())
        }

    }
}


class AllRotations(value: Long) {

    val rotatedValues = Array<Long>(doubleDigitsCount) { i -> rotate(value, digitSize * i) }

    fun contains(test: Long): Boolean {
        for (v in rotatedValues) {
            if (v == test)
                return true
        }
        return false
    }


    companion object {
        const val singleDigitsCount = 6
        const val doubleDigitsCount = 2 * singleDigitsCount
        const val digitSize = 4
        const val singleBitsCount = digitSize * singleDigitsCount
        const val doubleBitsCount = digitSize * doubleDigitsCount
        const val mask = 1L.shl(doubleBitsCount) - 1


        fun rotate(value: Long, shift: Int): Long {
            val hi = value.shl(shift).and(mask)
            val lo = value.shr(doubleBitsCount - shift)
            return hi.or(lo)
        }
    }
}

Вот простой тест, который работает: 

val solved = Cubo(0x011233, 0x455677, 0, 0)
val targetState = TargetState(solved)

val c1 = Cubo(0x233455, 0x677011, 0, 0)
val c2 = Cubo(0x455677, 0x011233, 0, 0)
val cbad = Cubo(0x455677, 0x011233, 1, 0)

println(c1.isSolved(targetState))
println(c2.isSolved(targetState))
println(cbad.isSolved(targetState))
0 голосов
/ 29 января 2019

Конкатенация

"Конкатенация" двух шестнадцатеричных 6-значных чисел фактически означает сдвиг влево на 24 бита (поскольку каждая шестнадцатеричная цифра имеет 4 бита, а длина равна 6) первогономер и взятие второго числа поразрядно or результат сдвига. 

infix fun Long.hexConcat(num: Long) = num.or(shl(24))

Содержит

Чтобы проверить, содержится ли шестизначное шестнадцатеричное числов первых или последних 6 цифрах 12-значного шестнадцатеричного числа вы можете поразрядно and их обоих (для проверки конца).Чтобы проверить, находится ли он в начале, вы должны сначала сдвинуть его вправо на 24 бита, а затем поразрядно and it. 

infix fun Long.containsAsHex(num: Long) = and(num) == num || shr(24) == num

Пример: 

fun main() {

    val a = 0x011233L
    val b = 0x455677L

    val c = a hexConcat b

    println(c.toString(16)) // 11233455677
    println(c containsAsHex a) // true
}

Конечно, вы можете параметризовать hexConcat далее, чтобы не ограничивать его шестизначными шестизначными числами.

В случае, если шестнадцатеричное шестнадцатеричное число может быть где угодно в 12-значном шестнадцатеричном числе:

Чтобы проверить, содержит ли шестнадцатеричное число еще одно, вы сдвигаете его на 4 бита вправо до тех пор, пока его значение не станет равным 0, или вы не найдете совпадение, которое будет означать, что смещенное число поразрядно and проверяемое числодолжен равняться числу для проверки. 

infix fun Long.containsAsHex(num: Long): Boolean {

    var shifted = this

    while (true) {

        if(shifted.and(num) == num) {
            return true
        }

        if(shifted == 0L) {
            return false
        }

        shifted = shifted.shr(4) // shift one hex digit
    }

    @Suppress("UNREACHABLE_CODE")
    return false
}
...