Android Rubik's Cube Kociemba оптимальный решатель нехватки памяти

Это может быть немного поздно, но я также столкнулся с этой проблемой совсем недавно, когда работал над роботом для решения кубика Рубика, используя Android-смартфон для сканирования кубика и вычисления решения, поэтому я помещу здесь то, что Я узнал.

В чем проблема?

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

Причиной такой медленности является класс CoordCube, который выглядит (очень упрощенно) так:

class CoordCube {
    short[] pruneTables;

    static {
        /* compute and save ~50MB data in `pruneTables` */
    }
}

По сути, он загружает довольно большой объем данных в таблицы поиска, которые необходимы для быстрой процедуры решения. Эта загрузка автоматически выполняется JVM после первого создания экземпляра этого класса. Это происходит line 159 в Search.solution():

/* simplified code of solution() */
if (cube.isValid()) {
    CoordCube c = new CoordCube(); // pruning tables will be loaded on this line

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

Возможные решения:

Теперь, когда мы определили, где находится проблема, давайте сосредоточимся на том, как ее решить.

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

Подход 1:

Первый и самый простой подход — просто вручную предварительно загрузить таблицы поиска в виде LoadingActivity с ProgressBar, показывающим наш текущий прогресс. Для этого мы сначала хотим иметь возможность вручную точно контролировать, когда какие таблицы загружаются (когда класс создается впервые, недостаточно точно), например:

loadTable1() {
     /* load pruning table number 1 */
}

Для этого я написал простую утилиту здесь (код слишком длинный для вставки). Обязательно ознакомьтесь с моими инструкциями о том, как правильно импортировать этот код в ваше приложение.

Также мы, вероятно, захотим выполнить загрузку в фоновом режиме, а именно в файле AsyncTask. Вот как я сделал это в своем приложении (PruneTableLoader включен в предыдущую ссылку):

private class LoadPruningTablesTask extends AsyncTask<Void, Void, Void> {
    private PruneTableLoader tableLoader = new PruneTableLoader();

    @Override
    protected Void doInBackground(Void... params) {
        /* load all tables if they are not already in RAM */
        while (!tableLoader.loadingFinished()) { // while tables are left to load
            tableLoader.loadNext(); // load next pruning table
            publishProgress(); // increment `ProgressBar` by one
        }

        return null;
    }

    @Override
    protected void onProgressUpdate(Void... values) {
        super.onProgressUpdate(values);
        /* increment `ProgressBar` by 1 */
    }
}

При использовании моего PruneTableLoader для загрузки всех таблиц требуется около 40s на моем Samsung Galaxy S3 с 250 MB RAM free. (напротив, при их автоматической загрузке требуется well over 2min, и, кроме того, это часто приводит к сбою ...)

Это все еще может звучать довольно медленно, учитывая, что на ПК требуется < 1s, но, по крайней мере, вы должны сделать это только один раз, поскольку Android кэширует статические переменные, и вам не нужно загружать их при каждом запуске вашего приложения.

Подход 2: (не проверено)

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

Подход 3: (не проверено)

Что ж, самым сложным, а также на десятилетия самым затратным решением было бы просто переписать весь алгоритм в C или C++ и вызвать его в приложении через JNI. (Герберт Коциемба, насколько мне известно, еще не опубликовал свой C-sourcecode...)

Это будет самое быстрое решение с точки зрения производительности. (также для самой процедуры решения)

В целом, подход 1, вероятно, является лучшим подходом с точки зрения соотношения усилий/выгод для начала (и он также был для меня), поэтому я бы порекомендовал вам использовать его, если время загрузки не такая огромная проблема для вашего приложения.

Однако я не полностью доволен его эффективностью, поэтому я могу попробовать подход 2 и, возможно, даже подход 3 в будущем. В случае, если я это сделаю, я обновлю этот пост с моими результатами.