Какой есть способ проверки полного вхождения одного массива в другой на JavaScript без использования двойного цикла?

Посоветуйте способ проверки полного вхождения одного массива в другой в независимости от порядка элементов на JavaScript без использования двойного цикла - собственно вопрос.

Пока имею это -

var equalTags = 0;
for(var a=0; a<tag.length; a++) {
  for(var b=0; b<tagsOff.length; b++) {
    if (tag[a]==tagsOff[b]) {
      equalTags ++;
     }	
  }
  if (equalTags == tag.length) {
    console.log(i+' - off - '+equalTags);
  } else {
    console.log(i+' - on - '+equalTags);
}
}


Хотелось бы избавиться от двойного цикла и от циклов вообще, если есть более элегантное решение - буду благодарен
  • Вопрос задан
  • 14809 просмотров
Решения вопроса 1
ramntry
@ramntry
Если @egor_nullptr вас понял правильно, и вам нужно проверить, что массив b хотя бы в одном экзепляре содержит каждый элемент массива a, то предлагаю такое решение:
Array.prototype.hasAll = function(a) {
    var hash = this.reduce(function(acc, i) { acc[i] = true; return acc; }, {});
    return a.every(function(i) { return i in hash; });
};

По сравнению с решением @egor_nullptr оно асимптотически быстрее: O(n + m) против O(n * m), где n, m - размеры массивов a, b. При n = m = 100 000 на моей машине мой вариант отрабатывает быстрее в 200 раз. Тестировал так.

Знаете, каков мой опыт разработки на JavaScript? Я программирую на нём 40 минут, в обнимку с JavaScript Reference от Mozilla. Мой основной язык - C++. А вам очень советую добраться-таки до какой-нибудь книжки по алгоритмам и структурам данных (например, до "Introduction to Algorithms". Она есть на русском, лучший перевод, на мой взгляд, от МЦНМО). Это полезно, уверяю вас.
Ответ написан
Пригласить эксперта
Ответы на вопрос 4
egor_nullptr
@egor_nullptr
Array.prototype.diff = function(a) {
    return this.filter(function(i) {return !(a.indexOf(i) > -1);});
};

[5,3,4].diff([1,2,3,4,5,6])  
// => [], и это означает полное вхождение
Ответ написан
Комментировать
NeX
@NeX
Если подключен undersore, то, например, так:
http://underscorejs.ru/#without
// Вернет массив a без элементов из массива a
if (_.without.apply(this, b.unshift(a))) {
}
Ответ написан
Комментировать
@Artyushov
Если важна именно производительность, то задача аналогична задаче о проверке вхождения подстроки. Для этого можно воспользоваться алгоритмами Кнута-Морриса-Пратта или Рабина-Карпа.
Ответ написан
Комментировать
Fesor
@Fesor
Full-stack developer (Symfony, Angular)
Обычно делаю такие проверки через пересечения массивов (или же вам привели функцию diff). Без вложенных циклов никак не выйдет, ибо по сути и indexOf и array.filter это циклы. Разве что вы можете прервать выполнение цикла как только найдется элемент, не попадающий в другой массив.
function isSame(a, b) {
    if (a.length > b.length) {
         b = [a, a = b][0]; //swap
    }

    for(var i = 0, length = a.length;i<length;i++) {
         if (-1 === b.indexOf(a[i])) {
              return false;
         }
    }
    
    return true;
}


что-то типа такого. Но мне больше нравится вариант с diff.
Ответ написан
Комментировать
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы