Фильтровать один раз или фильтровать несколько раз

У меня есть массив с объектами:

objects = [a, b, c, ...]

У меня есть ряд функций, которые возвращают true/false для данного объекта.

functions = [f1, f2, f3, ...]

Теперь я хочу получить все объекты, которые передают все функции. Что наиболее эффективно?

functions.forEach(function(f) {
       objects = objects.filter(f);
})

OR

objects = objects.filter(function(o) {
       functions.forEach(function(f) {
            if(!f(o)) return false;
       })
})

Я не уверен, что наиболее эффективно, это зависит от того, насколько тяжела функция фильтра? Они одинаковы?


javascript algorithm code-complexity
person user1415066    schedule 02.06.2016    source источник
comment
Сложность должна быть одинаковой. Разница только во взаимодействии аппаратной архитектуры и реализации алгоритма. Это зависит от платформы, которую вы не указали. В любом случае, единственный способ узнать наверняка — измерить и выбрать лучший вариант на вашей платформе.   -  person Spektre    schedule 02.06.2016
comment
Спасибо, это клиентский код для веб-сайта.   -  person user1415066    schedule 02.06.2016

Ответы (2)


arrow_upward
1
arrow_downward

В обоих случаях вы вызываете objects.filter для каждой функции, сложности одинаковы. Вы можете немного оптимизировать, если будете использовать filter для результата предыдущего фильтра вместо того, чтобы применять его каждый раз ко всем объектам.

for (f in functions){
    objects = objects.filter(functions[f])
}

Если возможно, отсортируйте функцию по временной сложности умножить на вероятность возврата значения True (по возрастанию).

person Arthur Hv    schedule 02.06.2016
comment
Дополнительные условия могут даже замедлить работу, как я уже упоминал ранее, зависит от платформы и реализации алгоритмов. Но поскольку это клиентская сторона веб-страницы, и если фильтры работают на стороне сервера, а последовательность вызовов на стороне клиента, это должно повысить производительность. - person Spektre; 02.06.2016

arrow_upward
1
arrow_downward

Я провел небольшой тест:

  console.time("Creating objects");
  var objects1 = [];
  var objects2 = [];
  while (objects1.length < 20000) {
    var value = 1000 * Math.random();
    objects1.push({ value: value });
    objects2.push({ value: value });
  }
  console.timeEnd("Creating objects");

  console.time("Creating functions")
  var functions = [];
  while (functions.length < 1000) {
    var rnd_value = 1000 * Math.random();
    functions.push(function(o) {
        return o.value >= rnd_value;
    });
  }
  console.timeEnd("Creating functions")

  console.time("Functions outer")

  functions.forEach(function(f) {
    objects1 = objects1.filter(f);
  });

  console.timeEnd("Functions outer");

  console.time("Filter outer")

  objects2 = objects2.filter(function(o) {
    var ret = true;
    functions.forEach(function(f) {
      if (ret && !f(o)) ret = false;
    });
    return ret;
  });

  console.timeEnd("Filter outer");

Результат в консоли: Внешние функции: 3188,918 мс Внешний фильтр: 454,249 мс

Поэтому я предполагаю, что функция фильтра в массиве довольно тяжелая в javascript. Другими словами, я должен вызывать его как можно меньше раз.

person user1415066    schedule 02.06.2016
comment
filter создает новый массив при каждом вызове. Однако, если это не является узким местом в вашем коде, просто сделайте то, что проще всего. - person 1983; 02.06.2016