3

mixed_setsと呼ばれるタプルのリストには、3つの別個のセットが存在します。各セットには、交差する値を持つタプルが含まれています。あるセットのタプルは、別のセットのタプルと交差しません。

セットを整理するために、次のコードを考え出しました。タプルが関係している場合、Pythonセットの機能が制限されていることがわかりました。交差の設定操作で各タプルインデックスを調べ、それを囲むタプルオブジェクトで停止しないようにすると便利です。

コードは次のとおりです。

mixed_sets=  [(1,15),(2,22),(2,23),(3,13),(3,15),
              (3,17),(4,22),(4,23),(5,15),(5,17),
              (6,21),(6,22),(6,23),(7,15),(8,12),
              (8,15),(9,19),(9,20),(10,19),(10,20),
              (11,14),(11,16),(11,18),(11,19)]

def sort_sets(a_set):
    idx= 0
    idx2=0
    while len(mixed_sets) > idx and len(a_set) > idx2:
        if a_set[idx2][0] == mixed_sets[idx][0] or a_set[idx2][1] == mixed_sets[idx][1]:
            a_set.append(mixed_sets[idx])
            mixed_sets.pop(idx)
            idx=0

        else:
            idx+=1
            if idx == len(mixed_sets):
                idx2+=1
                idx=0
    a_set.pop(0) #remove first item; duplicate
    print a_set, 'a returned set'            
    return a_set

sorted_sets=[]
for new_set in mixed_sets:
    sorted_sets.append(sort_sets([new_set]))

print mixed_sets #Now empty.

OUTPUT:
[(1, 15), (3, 15), (5, 15), (7, 15), (8, 15), (3, 13), (3, 17), (5, 17), (8, 12)] a returned set
[(2, 22), (2, 23), (4, 23), (6, 23), (4, 22), (6, 22), (6, 21)] a returned set
[(9, 19), (10, 19), (10, 20), (11, 19), (9, 20), (11, 14), (11, 16), (11, 18)] a returned set

現在、これはこのタスクを実行するための最もPython的な方法のようには見えません。このコードはタプルの大きなリスト（約2E6）を対象としており、既にソートされているタプルをチェックする必要がなければ、プログラムの実行が速くなると感じました。したがって、pop（）を使用してmixed_setsリストを縮小しました。pop（）を使用すると、リスト内包表記、forループ、またはイテレータに問題があることがわかったため、代わりにwhileループを使用しました。

それは機能しますが、whileループとidxおよびidx2カウンターを使用しない、このタスクを実行するためのよりPython的な方法はありますか？

4

1 に答える 1

0

おそらく、最初に mixed_sets のタプルのすべての最初の要素のセットと、すべての 2 番目の要素のセットを計算することで、速度を上げることができます。次に、反復で、最初または 2 番目の要素がこれらのセットのいずれかに含まれているかどうかを確認し、二分探索を使用して正しい完全なタプルを見つけることができます。実際には、辞書を使用してシミュレートできるマルチセットが必要です。

[現在テストされていません]のようなもの：

from collections import defaultdict
# define the mixed_sets list.
mixed_sets.sort()
first_els = defaultdict(int)
secon_els = defaultdict(int)

for first,second in mixed_sets:
    first_els[first] += 1
    second_els[second] += 1


def sort_sets(a_set):
    index= 0
    while mixed_sets and len(a_set) > index:
        first, second = a_set[index]
        if first in first_els or second in second_els:
            if first in first_els:
                element = find_tuple(mixed_sets, first, index=0)
                first_els[first] -= 1
                if first_els[first] <= 0:
                    del first_els[first]
            else:
                element = find_tuple(mixed_sets, second, index=1)
                second_els[second] -= 1
                if second_els[second] <= 0:
                    del second_els[second]

            a_set.append(element)
            mixed_sets.remove(element)
        index += 1
    a_set.pop(0) #remove first item; duplicate
    print a_set, 'a returned set'            
    return a_set

"find_tuple(mixed_sets, first, index=0,1)" は、指定されたインデックスで "first" を持つ mixed_sets に属するタプルを返します。

おそらく、mixed_sets も複製し、コピーの 1 つを最初の要素で、もう 1 つを 2 番目の要素で並べ替える必要があります。

または、再び辞書で遊ぶこともできます。「first_els」と「second_els」の値にタプルのソート済みリストも追加します。

パフォーマンスがどのようにスケーリングするかはわかりませんが、データが 200 万のオーダーであれば、あまり心配する必要はないと思います。

于 2012-08-16T19:43:05.157 に答える