Обсудив немного об оптимизации детали из моего кода в предыдущем вопросе и получив некоторые низкоуровневые улучшения, @SergGr предложил мне создать новый вопрос, чтобы попытаться получить улучшение высокого уровня идостичь своей главной цели.
В моем коде мне нужно применить несколько ходов в «зашифрованном» квадрате-1 пазле объекте и после этого проверить, было ли оно решено.Когда я нашел лучшую реализацию квадратного объекта-головоломки в Интернете , я решил использовать его в своем приложении для Android.
Затем, как вы можете видеть, класс состоит из четырех простых чисел (integer) полей:
var ul = 0x011233
var ur = 0x455677 //continuation of ul
var dl = 0x998bba
var dr = 0xddcffe //continuation of dl
Эти поля означают «кусочки» головоломки квадрата-1, где каждая цифра в представлении hexadecimal равна единицеиз этих фигур (двойные цифры, такие как 11, 33, bb ... означает тот же «кусок» куба, который является «большой» частью).
Как вы можетевидите, некоторые операции, которые представляют реальные действия через головоломку, выполняются с использованием этих чисел, но самое большее это перестановки через ее биты.
В случае моего приложения я должен проверить, решена ли головоломка, но,для моей ситуации решенное состояние не обязательно равно необработанным полям.Поскольку мы говорим о варианте кубика Рубика, грани могут быть перемещены, то мы можем иметь решенное состояние, например (ul + "" + ur): [112334 556770], [233455 677011], [455677 11233*] и т. Д.
Обс .: примечание к начальному нулю ...
Тогда я подумал о простом алгоритме проверки решенного состояния путем поиска циклических перестановок в фиксированной решаемой последовательности, но с использованием Strings.Однако после некоторых тестов я понял, что эта работа, используя Strings, как и я, делала мое приложение все еще настолько медленным, как только мне пришлось вызывать эту проверку тысячу раз в большом цикле.
Быстрое объяснение оМой алгоритм использует строки:
- Преобразование всех чисел в
String (в данном случае шестнадцатеричная строка); - Фиксированное разрешенное состояние (
ul+ur): s = "011233"+"455677"; - Состояние, чтобы проверить, решено ли (
ul+ur): t = "233455"+"677011"; - Если мы сопоставим
s+s, мы проверим, можем ли мы найти t внутри: "011{233455677011}233455677",затем isSolved() проверка возврата true.
Где я должен применить это
По сути, основной код моего приложения - это, и я проверяю, решена ли головоломка следующим образом:
for (sequence in sequences) { //814*814 elements
auxCube.applySequence(sequence.seq) //applies the current sequence to the auxiliary cube
if (auxCube.isSolved()) { //checks if it was solved
searches.add(Search(sequence.seq)) //adds the sucess in a list
}
auxCube.copy(oldCube) //back test cube to initial state to continue finding sequences
}
Как видите, здесь используются только две сделанные мной функции.Я опишу метод applySequence() ниже.
Метод applySequence()
Я сам создал этот метод, чтобы применить отформатированные последовательности к объекту-головоломке квадрат-1.После того, как официальные последовательности для этой головоломки составлены некоторыми персонажами (похоже: «(1, 2) / (6, -3) /», я сделал несколько шагов, чтобы извлечь числа и, после, переместить куб. Он выглядит так:
fun applySequence(sequence: String) {
//remove all "(", ")", "," and " " characters and split in each "/"
val pairs = sequence.replace(" ", "").replace("\\(", "").replace("\\)", "").split("/")
//if starts with / then perform respective move
if (sequence.startsWith("/")) slashMove()
//iterate over pairs
for (pair in pairs) {
//checks if pair is not empty
if (pair != "") {
//split pair in the "," character
val pairMoves = pair.split(",")
//perform top and bottom moves with extracted numbers
move(true, Integer.parseInt(pairMoves[0]))
move(false, Integer.parseInt(pairMoves[1]))
slashMove()
}
}
//if sequence not ends with / then applies respective move
if (!sequence.endsWith("/")) slashMove()
}
Этот способ очень прост, но, учитывая, что он использует String операций, таких как concat() и contains(), в цикле, в 600 000 раз превышающем производительность, в Android снижается.
После попытки оптимизации IЯ понял, что один из лучших способов сделать это - это побитовые операции, такие операции, которые автор делал над своим исходным кодом, однако я не мог понять это.
В качестве дополнительной информации о проблеме, если я удалюПри вызове моего метода isSolved() окончательное время поиска уменьшается на 20~30 seconds.
Затем, как выполнить операцию isSolved(), используя побитовое переключение для более легкой работы в большом цикле for (для Android)?