Алгоритм фильтрации данных

Question

Можете ли вы предложить мне алгоритм фильтрации данных.

Я использую javascript и пытаюсь выписать функцию фильтра, которая фильтрует массив данных. У меня есть массив данных и массив фильтров, поэтому для применения каждого фильтра к любым данным я написал 2 для петли

foreach(data)
{
  foreach(filter)
  {
   check data with filter
  }
}

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

Я использую библиотеку Mootools, а массив данных - это массив JSON

Данные и фильтр

Данные - это массив JSON, скажем, пользователя, поэтому он будет

data = [{"name" : "first", "email" :  "first@first", "age" : "20"}.
        {"name" : "second", "email" :  "second@second", "age" : "21"}
        {"name" : "third", "email" :  "third@third", "age" : "22"}]

Массив фильтров - это в основном самоопределяемый класс для различных полей данных

alFilter[0] = filterName;
alFilter[1] = filterEmail;
alFilter[2] = filterAge;

Поэтому, когда я вхожу в первый цикл for, я получаю один объект JSON (первая строка) в приведенном выше случае. Когда я ввожу второй цикл for (фильтр filters), у меня есть класс фильтра, который извлекает точное поле, с которым будет работать текущий фильтр, и проверяет фильтр с соответствующим полем данных.

Так что в моем примере

foreach(data)
{
 foreach(filter)
{
  //loop one - filter name
 // loop two - filter email
 // loop three - filter age
}
}

когда второй цикл заканчивается, я устанавливаю флаг, обозначающий, были ли данные отфильтрованы или нет, и в зависимости от этого данные отображаются.

Answer 1

Вам нужно будет дать нам более подробную информацию о точной структуре ваших данных и фильтрах, чтобы действительно помочь вам. Используются ли фильтры для выбора подмножества данных или для изменения данных? Что делают фильтры?

Тем не менее, есть несколько общих предложений:

1. Делай меньше работы . Есть ли способ ограничить объем данных, над которыми вы работаете? Какой-то предварительный фильтр, который может работать быстро и обрезать его перед выполнением основного цикла?
2. Вырваться из внутреннего цикла как можно скорее . Если один из фильтров отклоняет данные, вырывается из внутреннего цикла и переходит к следующему. Если это возможно, то вам также следует постараться сделать так, чтобы в первую очередь использовались наиболее селективные фильтры. (Это предполагает, что ваши фильтры используются для отклонения элементов из списка, а не для их изменения)
3. Проверка на избыточность в вычислениях, выполняемых фильтрами. Если каждый из них выполняет некоторые сложные вычисления, которые разделяют некоторые подпрограммы, то, возможно, памятка или динамическое программирование может использоваться, чтобы избежать избыточных вычислений.

Действительно, все сводится к первому пункту, выполняет меньше работы на всех трех уровнях вашего кода. Можете ли вы сделать меньше работы, ограничивая элементы во внешнем цикле? Делает ли меньше работы, останавливаясь после определенного фильтра и делая в первую очередь самые селективные фильтры? Делать меньше работы, не делая лишних вычислений внутри каждого фильтра?

Answer 2

Вам следует отсортировать применение ваших фильтров, чтобы оптимизировать две вещи: дорогие проверки должны идти последними, а проверки, которые удаляют большое количество данных, должны идти первыми. Затем вы должны убедиться, что проверка оборвана, как только появится результат "out".

Answer 3

Это довольно много, как вы должны это сделать. Хитрость заключается в том, чтобы оптимизировать этот элемент «проверка данных с помощью фильтра». Вам нужно просмотреть все ваши данные и проверить все ваши фильтры - вы не получите быстрее, чем это.

Избегайте сравнения строк, используйте модели данных как можно более родными, старайтесь сократить набор данных на каждом проходе с помощью filter и т. Д.

Без дополнительных знаний это трудно оптимизировать для вас.

Answer 4

Если ваши фильтры ищут конкретные значения, диапазон или начало текста, тогда jOrder (http://github.com/danstocker/jorder) подойдет вашей проблеме.

Все, что вам нужно сделать, это создать таблицу jOrder следующим образом:

var table = jOrder(data)
    .index('name', ['name'], { grouped: true, ordered: true })
    .index('email', ['email'])
    .index('age', ['age'], { grouped: true, ordered: true, type: jOrder.number });

А затем позвоните table.where(), чтобы отфильтровать таблицу.

Когда вы ищете точные совпадения:

filtered = table.where([{name: 'first'}, {name: 'second'}]);

Когда вы ищете определенный диапазон одного поля:

filtered = table.where([{age: {lower: 20, upper: 21}}], {mode: jOrder.range});

Или, когда вы ищете значения, начинающиеся с данной строки:

filtered = table.where([{name: 'fir'}], {mode: jOrder.startof});

Таким образом, фильтрация будет происходить на порядок быстрее, чем с вложенными циклами.

Answer 5

Предполагая, что фильтр удаляет данные, если они не совпадают, я полагаю, что вы переключаете два цикла следующим образом:

foreach(filter) {
    foreach(data) {
        check data with filter
    }
}

Таким образом, второй фильтр должен обрабатывать не все данные, а только данные, прошедшие первый фильтр и т. Д. Конечно, приведенные выше советы (например, последние дорогостоящие проверки) все еще верны, и их следует учитывать дополнительно.