10

Самый простой код для пересечения массивов на JavaScript

10

Заголовок: Как реализовать пересечение массивов в JavaScript без использования библиотек?

Описание проблемы: Мне нужно написать функцию для нахождения пересечения массивов в JavaScript. Я хотел бы, чтобы код был максимально простым и без использования сторонних библиотек.

Например, если я вызову:

intersection([1, 2, 3], [2, 3, 4, 5])

то ожидаю получить:

[2, 3]

Как я могу это реализовать?

5 ответ(ов)

1

Для нахождения пересечения двух массивов, если у вас уже есть отсортированные массивы, можно использовать два подхода: разрушительный и неразрушительный.

Разрушительный метод

Разрушительный метод является более простым и работает следующим образом:

/* Находит пересечение двух массивов разрушительно
 *
 * ПАРАМЕТРЫ
 *  a - первый массив, должен быть отсортирован
 *  b - второй массив, должен быть отсортирован
 *
 * ЗАМЕТКИ
 *  Состояние входных массивов не определено после 
 *  выполнения функции. Их следует (вероятно) удалить.
 *
 *  Должен иметь O(n) операций, где n = MIN(a.length, b.length)
 */
function intersection_destructive(a, b) {
  var result = [];
  while (a.length > 0 && b.length > 0) {
    if (a[0] < b[0]) {
      a.shift();
    } else if (a[0] > b[0]) {
      b.shift();
    } else { /* они равны */
      result.push(a.shift());
      b.shift();
    }
  }
  return result;
}

В этом методе мы постоянно сравниваем первые элементы обоих массивов. Если один из элементов меньше, он удаляется из массива, а если равен — добавляется в результат.

Неразрушительный метод

Неразрушительный метод немного сложнее, поскольку нам нужно отслеживать индексы:

/* Находит пересечение двух массивов неразрушительно
 *
 * ПАРАМЕТРЫ
 *  a - первый массив, должен быть отсортирован
 *  b - второй массив, должен быть отсортирован
 *
 * ЗАМЕТКИ
 *
 *  Должен иметь O(n) операций, где n = MIN(a.length, b.length)
 */
function intersect_safe(a, b) {
  var ai = 0, bi = 0;
  var result = [];

  while (ai < a.length && bi < b.length) {
    if (a[ai] < b[bi]) {
      ai++;
    } else if (a[ai] > b[bi]) {
      bi++;
    } else { /* они равны */
      result.push(a[ai]);
      ai++;
      bi++;
    }
  }
  return result;
}

В этом варианте мы используем два указателя ai и bi, чтобы отслеживать текущие индексы в массиве a и b, что позволяет нам не изменять сами массивы.

Итог

Оба метода имеют временную сложность O(n), где n — это минимальная длина одного из массивов. Выбор метода зависит от требований вашего конкретного случая — хотите ли вы сохранить исходные массивы нетронутыми или нет.

0

Вы можете использовать библиотеки Underscore.js или lodash.js для нахождения пересечения массивов. Ваш пример использует метод _.intersection, который возвращает массив, содержащий все элементы, которые присутствуют в обоих массивах.

Вот как это работает:

_.intersection([0, 345, 324], [1, 0, 324]);  // возвращает [0, 324]

В данном случае, метод _.intersection принимает два массива: [0, 345, 324] и [1, 0, 324], и возвращает новый массив, содержащий только те значения, которые есть в обоих исходных массивах. В результате вы получаете [0, 324], так как эти два элемента присутствуют в обоих массивов.

Таким образом, для нахождения пересечения массивов с помощью Underscore.js или lodash.js просто используйте метод _.intersection.

0

Для нахождения элементов массива a, которые также присутствуют в массиве b, можно использовать следующий код, который работает за линейное время:

// Возвращает элементы массива a, которые также находятся в b за линейное время:
function intersect(a, b) {
  return a.filter(Set.prototype.has, new Set(b));
}

// Пример:
console.log(intersect([1, 2, 3], [2, 3, 4, 5]));

Я рекомендую данное лаконичное решение, которое превосходит другие реализации на больших объемах данных. Если производительность на небольших входных данных важна, проверьте альтернативы ниже.

Альтернативы и сравнение производительности:

Посмотрите следующий фрагмент для альтернативных реализаций и проверьте https://jsperf.com/array-intersection-comparison для сравнений производительности.

function intersect_for(a, b) {
  const result = [];
  const alen = a.length;
  const blen = b.length;
  for (let i = 0; i < alen; ++i) {
    const ai = a[i];
    for (let j = 0; j < blen; ++j) {
      if (ai === b[j]) {
        result.push(ai);
        break;
      }
    }
  } 
  return result;
}

function intersect_filter_indexOf(a, b) {
  return a.filter(el => b.indexOf(el) !== -1);
}

function intersect_filter_in(a, b) {
  const map = b.reduce((map, el) => { map[el] = true; return map; }, {});
  return a.filter(el => el in map);
}

function intersect_for_in(a, b) {
  const result = [];
  const map = {};
  for (let i = 0, length = b.length; i < length; ++i) {
    map[b[i]] = true;
  }
  for (let i = 0, length = a.length; i < length; ++i) {
    if (a[i] in map) result.push(a[i]);
  }
  return result;
}

function intersect_filter_includes(a, b) {
  return a.filter(el => b.includes(el));
}

function intersect_filter_has_this(a, b) {
  return a.filter(Set.prototype.has, new Set(b));
}

function intersect_filter_has_arrow(a, b) {
  const set = new Set(b);
  return a.filter(el => set.has(el));
}

function intersect_for_has(a, b) {
  const result = [];
  const set = new Set(b);
  for (let i = 0, length = a.length; i < length; ++i) {
    if (set.has(a[i])) result.push(a[i]);
  }
  return result;
}

Результаты в Firefox 53:

  • Операций в секундах на больших массивах (10,000 элементов):

    filter + has (this)               523 (данный ответ)
    for + has                         482
    for-loop + in                     279
    filter + in                       242
    for-loops                          24
    filter + includes                  14
    filter + indexOf                   10
    
  • Операций в секундах на маленьких массивах (100 элементов):

    for-loop + in                 384,426
    filter + in                   192,066
    for-loops                     159,137
    filter + includes             104,068
    filter + indexOf               71,598
    filter + has (this)            43,531 (данный ответ)
    filter + has (стрелочная функция)  35,588
    

Эти данные показывают, что для больших массивов использование filter с Set является наиболее эффективным подходом. Однако для небольших массивов цикл for с in может давать лучшие результаты.

0

Самый простой, быстрый O(n) и короткий способ:

function intersection (a, b) {
    const setA = new Set(a);
    return b.filter(value => setA.has(value));
}

console.log(intersection([1,2,3], [2,3,4,5]))

@nbarbosa предложил почти такое же решение, но он преобразует оба массива в Set, а затем обратно в массив. Главная разница в том, что его код будет возвращать только уникальные элементы, в то время как результат этого кода будет содержать повторяющиеся значения из массива b (при условии, что оба массива не заполнены уникальными значениями).

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

0

В вашем коде вы создаете метод intersect для массива в ES6, который находит пересечение исходного массива с произвольным количеством других массивов, переданных в качестве аргументов. Давайте разберем этот код:

Array.prototype.intersect = function(...a) {
  return [this, ...a].reduce((p, c) => p.filter(e => c.includes(e)));
}

var arrs = [[0, 2, 4, 6, 8], [4, 5, 6, 7], [4, 6]],
    arr = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9];

document.write("<pre>" + JSON.stringify(arr.intersect(...arrs)) + "</pre>");

Объяснение кода:

  1. Метод intersect:

    • Данный метод добавляется в прототип Array, что позволяет вызывать его на любом массиве.
    • Он принимает неопределенное количество массивов в качестве аргументов, благодаря использованию оператора распаковки (...a).
    • Метод создает новый массив, который включает исходный массив (this) и переданные массивы (a).
  2. reduce:

    • С помощью метода reduce мы проходим по массивам, выполняя операцию фильтрации.
    • На первом шаге p (предыдущее значение) будет равен исходному массиву, а c (текущий элемент) — первому массиву из a.
    • Мы используем filter, чтобы оставить только те элементы из p, которые содержатся в массиве c.
  3. Пример использования:

    • Массив arrs содержит несколько массивов, с которыми мы будем находить пересечение относительно массива arr.
    • Когда мы вызываем arr.intersect(...arrs), результатом будет массив, содержащий только те элементы, которые присутствуют во всех массивов.

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

Чтобы ответить на вопрос, пожалуйста, войдите или зарегистрируйтесь