Какая разница между фильтрацией по аккумулятору / току в методе уменьшения - PullRequest
Новая
       47

Какая разница между фильтрацией по аккумулятору / току в методе уменьшения

1 голос
/ 24 января 2020

При объединении в цепочку Array.prototype.reduce с Array.prototype.filter какая разница (концептуально и под колпаком) при фильтрации по текущему значению вместо значения аккумулятора? 

// function union creates a union of all values that appear among arrays
// example A

const union = (...arrays) => {
    return arrays.reduce((acc, curr) => {
      const newElements = acc.filter(el => !curr.includes(el));

      return curr.concat(newElements);
    });
  };
 console.log(union([1, 10, 15, 20], [5, 88, 1, 7], [1, 10, 15, 5]));

// output (7) [1, 10, 15, 5, 88, 7, 20]

// example B

const union = (...arrays) => {
    return arrays.reduce((acc, curr) => {
      const newElements = curr.filter(el => !acc.includes(el));

      return acc.concat(newElements);
    });
  }; 
  console.log(union([1, 10, 15, 20], [5, 88, 1, 7], [1, 10, 15, 5]));

//output (7) [1, 10, 15, 20, 5, 88, 7]

Разница в выходе будет предположить, что порядок, в котором оцениваются массивы, является «противоположным». Насколько я могу судить, при использовании arr.filter значения оцениваются от начала до конца, а для curr.filter верно обратное. Кроме того, зависят ли они от каких-либо других последствий, если вы фильтруете через аккумулятор или текущее значение? Может ли это вызвать ошибку в другом контексте?

Ответы [ 2 ]

1 голос
/ 24 января 2020

Проблема не в использовании filter внутри reduce, а в том, что касается порядка, в котором вы используете acc и curr.

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

const testData = [
  [1, 10, 15, 20],
  [5, 88, 1, 7],
  [1, 10, 15, 5],
]

Теперь нам нужно просмотреть каждую версию функции и посмотреть, что выводится на каждом этапе.

Стоит отметить (что я не знал до этого вечера!), Что если reduce не получит initialValue в качестве второго аргумента, он будет использовать первый элемент в массиве как initialValue , Это означает, что нам нужно рассматривать только 2 выполнения каждой функции вместо 3. ?

Пример A 

const union = (...arrays) => {
  return arrays.reduce((acc, curr) => {
    const newElements = acc.filter(el => !curr.includes(el))

    return curr.concat(newElements)
  })
}

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

Важно то, что мы помещаем newElements в конец curr. Вот почему порядок отличается для двух разных версий.

Первое исполнение 

const acc = [1, 10, 15, 20]
const curr = [5, 88, 1, 7]
const newElements = [10, 15, 20] // these elements exist in acc but not in curr
curr.concat(newElements) === [5, 88, 1, 7, 10, 15, 20]

Второе выполнение 

const acc = [5, 88, 1, 7, 10, 15, 20] // carried over from first execution
const curr = [1, 10, 15, 5]
const newElements = [88, 7, 20] // these elements exist in acc but not in curr
curr.concat(newElements) === [1, 10, 15, 5, 88, 7, 20]

Пример B 

const union = (...arrays) => {
  return arrays.reduce((acc, curr) => {
    const newElements = curr.filter(el => !acc.includes(el))

    return acc.concat(newElements)
  })
}

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

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

First выполнение 

const acc = [1, 10, 15, 20]
const curr = [5, 88, 1, 7]
const newElements = [5, 88, 7] // these elements exist in curr but not in acc
acc.concat(newElements) === [1, 10, 15, 20, 5, 88, 7]

второе выполнение 

const acc = [1, 10, 15, 20, 5, 88, 7] // carried over from first execution
const curr = [1, 10, 15, 5]
const newElements = [] // these elements exist in acc but not in curr
acc.concat(newElements) === [1, 10, 15, 20, 5, 88, 7]

Заключение

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

Кроме того, зависят ли они от каких-либо других последствий, если вы фильтруете через аккумулятор или текущее значение? Может ли это вызвать ошибку в другом контексте?

К счастью, нет никаких проблем с ошибками. Примечательно, однако, что вторая версия вашей функции на ~ 10% быстрее , чем первая версия. Я предполагаю, что это чисто случайно. Другой набор тестовых данных может дать разные результаты производительности.

0 голосов
/ 24 января 2020

В примере 1, к тому времени, когда вы объедините два списка, вы убедитесь, что acc эмулятор не будет содержать элементов из curr ent.

В примере 2 с другой стороны, вы должны убедиться, что curr ent не будет содержать элементов, которые уже присутствуют в acc umulator.

Разница заключается в конечном порядке, в котором элементы Появится

Я думаю, что оба примера не эффективны, поскольку они оба включают O(n2) сложность времени, так как вы вкладываете итерации. Второй, как утверждают другие, может быть немного более производительным, так как вложенные итерации будут выполняться для фрагмента, который предположительно короче, чем аккумулятор.

Я бы лучше написал больше или меньше как это: 

const union = (...tuples) => Array.from(
  new Set(
    tuples.flatMap(n => n),
  )
);



console.log(
  union([1, 10, 15, 20], [5, 88, 1, 7], [1, 10, 15, 5]),
);
...