2

あなたがフォローしているがフォローしていないTwitterユーザーのリストを取得するアプリ（特定のTwitterユーザー用）があります。それはこれを行います：

  • 時間xと時間yの2つのリストを比較し、より多くの人があなたをフォローしているかどうかを確認します。
  • Twitterユーザーxがあなたをフォローバックするのにかかった時間を確認してください。
  • ユーザーxがあなたをフォローバックするのにかかったリツイート/コメントの数を確認してください

私が思いついた簡単な方法は、持っているだけです-多くはユーザーとの関係に属しており、人々はあなたをフォローしていません。例：

User table
-id

TwitterUser table
-user_id 
-timestamp
-isFollowing

したがって、そのSQLスキーマを使用すると、特定のユーザーのフォローしていないすべてのユーザーを取得でき、タイムスタンプで比較して上記の要件に一致させることができます。

ただし、SQLデータベースよりもこのデータセットを表すのに優れたDBバックエンドがあることを期待していました。私はredisを使って実験してきましたが、どうやってそれをやってのけるのかわかりません。

私はおそらくドキュメントストアを考えています-b/c私がやりたいのは、2つのデータセットの差分を取ることだけです。もっと正確に言うと、TwitterユーザーIDの2つのリストを比較したいと思います。

何か案は？

4

2 に答える 2

5

2つのアレイを比較するブルートフォースアプローチでは、時間計算量がO（N * M）になります。ここで、NとMはアレイのサイズです。したがって、これを効率的に行うには、代わりにインテリジェントなデータ構造を使用してそれらを保存する必要があります。

私は次のアプローチを思いついた：

  1. Twitter IDのリストは、IDが一意であるため、セットになっています。Redisはセットをサポートし、差分などのセット操作を実行できます。キーids_at_time_xと。を含む2つのセットがあるとしますids_at_time_y。次のように要素を追加しますSADD 。

    SADD ids_at_time_x "15424"

    差分実行を実行する準備ができたら

    SDIFF ids_at_time_x ids_at_time_y

    ids_at_time_xこれにより、に存在しないIDのリストが返されids_at_time_yます。逆の操作を行う場合、つまり、に存在しないIDのリストを取得する場合はids_at_time_x、引数を交換するだけです。

    SDIFF ids_at_time_y ids_at_time_x

    SDIFFの最も優れている点は、非常に効率的に動作することです。時間計算量はO（N）です。ここで、Nはこれら2つのセットの要素の総数です。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がソートされているという事実を使用します。2つのインデックスがあり、どちらもゼロから始まります。AとBの最初の2つの要素を比較します。A[0]がB[0]より小さい場合、A [0]はAにのみ存在することがわかっているので、それをリストsetAに追加し、Aのインデックスを1つ増やします。 。B[0]がA[0]より小さい場合、リストsetBにB [0]を追加し、Bのインデックスを1つ増やします。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 に答える