Перебор массива - вложенный цикл
Не могу понять где ошибки.
Задача: необходимо написать функцию, которая проверяла - содержаться ли элементы массива array 2 в массиве array 1 и в зависимости от этого возвращала булевое значение. Решение (неработающее): Создаю два цикла: -внешний цикл перебирает значения array1 и присваивает их var arrayElem, которая передаётся во внутренний цикл; -во внутреннем цикле перебираются значения array2 и сравниваются с var arrayElem; -если значения равны то array2[j] помещаеться в пустой массив matchArray; -если длина массива matchArray === длине массива array2 возвращаеться true, иначе false. Код:
function contains(array1, array2) { |
Цитата:
var a1=[1,2,3,4,5];
var a2=[2,4];
alert(cross(a1,a2));
function cross(Ar1,Ar2) {
for (var i=0; i<Ar1.length; i++) {
for (var j=0; j<Ar2.length; j++) {
if (Ar1[i]==Ar2[j]) {
return true;
};
};
};
return false;
};
|
ksa, то есть при первом же совпадении считаем остальные элементы тоже совпавшими? Странная логика..
|
Используя ES5 функционал:
var a1 = [1,2,3,4,5];
var a2 = [2,4];
alert(isSubset(a1, a2));
function isSubset(a1, a2) {
return a2.every(function(element) {
return a1.indexOf(element) !== -1;
});
}
; |
Цитата:
|
Цитата:
Если второй массив должен быть частью первого - тогда все сложнее. Ведь может получиться и такая комбинация var a1=[1,2,3,4,5]; var a2=[2,4,4,2]; И как тогда? |
Цитата:
function contains(array1, array2) {
"use strict";
array1 = [1, 2, 3, 4, 5];
what = [1, 2, 3];
var matchArray = [];
var counter = 0;
for (var i = 0; i < array1.length; i++) {
var arrayElem = array1[i];
for (var j = 0; j < what.length; i++) {
if (what[j] === arrayElem) {
counter = counter + 1;
}
}
}
if (counter === what.length) {
return true;
} else {
return false;
}
}
К сожалению, мне как начинающему не совсем понятен Ваш код. Забыл сказать: я не могу в коде использовать те элементы JS, которые мы ещё не изучали а до indexOf еще не добежали. |
Цитата:
var a1=[1,2,3,4,5];
var a2=[2,4,4,2];
alert(isSubset(a1, a2));
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++) {
if (a1[j] === element) {
found = true;
break;
}
}
if (!found) {
return false;
}
}
return true;
}
|
Цитата:
|
Цитата:
Я не зря назвал функцию isSubset. В множествах нет повторяющихся элементов, поэтому [2, 4, 4, 2] - тоже самое что и [2, 4], и в множествах порядок не имеет значения. Именно так функция и работает - игнорирует порядок и повторы. |
Цитата:
Например в первом массиве нет двух 2, как и двух 4... Т.о. второй массив ну никак не может быть частью первого. |
Цитата:
|
ksa, тогда предлагаю такой вариант:
Сначала отсортировать a2, далее при переборе хранить найденный индекс совпадающего элемента в a1, сверять текущий элемент с предыдущим элементом, и если они равны, то искать дубль уже с сохраненного индекса, а не с начала. |
var a1 = [1, 2, 3, 4, 5];
var a2 = [2, 4, 4, 2];
var buf = {},
rez = false,
i;
for (i = 0; i < a2.length; i++) {
buf[a2[i]] = true;
}
for (i = 0; i < a1.length; i++) {
if (buf[a1[i]]) {
rez = true;
break;
}
}
alert(rez);
то же самое http://javascript.ru/forum/misc/4366...ny-stroki.html |
Цитата:
|
Цитата:
|
Цитата:
- переделать первый массив в объект (o[a[i]]=<количество_елементов>) - пройтись по второму массиву проверяя и "минусуя" количество - если проверка и декремент не выявил патологии - таки является частью. Т.о. 1 проход по первому и 1 проход по второму - вроде не так уж и плохо получится... :) |
Цитата:
Цитата:
Т.к. массив var a2 = [2, 4, 4, 2]; не является частью массива var a1 = [1, 2, 3, 4, 5]; |
что вы считаете частью массива?
не нашел у Т. С. такого a2 [2, 3] ? a3 [3, 2] ? a4 [3] ? массива a1 = [1, 2, 3, 4, 5]; |
Цитата:
http://javascript.ru/forum/misc/4383...tml#post288560 Цитата:
Вот мой вариант на проверку именно части одного массива в другом var a1 = [1, 2, 3, 4, 5];
var a2 = [2, 4, 4, 2];
alert(part(a1,a2));
a2 = [2, 4];
alert(part(a1,a2));
function part(Ar1,Ar2) {
var o={};
for (var i=0; i<Ar1.length; i++) {
o[Ar1[i]]=(o[Ar1[i]]||0)+1;
};
for (i=0; i<Ar2.length; i++) {
if (o[Ar2[i]]) {
if (o[Ar2[i]]--==0) {
return false;
};
} else {
return false;
};
};
return true;
};
|
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--){}
Устройства Даффа и других. Метод написанный и не оттестированный - это всего лишь предположение, далекое от жизни. Честно, я и сейчас вижу как это можно написать лучше.:) |
Какая жизненная тема оказалась! :D
|
Цитата:
var a1 = [2, 5, 2, 4, 5, 11, 5, 9, 9];
var a2 = [2, 7, 8, 6, 1, 1];
var a3 = [3, 1];
var a4 = [5];
alert(isValueInArray(a1, a2));
alert(isValueInArray(a1, a3));
alert(isValueInArray(a1, a4));
function isValueInArray(a1, a2) {
var i = 0,
j = 0,
sl, el,
l1 = a1.length,
l2 = a2.length,
len = l1 % 8,
slen = Math.floor(l1 / 8);
for (; i < l2; j = 0) {
el = a2[i++];
for (; 0 < len; len--) {
if (el == a1[j++]) return true;
}
for (sl = slen; 0 < sl; sl--) {
if (
el == a1[j++] ||
el == a1[j++] ||
el == a1[j++] ||
el == a1[j++] ||
el == a1[j++] ||
el == a1[j++] ||
el == a1[j++] ||
el == a1[j++])
return true;
}
}
return false;
}
|
Спасибо за ссылку плюсанул
http://jsperf.com/isvalueinarray не знал, что while на 25% медленный и по ходу на больших массивах for впереди |
Poznakomlus,
Я правильно понимаю, что основная идея такой оптимизации лежит в сокращении количества итераций цикла за счет проверки группами? Не уверен что правильно разобрал алгоритм. |
|
Так, что-то сегодня или со мной, или не знаю с чем.
Уже второй раз сначала получаю неправильные результаты замеров производительности. Когда впервые запустил пример кода по вашей ссылке, получилось, что оптимизированный вариант был почти вдвое быстрее. Теперь не пойму, куда я смотрел или что это было. А запись исходной реализации на C после долгого отсутствия практики на нем взрывает мозг. |
| Часовой пояс GMT +3, время: 13:19. |