并行过滤中的数据结构优化

推荐系统 过滤

在系统设计的时候,数据结构对性能的影响巨大。 有些时候我们通过数据结构的调整以时间换空间, 有的时候则是者空间换时间。

除了空间和时间相互的权衡,还有对信息分布假设,或者对信息错误容忍度的权衡。


过滤需求

在推荐系统中,对数据过滤是一个常规的需求。 不同的业务有不同的过滤需求。 通常一个位置的数据需要3~4个过滤策略:

  1. 内容被拉黑
  2. 用户不喜欢/举报了
  3. 内容所属用户被拉黑
  4. 用户拉黑了内存所属用户

过滤接口

对内容过滤,可以抽象成一个统一的接口:

interface Filter{
    List<String> doFilter(List<String> idList);
}

那么就可以通过遍历过滤器过滤所有数据:

List<String> idList;
for(filter in filters){
    idList = filter.doFilter(idList);
}

以上这样写显然,所有过滤操作只能是串行的执行。如果多个Filter都是RPC。 显然会造成耗时累加的问题。


并行过滤

为了解决以上问题,显然需要将过滤操作改成并行。这样会得到4个过滤后不同的数据。 然后对数据去交集运算, 通常对 m、n 求交集的算法复杂度是 mn。 那么这里的算法复杂度就是 kn^2 – O(n^2)。

这里可以通过修改返回的数据结构进行优化,讲复杂度降到 O(n) ,并且是降低了存储空间的。

怎么实现呢?

修改filter接口的返回值,使得每次调用返回和传入参数长度一样的 Integer ArrayList。

ArrayList<Integer> doFilter(List<String> idList);

其中Integer消耗的空间肯定是比字符串少的。

标记元素被谁过滤

这里其实也可以直接使用BitMap,为什么要使用 ArrayList 呢?

在实际的应用中,我们需要知道一个内容是由于什么原因而被过滤掉。 如果是用Bitmap,那么就只能标记元素是否被过滤。 而使用 Integer,则可以通过bit位的方式记录有那些过滤器会过滤该元素。

数据结构

数据结构是真的很有用。 现如今,大多数场景下不需要自己开发。 但是对于数据结构,已经算法复杂度的理解还是需要有的。


讲真,算法和数据结构是自己的弱项。

吕飞

锲而舍之,朽木不折;锲而不舍,金石可镂