1

バックグラウンド

2つのリストがあります。最初のリストにitemsは約250のタプルが含まれ、各タプルには3つの要素が含まれています。

(path_to_a_file, size_in_bytes, modified_time)

2番目のリストには、最大250の要素が含まれています。これは、リストresult内のパスに基づいて行を検索するデータベースクエリの結果です。itemsの要素の数はresult、それらのファイルがすでにデータベースにあるかどうかによって異なります。

結果の各要素は、SQLAlchemyクエリから返された行オブジェクトであり、行の値の属性が含まれています（、、pathおよびmtimeここhashで関心のあるものです）

私がやろうとしているのは、同じmtimeを持つすべての要素を除外しitems（resultsそして、フィルタリングされた数と合計サイズを追跡し）、異なるmtimeを持つアイテムまたはそうでないアイテムで新しいリストを作成することですに存在しresultます。(path,size,mtime_from_result,hash_from_result)mtimeが異なるアイテムと、データベースになかったアイテムを保存する必要があります(path,size,mtime,None)。

これをあまりローカライズしないようにしたいと思いますが、質問をするために何を達成しようとしているのかを説明する必要があると感じました。

問題

このループをできるだけ速くしたいのですが、最も重要なのは期待どおりに機能させることです。

アイテムを繰り返し処理するときに、リストからアイテムを削除しても安全ですか？前方への反復は奇妙な結果をもたらすことに気づきましたが、後方への反復は問題ないようです。より良いアプローチはありますか？

関係が1対1であり、再び一致しないことがわかっているため、一致したアイテム（i.path == j[0]）を削除します。リストを減らすことで、次の反復でより速く反復でき、さらに重要なことに、すべての比類のないアイテムを残しました。

おそらくリスト内包表記やジェネレーターを使用して、私が見落としているはるかに優れたソリューションがあると感じずにはいられません。

send_items=[]
for i in result[::-1]:
    for j in items[::-1]:
        if i.path==j[0]:
            result.remove(i) #I think this remove is possibly pointless?
            items.remove(j)
            if i.mtime==j[2]:
                self.num_skipped+=1
                self.size_skipped+=j[1]
            else:
                send_items.append((j[0],j[1],i.mtime,i.hash))
            break
send_items.extend(((j[0],j[1],j[2],None) for j in items))
4

4 に答える 4

1

私はこれを次のように行います：

def get_send_items(items, results):
    send_items = []
    results_dict = {i.path:i for i in results}
    for p, s, m in items:
        result = results_dict.get(p)
        if result is None:
            send_items.append((p, s, m, None))
        elif result.mtime != m:
            send_items.append((p, s, result.mtime, result.hash))
    return send_items

これがあなたの解決策の私の分析です（両方とも長さNであると仮定しますresult）items：

  • result[::-1]のコピーを作成するresultので、呼び出しresult.remove(i)は反復に影響しません。また、とにかく影響しません。ループはresult1回だけなので、要素を削除しても意味がありません。それは余分な仕事を生み出すだけです。
  • result[::]のコピーを作成するために呼び出すことができますresult。
  • 呼び出すとitems.remove(j)、実際には効率が低下します。remove()O（N）時間がかかります。したがって、これを呼び出すと、アルゴリズムの効率がO（N ^ 2）からO（N ^ 3）に低下します。
  • （私のソリューションのように）O（N）の追加メモリを使用することにより、辞書またはO（1）ルックアップを持つセットを使用する場合、実行時間をO（N）に短縮できます。
于 2012-06-21T14:34:05.020 に答える
0

最初の刺し傷：

items_dict = dict( (el[0], el[1:]) for el in items )
new = []
modified = []
other = []
for res in result:
    put_to = None
    item = items_dict.get(res.path, (None, None))
    if item is (None, None):
        put_to = new
    elif res.mtime != item[1]:
        put_to = modified
    else:
        put_to = other
    put_to.append( (res.path, item) )
于 2012-06-21T14:39:04.127 に答える
0

まず第一に、私はファイルパスがファイルを識別すると仮定しています-それらは一意です。

結果の辞書を作成するので、メンバーシップを簡単に確認し、それに関連付けられた値を確認できます。

dict_results = {file: (size, modified_time) for file, size, modified_time in results}

次に、リスト内包表記を使用して、不要な要素を除外できます。

[(file, size, modified_time) for file, size, modified_time in items if (file not in dict_results) or (not dict_results[file][1] == modified_time)]

例えば：

>>> results = [(1, 1, 1), (2, 2, 3)]
>>> items = [(1, 1, 1), (2, 2, 2), (3, 3, 3)]
>>> dict_results = {file: (size, modified_time) for file, size, modified_time in results}
>>> [(file, size, modified_time) for file, size, modified_time in items if (file not in dict_results) or (not dict_results[file][1] == modified_time)]
[(2, 2, 2), (3, 3, 3)]
于 2012-06-21T14:31:22.730 に答える
0

Marcinが示唆するように結果をセットに挿入し、リスト内包表記を使用してアイテムをフィルタリングするのはどうですか。

mtimes_set = set(result[2] for result in results)
send_items = (item for item in items if item[2] not in mtimes_set)

パス部分を誤解しました。これはまだ実行できます（ただし、最後の括弧のセットについては少し醜いです）。

path_dict = dict((result[0], result) for result in results)
send_items = (item for item in items if item[0] in path_dict and path_dict[item[0]][2] != item[2])

ここでは、見たパスのディクショナリを作成してから、dictにパスがあり、mtimeが異なるパスを返すジェネレーターを作成しています。今すぐアイテムではなく、ここではなくpath_dict結果アイテムを返すように変更するのは簡単です。

于 2012-06-21T14:32:57.890 に答える