2

我有一个应用程序（对于给定的 twitter 用户），它会获取您关注但不关注您的 twitter 用户列表。它这样做：

  • 比较两个列表，一个来自时间 x 和时间 y，看看是否有更多的人关注你。
  • 看看 twitter 用户 x 花了多长时间关注你。
  • 看看用户 x 有多少转推/评论来关注你

我想出的简单方法就是与用户和不关注你的人建立一个有很多属于关系的关系，例如：

User table
-id

TwitterUser table
-user_id 
-timestamp
-isFollowing

因此，使用该 SQL 模式，我可以获得给定用户的所有非后续用户，并且可以通过时间戳对它们进行比较以匹配上述要求。

但是，我希望有一个比 sql 数据库更好的数据库后端来表示这个数据集。我一直在尝试使用 redis，但不知道如何实现它。

我在想也许是一个文档存储-b/c 我想要做的就是获取两个数据集的差异。或者更准确地说：我想区分两个 twitter 用户 ID 列表。

有任何想法吗？

4

2 回答 2

5

比较两个数组的蛮力方法将具有 O(N*M) 的时间复杂度，其中 N 和 M 是数组的大小。因此，我们应该使用一些智能数据结构来存储它们以有效地执行此操作。

我想出了以下方法：

  1. twitter id 列表是一个集合，因为 id 是唯一的。Redis 支持集合并允许执行集合操作，例如差异。假设你有 2 套钥匙ids_at_time_x和ids_at_time_y。SADD 使用如下方式向它们添加元素：

    SADD ids_at_time_x "15424"

    当您准备好执行差异执行时

    SDIFF ids_at_time_x ids_at_time_y

    这将返回一个ids_at_time_x不存在于ids_at_time_y. 如果您想做反向操作，即检索不存在于 中的 id 列表ids_at_time_x，只需交换参数：

    SDIFF ids_at_time_y ids_at_time_x

    SDIFF 最好的一点是它的运行效率非常高——时间复杂度为 O(N)，其中 N 是这两组中元素的总数。即使您进行 2 次差异操作，时间复杂度仍然是线性的。

  2. 将它们存储为排序列表。Redis 支持排序集。添加 id 时，您必须包含一个元素分数（Redis 将根据分数进行排序），在您的情况下等于 id ：

    ZADD ids_at_time_x 15424 "15424"

    当列表准备好时，我们检索它们并在代码中比较它们。这是伪代码：

    n = size of A
m = size of B
i = 0
j = 0
setA = [] // List of elements that present only in A
setB = [] // List of elements that present only in B
intersection = [] // List of elements that present in A and B

while i < n or j < m {
  if j == m {
    setA.add(A[i])
    i = i + 1
  } else if i == n {
    setB.add(B[j])
    j = j + 1
  } else if A[i] < B[j] {
    setA.add(A[i])
    i = i + 1
  } else if B[j] < A[i] {
    setB.add(B[j])
    j = j + 1
  } else {
    intersection.add(A[i])
    i = i + 1
    j = j + 1
  }
}

    解释：我们使用 A 和 B 已排序的事实。我们有两个索引，都从零开始。比较 A 和 B 的两个第一个元素。如果 A[0] 小于 B[0]，我们知道 A[0] 只存在于 A 中，因此我们将其添加到列表 setA 并将 A 的索引增加一. 如果 B[0] 小于 A[0]，我们将 B[0] 添加到列表 setB 并将 B 的索引增加一。如果 A[0] == B[0] 我们将 A[0] 添加到交叉点列表并增加两个索引。此代码也适用于线性时间 O(N)，其中 N 是 A 和 B 中元素的总数。

    请注意，这种方法适用于任何可以返回排序列表的数据库，这意味着您可以将其存储在传统的 SQL 数据库中并使用ORDER BY twitter_id) 检索列表。

查看 Redis 支持的所有数据类型及其命令的完整列表，它们都有很好的文档记录。Redis 也有多种语言的官方客户端，所以这应该不是问题。您仍然可以将重要数据存储在 SQL 数据库中，并让 Redis 处理 id 列表。

于 2012-05-28T04:24:42.923 回答
0

neo4j (http://neo4j.org) 是一个用于将数据存储为图形的数据库引擎。我没有任何实际使用 neo4j 的经验，但它似乎很合适。

于 2012-05-28T01:48:50.180 回答