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

Question

[diasflack]

Посоветуйте способ проверки полного вхождения одного массива в другой в независимости от порядка элементов на 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);
}
}

Хотелось бы избавиться от двойного цикла и от циклов вообще, если есть более элегантное решение - буду благодарен

Comments

[ramntry]

Автор, сформулируйте задачу строже. Пусть даны массивы a и b - иии? Что именно вы хотите проверить?
Код, приведённый вами, только путает - он вообще непонятно, что делает. Что такое i, on, off? Какой смысл у equalTags? Например, при tag = tagsOff = [0, 0, 1, 0] equalTags насчитает 10 - и чего это значит?

Answer 1

[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". Она есть на русском, лучший перевод, на мой взгляд, от МЦНМО). Это полезно, уверяю вас.

Comments

[ramntry]

Если интересно, что там происходит, могу привести предельно простую реализацию приблизительно того же алгоритма на чистом С без использования сторонних библиотек: https://gist.github.com/ramntry/7552002#file-hasall-c . Так как писать хеш-таблицу для чисел совсем неинтересно, я чуть видоизменил пример: массивы в программах по ссылке выше содержат не числа, а их строковые представления. Можно заметить, что эта наивная реализация обгоняет JavaScript-код всего в 4 раза - ясно, что разработчики V8 (JavaScript-движок по умолчанию в nodejs) серьёзно постарались.

[KalininAndreyVictorovich]

Как я понимаю, этот метод будет работать неправильно, если элементами массива будут объекты.

[ramntry]

@KalininAndreyVictorovich, будет очень здорово, если вы приведёте пример, когда это работает неверно, и объясните, почему так происходит. Понятие равенства и его согласованность с порядком на элементах, а также с хешем всегда нетривиально. Например, требование равенства хешей равных по значению объектов обыкновенно предъявляется, а вот обратное ему - нет. Иногда равенство понимают не по значению, а по адресу. Отдельная история возникает с mutable-объектами или объектами, кеширующими часть своего состояния. Для них приходится различать "значение" и "состояние". Вобщем, тонкостей множество, в каждом языке или программной системе они решаются по-своему, как это сделано в JS я не знаю. Как я уже упоминал, я вообще не знаю JS. Однако мне будет очень интересно послушать о том, как разработчики JS эти проблемы разрешили (или не разрешили).

[diasflack]

Спасибо! И за решение и за наводку на книжку. Давно искал, что почитать по алгоритмам. Единственный минус вашего решения - .reduce не поддерживается IE ниже 9, но в топку осла =)

[ramntry]

Не за что.

И every, и reduce тривиально переписываются циклами (один за другим). Лаконичность и элегантность может пострадать, но производительность (судя по моим тестам) даже чуть-чуть увеличится (асимптотика останется той же, но константа чуть уменьшится). Однако если размеры ваших массивов никогда не превышают десятка, то разницы в скорости с решением @egor_nullptr вы не увидите никакой (оно, разумеется, тоже легко переписывается с явными циклами (вложенными) и не нуждается строго в filter и indexOf).

Удачи с книжкой. Если мат.введение покажется слишком сложным, на время можете его опустить, разве что про O-нотацию почитайте перед переходом к следующим главам. А потом вернётесь.

Answer 2

[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])  
// => [], и это означает полное вхождение

Answer 3

[NeX]

Если подключен undersore, то, например, так:
http://underscorejs.ru/#without

// Вернет массив a без элементов из массива a
if (_.without.apply(this, b.unshift(a))) {
}

Answer 4

[Artyushov]

Если важна именно производительность, то задача аналогична задаче о проверке вхождения подстроки. Для этого можно воспользоваться алгоритмами Кнута-Морриса-Пратта или Рабина-Карпа.

Answer 5

[Сергей Протько]

Обычно делаю такие проверки через пересечения массивов (или же вам привели функцию 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.