Как работает эта функция возвращающая элементы одного массива отсутствующие у другого?

Question

[Аркадий Тагиров]

Вот код:

function diffArray(arr1, arr2) {
  var diff = function(a, b) {
    return a.filter(function(value) { return b.indexOf(value) === -1; });
};
return diff(arr1, arr2).concat(diff(arr2, arr1));
}

diffArray([1, "calf", 3, "piglet"], [1, "calf", 3, 4]);
//Возвращает: ["piglet",4]

Я не понимаю как return b.indexOf(value) === -1; возвращает элемент который отсутствует в arr2, но присутствует в arr1.
Спасибо за ответ.

Comments

[Hyubert]

Метод filter() вызывает переданную функцию callback (в этом случае это колбэк = function(value) { return b.indexOf(value) === -1; }) один раз для каждого элемента, присутствующего в массиве, и конструирует новый массив со всеми значениями

[Hyubert]

а о indexOf здесь

Answer 1

[holymotion]

У вас есть функция diffArray, она вызывается с переданными в неё 2мя массивами, данная функция (diffArray) возвращает результат вызова вложенных функции diff (и конкатенация их результатов)

Во вложенной функции, мы вызываем метод filter, в пример выше filter возвращает новый массив из элементов прошедших проверку на вхождение подстрок. Метод indexOf для Array, ищет у указанного массива "b" указанное значение (value) массива "a", в случае "не нахождения" возвращается -1
Получается что мы проходимся по всем элементам массива a ища несовпадения в массиве b, результат этого прохождения - новый массив.

Answer 2

[nirvimel]

Как она работает? - УЖАСНО! Потому что, не смотря на красивый вид, ее вычислительная сложность составляет O (m * n) ! И это неприемлемо для задачи, которая имеет простые решения с меньшей вычислительной сложностью.

function diff(a, b) {
    const b_set = new Set(b);
    return a.filter(x => !b_set.has(x));
}

console.log(diff([1, 2, 3, 4], [5, 4, 3, 2])); // result === [1]

Вот пример решения той же задачи за O (m + n) (изначально я тут ошибся с оценкой сложности, но в комментах мы вместе с Interface пришли к истине в этом вопросе).

Comments

[Hyubert]

обожаю когда используют стрелочную функцию (нет)

[nirvimel]

Hyubert: (нет) ?

[Hyubert]

nirvimel: сарказм

[Aves]

nirvimel Во первых, там не m * n, а та же m * log(n), а во вторых, в случае js говорить о вычислительной сложности - это гадать на кофейной гуще, слишком много зависит от движка и обстоятельств. https://jsperf.com/diffarray - в chromium 56 indexOf в 2 раза быстрее.

[nirvimel]

Aves:
1. Вычислительная сложность - это свойство алгоритма и структуры данных, а не реализации.
2. В 2 раза быстрее или в 22 раза - это просто константа, которая не учитывается в разговоре о вычислительной сложности.
3. Поиск в неотсортированном массиве (indexOf) всегда линейно завит от его размера, это свойство структуры данных.

[Aves]

nirvimel: 1. Алгоритмически has и indexOf обладают одинаковой сложностью.
2. Какой смысл говорить о абстрактной вычислительной сложности, тем более словами "УЖАСНО" и "неприемлемо", если производительность от нее не зависит?

[Interface]

Hyubert что не так со стрелочными функциями?

[Hyubert]

Interface: не нрависть мне что если его использовать то нужет babel

[Interface]

Hyubert: нуу.. логично-вытекающий вопрос: что не так с babel? :) Можно и не babel'ем пользоваться кстати говоря. Их сейчас уже много всего поддерживает нативно caniuse.com/#search=arrow%20function. Например node. Да и в данном случае, использовалось это сугубо в демострационных целях.

[Hyubert]

Interface: 70% поддержки не очень много, да и лучше подождать пока стандартом станет ES6, а пока и без них обойдусь

[Interface]

Hyubert стандартом? Он же от июня 2015, да и называется ECMAScript 2015. Многие уже async / await используют во всю.

[nirvimel]

Aves: На масштабах чуть крупнее HelloWorld решает вычислительная сложность, а не реализация - https://jsperf.com/yet-another-diff-array

[nirvimel]

Hyubert: Почему нормальных разработчиков должны волновать проблемы несчастных юзеров IE?

[Hyubert]

nirvimel: не должно, но если это, хотябы 10% пользователей, то будет

[Interface]

nirvimel https://jsperf.com/yetanotherdiffarray3 те же масштабы, только массивы другого вида - результат уже другой. Так что, думаю, здесь нельзя выделить серебрянной пули. Плюс надо понимать что поиск в хэш таблице тоже не бесплатная операция

[nirvimel]

Interface: Поиск в хештаблице идет за O(log(n)), так что это почти бесплатная операция. А вот построение хештаблицы из неотсортированного массива - O(n), и это уже серьезно.
В итоге вся функция выполняется за O(n + m * log(n)) (да, я немного ошибся с первоначальной оценкой в ответе), но это все-таки меньше, чем O(n * m).

[Interface]

nirvimel: я больше про то, что если у нас массив из 2 элементов (грубо говоря) то операция хэширования займет больше времени, чем два сравнения. Википедия кстати говорит, что поиск в хэш таблице - О(1) (https://en.wikipedia.org/wiki/Hash_table#Advantages). Но я тут упустил из внимания то, что это Set, а не объект. И что у него внутри не нашел еще.

[nirvimel]

Interface: О(1) - нижняя оценка, O(n) - верхняя, а средняя зависит от уровня заполнения. Но при заполнении < 1/2 таки ближе к О(1), чем к O(log(n)). Тут я опять признаю, что изначально ошибся. Но истина дороже!

[nirvimel]

Interface: В вашем примере 7 << 100000 (много меньше) и чрезвычайно высока вероятность встретить случайное целое от нуля до семи среди самых первых элементов огромного массива. Поэтому при вызове indexOf фактически не происходит полного сканирования массива и значение размера массива теряет смысл. При этом new Set() по-прежнему делает проход по всему массиву, на том и проигрывает.

[Interface]

nirvimel: это вообщем то понятно. Вообще получилось что изначально хотел привести другой тест, но меня занесло не в ту степь :D https://jsperf.com/yetanotherdiffarray44/1 - вот этот тест. Мой посыл в том, что с ростом "серьезности" может расти не длина массивов, а их число -> оптимизация способная повысить скорость обработки 1-го большого массива, но требующая "подготовки" в данном случае может сыграть в минус. Хотя, должен сказать, ваше решение для общего случая мне нравится больше.