algorithm - 设计相似度表

Question

我想不出更好的方法来解决以下问题...？ 想象一下，我有一个大表，其中的行和列是某种 id ..让我们说书 id

book_id-->1    2     3     .....
  1       1   0.92    0.33
  2
  3

此表中的条目告诉您每本书的相似程度。 所以从上表来看...书 1 和书 2 的相似度指数为 0.92。

所以，我已经在银行端计算了这个……让我们说“n”个条目。

从 n+1 开始，数据是实时的..

所以我要做的第一步是填充这个新行。这是一个非常幼稚的方法。

 i = 0; i < total_books ; i++
    sim(book(n+1),book(i)) 

可以说计算任何书籍相似度的计算都非常快。 但是由于这必须发生“n”次，因此加起来..

如果有“m”本新书，那么它是一个 n^2 操作(我认为)。 是否有更好的算法/数据结构可以使这种计算可接受。

此外，只是为了填充一些背景。 这种相似性不过是两个向量之间的点积。 (谷歌搜索余弦相似度会给出一个想法)。但这没什么特别的……只是在两个向量之间取点积……它会返回一个介于 0 和 1 之间的值。

Answer 1

当你将 1 本书添加到 n 本书的集合中时，它会执行 n 个操作 当您将 m 本书添加到 n 本书的集合中时，它会执行 (n) + (n+1) + ... (n+m-1) 操作(待验证):n*m + (1+ 2 + ... (m-1)) 所以它应该是 O(n*m + m*m)。

如果您以一种天真的方式实现了您的解决方案，则仅当 id(book_i) < id(book_j) 时，您可以通过计算和存储 sim(book_i,book_j) 来将计算时间减半(这不会改变复杂性)。 然后，当您想要检索 sim(i,j) 时，您只需确保以正确的顺序使用参数。