Javascript.RU

Создать новую тему Ответ
 
Опции темы Искать в теме
  #21 (permalink)  
Старый 23.12.2013, 23:00
Новичок на форуме
Отправить личное сообщение для SWin Посмотреть профиль Найти все сообщения от SWin
 
Регистрация: 03.12.2013
Сообщений: 8

danik.js, бы вы вкратце рассказать о порядке выполнения кода.
Моих более чем скромных знаний JS не хватает.

Насколько я понимаю при нахождении совпадающего элемента массива
a1[j] === element вложенный цикл прерываеться командой break, при этом found = true и выполнениние функции продолжается во внешнем цикле со строки for (var i = 0; i < a2.length; i++).
При этом значение found снова становиться false и дальше снова переходим во внутренний цикл и так по кругу.
Правильно?
Что происходит дальше. Не совсем понятны строки ниже 15-ой.

Сообщение от danik.js Посмотреть сообщение
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;
}
Ответить с цитированием
  #22 (permalink)  
Старый 24.12.2013, 00:33
Аватар для danik.js
Профессор
Отправить личное сообщение для danik.js Посмотреть профиль Найти все сообщения от danik.js
 
Регистрация: 11.09.2010
Сообщений: 8,804

Сообщение от SWin
Что происходит дальше. Не совсем понятны строки ниже 15-ой.
Ну дык если какой-то элемент из a2 не нашли в a1, то какой смысл проверять остальные элементы?
__________________
В личку только с интересными предложениями
Ответить с цитированием
  #23 (permalink)  
Старый 24.12.2013, 03:07
Аватар для Vlasenko Fedor
Профессор
Отправить личное сообщение для Vlasenko Fedor Посмотреть профиль Найти все сообщения от Vlasenko Fedor
 
Регистрация: 13.03.2013
Сообщений: 1,572

А это иллюстрация того, что выбрано не правильное решение.
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);
Ответить с цитированием
  #24 (permalink)  
Старый 24.12.2013, 04:14
Аватар для Vlasenko Fedor
Профессор
Отправить личное сообщение для Vlasenko Fedor Посмотреть профиль Найти все сообщения от Vlasenko Fedor
 
Регистрация: 13.03.2013
Сообщений: 1,572

Немного оптимизировал
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));

Последний раз редактировалось Vlasenko Fedor, 24.12.2013 в 13:21.
Ответить с цитированием
  #25 (permalink)  
Старый 24.12.2013, 18:19
Аватар для Vlasenko Fedor
Профессор
Отправить личное сообщение для Vlasenko Fedor Посмотреть профиль Найти все сообщения от Vlasenko Fedor
 
Регистрация: 13.03.2013
Сообщений: 1,572

Вариант №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

Последний раз редактировалось Vlasenko Fedor, 25.12.2013 в 05:08.
Ответить с цитированием
  #26 (permalink)  
Старый 25.12.2013, 01:15
Аватар для Vlasenko Fedor
Профессор
Отправить личное сообщение для Vlasenko Fedor Посмотреть профиль Найти все сообщения от Vlasenko Fedor
 
Регистрация: 13.03.2013
Сообщений: 1,572

okouser,
тестируйте на примерах. Буфер нужен для уменьшения количеств итераций. И как раз он и служит для увеличения скорости
В твоем варианте максимальная длина проверки a.length * b.length
Вот тебе и буфер

Последний раз редактировалось Vlasenko Fedor, 25.12.2013 в 01:30.
Ответить с цитированием
  #27 (permalink)  
Старый 25.12.2013, 01:51
Аватар для Vlasenko Fedor
Профессор
Отправить личное сообщение для Vlasenko Fedor Посмотреть профиль Найти все сообщения от Vlasenko Fedor
 
Регистрация: 13.03.2013
Сообщений: 1,572

Сообщение от okouser Посмотреть сообщение
В чем проблема?
Я привел решения задачи для трех случаев:
2) когда нужно проверить произвольное вхождение всех элементов
У вас последовательное, не произвольное
arr =[5, 1] и arr[1, 5] разный результат
Ответить с цитированием
  #28 (permalink)  
Старый 25.12.2013, 02:35
Аватар для Vlasenko Fedor
Профессор
Отправить личное сообщение для Vlasenko Fedor Посмотреть профиль Найти все сообщения от Vlasenko Fedor
 
Регистрация: 13.03.2013
Сообщений: 1,572

var a1 = [1, 2, 3, 4, 5];
var a2 = [1, 5];
var a2 = [5, 1];
При таких значениях
Ответить с цитированием
  #29 (permalink)  
Старый 25.12.2013, 04:39
Аватар для Vlasenko Fedor
Профессор
Отправить личное сообщение для Vlasenko Fedor Посмотреть профиль Найти все сообщения от Vlasenko Fedor
 
Регистрация: 13.03.2013
Сообщений: 1,572

Вариант №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;
      };

Последний раз редактировалось Vlasenko Fedor, 25.12.2013 в 05:24.
Ответить с цитированием
  #30 (permalink)  
Старый 25.12.2013, 12:13
Аватар для Vlasenko Fedor
Профессор
Отправить личное сообщение для Vlasenko Fedor Посмотреть профиль Найти все сообщения от Vlasenko Fedor
 
Регистрация: 13.03.2013
Сообщений: 1,572

Я написал так, к тому, что в рассмотренных здесь вариантах не были применены технологии прироста производительности.
К примеру изменение порядка цикла на обратный
var i = arr.length - 1;
while(i--){}

Устройства Даффа и других.
Метод написанный и не оттестированный - это всего лишь предположение, далекое от жизни. Честно, я и сейчас вижу как это можно написать лучше.

Последний раз редактировалось Vlasenko Fedor, 25.12.2013 в 12:22.
Ответить с цитированием
Ответ



Опции темы Искать в теме
Искать в теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Как подчинить себе цикл wreder jQuery 17 20.11.2013 22:17
Цикл завешивает страницу, помогите Romingood jQuery 5 19.10.2013 14:30
Нужен цикл для создания огромного массива apish Общие вопросы Javascript 2 20.09.2012 16:10
JS Перебор ассоциативного многомерного массива zbs2000 Events/DOM/Window 8 23.07.2012 01:23
Перебор массива объектов Триви jQuery 12 26.08.2011 09:22