计算一组选定类别的项目计数器

最后发布: 2009-07-26 19:00:45


问题

在我们的Ruby on Rails项目中,我们对食谱有很多分类标准,例如Cook方法,场合等。每个食谱都属于这些类别中的一个或几个。 当某人开始浏览食谱时,他/她可以缩小到一组特定的类别。 然后,我们需要计算从该集合可访问的所有类别中的食谱数量(“可访问”表示该类别中的某些食谱也属于所选类别)。 这类似于Amazon搜索的工作方式:有人输入“软件”,并且左侧有一个菜单,上面显示“书(200)”,“电影(300)”等,因此用户可以通过单击这些链接来更深入。

现在,我们已经大致实现了它:

  1. 从URL构建一组选定的类别;
  2. 执行查询,以从属于当前所选条件的所有配方中获取类别ID;
  3. 建立将所有类别ID映射到配方计数的索引,并仅呈现那些具有非零计数器的配方;
  4. 将该索引在memcached中存储24小时,因此我们每天只为特定页面计算一次。

我担心的是,如果发生高速缓存未命中,构建索引可能会花费很多时间。 也许您对如何解决此问题或改进当前解决方案有任何建议?

ruby-on-rails ruby data-mining
回答

您所描述的是一个非常糟糕的组合问题:对于每个选定的类别,迭代每个配方,然后迭代该配方的类别 ,然后返回该类别的配方计数。 即使使用优化的SQL,您在谈论的是嵌套子选择,并且从逻辑上讲,这不能在少于指数时间内完成。 (这意味着当您获得很多食谱时, 确实会受到伤害。)并且由于可能的组合数量等于(类别)^ 2,因此缓存也变得越来越不切实际。

您确定必须这样做吗? 您对BTW的亚马逊有误; 他们没有像这样的“交叉类别视图”。 它们显示搜索命中次数,使用搜索索引很容易。 在搜索框中输入“软件”并不是将软件视为一个类别。 将其视为关键字。

如果没有人要求此功能,建议您对其进行简化。 在类别过滤器视图上,仅显示所有匹配的食谱。 在每个食谱页面上 ,您可以显示该食谱所在的所有类别的侧边栏列表,并根据需要对这些类别进行计数。 (可以轻松地将其作为“类别”模型中的属性进行缓存,并在调出食谱时通过急切的加载进行检索。)

如果你确实有某种原因做到这一点-是这样的错误印象,使用户真正希望看到的类别,他们没有过滤的要求下,它的权力-那么至少用SQL做到这一点。 嵌套的子选择确实会伤害您,并且会占用数据库的内存,但是它们比在Ruby中进行存储要快。 另外,还有一些Rails插件可以改变缓存的行为,以便您在当前匹配项上显示过期结果,然后为下一个匹配项重新生成缓存。

但我会建议您进行跟踪,并确定是否有人使用它,然后再进行更多工作。


回答

每天索引不是很干净。 当您插入或更新数据集时,为什么不索引它?

插入数据集(如配方)

  • 启动一个线程,该线程将内容添加到索引

  • 如果线程(高负载!)发生超时(如1秒),则将其停止

日常:

  • 将当前索引保存到磁盘

  • 更新整个索引

  • 如果失败,请从磁盘恢复保存的索引

  • 否则读取索引到内存缓存


回答

您没有提供有关类别/产品数量的任何估计,但是我会假设其中有很多:)

如果我想要性能,这是我的方法:(我知道,这很疯狂:))

  • 对于每个类别,请在内存缓存中保留一个位向量,这意味着:如果ID为n的乘积属于该类别,则第n位为1

让我举个例子:如果产品1、7、9和10在A类中,而1,6,9在B类中,而1、9、11在C中,则:

  • A是01000001 01100000
  • B是01000010 01000000
  • C为01000000 01010000

当您要计算这些集合的交集时,只需在集合之间进行按位“与”运算即可得到结果。

结果是:

  • 结果= A AND B AND C = 01000000 01000000

如果要为每个类别进行计算,只需进行另一个类别和结果

备注:

  • 不要忘记在更改数据库中的内容时重新计算这些向量
  • 如果您打算相交很多类别,这将非常快
  • 对于每个类别,您必须存储大于TOTAL_NR_OF_PRODUCTS / 8的向量