Pull to refresh

Отложенная обработка массива

Reading time 4 min
Views 8.6K
Однажды, при разработке сложного приложения на JavaScript-е возникла непреодолимая проблема — большой массив в Internet Explorer (далее IE). Так как я изначально проверял работу в Chrome, то не замечал каких-либо проблем при использовании массивов. Скажу больше — вложенные массивы не вызывали чувства страха. Chrome легко справлялся с трудными задачами. Однако IE, в очень жёсткой форме, указал на все мои огрехи и недостатки кода, особенно на обработку Больших массивов.

В двух словах


Разрабатываемое приложение должно было, в режиме реального времени, реагировать на события приходящие с сервера. Для этих целей воспользовались библиотекой Socket.IO, что позволило легко реализовать двухстороннее общение с сервером. При этом приложение также было завязано на сторонний сервис, к которому я имел доступ только через внешнее REST API.

Слабым звеном оказался большой цикл который должен был обрабатывать массив данных, полученные как раз со стороннего сервиса. При этом приходилось в цикле одновременно изменять DOM модель. В этих случаях IE уходил в состояние глубокой задумчивости и естественно рвал соединение. Чисто внешне это было неприемлемо — блокировка приложения и постоянно крутящийся значок загрузки не могли удовлетворить заказчика. Да, многие могут справедливо указать на большие затраты при изменении DOM модели. И должен вас заверить, что эта часть проблемы была решена выносом всех изменений за пределы цикла. Однако основная проблема — разрыв соединения при обработке массива осталась.

Полный рефакторинг страшно пугал, так как уже были написаны тысячи строк кода. К тому же поджимали сроки. Именно в таких условиях родилась идея “отложенной”, частичной обработки массива.

Алгоритм


Массив логически разбивается на несколько диапазонов, обработку каждого из которых производим с задержкой. Суть работы представлена на рисунке:



Таким образом имея единый глобальный массив Array функция обрабатывает его по частям, с заранее заданной задержкой. Для асинхронного язык, которым является JavaScript, данная техника позволяет разгрузить основной поток (так же один единственный) при обработки очень больших массивов.

Основное тело обработчика:
//Lazy array processing
/**
* Input parameters
* params = {
*   outerFuntion : function(array, start, stop),
*   mainArray: []
*   startIndex: Int,
*   stepRange Int,
*   timeOut: Int,
*   callback: function()
*}
*/
var lazyProcessing = function(params) {
    var innerFunction = (function(_) {
        return function() {
           var arrayLength = _.mainArray.length,
               stopIndex   = _.startIndex + _.stepRange;
            if(arrayLength < stopIndex) {
                _.outerFunction(
                       _.mainArray,
                       _.startIndex,
                       arrayLength - _.startIndex);
                if(_.callback != undefined) {
                    _.callback();
                }
                return;
            } else {
                _.outerFunction(
                       _.mainArray,
                       _.startIndex,
                       stopIndex);
                _.startIndex += _.stepRange;
                lazyProcessing(_);
            }
        }
    })(params);
   
    setTimeout(innerFunction, params.timeOut);
};
//Outer function works with mainArray in given range
var func = function(mainArray, start, stop) {
    //TODO: this should be everything you want to do with elements of
    for (var i = start; i < stop; ++i) {
        // do something
    }
};

В теле функции lazyProcessing создается локальная функция innerFunction, которая замыкает в себе полученные параметры params. Это позволяет каждый раз, при рекурсивном вызове функции lazyProcessing из себя, сохранять уникальные параметры.

Функция innerFunction возвращает безымянную функция, которая выполняет следующие достаточно простые действия:
  1. Проверяет достижение конца глобального массива
  2. Вызывает внешнюю функцию outerFuntion с различными значениям stop
  3. В случае достижения конца массива — вызывает callback функцию
  4. В противном случае рекурсивно вызывает lazyProcessing.

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

При достижении конца массива может быть вызвана callback функция, но это опционально.

За и против


Естественно в данном решении есть свои подводные камни и недостатки:
  1. Если установить stepRange минимальным, при достаточно большом mainArray массиве, можно банально «упасть» по переполнению стека
  2. Поток все же будет блокироваться при вызове внешней outerFunction. Т.е. быстродействие напрямую будет зависеть от алгоритма обработки элементов массива
  3. “Лапша” из вложенных и возвращаемых функций смотрится не очень дружественно

Вместе с тем, частичная обработка массива через равные промежутки времени — не блокирует поток выполнения программы. Что позволяет обрабатывать другие callback функции.

Полный работающий пример:
//Test array
var test = [];
for(var i = 0; i < 100000; ++i) {
    test[i] = i;
}
//Lazy array processing
/*
params = {
    outerFuntion : function(array, start, stop),
    mainArray: []
    startIndex: Int,
    stepRange Int,
    timeOut: Int,
    callback: function()
}
*/
var lazyProcessing = function(params) {
    var _params = params;
    var innerFunction = (function(_) {
        return function() {
            var arrayLength = _.mainArray.length,
                stopIndex   = _.startIndex + _.stepRange;
            if(arrayLength < stopIndex) {
                _.outerFunction(
                    .mainArray,
                    _.startIndex,
                    arrayLength - _.startIndex);
                if(_.callback != undefined) {
                    _.callback();
                }
                return;
            } else {
                _.outerFunction(
                    _.mainArray,
                    _.startIndex,
                    stopIndex);
                _.startIndex += _.stepRange;
                lazyProcessing(_);
            }
        }
    })(_params);
   
    setTimeout(innerFunction, _params.timeOut);
};
//Test function works with array
var func = function(mainArray, start, stop) {
    //TODO: this should be everything
    //you want to do with elements of mainArray
    var _t = 0;
    for (var i = start; i < stop; ++i) {
        mainArray[i] = mainArray[i]+2;
        _t += mainArray[i];
    }
};
lazyProcessing({
        outerFunction: func,
        mainArray: test,
        startIndex: 0,
        stepRange: 1000,
        timeOut: 100,
        callback: function() {
                    alert("Done");
                  }
        });



PS. Пользователь zimorodok скинул замечательный пример — такой же по духу и по сути. Не могу не добавить его.
Проход по массиву с callback-ом для каждого элемент с возможностью задавать timeOut:
/*
example of use
var arr = ['masha','nadya', 'elena'];
iterate_async(arr, function (el, index, arr) {
    console.log(el + ' is #' + (index + 1));
}, 99);
*/
function iterate_async (arr, callback, timeout) {
	var item_to_proceed;

	item_to_proceed = 0;
	(function proceed_next () {
		if (item_to_proceed < arr.length) {
			setTimeout(function () {
				callback.call(arr, arr[item_to_proceed], item_to_proceed, arr);
				item_to_proceed += 1;
				proceed_next();
			}, timeout || 50);
		}
	}());
}
Tags:
Hubs:
+4
Comments 14
Comments Comments 14

Articles