Pull to refresh

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

Reading time 7 min
Views 6K
В одном из проектов на работе встала, казалось бы, тривиальная задача: подгружать картинки и описания к ним с сервера, чтобы пользователь мог переключать их без задержки. Для этого использовался метод, который при каждом переключении проверял, сколько элементов осталось в очереди, и, если там осталось меньше определённого числа, подгружал очередной элемент. Дело решалось константой, равной 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.
Спасибо всем, кто дочитал до конца. Было приятно поделиться интересной задачей.
Tags:
Hubs:
+28
Comments 1
Comments Comments 1

Articles