行过滤算法

统计信息：字数 1864 阅读4分钟

行数组数据结构

let rows = [
  {_id, '0000': 'abc', '1111': 100},
  {_id, '0000': 'ab', '1111': 20},
  {_id, '0000': 'c', '1111': 30},
];

过滤数组数据结构

let filters = [
  {key: '0000', type: 'contain', target: 'a'},
  {key: '1', type: 'large', target: 10},
  ...
];

let filter_conjunction = 'and'
// 'and' 'or' 表示不同过滤条件是和还是或（交集还是并集）

实际上，过滤算法就是多重数组的过滤，关键是不同值类型，使用不同的过滤条件处理

思路，循环每一个行，然后看当前的行是否满足条件，主要代码如下

let resultRows = rows.filter(row => {
  if (filter_conjunction === 'and') {
    for (let i = 0; i < filters.length; i++) {
      let filter = filters[i];
      const { key, type, target } = filter;
      // 值是字符串
      if (type === 'contain') {
        if (!row[key].includes(target)) {
          return false;
        }
      }
      // 值是数值
      if (type === 'large') {
        if (!row[key] > target) {
          return false;
        }
      }
    }
    return true;
  }
  if (filter_conjunction === 'or') {
    for (let i = 0; i < filters.length; i++) {
      let filter = filters[i];
      const { key, type, target } = filter;
      // 值是字符串
      if (type === 'contain') {
        if (row[key].includes(target)) {
          return true;
        }
      }
      // 值是数值
      if (type === 'large') {
        if (row[key] > target) {
          return true;
        }
      }
    }
    return false;
  }
});

实际上，不同的列类型，值类型，对应不同的过滤条件，都需要单独的函数判断，这是过滤函数的复杂度

算法分析

算法复杂度：行数量 * 过滤器数量（如果过滤器条件是循环，那么需要求积）

---

Last update: November 9, 2024