Все способы перебора массива в JavaScript

http://stackoverflow.com/questions/9329446/for-each-over-an-array-in-javascript
  • Перевод

Содержание:


  • I. Перебор настоящих массивов
    1. Метод forEach и родственные методы
    2. Цикл for
    3. Правильное использование цикла for...in
    4. Цикл for...of (неявное использование итератора)
    5. Явное использование итератора

  • II. Перебор массивоподобных объектов
    1. Использование способов перебора настоящих массивов
    2. Преобразование в настоящий массив
    3. Замечание по объектам среды исполнения



I. Перебор настоящих массивов


На данный момент есть три способа перебора элементов настоящего массива:
  1. метод Array.prototype.forEach;
  2. классический цикл for;
  3. «правильно» построенный цикл for...in.

Кроме того, в скором времени, с появлением нового стандарта ECMAScript 6 (ES 6), ожидается еще два способа:
  1. цикл for...of (неявное использование итератора);
  2. явное использование итератора.

1. Метод forEach и родственные методы


Если ваш проект рассчитан на поддержку возможностей стандарта ECMAScript 5 (ES5), вы можете использовать одно из его нововведений — метод forEach.

Пример использования:
var a = ["a", "b", "c"];
a.forEach(function(entry) {
    console.log(entry);
});

В общем случае использование forEach требует подключения библиотеки эмуляции es5-shim для браузеров, не имеющих нативной поддержки этого метода. К ним относятся IE 8 и более ранние версии, которые до сих пор кое-где еще используются.

К достоинствам forEach относится то, что здесь не нужно объявлять локальные переменные для хранения индекса и значения текущего элемента массива, поскольку они автоматически передаются в функцию обратного вызова (колбек) в качестве аргументов.

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

forEach предназначен для перебора всех элементов массива, но кроме него ES5 предлагает еще несколько полезных методов для перебора всех или некоторых элементов плюс выполнения при этом каких-либо действий с ними:
  • every — возвращает true, если для каждого элемента массива колбек возвращает значение приводимое к true.
  • some — возвращает true, если хотя бы для одного элемента массива колбек возвращает значение приводимое к true.
  • filter — создает новый массив, включающий те элементы исходного массива, для которых колбек возвращает true.
  • map — создает новый массив, состоящий из значений возращаемых колбеком.
  • reduce — сводит массив к единственному значению, применяя колбек по очереди к каждому элементу массива, начиная с первого (может быть полезен для вычисления суммы элементов массива и других итоговых функций).
  • reduceRight — работает аналогично reduce, но перебирает элементы в обратном порядке.

2. Цикл for


Старый добрый for рулит:

var a = ["a", "b", "c"];
var index;
for (index = 0; index < a.length; ++index) {
    console.log(a[index]);
}

Если длина массива неизменна в течение всего цикла, а сам цикл принадлежит критическому в плане производительности участку кода (что маловероятно), то можно использовать «более оптимальную» версию for с хранением длины массива:

var a = ["a", "b", "c"];
var index, len;
for (index = 0, len = a.length; index < len; ++index) {
    console.log(a[index]);
}

Теоретически этот код должен выполняться чуть быстрее, чем предыдущий.

Если порядок перебора элементов не важен, то можно пойти еще дальше в плане оптимизации и избавиться от переменной для хранения длины массива, изменив порядок перебора на обратный:

var a = ["a", "b", "c"];
var index;
for (index = a.length - 1; index >= 0; --index) {
    console.log(a[index]);
}

Тем не менее, в современных движках JavaScript подобные игры с оптимизацией обычно ничего не значат.

3. Правильное использование цикла for...in


Если вам посоветуют использовать цикл for...in, помните, что перебор массивов — не то, для чего он предназначен. Вопреки распространенному заблуждению цикл for...in перебирает не индексы массива, а перечислимые свойства объекта.

Тем не менее, в некоторых случаях, таких как перебор разреженных массивов, for...in может оказаться полезным, если только соблюдать при этом меры предосторожности, как показано в примере ниже:

// a - разреженный массив
var a = [];
a[0] = "a";
a[10] = "b";
a[10000] = "c";
for (var key in a) {
    if (a.hasOwnProperty(key) &&
        /^0$|^[1-9]\d*$/.test(key) &&
        key <= 4294967294) {
        console.log(a[key]);
    }
}

В данном примере на каждой итерации цикла выполняется две проверки:
  1. то, что массив имеет собственное свойство с именем key (не наследованное из его прототипа).
  2. то, что key — строка, содержащая десятичную запись целого числа, значение которого меньше 4294967294. Откуда берется последнее число? Из определения индекса массива в ES5, из которого следует, что наибольший индекс, который может иметь элемент в массиве: (2^32 - 2) = 4294967294.

Конечно, такие проверки отнимут лишнее время при выполнении цикла. Но в случае разреженного массива этот способ более эффективен, чем цикл for, поскольку в этом случае перебираются только те элементы, которые явно определены в массиве. Так, в примере выше будет выполнено всего 3 итерации (для индексов 0, 10 и 10000) — против 10001 в цикле for.

Чтобы не писать такой громоздкий код проверок каждый раз, когда требуется перебор массива, можно оформить его в виде отдельной функции:

function arrayHasOwnIndex(array, key) {
    return array.hasOwnProperty(key) && /^0$|^[1-9]\d*$/.test(key) && key <= 4294967294;
}

Тогда тело цикла из примера значительно сократится:

for (key in a) {
    if (arrayHasOwnIndex(a, key)) {
        console.log(a[key]);
    }
}

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

for (key in a) {
    if (a.hasOwnProperty(key) && String(parseInt(key, 10)) === key) {
        console.log(a[key]);
    }
}

4. Цикл for...of (неявное использование итератора)


ES6, пока все еще пребывающий в статусе черновика, должен ввести в JavaScript итераторы.

Итератор — это реализуемый объектом протокол, который определяет стандартный способ получения последовательности значений (конечной или бесконечной).
Итератор — это объект, в котором определен метод next() — функция без аргументов, возвращающая объект с двумя свойствами:
  1. done (boolean) — принимает значение true, если итератор достиг конца итерируемой последовательности. В противном случае имеет значение false.
  2. value — определяет значение, возвращаемое итератором. Может быть не определено (отсутствовать), если свойство done имеет значение true.

Многие встроенные объекты, в т.ч. настоящие массивы, имеют итераторы по умолчанию. Простейший способ применения итератора в настоящих массивах — использовать новую конструкцию for...of.

Пример использования for...of:

var val;
var a = ["a", "b", "c"];
for (val of a) {
    console.log(val);
}

В приведенном примере цикл for...of неявно вызывает итератор объекта Array для получения каждого значения массива.

5. Явное использование итератора


Итераторы можно также использовать и явно, правда, в этом случае код становится значительно сложнее, по сравнению с циклом for...of. Выглядит это примерно так:

var a = ["a", "b", "c"];
var it = a.entries();
var entry;
while (!(entry = it.next()).done) {
    console.log(entry.value[1]);
}

В данном примере метод Array.prototype.entries возвращает итератор, который используется для вывода значений массива. На каждой итерации entry.value содержит массив вида [ключ, значение].

II. Перебор массивоподобных объектов


Кроме настоящих массивов, в JavaScript встречаются также массивоподобные объекты. С настоящими массивами их роднит то, что они имеют свойство length и свойства с именами в виде чисел, соответствующие элементам массива. В качестве примеров можно назвать DOM коллекции NodeList и псевдомассив arguments, доступный внутри любой функции/метода.

1. Использование способов перебора настоящих массивов


Как минимум большинство, если не все, способы перебора настоящих массивов могут быть применены для перебора массивоподобных объектов.

Конструкции for и for...in могут быть применены к массивоподобным объектам точно тем же путем, что и к настоящим массивам.

forEach и другие методы Array.prototype также применимы к массивоподобным объектам. Для этого нужно использовать вызов Function.call или Function.apply.

Например, если вы хотите применить forEach к свойству childNodes объекта Node, то это делается так:

Array.prototype.forEach.call(node.childNodes, function(child) {
    // делаем что-нибудь с объектом child
});

Для удобства повторного использования этого приема, можно объявить ссылку на метод Array.prototype.forEach в отдельной переменной и использовать ее как сокращение:

// (Предполагается, что весь код ниже находится в одной области видимости)
var forEach = Array.prototype.forEach;

// ...

forEach.call(node.childNodes, function(child) {
    // делаем что-нибудь с объектом child
});

Если в массивоподобном объекте имеется итератор, то его можно использовать явно или неявно для перебора объекта таким же способом, как и для настоящих массивов.

2. Преобразование в настоящий массив


Есть также еще один, очень простой, способ перебора массивоподобного объекта: преобразовать его в настоящий массив и использовать любой из рассмотренных выше способов перебора настоящих массивов. Для преобразования можно использовать универсальный метод Array.prototype.slice, который может быть применен к любому массивоподобному объекту. Делается это очень просто, как показано в примере ниже:

var trueArray = Array.prototype.slice.call(arrayLikeObject, 0);

Например, если вы хотите преобразовать коллекцию NodeList в настоящий массив, вам нужен примерно такой код:

var divs = Array.prototype.slice.call(document.querySelectorAll("div"), 0);

Update: Как было отмечено в комментариях rock и torbasow, в ES6 вместо Array.prototype.slice можно использовать более наглядный метод Array.from.

3. Замечание по объектам среды исполнения


Если вы применяете методы Array.prototype к объектам среды исполнения (таких как DOM коллекции), то вы должны иметь в виду, что правильная работа этих методов не гарантирована во всех средах исполнения (в т.ч. в браузерах). Это зависит от поведения конкретного объекта в конкретной среде исполнения, если точнее, от того, как в этом объекте реализована абстрактная операция HasProperty. Проблема в том, что сам стандарт ES5 допускает возможность неправильного поведения объекта по отношению к этой операции (см. §8.6.2).

Поэтому важно тестировать работу методов Array.prototype в каждой среде исполнения (браузере), в которой планируется использование вашего приложения.
Поделиться публикацией
Похожие публикации
AdBlock похитил этот баннер, но баннеры не зубы — отрастут

Подробнее
Реклама
Комментарии 61
  • +4
    Автор забыл самый быстрый (пруф)
    var i = testData.length;
    
    while (i--){
        console.log(testData[i]);
    }
    
    • –3
      Просто другая запись аналогичного цикла for:
      for (var i = testData.length; i--; ) {
      console.log(testData[i]);
      }
      • +3
        В хроме показывает «14% slower».
        • +2
          • 0
            Может, разница из-за того, что я юзаю линух.
            • 0
              Да там большую роль уже играет какие сработали оптимизации в движке, развернулся ли цикл и прочее. Синтетический тест такой синтетический.
        • –5
          AFAIK, принято считать, что цикл while эквивалентен for, во всяком случае в JavaScript. Наверное поэтому автор и не упомянул while.
          Да, и у вас в коде ошибка, должно быть:
          var i = testData.length - 1;
          • +7
            Не должно
            • +5
              Да, не должно. Это я ошибся.
          • 0
            Я когда то делал тесты ( уже не найду ), и там зависит от браузера и того что перебирать, на сколько я помню DOM быстрее перебирать с начала, да и разница там была минимальная и частенько такой вариант проигрывал, зависит от браузера.
            Скорость перебора forEach тоже зависит от браузера ( тоже делал тесты ), в хроме forEach работает по скорости почти как for, но тоже зависит от данных.

            П.с Нужно избегать использования delete в цикле, из за него скорость падает в разы
          • 0
            Немного поздновато но все же.

            jsperf.com/for-until-length-vs-until-undefined/18

            В хроме быстрей for backwards в лисе while backwards.
            • 0
              Отмечу, что без return total хром вообще пропускает вычисления. (для наглядности jsperf.com/for-until-length-vs-until-undefined/20 )

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

              Реальные тесты это пипец, как не просто =) Лучше всего создать N массивов с рендомными значениями, дальше внутри теста при каждом следующем вызове брать следующий массив пока указатель не станет равен N. (и дальше сбросить его). Если массивов больше нескольких сотен, то хороший шанс, что оптимизатор не поймёт что не так. Результат вычислений так же следует куда-то складываь (например window.result += total в конце функции)

              Скажу сразу: если на простых операциях (перебор, сложения/вычитания, математика и строки) вы видите большую дельту ФФ и хрома — значит где-то тест оптимизирован до безобразия (пропущен), что маловероятно на реальных данных.
              • 0
                Ну перед тем как комментить я себе написал тест под NodeJS примерно как вы описали.
                Геренились массивы с рандомными данными. Итог был в пользу обратного for'a.
                А в целом не особо критично главное что forEach зло. =)
                • 0
                  Попробовал изголиться на реальных данных несколько приумноженных. iojs 1.5 while с зада оказался лучшим вариантом =)
                  • 0
                    Странно, разницы в коде быть не должно…
                    Т.е. что с конца идти в for что с начала во while по идее время должно отличаться менее чем на 5% + если тесты скорости запускать «зеброй» (не по тесту на секцию, а чередовать) время вообще отличаться не должно особо…
                    А код в студию можно?)

                    Поясню: for (i = 0; i < l; i++) и i=l; while (i >= 0) i--; превращаются фактически в одни и те же команды JIT, разве что минус и плюс разнятся.

                    А что forEach зло так это старо, как мир =) Кофескрипт в помощь ленивым так сказать =)
              • 0
                --i
                

                А так будет еще немного быстрее.
              • +1
                Недавно столкнулся с тем, что привычный мне способ пробегать по массиву, используя map, reduce, filter, every, any и пр. (десятки их) методы, внутри генераторов принуждает меня либо отказаться от заветных yield-ов (потому что они работают только в теле генератора, а callback — метод), либо использовать встроенные в синтаксис языка конструкции. А учитывая что nodejs всё никак не хочет добавить for-of стало как-то грустно.

                Поглядывая на io, я понимаю, почему они решили отколоться. А ещё там есть стрелочные функции… полагаю, что это очень удобная штука для функционального подхода.
                • 0
                  нет там стрелочных функций
                  • 0
                    Правда? :( Ориентировался на этот комментарий (--harmony-arrow-functions). Руки проверить пока не дошли.
                    • +1
                      да с флагом работают
                      • 0
                        Кстати под Windows инсталлятор сносит нафиг ноду. Не знаю как под другими ОС.
                        Так что если хочется поэксперементировать только, то надо качать в чистом виде, а не инсталлер.
                        • 0
                          подтверждаю, правда я использую вот этот менеджер и оно конфликтит пока github.com/coreybutler/nvm-windows. Думаю написать автору по поводу поддержки io.js
                  • 0
                    Насчет устройства словаря в Python очень было приятно послушать доклад с одного из Python Meetup. Может, кому-нибудь пригодится.
                  • +1
                    var a = ["a", "b", "c"];
                    var entry;
                    while (!(entry = a.next()).done) {
                        console.log(entry.value);
                    }
                    

                    Итератор тут явно не получают, а у массива нет метода next.

                    Преобразование в настоящий массив

                    Про for-of с итераторами заикнулись, а про Array.from ни слова.
                    • +2
                      а у массива нет метода next.

                      Да, нет, и ни у одного объекта его пока нет. Пока это не стало стандартом. А как станет, и массив сможет иметь итератор.
                        • 0
                          Не пойму, о чем вы пытаетесь спорить со мной (или с OP). О том, что ни у одного объекта пока нет метода next, или что массив сможет иметь итератор?
                          • +1
                            Пытаюсь спорить? :) Констатирую факт, что пример не верный в принципе. И стандартные возможности протокола итераторов сейчас поддерживаются везде, кроме IE, да и на нём легко реализуются полифилами.
                            • 0
                              Констатирую факт, что пример не верный в принципе

                              Да, вы правы. Возможно, вам стоит сообщить об этом автору (на SO)… А мне придется менять пример.
                              • 0
                                Поправка: У автора все правильно. Оказывается, это я не так скопировал пример. Уже поправил.
                            • +1
                              Как я понял, метод next есть. Но не у массива, а у его итератора и вам нужно переписать код, чтобы он сначала получал итератор, а потом уже использовал next, чтобы получить код, эквивалентный for of. То, что есть, не является эквивалентным кодом.
                              • 0
                                Вы правы. Итератор можно получить через вызов Array.prototype.values() или Array.prototype.entries(). В оригинале так и было, но я умудрился скопипастить пример с ошибками.
                      • –1
                        Поясните за этот регексп /^0$|^[1-9]\d*$/, он там для чего и почему бы не заменить его на ^\d+$ или даже что-то такое «Number(key) === key && key%1 === 0»
                        Там же — пишете что «key — строка» и проверяете как «key <= 4294967294»
                        • 0
                          Поясните за этот регексп /^0$|^[1-9]\d*$/

                          Это:
                          строка, содержащая десятичную запись целого числа, значение которого меньше 4294967294

                          ^\d+$ допускает недесятичные числа как напр-р: 012.

                          Там же — пишете что «key — строка» и проверяете как «key <= 4294967294»

                          При сравнении с числом строка всегда приводится к числу.

                          Вообще, как указано в статье, это формальная (я бы даже сказал занудная) проверка. В большинстве случаев можно использ-ть более простую как: String(parseInt(key, 10)) === key
                          • +3
                            (it >>> 0) === +it
                            

                            Но с наркотиками лучше не баловаться, а иначе не пригодится.
                            • +1
                              +it === (it|0)
                              

                              Тем более, что нам нужны только целые числа.
                              • +2
                                У вас — toInt32, а нужен toUInt32, разницу чуете? :)
                                • 0
                                  А, да :)
                                  Честно говоря, не так много практики в строго типизированных языках, сколько хотелось бы, так что и в JS это для меня не всегда очевидно.
                        • +1
                          Если вас беспокоят возможные затраты на вызов колбека для каждого элемента, не волнуйтесь и прочитайте это.

                          Тот тест по ссылке уже кто-то расширил, у меня на Chrome/Firefox, ForEach медленнее чем for в 50-60 раз.
                          • +1
                            У меня в firefox forEach медленнее в ≈30 раз, в Chromium — >60 раз. Подозреваю, что если forEach будут активно использовать, то браузеры начнут агрессивно встраивать код на основании предположений о типе this, а до тех пор придётся терпеть.

                            Думаю, что этот момент можно несколько приблизить, написав популярный(!) benchmark, проверяющий скорость выполнения ES6‐конструкций.
                          • 0
                            в javascript играет роль .length в условии цикла или нет? просто в php лучше присваивать переменной count перед циклом, но здесь в примерах везде идет в условии…
                            • +1
                              Насколько понимаю, в современных движках — нет.
                              • +3
                                Для каждого браузера по разному. Но, например, в текущем Chrome код, который не сохраняет длину массива в локальную переменную, будет работать быстрее. Свеженькая статья на эту тему.
                                • +1
                                  Я не сказал, что он будет работать быстрее. Я скорее сказал: это иллюзия, что он будет работать медленнее «потому что length в цикле больше никто не читает» — как CPU положит, так и будет работать :) У меня есть машина (с Xeonом) там у меня получилось быстрее — я это исключительно для того в пост добавил, чтобы показать, что это все замеры погоды в северном полушарии.
                                • +1
                                  Если перебор коллекции, а не массива, то очень желательно сохранить длину, а по хорошему сохраняются всегда чтобы не пропустить, просто best practices, но сейчас возможно это уже и не так актуально.
                                • +7
                                  Ну и ряд функциональных подходов
                                  • Tail optimized recursion
                                    function loop(fn) {
                                        var index = 0;
                                        
                                        return function over(array) {
                                            if (index >= array.length) {
                                                return;
                                            }
                                            fn(array[index], index, array);
                                            index++;
                                            over(array);
                                        };
                                    }
                                    
                                    var consoleLog = loop(function (item, index, array) {
                                        console.log(item, index, array);
                                    });
                                    
                                    consoleLog([1, 2, 3, 4]);
                                    

                                    jsbin.com/rimabu/3/edit?js

                                  • Y Combinator
                                    function Y(le) {
                                        return function(f) {
                                            return f(f);
                                        }(function(f) {
                                            return le(function(x) {
                                                return (f(f))(x);
                                            });
                                        });
                                    }
                                    
                                    function loop(fn) {
                                        var index = index || 0;
                                        return function (over) {
                                            return function (array) {
                                                if (index >= array.length) {
                                                    return;
                                                }
                                                fn(array[index], index, array);
                                                index++;
                                                over(array);
                                            };
                                        };
                                    }
                                    
                                    var consoleLog = Y(loop(function (item, index, array) {
                                        console.log(item, index, array);
                                    }));
                                    
                                    consoleLog([1, 2, 3, 4]);
                                    
                                    

                                    jsbin.com/ligawa/2/edit?js
                                  • 0
                                    Для Chrome и FF пока самый практичный вариант это прямой перебор с предварительным вычислением длины массива.
                                    jsperf.com/function-call-cost-on-ie6/9

                                    При этом для FF кэш длины массива не так важен.
                                    • +1
                                      Для преобразования можно использовать универсальный метод Array.prototype.slice, который может быть применен к любому массивоподобному объекту.


                                      Или Array.from() из ECMAScript 6, что читается яснее.
                                      • 0
                                        Через setTimeout еще можно перебрать (в этом случае как правило в массиве функции), допустим для тяжелых циклов чтобы браузер не выдавал окна о долгом выполнении скриптов, неблокирующее/асинхронное выполнение ряда функций.
                                        • 0
                                          setImmediate и его полифил куда быстрее. Так же бить на «пачки» или транзакции.
                                        • 0
                                          Нормальная статья. Стоит упомянуть, что делать Array.prototype.slice.call(arguments) не рекомендуют.
                                          • –1
                                            arguments можно преобразовать с помощью Array.apply(0, arguments) (до тех пор, пока они не состоят из одного числа).
                                          • –2
                                            На мой взгляд не был упомянут вот такой очень удобный и универсальный подход:
                                            var items = [1, 2, 3];
                                            [].forEach.call(items, function(item, index) {
                                              console.log(item, index);
                                            });
                                            
                                            • +1
                                              1. forEach упомянут.
                                              2. Зачем создавать ещё один массив, и брать из него forEach, если он итак есть в items? o_O
                                              • 0
                                                Имелось ввиду, что items — не массив.
                                                • 0
                                                  А, ясно.
                                                  Но этот способ упомянут:
                                                  ...forEach и другие методы Array.prototype также применимы к массивоподобным объектам. Для этого нужно использовать вызов Function.call или Function.apply.
                                                  Например, если вы хотите применить forEach к свойству childNodes объекта Node, то это делается так...
                                                  • 0
                                                    Я так думаю, что Waxer просто хотел сказать, что вместо Array.prototype можно использовать []. Это короче. Но, в свете того, что мы пытаемся найти самый быстрый способ, создание еще одного инстанса Array не целесообразно.
                                            • +1
                                              Разреженные массивы — очень плохая практика: V8 и SpiderMonkey очень много памяти съедают, при чём отследить не просто: 10 элементов на всём диапазоне может норм, а 100 уже хоп(!) и +200Мб. (ВМ-е JIT-а выдаётся не так много памяти, а если включить мобильные версии в кандидаты исполнения, то...)
                                              Вывод: как правило, если нужен for ... in для массива, значит что-то идёт не так)

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