Блог

У меня есть общий вопрос, который касается того, возможно ли создать итераторы с нулевым распределением в Javascript. Обратите внимание, что под «итератором» я не женат на текущем определении итератора в ECMAScript, а просто на общем шаблоне для перебора пользовательских диапазонов.

Чтобы конкретизировать проблему, скажем, у меня есть список, подобный [5, 5, 5, 2, 2, 1, 1, 1, 1] и я хочу сгруппировать соседние повторения вместе и обработать их в форме, которая больше похожа на [5, 3], [2, 2], [1, 4]. Затем я хочу получить доступ к каждой из этих пар внутри цикла, что-то вроде «для каждой пары в сгруппированном (массиве), сделайте что-нибудь с pair». Кроме того, я хочу повторно использовать этот алгоритм группировки во многих местах и, что особенно важно, в некоторых действительно горячих внутренних циклах (думаю, миллионы циклов в секунду).

Вопрос: Существует ли шаблон итерации для выполнения этого, который имеет нулевые накладные расходы, как если бы я сам написал цикл вручную?

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

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

 function sumPairs(array) {
  let sum = 0

  for (let i = 0; i != array.length; ) {
    let elem = array[i  ], count = 1
    while (i < array.length amp;amp; array[i] == elem) { i  ; count  ; }
    
    // Here we can actually use the pair (elem, count)
    sum  = elem   count
  }

  return sum
}
  

Использование шаблона посетителя.Мы можем написать reduceGroups функцию, которая будет вызывать заданное visitor(acc, elem, count) для каждой пары (elem, count) , аналогично обычному Array.reduce методу. С этим наши вычисления становятся несколько понятнее для чтения.

 function sumPairsVisitor(array) {
  return reduceGroups(array, (sofar, elem, count) => sofar   elem   count, 0)
}
  

К сожалению, Firefox, в частности, по-прежнему выделяет при запуске этой функции, если определение замыкания не перемещается вручную за пределы функции. Кроме того, мы теряем способность использовать управляющие структуры, например break , если мы не усложним интерфейс сильно.

Написание пользовательского итератора.Мы можем создать пользовательский «итератор» (не итератор ES6), который предоставляет elem count свойства and , empty свойство, указывающее, что больше не осталось пар, и next() метод, который обновляет elem и count до следующей пары. Потребляющий код выглядит следующим образом:

 function sumPairsIterator(array) {
  let sum = 0
  for (let iter = new GroupIter(array); !iter.empty; iter.next())
    sum  = iter.elem   iter.count
  return sum
}
  

Я нахожу этот код самым простым для чтения, и мне кажется, что это должен быть самый быстрый метод абстракции. (В лучшем случае скалярная замена может полностью свернуть определение итератора в функцию. Во втором лучшем случае должно быть ясно, что итератор не экранирует цикл for , поэтому он может быть распределен по стеку). К сожалению, и Chrome, и Firefox, похоже, выделяют здесь.

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

Я бы также согласился с постпроцессором Javascript (возможно, компилятором закрытия Google?) который способен выполнить это.

Проверьте это. Я не тестировал его производительность, но она должна быть хорошей.

( ) (в основном) совместим с итераторами ES6.
(-) принесено ...GroupingIterator.from(arr) в жертву, чтобы не создавать объект-значение (imo. garbage). Это в основном в приведенном выше пункте.
afaik, основным вариантом использования для этого в любом случае является for..of цикл.
( ) не создано объектов (GC)
( ) объединение объектов для итераторов; (снова GC)
( ) совместимость с управляющими структурами, такими как break

 class GroupingIterator {
  /* object pooling */
  static from(array) {
    const instance = GroupingIterator._pool || new GroupingIterator();
    GroupingIterator._pool = instance._pool;
    instance._pool = null;

    instance.array = array;
    instance.done = false;

    return instance;
  }

  static _pool = null;
  _pool = null;

  /* state and value / payload */

  array = null;
  element = null;
  index = 0;
  count = 0;

  /* IteratorResult interface */

  value = this;
  done = true;

  /* Iterator interface */

  next() {
    const array = this.array;
    let index = this.index  = this.count;

    if (!array || index >= array.length) {
      return this.return();
    }

    const element = this.element = array[index];
    while (  index < array.length) {
      if (array[index] !== element) break;
    }
    this.count = index - this.index;
    return this;
  }

  return() {
    this.done = true;
    // cleanup
    this.element = this.array = null;
    this.count = this.index = 0;

    // return iterator to pool
    this._pool = GroupingIterator._pool;
    return GroupingIterator._pool = this;
  }
  
  /* Iterable interface */

  [Symbol.iterator]() {
    return this;
  }
}


var arr = [5, 5, 5, 2, 2, 1, 1, 1, 1];

for (const item of GroupingIterator.from(arr)) {
  console.log("element", item.element, "index", item.index, "count", item.count);
}