2つのpython-listsで共通の属性を持つオブジェクトを見つけるのに効率的な方法

Question

見出しが混乱している可能性があります - 私は何をしたいのか説明しようとします： 私はコンピュータ科学を勉強していて、私の講義「Data-Warehousing &データマイニング」のプロジェクトとしてお勧めします。今、私は映画評価によって2人のユーザーの類似度を計算しようとしています。

class Rating(Model): 
    def __init__(self, userID, movieID, rating): 
      ... 

私は評価の__eq__, __ne__ and __hash__をオーバーライドだけ、彼らの両方が評価されている映画を見つけるために、2ユーザーの評価のセットを作成することを可能にするMOVIEIDを考えます。ユーザー/自分の評価のエオシン-距離を計算することを可能にするために、同じ順序でソート 2つのリスト：

def similarity(userA, userB): 
    ratingsA = userA.ratings 
    ratingsB = userB.ratings 
    common_ratings = set((ratingsA, ratingsB)) 

私が今欲しい

は、次のようなものです。

[Rating(userID=1, movieID=4, rating=4.7), Rating(user=1, movie=7, rating=9.8)] 
[Rating(userID=2, movieID=4, rating=2.0), Rating(user=2, movie=7, rating=6.6)]  

私のアプローチは本当に好きではありませんが、私は最後のカップルの時間よりも良い方法を見つけることができませんでした。

もう、あまり効率的な方法は、（？と思う）、このようなものだ：40000本の映画や確率の周りにあるので、

lA = [] 
lB = [] 
for rA in ratingsA: 
    for rB in ratingsB: 
     if rA.movieID == rB.movieID: 
      lA.append(rA) 
      lB.append(rB) 
sim = cos_dist(lA, lB) 

このアプローチは、おそらく動作しますが、私は、実行時には恐ろしいだろうと思います2人のユーザーが同じ映画を評価してもかなり低いです...

多分誰かが効率的なアプローチをしていますか？ ありがとうございます！

Answer 1

あなたのアプローチはO（N^2）最悪の場合です。

sorted_ratingsA = sorted(ratingsA, lambda x: x.movieID) 
sorted_ratingsB = sorted(ratingsB, lambda x: x.movieID) 

そして今、我々は、（効率の理由から）最後の1からこれらのリストから項目をポップし、movieID上の順序を使用することができます：あなたはO（N Nをログ）評価リストをソートする複雑さを軽減することができます特定のIDがユーザーによって評価されたかどうかをチェックします。線に沿って何か：

lA = [] 
lB = [] 
maxA = sorted_ratingsA.pop() 
maxB = sorted_ratingsB.pop() 
while sorted_ratingsA and sorted_ratingsB: 
    if maxA.movieID == maxB.movieID: 
     lA.append(maxA) 
     lb.append(maxB) 
     # instead of the following two pop calls you could simply 
     # change the elif into a new if statement. 
     maxA = sorted_ratingsA.pop() 
     maxB = sorted_ratingsB.pop() 
    elif maxA < maxB: 
     maxB = sorted_ratingsB.pop() 
    else: 
     maxA = sorted_ratingsA.pop() 

あなたは、同じIDのいずれかが検出されるまでの最大値がポップさやidが以下になるまで、その場合には、あなたが他のリストから飛び出る開始含まれているリストを見ることができるように。リストが昇順になっているということは、すべての一致がO（N log N）にあることを意味します。

listの終わりをポップするとpop(0)のようなものを使用すると、平均的に各POPのO（N）の費用がかかるとO（Nを再導入だろうがは、 O（1）時間を償却かかるのでpop()を使用することが不可欠です^ 2）因子。

---

代わりに、ハッシングを使用するだけで、平均時間O（N）になるはずです。最初movieIDから評価への2つのマップを作成し、マップを交差：

mapA = {x.movieId: x for x in ratingsA} 
mapB = {x.movieId: x for x in ratingsB} 
common_keys = mapA.keys() & mapB.keys() 

lA = [mapA[k] for k in common_keys] 
lB = [mapB[k] for k in common_keys] 

あなたは< 3.xのはviewkeys()でkeys()を置き換えるのpythonを使用している場合。

注：set変化に対する繰り返し順序がセットが変更された場合にのみので、この解決策は、ハッシュ、lAとlBマッチの順序を使用するので、2回の反復が上記対応する評価を取得した場合でも。ただし、レーティング自体の順番は定義されていません（movieIDが表示される順序はわかりませんが、lAとlBの間で一致します）。

---

これらのオブジェクトは、それだけでデータベースがあなたのために検索を行うようにする方が良いですSQLデータベース内にある場合は、どのような場合には、あなたの質問にSQLを言及しませんでした。おそらく、様々な分野でrankingsテーブルを持っている、あなたがやりたい ：

SELECT * FROM rankings 
JOIN rankings AS rankings2 
ON rankings.movieID = rankings2.movieID