Bolloky 1 мар 2013 в 09:59

«Умный» размер очереди в андроид

7 мин

В одном из проектов на работе встала, казалось бы, тривиальная задача: подгружать картинки и описания к ним с сервера, чтобы пользователь мог переключать их без задержки. Для этого использовался метод, который при каждом переключении проверял, сколько элементов осталось в очереди, и, если там осталось меньше определённого числа, подгружал очередной элемент. Дело решалось константой, равной 3. Но, как известно, андроид-устройства очень сильно различаются по производительности, и на иных телефонах такого числа было недостаточно, но задавать сильно большое число — неэффективно, так как пользователь мог вообще просмотреть один-два элемента и уйти с экрана. Тогда я и подумал, почему бы не определять это число по-умному?

Описание

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

Тип интернет соединения (Нас интересует только wifi это или edge, так как операция определения скорости соединения слишком трудоёмка)
Интервал переключения (Как часто пользователь переключает картинки)
Задержка при переключении (Когда всё хорошо, она должна составлять в моём случае 1мс)
Свободная оперативная память (Сразу отмечу что измеряется текущий остаток, выделенный процессу, а не общий размер оставшийся оперативной памяти, так что этот параметр не очень важен)
Размер очереди (Обратная связь важна, чтобы ингибировать слишком разросшуюся очередь)

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

Приступим

Так как данные сильно разнятся по величине (например, остаток памяти измеряется в байтах, так что там будут числа более чем с шестью разрядами, а тип соединения — это однозначная константа), для удобства введены несколько констант для нормализации значений, которые помогают привести все числа к диапазону ~ [-20;20]. Кроме констант иногда используется разница между определённым вручную нормальным значением и текущим, об этом ниже.

Подробнее

Тип интернет соединения (Переменная private double connectionType=0;)
Потребуется экземпляр класса NetworkInfo:

NetworkInfo activeNetwork = ((ConnectivityManager) context.getSystemService(Context.CONNECTIVITY_SERVICE)).getActiveNetworkInfo();

При на каждой итерации подсчётов в первую очередь проверяем
if (!activeNetwork.isConnectedOrConnecting()) return;
далее
connectionType = (activeNetwork.getType()); // EDGE = 0; WiFi = 1

Интервал переключения (Переменные

private long tapInterval = 5000; private byte tapTrigger = 0; private double tapAssemblyAverage = 5000;private long nextTap = 0; private long lastTap = 0;

)
Для получения интервала используется метод

public synchronized void setNextTap(long nextTap) {
        this.lastTap=this.nextTap;
        this.nextTap = nextTap;
        if (nextTap > lastTap) {
            tapInterval = nextTap - lastTap;
            lastTap = nextTap;
        }
        if (tapInterval > TAP_INTERVAL_UPPER_THRESHOLD) tapInterval = TAP_INTERVAL_UPPER_THRESHOLD;
        if (tapInterval < 100) tapInterval = 100;
        tapAssemblyAverage = (tapAssemblyAverage * tapTrigger + tapInterval) / (++tapTrigger);
    }

который вызывается из места, где пользователь переключает элементы. TAP_INTERVAL_UPPER_THRESHOLD — это константа, в моём случае равная 10 000 мс.
Как вы заметили, используется среднее значение переключения. tapTrigger сбрасывается при обновлении.

Задержка переключения (Переменные private long delayInterval = 500; private long finishDelay = 0; private long startDelay = 0;)
Для получения используются методы

public synchronized void setStartDelay(long start) {
        this.startDelay = start;
    }

public synchronized void setFinishDelay(long finish) {
        this.finishDelay = finish;
        if (finishDelay > startDelay) {
            delayInterval = finishDelay - startDelay;
        }
    }

Здесь важна последняя задержка, а не среднее значение задержек.

Свободная оперативная память (Переменная private long freeRam = 5000000;)
Повторю, что измеряется текущий остаток, выделенный процессу, а не общий размер оставшийся оперативной памяти.

freeRam = Runtime.getRuntime().freeMemory();

Нормализация

Для хранения нормализованных значений и их весов используется массив Relations/Weights double[][] RW = new double[2][5]; Для нормализации используется ряд констант и формул

Константы

private static final int TAP_EQUALIZER = 1000;
private static final int DELAY_EQUALIZER = 1000;
private static final int RAM_EQUALIZER = 1000000;

private static final int TAP_INTERVAL_UPPER_THRESHOLD = 10000;
private static final int DELAY_INTERVAL_UPPER_THRESHOLD = 5000;
private static final int NORMAL_TAP_INTERVAL = 9;

private static final int TAP_I = 0;
private static final int DELAY_I = 1;
private static final int CONNECTION = 2;
private static final int RAM = 3;
private static final int QUEUE = 4;

private synchronized void normalization() {
        if (delayInterval > DELAY_INTERVAL_UPPER_THRESHOLD) delayInterval = DELAY_INTERVAL_UPPER_THRESHOLD;
        if (delayInterval < 0) delayInterval = 0;

        if (connectionType > 1 || connectionType < 0) connectionType = 0.5;
        connectionType = (connectionType - 2) * 2;

        if (freeRam < 100000 || freeRam > 10000000) freeRam = 5000000;
    }
 private void cast() {
        RW[0][TAP_I] = (NORMAL_TAP_INTERVAL - (tapAssemblyAverage / TAP_EQUALIZER));
        RW[0][DELAY_I] = (double) (delayInterval / DELAY_EQUALIZER);
        RW[0][CONNECTION] = connectionType;
        RW[0][RAM] = (double) (freeRam / RAM_EQUALIZER);
        RW[0][QUEUE] = (double) (count);
    }

Веса

Остаётся сказать о весах. Их можно подобрать двумя способами: аналитически или симплексным методом, например, в Excel. Я подбирал веса аналитически, поэтому просто приведу результаты:

private void setInitialWeights() {
        RW[1][TAP_I] = 0.5;
        RW[1][DELAY_I] = 1;
        RW[1][CONNECTION] = -1;
        RW[1][RAM] = 0.1;
        RW[1][QUEUE] = -0.1;
    }

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

Вычисление

В следующем методе по стандартной формуле вычисляется размер очереди, и округляется до большего целого. Кроме того, здесь же вычисляется интервал обновления. Он зависит от изменения очереди. Если она изменилась больше чем на значение константы int SLEEP_COMPARISON_THRESHOLD = 2, то интервал уменьшается, в противном случае — увеличивается.

Константы и переменные

private static final int SLEEP_COMPARISON_THRESHOLD = 2;
private static final int SLEEP_ADDITION_INC_STEP = 100;
private static final int SLEEP_ADDITION_DEC_STEP = -500;
private long sleepInterval = 500;

private int activation() {
        double value = 0;
        for (int i = 0; i < 5; i++) value += RW[0][i] * RW[1][i];
        sleepInterval += ((Math.abs(count - value) > SLEEP_COMPARISON_THRESHOLD || sleepInterval > 10000)) ? SLEEP_ADDITION_DEC_STEP : SLEEP_ADDITION_INC_STEP;
        if (sleepInterval < 500) sleepInterval = 500;
        Log.d("QUEUE", "sleep: " + String.valueOf(sleepInterval));
        if (value < 1) value = 1;
        Log.d("QUEUE", "queue: " + String.valueOf(value));
        return (int) Math.ceil(value);
    }

Полный код

public class IntellijQueue extends Thread {
    private static final int TAP_I = 0;
    private static final int DELAY_I = 1;
    private static final int CONNECTION = 2;
    private static final int RAM = 3;
    private static final int QUEUE = 4;

    private static final int TAP_EQUALIZER = 1000;
    private static final int DELAY_EQUALIZER = 1000;
    private static final int RAM_EQUALIZER = 1000000;
    private static final int SLEEP_COMPARISON_THRESHOLD = 2;
    private static final int SLEEP_ADDITION_INC_STEP = 100;
    private static final int SLEEP_ADDITION_DEC_STEP = -500;
    private static final int TAP_INTERVAL_UPPER_THRESHOLD = 10000;
    private static final int DELAY_INTERVAL_UPPER_THRESHOLD = 5000;
    private static final int NORMAL_TAP_INTERVAL = 9;


    public volatile int count = 3;

    private long finishDelay = 0;
    private long startDelay = 0;
    private long nextTap = 0;

    private long lastTap = 0;
    private long sleepInterval = 500;
    private double connectionType = 0;
    private long tapInterval = 5000;
    private long delayInterval = 500;
    private long freeRam = 5000000;
    private double RW[][];
    private byte tapTrigger = 0;
    private double tapAssemblyAverage = 5000;
    private NetworkInfo activeNetwork;

    public IntellijQueue(Context context) {
        this.setPriority(MIN_PRIORITY);
        this.setDaemon(true);
        activeNetwork = ((ConnectivityManager) context.getSystemService(Context.CONNECTIVITY_SERVICE)).getActiveNetworkInfo();
        RW = new double[2][5];
        setInitialWeights();
        lastTap = System.currentTimeMillis();

    }

    private void setInitialWeights() {
        RW[1][TAP_I] = 0.5;
        RW[1][DELAY_I] = 1;
        RW[1][CONNECTION] = -1;
        RW[1][RAM] = 0.1;
        RW[1][QUEUE] = -0.1;
    }

    private void cast() {
        RW[0][TAP_I] = (NORMAL_TAP_INTERVAL - (tapAssemblyAverage / TAP_EQUALIZER));
        RW[0][DELAY_I] = (double) (delayInterval / DELAY_EQUALIZER);
        RW[0][CONNECTION] = connectionType;
        RW[0][RAM] = (double) (freeRam / RAM_EQUALIZER);
        RW[0][QUEUE] = (double) (count);
    }

    private int activation() {
        double value = 0;
        for (int i = 0; i < 5; i++) value += RW[0][i] * RW[1][i];
        sleepInterval += ((Math.abs(count - value) > SLEEP_COMPARISON_THRESHOLD || sleepInterval > 10000)) ? SLEEP_ADDITION_DEC_STEP : SLEEP_ADDITION_INC_STEP;
        if (sleepInterval < 500) sleepInterval = 500;
        Log.d("QUEUE", "sleep: " + String.valueOf(sleepInterval));
        if (value < 1) value = 1;
        Log.d("QUEUE", "queue: " + String.valueOf(value));
        return (int) Math.ceil(value);
    }

    private synchronized void updateValues() {
        if (!activeNetwork.isConnectedOrConnecting()) return;
        connectionType = (activeNetwork.getType()); // EDGE = 0; WiFi = 1
        tapTrigger=0;
        freeRam = Runtime.getRuntime().freeMemory();
        Log.d("QUEUE", "tap interval: " + String.valueOf(tapInterval));
        Log.d("QUEUE", "delay interval: " + String.valueOf(delayInterval));
        Log.d("QUEUE", "free RAM: " + String.valueOf(freeRam));

        normalization();
        cast();
    }

    private synchronized void normalization() {
        if (delayInterval > DELAY_INTERVAL_UPPER_THRESHOLD) delayInterval = DELAY_INTERVAL_UPPER_THRESHOLD;
        if (delayInterval < 0) delayInterval = 0;

        if (connectionType > 1 || connectionType < 0) connectionType = 0.5;
        connectionType = (connectionType - 2) * 2;

        if (freeRam < 100000 || freeRam > 10000000) freeRam = 5000000;
    }

    @Override
    public void run() {
        try {
            while (true) {
                updateValues();
                count = activation();
                sleep(sleepInterval);
            }
        } catch (InterruptedException e) {

        }
    }

    public synchronized void setStartDelay(long start) {
        this.startDelay = start;
        Log.d("QUEUE", "S Ok.");
    }

    public synchronized void setFinishDelay(long finish) {
        this.finishDelay = finish;
        Log.d("QUEUE", "F Ok.");
        if (finishDelay > startDelay) {
            delayInterval = finishDelay - startDelay;
        }
    }

    public synchronized void setNextTap(long nextTap) {
        this.lastTap=this.nextTap;
        this.nextTap = nextTap;
        if (nextTap > lastTap) {
            tapInterval = nextTap - lastTap;
            lastTap = nextTap;
        }
        if (tapInterval > TAP_INTERVAL_UPPER_THRESHOLD) tapInterval = TAP_INTERVAL_UPPER_THRESHOLD;
        if (tapInterval < 100) tapInterval = 100;
        tapAssemblyAverage = (tapAssemblyAverage * tapTrigger + tapInterval) / (++tapTrigger);
    }
}

Итог

После подключения класса к проекту, задержки при переключении исчезли. При тестировании на разных девайсах очередь изменялась в диапазоне от 2 до 11. Тесты проводились на: Samsung Galaxy S2, Galaxy S3, Samsung Gio, Motorolla Atrix 2, Nexus, планшет Explay.
Спасибо всем, кто дочитал до конца. Было приятно поделиться интересной задачей.

Теги:

android development

Хабы:

Разработка под Android

«Умный» размер очереди в андроид

Описание

Приступим

Подробнее

Нормализация

Веса

Вычисление

Итог

Публикации

Истории

Работа

Ближайшие события