danik.js, бы вы вкратце рассказать о порядке выполнения кода.
Моих более чем скромных знаний JS не хватает. Насколько я понимаю при нахождении совпадающего элемента массива a1[j] === element вложенный цикл прерываеться командой break, при этом found = true и выполнениние функции продолжается во внешнем цикле со строки for (var i = 0; i < a2.length; i++). При этом значение found снова становиться false и дальше снова переходим во внутренний цикл и так по кругу. Правильно? Что происходит дальше. Не совсем понятны строки ниже 15-ой. Цитата:
|
Цитата:
|
А это иллюстрация того, что выбрано не правильное решение.
var a1 = [1, 2, 3, 4, 5]; var a2 = [2, 4, 4, 2]; var b = 0; alert(isSubset(a1, a2)); alert(b); function isSubset(a1, a2) { for (var i = 0; i < a2.length; i++) { var element = a2[i]; var found = false; for (var j = 0; j < a1.length; j++) { b++; if (a1[j] === element) { found = true; break; } } if (!found) { return false; } } return true; } и предложное мной var a1 = [1, 2, 3, 4, 5]; var a2 = [2, 4, 4, 2]; var buf = {}, rez = false, i, b = 0; for (i = 0; i < a2.length; i++) { buf[a2[i]] = true; b++; } for (i = 0; i < a1.length; i++) { b++; if (buf[a1[i]]) { rez = true; break; } } alert(rez); alert(b); |
Немного оптимизировал
var a1 = [1, 2, 3, 4, 5]; var a2 = [2, 4, 4, 2]; var comparing = function (ar1, ar2) { var a, b, i, buf = {}; ar1.length < ar2.length ? (a = ar1, b = ar2) : (a = ar2, b = ar1); for (i = 0; i < a.length; i++) buf[a[i]] = 1; for (i = 0; i < b.length; i++) { if(buf[b[i]]) return true; } return false; } alert(comparing(a1, a2)); алгоритм такой 1. Сравниваем длину массивов 2. Из меньшего делаем объект(алфавит) с оригинальными значениями. При таком подходе мы быстрее переходим непосредственно к нахождению первого вхождения. Но, это как бабка надвое гадала может в конечном результате привести к увеличению операций для поиска. В некоторых ситуациях следовало из массивов делать 2 объекта с оригинальными значениями. И сравнивать уже их. 3. Соответственно поиск совпадающего значения http://javascript.ru/php/array_diff_key http://javascript.ru/php/array_diff Как вариант компактного var a1 = [1, 2, 3, 4, 5]; var a2 = [2, 4, 4, 2]; var comparing = function (a, b) { var i, buf = {}; for (i = 0; i < a.length; i++) buf[a[i]] = 1; for (i = 0; i < b.length; i++) if (buf[b[i]]) return true; return false; }; alert(comparing(a1, a2)); |
Вариант №2 Поиск совладения значений массива в любом порядке в искомом массиве
var a1 = [1, 2, 1, 3, 4, 5, 1, 9]; var a2 = [1, 5]; var a3 = [5, 1]; var a4 = [5, 1, 1, 3, 7]; var comparing = function (a, b) { if (a.length < b.length) return false; var i, buf = {}, maxel = b.length - 1; for (i = 0; i < a.length; i++) buf[a[i]] = (buf[a[i]] || 0) + 1; for (i = 0; ;) { if (!buf[b[i]]--) return false; if (i++ == maxel) return true; } } alert(comparing(a1, a2)); alert(comparing(a1, a3)); alert(comparing(a1, a4)); Здесь максимальная длина проверки a.length + b.length |
okouser,
тестируйте на примерах. Буфер нужен для уменьшения количеств итераций. И как раз он и служит для увеличения скорости В твоем варианте максимальная длина проверки a.length * b.length Вот тебе и буфер |
Цитата:
arr =[5, 1] и arr[1, 5] разный результат |
var a1 = [1, 2, 3, 4, 5];
var a2 = [1, 5]; var a2 = [5, 1]; При таких значениях |
Вариант №1 Возвращает false или индекс элемента с которого начинается совпадение
Да первый вариант стоит того. Не знаю может кто красивее напишет var a1 = [2, 5, 2, 4]; var a2 = [2, 4]; var a3 = [3, 4]; var a4 = [5]; alert(isSubset(a1, a2)); alert(isSubset(a1, a3)); alert(isSubset(a1, a4)); function isSubset(a1, a2) { var i = 0, j = 1, ind = 0, maxid = a2.length - 1; for (; i < a1.length; i++) { if (a1.length - i == maxid) return false; if (a1[i] != a2[0]) continue; ind = i; if (maxid == 0) return ind; for (; j < a2.length; j++) { if (a1.length - i == maxid) return false; if (a2[j] != a1[i+1]) break; if (j == maxid) return ind; } } return false; }; Вариант 3. Самый простой. Цикл внутри цикла. Находит единственное совпадение var a1 = [2, 5, 2, 4]; var a2 = [7, 8]; var a3 = [3, 4]; var a4 = [5]; alert(isSubset(a1, a2)); alert(isSubset(a1, a3)); alert(isSubset(a1, a4)); function isSubset(a1, a2) { for (var i = 0; i < a2.length; i++) { for (var j = 0; j < a1.length; j++) { if (a2[i] == a1[j]) return true; } } return false; }; |
Я написал так, к тому, что в рассмотренных здесь вариантах не были применены технологии прироста производительности.
К примеру изменение порядка цикла на обратный var i = arr.length - 1; while(i--){} Устройства Даффа и других. Метод написанный и не оттестированный - это всего лишь предположение, далекое от жизни. Честно, я и сейчас вижу как это можно написать лучше.:) |
Часовой пояс GMT +3, время: 06:10. |