Как найти одинаковые значения в двух массивах?

Question

[bozuriciyu]

const one = ['one', 'two', 'three', 'four', 'five']
const two = ['a', 'b', 'five', 'c', 'one']

Как эффективно найти повторяющиеся значения во втором массиве? Т.е. на выходе ['five', 'one']

Значений будет многовато, тысячи, хотелось бы эффективное решение.

Answer 1

[Сергей Соколов]

Оптимизировать – непереоптимизировать!

Сортируем только короткий из двух. По длинному один раз и бинарным поиском в коротком.

let one = ['one', 'two', 'three', 'four', 'five'];
let two = ['a', 'b', 'five', 'c', 'one'];
const [long, short] = one.length > two.length ? [one,two] : [two,one];
short.sort();
const shortLength = short.length;

const binSearch = needle => {
  let start = 0, finish = shortLength - 1;
  while (start <= finish) {
    const center = Math.floor((start + finish) / 2);
    if (short[center] < needle) start = center + 1;
    else if (short[center] > needle) finish = center - 1;
    else return true;
  }
  return false;
}

const result = [];
for (let i = 0, length = long.length; i < length; i++)
  if (binSearch(long[i])) result.push(long[i]);

result // ["five","one"]

</Г-code>

Comments

[longclaps]

А ведь недурно. Призадумался над выбором ролей длинный/короткий, но всё четко.

[Сергей Соколов]

longclaps, вот с разметкой г-кода в подписи не справился : (

ожидание

сразу после редактирования:

реальность

после обновления страницы:

#bugreport

Answer 2

[Сергей Сергей]

Эффективнее пользоваться встроенными методами массивов, типа forEach или map, так как эти функции "заложены" в интерпретатор.

И могу предложить что-то такое

matched = one.filter( el => two.indexOf( el ) > -1 );

Comments

[Роман]

Сергей Сергей, а какой критерий для определения эффективности вы используете?

[Сергей Сергей]

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

Answer 3

[longclaps]

Эффективнее пользоваться встроенными в голову мозгами, при наличии.

Можно ручками написать слияние:

let one = ['one', 'two', 'three', 'four', 'five'];
let two = ['a', 'b', 'five', 'c', 'one'];
one.sort();
two.sort();
let i = one.length, j = two.length, three = [];
while (i > 0 && j > 0) {
    i--;
    j--;
    if (one[i] > two[j]) j++;
    else if (one[i] < two[j]) i++;
    else three.push(one[i]);
}
console.log(three);

Можно воспользоваться библиотекой:

const _ = require("lodash");
console.log(_.intersection(one, two));

Можно воспользоваться встроенным классом Set (пусть будет задание на дом).

ps Developer, увидишь Кнута - передавай привет.

Comments

[bozuriciyu]

Давно я такого говнокода не видел.

[Роман]

bozuriciyu, автор, скажите, вы хотите эффективное или красивое решение?
сложность алгоритма отмеченного решением O(n1*n2)
сложность этого алгоритма O(n1+n2) (правда при условии что массивы отсортированы))))

[Роман]

bozuriciyu, можно сделать решение со сложностью O(2*(n1+n2)) не зависящее от сортировки.

let one = ['one', 'two', 'three', 'four', 'five'];
let two = ['a', 'b', 'five', 'c', 'one'];
let tmp = [...one, ...two]  // эта часть так же имеет сложность, но от нее можно избавиться
   .reduce((a,v)=>{a[v]?a[v]++:a[v]=1; return a},{}); // O(n1+n2)
let res =   Object.keys(tmp)
   .filter(k=>tmp[k]-1); // в минимуме O(max(n1,n2)) в максимуме O(n1+n2)

[longclaps]

0xD34F, Алексей Уколов, Денис Инешин, Сергей Соколов, Владимир Проскурин, xmoonlight,
Алексей Ярков DevMan, Pardon Me! Where Do I Find 4giveness?, Александр Аксентьев, Ivan Bogachev, Максим Зайцев,

Неужели никто из кураторов тэга не напишет говнокод хуже меня?
Я объявляю говнокод-челленж!

[xmoonlight]

longclaps, Ты - победил! Ещё хуже, чем ты - уже никто не сможет написать!
:)))

[Роман]

xmoonlight, я уверен что смогу, но меня не позвали, не дорос видимо))))

[Владимир Проскурин]

В голову лезет только следующий высокопроизводительный алгоритм.

1. Сортируем массивы (не важно в каком порядке, главное чтобы в одинаковом порядке оба массива).
   
2. Собираем комбинации из всех возможных значений в каждом массиве отдельно, получая два массива с комбинациями.
   
3. Создаем пустой массив maxElement = [], в котором будем хранить самый длинную найденную комбинацию
   
4. И теперь проходимся по массиву комбинаций 1, и ищем в нем элементы, которые есть в массиве комбинаций 2 (желательно вложенным циклом). Сравнивать нужно arr1.join('') === arr2.join('').
   
5. Если нашли элемент по такому условию, то проверяем его еще на следующее условие
   

if (lastElement.length > maxElement.length) {
    maxElement = lastElement;
}

Таким образом, элемент с максимальным количеством совпадений maxElement и будет результатом ['five', 'one'].

Я не успел написать код, т.к. уже пора спать. Но думаю, массивы из вопроса автора он бы легко обработал до утра.

[Роман]

Владимир Проскурин, участнику демарша зачет)))))))

[longclaps]

Сравнивать нужно arr1.join('') === arr2.join('').

Владимир Проскурин, это он:

let one = ['a', 'bc'];
let two = ['ab', 'c'];

[Владимир Проскурин]

longclaps, не очень понял, про что вы.

[Lawrence Gordon]

Лол, такой дури давно уже не видел))))

Answer 4

[rPman]

Создаем на основе одного массива индекс (инвертируем ключи и значения), преобразуя массив в объект.
А затем простым перебором элементов второго массива проверяем наличие по ключу в инвертированным.

т.е. итоговая трудоемкость просто линейная (на самом деле там умноженное на логарифм но работа с ключами в javascript очень эффективна, на столько что этот логарифм вы заметите только на ОЧЕНЬ БОЛЬШИХ массивах, в крайнем случае можно использовать Map, он точно быстрый.

Comments

[Роман]

зря стараетесь, bozuriciyu под эффективностью по всей видимости понимает красоту и лаконичность кода.

Answer 5

[fumitox84]

Можно так

function checkArrayIntersection(array1: string[], array2: string[]): boolean {
  return array1.some(item => array2.includes(item));
}

// Пример использования
const array1 = ["apple", "banana", "orange"];
const array2 = ["pear", "grape", "banana"];

const hasIntersection = checkArrayIntersection(array1, array2);

console.log(hasIntersection); // Выводит true, так как 'banana' есть в обоих массивах

Answer 6

[Lawrence Gordon]

const filteredArray = one.filter(value => two.includes(value));