49

次のような整数のリストがあると考えてください。

#--------------------------------------
0 [0,1,3]
1 [1,0,3,4,5,10,...]
2 [2,8]
3 [3,1,0,...]
...
n []
#--------------------------------------

問題は、少なくとも1つの共通要素を持つリストをマージすることです。したがって、特定の部分のみの結果は次のようになります。

#--------------------------------------
0 [0,1,3,4,5,10,...]
2 [2,8]
#--------------------------------------

大きなデータ(要素は単なる数値)でこれを行う最も効率的な方法は何ですか?tree構造について考えることはありますか ?私は今、リストを交差点に変換して反復することで仕事をしていますがsets、遅いです!さらに、とても初歩的な感じがします!さらに、一部のリストはいつかマージされないままであるため、実装には何か(不明)が欠けています!そうは言っても、自己実装を提案する場合は、寛大で、簡単なサンプルコード[明らかにPythonが私のお気に入りです:)]または疑似コードを提供してください。
更新1: これが私が使用していたコードです:

#--------------------------------------
lsts = [[0,1,3],
        [1,0,3,4,5,10,11],
        [2,8],
        [3,1,0,16]];
#--------------------------------------

関数は(バグあり!!):

#--------------------------------------
def merge(lsts):
    sts = [set(l) for l in lsts]
    i = 0
    while i < len(sts):
        j = i+1
        while j < len(sts):
            if len(sts[i].intersection(sts[j])) > 0:
                sts[i] = sts[i].union(sts[j])
                sts.pop(j)
            else: j += 1                        #---corrected
        i += 1
    lst = [list(s) for s in sts]
    return lst
#--------------------------------------

結果は次のとおりです。

#--------------------------------------
>>> merge(lsts)
>>> [0, 1, 3, 4, 5, 10, 11, 16], [8, 2]]
#--------------------------------------

更新2: 私の経験では、以下のNiklas Baumstarkによって提供されたコードは、単純なケースでは少し速いことが示されました。「Hooked」によって与えられた方法は完全に異なるアプローチであるため、まだテストされていません(ちなみにそれは興味深いようです)。これらすべてのテスト手順は、結果を保証するのが非常に難しいか、不可能である可能性があります。私が使用する実際のデータセットは非常に大きく複雑であるため、繰り返すだけではエラーを追跡することはできません。つまり、モジュールとして大きなコード内でメソッドをその場所にプッシュする前に、メソッドの信頼性に100%満足する必要があります。単純に今のところ、 Niklasの方法はより高速であり、単純集合の答えはもちろん正しいです。
しかし、実際の大規模なデータセットでうまく機能することをどのように確認できますか?エラーを視覚的に追跡することができないので!

更新3: この問題では、メソッドの信頼性が速度よりもはるかに重要であることに注意してください。最終的に最大のパフォーマンスを得るために、PythonコードをFortranに変換できるようになることを願っています。

更新4:
この投稿には多くの興味深い点があり、寛大に答え、建設的なコメントが与えられています。すべてをよく読むことをお勧めします。質問の展開、驚くべき答え、建設的なコメントと議論に感謝します。

4

18 に答える 18

26

私の試み:

def merge(lsts):
    sets = [set(lst) for lst in lsts if lst]
    merged = True
    while merged:
        merged = False
        results = []
        while sets:
            common, rest = sets[0], sets[1:]
            sets = []
            for x in rest:
                if x.isdisjoint(common):
                    sets.append(x)
                else:
                    merged = True
                    common |= x
            results.append(common)
        sets = results
    return sets

lst = [[65, 17, 5, 30, 79, 56, 48, 62],
       [6, 97, 32, 93, 55, 14, 70, 32],
       [75, 37, 83, 34, 9, 19, 14, 64],
       [43, 71],
       [],
       [89, 49, 1, 30, 28, 3, 63],
       [35, 21, 68, 94, 57, 94, 9, 3],
       [16],
       [29, 9, 97, 43],
       [17, 63, 24]]
print merge(lst)

基準:

import random

# adapt parameters to your own usage scenario
class_count = 50
class_size = 1000
list_count_per_class = 100
large_list_sizes = list(range(100, 1000))
small_list_sizes = list(range(0, 100))
large_list_probability = 0.5

if False:  # change to true to generate the test data file (takes a while)
    with open("/tmp/test.txt", "w") as f:
        lists = []
        classes = [
            range(class_size * i, class_size * (i + 1)) for i in range(class_count)
        ]
        for c in classes:
            # distribute each class across ~300 lists
            for i in xrange(list_count_per_class):
                lst = []
                if random.random() < large_list_probability:
                    size = random.choice(large_list_sizes)
                else:
                    size = random.choice(small_list_sizes)
                nums = set(c)
                for j in xrange(size):
                    x = random.choice(list(nums))
                    lst.append(x)
                    nums.remove(x)
                random.shuffle(lst)
                lists.append(lst)
        random.shuffle(lists)
        for lst in lists:
            f.write(" ".join(str(x) for x in lst) + "\n")

setup = """
# Niklas'
def merge_niklas(lsts):
    sets = [set(lst) for lst in lsts if lst]
    merged = 1
    while merged:
        merged = 0
        results = []
        while sets:
            common, rest = sets[0], sets[1:]
            sets = []
            for x in rest:
                if x.isdisjoint(common):
                    sets.append(x)
                else:
                    merged = 1
                    common |= x
            results.append(common)
        sets = results
    return sets

# Rik's
def merge_rik(data):
    sets = (set(e) for e in data if e)
    results = [next(sets)]
    for e_set in sets:
        to_update = []
        for i, res in enumerate(results):
            if not e_set.isdisjoint(res):
                to_update.insert(0, i)

        if not to_update:
            results.append(e_set)
        else:
            last = results[to_update.pop(-1)]
            for i in to_update:
                last |= results[i]
                del results[i]
            last |= e_set
    return results

# katrielalex's
def pairs(lst):
    i = iter(lst)
    first = prev = item = i.next()
    for item in i:
        yield prev, item
        prev = item
    yield item, first

import networkx

def merge_katrielalex(lsts):
    g = networkx.Graph()
    for lst in lsts:
        for edge in pairs(lst):
            g.add_edge(*edge)
    return networkx.connected_components(g)

# agf's (optimized)
from collections import deque

def merge_agf_optimized(lists):
    sets = deque(set(lst) for lst in lists if lst)
    results = []
    disjoint = 0
    current = sets.pop()
    while True:
        merged = False
        newsets = deque()
        for _ in xrange(disjoint, len(sets)):
            this = sets.pop()
            if not current.isdisjoint(this):
                current.update(this)
                merged = True
                disjoint = 0
            else:
                newsets.append(this)
                disjoint += 1
        if sets:
            newsets.extendleft(sets)
        if not merged:
            results.append(current)
            try:
                current = newsets.pop()
            except IndexError:
                break
            disjoint = 0
        sets = newsets
    return results

# agf's (simple)
def merge_agf_simple(lists):
    newsets, sets = [set(lst) for lst in lists if lst], []
    while len(sets) != len(newsets):
        sets, newsets = newsets, []
        for aset in sets:
            for eachset in newsets:
                if not aset.isdisjoint(eachset):
                    eachset.update(aset)
                    break
            else:
                newsets.append(aset)
    return newsets

# alexis'
def merge_alexis(data):
    bins = range(len(data))  # Initialize each bin[n] == n
    nums = dict()

    data = [set(m) for m in data]  # Convert to sets
    for r, row in enumerate(data):
        for num in row:
            if num not in nums:
                # New number: tag it with a pointer to this row's bin
                nums[num] = r
                continue
            else:
                dest = locatebin(bins, nums[num])
                if dest == r:
                    continue  # already in the same bin

                if dest > r:
                    dest, r = r, dest  # always merge into the smallest bin

                data[dest].update(data[r])
                data[r] = None
                # Update our indices to reflect the move
                bins[r] = dest
                r = dest

    # Filter out the empty bins
    have = [m for m in data if m]
    return have

def locatebin(bins, n):
    while bins[n] != n:
        n = bins[n]
    return n

lsts = []
size = 0
num = 0
max = 0
for line in open("/tmp/test.txt", "r"):
    lst = [int(x) for x in line.split()]
    size += len(lst)
    if len(lst) > max:
        max = len(lst)
    num += 1
    lsts.append(lst)
"""

setup += """
print "%i lists, {class_count} equally distributed classes, average size %i, max size %i" % (num, size/num, max)
""".format(class_count=class_count)

import timeit
print "niklas"
print timeit.timeit("merge_niklas(lsts)", setup=setup, number=3)
print "rik"
print timeit.timeit("merge_rik(lsts)", setup=setup, number=3)
print "katrielalex"
print timeit.timeit("merge_katrielalex(lsts)", setup=setup, number=3)
print "agf (1)"
print timeit.timeit("merge_agf_optimized(lsts)", setup=setup, number=3)
print "agf (2)"
print timeit.timeit("merge_agf_simple(lsts)", setup=setup, number=3)
print "alexis"
print timeit.timeit("merge_alexis(lsts)", setup=setup, number=3)

これらのタイミングは、クラスの数、リストの数、リストのサイズなど、ベンチマークの特定のパラメーターに明らかに依存しています。より役立つ結果を得るには、これらのパラメーターをニーズに合わせて調整してください。

以下は、さまざまなパラメーターに対する私のマシンでの出力例です。それらは、取得する入力の種類に応じて、すべてのアルゴリズムに長所と短所があることを示しています。

=====================
# many disjoint classes, large lists
class_count = 50
class_size = 1000
list_count_per_class = 100
large_list_sizes = list(range(100, 1000))
small_list_sizes = list(range(0, 100))
large_list_probability = 0.5
=====================

niklas
5000 lists, 50 equally distributed classes, average size 298, max size 999
4.80084705353
rik
5000 lists, 50 equally distributed classes, average size 298, max size 999
9.49251699448
katrielalex
5000 lists, 50 equally distributed classes, average size 298, max size 999
21.5317108631
agf (1)
5000 lists, 50 equally distributed classes, average size 298, max size 999
8.61671280861
agf (2)
5000 lists, 50 equally distributed classes, average size 298, max size 999
5.18117713928
=> alexis
=> 5000 lists, 50 equally distributed classes, average size 298, max size 999
=> 3.73504281044

===================
# less number of classes, large lists
class_count = 15
class_size = 1000
list_count_per_class = 300
large_list_sizes = list(range(100, 1000))
small_list_sizes = list(range(0, 100))
large_list_probability = 0.5
===================

niklas
4500 lists, 15 equally distributed classes, average size 296, max size 999
1.79993700981
rik
4500 lists, 15 equally distributed classes, average size 296, max size 999
2.58237695694
katrielalex
4500 lists, 15 equally distributed classes, average size 296, max size 999
19.5465381145
agf (1)
4500 lists, 15 equally distributed classes, average size 296, max size 999
2.75445604324
=> agf (2)
=> 4500 lists, 15 equally distributed classes, average size 296, max size 999
=> 1.77850699425
alexis
4500 lists, 15 equally distributed classes, average size 296, max size 999
3.23530197144

===================
# less number of classes, smaller lists
class_count = 15
class_size = 1000
list_count_per_class = 300
large_list_sizes = list(range(100, 1000))
small_list_sizes = list(range(0, 100))
large_list_probability = 0.1
===================

niklas
4500 lists, 15 equally distributed classes, average size 95, max size 997
0.773697137833
rik
4500 lists, 15 equally distributed classes, average size 95, max size 997
1.0523750782
katrielalex
4500 lists, 15 equally distributed classes, average size 95, max size 997
6.04466891289
agf (1)
4500 lists, 15 equally distributed classes, average size 95, max size 997
1.20285701752
=> agf (2)
=> 4500 lists, 15 equally distributed classes, average size 95, max size 997
=> 0.714507102966
alexis
4500 lists, 15 equally distributed classes, average size 95, max size 997
1.1286110878
于 2012-02-02T12:49:03.147 に答える
13

このトピックについてこれまでに述べられ、行われたすべてのことを、この質問と重複する質問に要約しようとしました。

すべてのソリューションをテストして時間を計ろうとしました(すべてのコードはこちら)。

テスト

これはTestCase、テスト モジュールからのものです。

class MergeTestCase(unittest.TestCase):

    def setUp(self):
        with open('./lists/test_list.txt') as f:
            self.lsts = json.loads(f.read())
        self.merged = self.merge_func(deepcopy(self.lsts))

    def test_disjoint(self):
        """Check disjoint-ness of merged results"""
        from itertools import combinations
        for a,b in combinations(self.merged, 2):
            self.assertTrue(a.isdisjoint(b))

    def test_coverage(self):    # Credit to katrielalex
        """Check coverage original data"""
        merged_flat = set()
        for s in self.merged:
            merged_flat |= s

        original_flat = set()
        for lst in self.lsts:
            original_flat |= set(lst)

        self.assertTrue(merged_flat == original_flat)

    def test_subset(self):      # Credit to WolframH
        """Check that every original data is a subset"""
        for lst in self.lsts:
            self.assertTrue(any(set(lst) <= e for e in self.merged))

このテストは、結果としてセットのリストを想定しているため、リストで機能するいくつかのソリューションをテストできませんでした。

以下をテストできませんでした。

katrielalex
steabert

私がテストできたものの中で、2つが失敗しました:

  -- Going to test: agf (optimized) --
Check disjoint-ness of merged results ... FAIL

  -- Going to test: robert king --
Check disjoint-ness of merged results ... FAIL

タイミング

パフォーマンスは、採用されたデータ テストと強く関連しています。

これまでのところ、3 つの回答が自分と他の回答の時間を計ろうとしました。彼らは異なるテストデータを使用したため、異なる結果が得られました。

  1. Niklas ベンチマークは非常に調整可能です。彼のバンクマークを使用すると、いくつかのパラメーターを変更してさまざまなテストを実行できます。

    彼が自身の回答で使用したのと同じ 3 つのパラメーター セットを使用し、それらを 3 つの異なるファイルに入れました。

    filename = './lists/timing_1.txt'
    class_count = 50,
    class_size = 1000,
    list_count_per_class = 100,
    large_list_sizes = (100, 1000),
    small_list_sizes = (0, 100),
    large_list_probability = 0.5,
    
    filename = './lists/timing_2.txt'
    class_count = 15,
    class_size = 1000,
    list_count_per_class = 300,
    large_list_sizes = (100, 1000),
    small_list_sizes = (0, 100),
    large_list_probability = 0.5,
    
    filename = './lists/timing_3.txt'
    class_count = 15,
    class_size = 1000,
    list_count_per_class = 300,
    large_list_sizes = (100, 1000),
    small_list_sizes = (0, 100),
    large_list_probability = 0.1,
    

    これは私が得た結果です:

    ファイルから:timing_1.txt

    Timing with: >> Niklas << Benchmark
    Info: 5000 lists, average size 305, max size 999
    
    Timing Results:
    10.434  -- alexis
    11.476  -- agf
    11.555  -- Niklas B.
    13.622  -- Rik. Poggi
    14.016  -- agf (optimized)
    14.057  -- ChessMaster
    20.208  -- katrielalex
    21.697  -- steabert
    25.101  -- robert king
    76.870  -- Sven Marnach
    133.399  -- hochl
    

    ファイルから:timing_2.txt

    Timing with: >> Niklas << Benchmark
    Info: 4500 lists, average size 305, max size 999
    
    Timing Results:
    8.247  -- Niklas B.
    8.286  -- agf
    8.637  -- Rik. Poggi
    8.967  -- alexis
    9.090  -- ChessMaster
    9.091  -- agf (optimized)
    18.186  -- katrielalex
    19.543  -- steabert
    22.852  -- robert king
    70.486  -- Sven Marnach
    104.405  -- hochl
    

    ファイルから:timing_3.txt

    Timing with: >> Niklas << Benchmark
    Info: 4500 lists, average size 98, max size 999
    
    Timing Results:
    2.746  -- agf
    2.850  -- Niklas B.
    2.887  -- Rik. Poggi
    2.972  -- alexis
    3.077  -- ChessMaster
    3.174  -- agf (optimized)
    5.811  -- katrielalex
    7.208  -- robert king
    9.193  -- steabert
    23.536  -- Sven Marnach
    37.436  -- hochl
    
  2. Svenのテスト データを使用すると、次の結果が得られました。

    Timing with: >> Sven << Benchmark
    Info: 200 lists, average size 10, max size 10
    
    Timing Results:
    2.053  -- alexis
    2.199  -- ChessMaster
    2.410  -- agf (optimized)
    3.394  -- agf
    3.398  -- Rik. Poggi
    3.640  -- robert king
    3.719  -- steabert
    3.776  -- Niklas B.
    3.888  -- hochl
    4.610  -- Sven Marnach
    5.018  -- katrielalex
    
  3. そして最後にAgfのベンチマークで得たもの:

    Timing with: >> Agf << Benchmark
    Info: 2000 lists, average size 246, max size 500
    
    Timing Results:
    3.446  -- Rik. Poggi
    3.500  -- ChessMaster
    3.520  -- agf (optimized)
    3.527  -- Niklas B.
    3.527  -- agf
    3.902  -- hochl
    5.080  -- alexis
    15.997  -- steabert
    16.422  -- katrielalex
    18.317  -- robert king
    1257.152  -- Sven Marnach
    

冒頭で述べたように、すべてのコードはこの git リポジトリで入手できます。すべてのマージ関数は というファイルcore.pyにあり、名前が で終わるすべての関数_mergeはテスト中に自動ロードされるため、独自のソリューションを追加/テスト/改善することは難しくありません。

また、何か問題がある場合はお知らせください。コーディングが多かったので、新鮮な目を使うことができました:)

于 2012-02-26T16:38:06.193 に答える
7

行列操作の使用

この回答の前に、次のコメントを付けましょう。

これは間違った方法です。数値が不安定になりやすく、提示されている他の方法よりもはるかに遅いため、自己責任で使用してください。

そうは言っても、動的な観点から問題を解決することに抵抗できませんでした (そして、この問題について新たな視点を得られることを願っています)。理論的には、これは常に機能するはずですが、固有値の計算はしばしば失敗する可能性があります。アイデアは、リストを行から列への流れと考えることです。2 つの行が共通の値を共有している場合、それらの間に接続フローがあります。これらの流れを水と考えると、流れの間に接続経路があると、流れが小さなプールに集まっていることがわかります。簡単にするために、小さなセットを使用しますが、それはあなたのデータセットでも機能します:

from numpy import where, newaxis
from scipy import linalg, array, zeros

X = [[0,1,3],[2],[3,1]]

データをフロー グラフに変換する必要があります。行iが値jに流れ込む場合、それを行列に入れます。ここには、3 つの行と 4 つの一意の値があります。

A = zeros((4,len(X)), dtype=float)
for i,row in enumerate(X):
    for val in row: A[val,i] = 1

一般に、4固有の値の数を取得するには、 を変更する必要があります。セットが 0 から始まる整数のリストである場合、これを単純に最大数にすることができます。ここで固有値分解を実行します。行列が正方形ではないため、正確には SVD です。

S  = linalg.svd(A)

プールの流れを表すため、この回答の 3x3 の部分のみを保持します。実際、この行列の絶対値のみが必要です。このクラスター空間にフローがあるかどうかだけを気にします。

M  = abs(S[2])

この行列 M をマルコフ行列と見なし、行の正規化によって明示的にすることができます。これが得られたら、(左) 固有値 decomp を計算します。このマトリックスの。

M /=  M.sum(axis=1)[:,newaxis]
U,V = linalg.eig(M,left=True, right=False)
V = abs(V)

連結されていない (非エルゴード) マルコフ行列には、連結されていないクラスターごとに 1 の固有値があるという優れた特性があります。これらのユニティ値に関連付けられた固有ベクトルは、必要なものです。

idx = where(U > .999)[0]
C = V.T[idx] > 0

前述の数値の不安定性のため、.999 を使用する必要があります。この時点で、完了です。独立した各クラスターは、対応する行を引き出すことができるようになりました。

for cluster in C:
    print where(A[:,cluster].sum(axis=1))[0]

意図したとおり、次のようになります。

[0 1 3]
[2]

に変更Xするlstと、次のようになります[ 0 1 3 4 5 10 11 16] [2 8]


補遺

なぜこれが役立つのでしょうか?基になるデータがどこから来たのかわかりませんが、接続が絶対的でない場合はどうなりますか? 行1に 80% の確率でエントリ3があるとします。この問題をどのように一般化しますか? 上記のフロー メソッドは問題なく機能し、その.999値によって完全にパラメーター化されます。単一性から遠ざかるほど、関連付けが緩くなります。


視覚表現

画像は 1K 語に相当するため、ここに私の例とあなたの例の行列 A と V のプロットを示しますlstV各例には 2 つの一意のリストしかないため、in が 2 つのクラスターに分割される方法に注意してください(これは、順列後に 2 つのブロックを持つブロック対角行列です)。

私の例 サンプルデータ


より迅速な実装

後から考えると、SVD ステップをスキップして、単一の分解のみを計算できることに気付きました。

M = dot(A.T,A)
M /=  M.sum(axis=1)[:,newaxis]
U,V = linalg.eig(M,left=True, right=False)

この方法の (速度以外の) 利点は、M対称であるため、計算がより高速かつ正確になることです (虚数を気にする必要はありません)。

于 2012-02-02T16:01:03.373 に答える
6

これが私の答えです。今日の一連の回答に対してチェックしていません。

交差ベースのアルゴリズムは、既存のすべてのセットに対して新しいセットをそれぞれチェックするため、O(N^2) です。そのため、各数値にインデックスを付けて O(N) 近くで実行するアプローチを使用しました (辞書検索がO(1))。次に、ベンチマークを実行しましたが、実行速度が遅いため、完全にばかげているように感じました。行う。10 ~ 15 個を超える個別のビンでテストすると、私のアルゴリズムははるかに高速になります。50 を超える個別のビンでデータをテストしてみると、非常に高速です。

(編集: ベンチマークの実行方法にも問題がありましたが、私の診断は間違っていました。繰り返されるテストの実行方法で動作するようにコードを変更しました)。

def mergelists5(data):
    """Check each number in our arrays only once, merging when we find
    a number we have seen before.
    """

    bins = range(len(data))  # Initialize each bin[n] == n
    nums = dict()

    data = [set(m) for m in data ]  # Convert to sets    
    for r, row in enumerate(data):
        for num in row:
            if num not in nums:
                # New number: tag it with a pointer to this row's bin
                nums[num] = r
                continue
            else:
                dest = locatebin(bins, nums[num])
                if dest == r:
                    continue # already in the same bin

                if dest > r:
                    dest, r = r, dest   # always merge into the smallest bin

                data[dest].update(data[r]) 
                data[r] = None
                # Update our indices to reflect the move
                bins[r] = dest
                r = dest 

    # Filter out the empty bins
    have = [ m for m in data if m ]
    print len(have), "groups in result"
    return have


def locatebin(bins, n):
    """
    Find the bin where list n has ended up: Follow bin references until
    we find a bin that has not moved.
    """
    while bins[n] != n:
        n = bins[n]
    return n
于 2012-02-26T12:56:31.713 に答える
6

編集: OK、他の質問はクローズされ、ここに投稿されました。

いい質問です!グラフの連結成分の問題と考えると、はるかに簡単です。次のコードは、優れたnetworkxグラフ ライブラリとこの質問pairsの関数を使用しています。

def pairs(lst):
    i = iter(lst)
    first = prev = item = i.next()
    for item in i:
        yield prev, item
        prev = item
    yield item, first

lists = [[1,2,3],[3,5,6],[8,9,10],[11,12,13]]

import networkx
g = networkx.Graph()
for sub_list in lists:
    for edge in pairs(sub_list):
            g.add_edge(*edge)

networkx.connected_components(g)
[[1, 2, 3, 5, 6], [8, 9, 10], [11, 12, 13]]

説明

新しい (空の) グラフを作成しますg。の各サブリストについてlists、その要素をグラフのノードと見なし、それらの間にエッジを追加します。(接続性のみを気にするので、すべてのエッジを追加する必要はありません。隣接するものだけです!)add_edgeは 2 つのオブジェクトを取り、それらをノードとして扱い (そしてそれらがまだ存在しない場合は追加します)、追加することに注意してください。それらの間の端。

次に、グラフの連結要素を見つけるだけです。問題は解決しました。-- そして、それらを交差セットとして出力します。

于 2012-02-19T22:46:51.900 に答える
3

この新しい関数は、必要最小限の分離テストのみを実行します。これは、他の同様のソリューションでは実行できないことです。また、 a を使用して、dequeリストのスライスやリストの早い段階からの削除など、できるだけ多くの線形時間操作を回避します。

from collections import deque

def merge(lists):
    sets = deque(set(lst) for lst in lists if lst)
    results = []
    disjoint = 0
    current = sets.pop()
    while True:
        merged = False
        newsets = deque()
        for _ in xrange(disjoint, len(sets)):
            this = sets.pop()
            if not current.isdisjoint(this):
                current.update(this)
                merged = True
                disjoint = 0
            else:
                newsets.append(this)
                disjoint += 1
        if sets:
            newsets.extendleft(sets)
        if not merged:
            results.append(current)
            try:
                current = newsets.pop()
            except IndexError:
                break
            disjoint = 0
        sets = newsets
    return results

特定のデータ セット内のセット間のオーバーラップが少ないほど、他の関数よりも優れた結果が得られます。

以下は事例です。4 つのセットがある場合は、比較する必要があります。

1、2
1、3
1、4
2、3
2、4
3、4

1 が 3 とオーバーラップする場合、2 と 3 のテストを安全にスキップするために、2 が 1 とオーバーラップするかどうかを確認するために 2 を再テストする必要があります。

これに対処するには 2 つの方法があります。1 つ目は、オーバーラップとマージのたびに、他のセットに対してセット 1 のテストを再開することです。2 つ目は、1 と 4 を比較してテストを続行し、戻って再テストすることです。後者の場合、1 回のパスでより多くのマージが発生するため、分離テストが少なくなり、再テスト パスではテスト対象のセットが少なくなります。

問題は、どのセットを再テストする必要があるかを追跡することです。上記の例では、1 は 2 に対して再テストする必要がありますが、4 に対しては再テストする必要はありません。これは、4 が最初にテストされる前に、1 がすでに現在の状態にあったためです。

カウンターにより、disjointこれを追跡できます。


私の答えは、FORTRAN に再コーディングするための改善されたアルゴリズムを見つけるという主な問題には役立ちません。これは、Python でアルゴリズムを実装する最も単純で最も洗練された方法であると私には思えます。

私のテスト(または受け入れられた回答のテスト)によると、次の最速のソリューションよりもわずかに(最大10%)高速です。

def merge0(lists):
    newsets, sets = [set(lst) for lst in lists if lst], []
    while len(sets) != len(newsets):
        sets, newsets = newsets, []
        for aset in sets:
            for eachset in newsets:
                if not aset.isdisjoint(eachset):
                    eachset.update(aset)
                    break
            else:
                newsets.append(aset)
    return newsets

他の実装で使用される非 Pythonic カウンター ( irange) や複雑なミューテーション ( delpop、 ) は必要ありません。insert単純な反復のみを使用し、重複するセットを最も単純な方法でマージし、データを通過するたびに単一の新しいリストを作成します。

テストコードの私の(より高速でシンプルな)バージョン:

import random

tenk = range(10000)
lsts = [random.sample(tenk, random.randint(0, 500)) for _ in range(2000)]

setup = """
def merge0(lists):
  newsets, sets = [set(lst) for lst in lists if lst], []
  while len(sets) != len(newsets):
    sets, newsets = newsets, []
    for aset in sets:
      for eachset in newsets:
        if not aset.isdisjoint(eachset):
          eachset.update(aset)
          break
      else:
        newsets.append(aset)
  return newsets

def merge1(lsts):
  sets = [set(lst) for lst in lsts if lst]
  merged = 1
  while merged:
    merged = 0
    results = []
    while sets:
      common, rest = sets[0], sets[1:]
      sets = []
      for x in rest:
        if x.isdisjoint(common):
          sets.append(x)
        else:
          merged = 1
          common |= x
      results.append(common)
    sets = results
  return sets

lsts = """ + repr(lsts)

import timeit
print timeit.timeit("merge0(lsts)", setup=setup, number=10)
print timeit.timeit("merge1(lsts)", setup=setup, number=10)
于 2012-02-22T18:14:34.287 に答える
2

これは、共通の要素が1つでもあるセットをマージするというcomingstormのヒントのおかげで、互いに素なセットのデータ構造(具体的には互いに素なフォレスト)を使用した実装です。わずかな(〜5%)速度向上のためにパス圧縮を使用しています。それは完全に必要というわけではありません(そしてそれは物事を遅くする可能性のある末尾再帰になるのを防ぎます)。ばらばらの森を表すためにaを使用していることに注意してください。データがsであるとすると、配列も機能しますが、それほど高速ではない可能性があります。finddictint

def merge(data):
    parents = {}
    def find(i):
        j = parents.get(i, i)
        if j == i:
            return i
        k = find(j)
        if k != j:
            parents[i] = k
        return k
    for l in filter(None, data):
        parents.update(dict.fromkeys(map(find, l), find(l[0])))
    merged = {}
    for k, v in parents.items():
        merged.setdefault(find(v), []).append(k)
    return merged.values()

このアプローチは、Rikのベンチマークの他の最良のアルゴリズムに匹敵します。

于 2012-08-22T00:15:29.830 に答える
1

楽しみのためだけに...

def merge(mylists):
    results, sets = [], [set(lst) for lst in mylists if lst]
    upd, isd, pop = set.update, set.isdisjoint, sets.pop
    while sets:
        if not [upd(sets[0],pop(i)) for i in xrange(len(sets)-1,0,-1) if not isd(sets[0],sets[i])]:
            results.append(pop(0))
    return results

そしてベストアンサーの書き直し

def merge(lsts):
  sets = map(set,lsts)
  results = []
  while sets:
    first, rest = sets[0], sets[1:]
    merged = False
    sets = []
    for s in rest:
      if s and s.isdisjoint(first):
        sets.append(s)
      else:
        first |= s
        merged = True
    if merged: sets.append(first)
    else: results.append(first)
  return results
于 2012-02-21T18:52:56.433 に答える
1

まず、ベンチマークが公平かどうかは正確にはわかりません。

関数の先頭に次のコードを追加します。

c = Counter(chain(*lists))
    print c[1]
"88"

これは、すべてのリストのすべての値のうち、88 個の異なる値しかないことを意味します。通常、現実の世界では重複はまれであり、より多くの異なる値が期待されます。(もちろん、あなたのデータがどこから来たのかわからないので、推測することはできません)。

重複はより一般的であるため、セットがばらばらである可能性が低いことを意味します。これは、 set.isdisjoint() メソッドがはるかに高速になることを意味します。これは、いくつかのテストの後にのみ、セットがばらばらではないことが判明するためです。

そうは言っても、ディスジョイントを使用する提示された方法がとにかく最速であると信じていますが、20倍高速である代わりに、異なるベンチマークテストを使用する他の方法よりも10倍高速であるべきだと言っているだけです。

とにかく、これを解決するために少し異なる手法を試してみようと思いましたが、マージソートが遅すぎました.この方法は、ベンチマークを使用した2つの最速の方法よりも約20倍遅いです:

全部注文しようと思った

import heapq
from itertools import chain
def merge6(lists):
    for l in lists:
        l.sort()
    one_list = heapq.merge(*[zip(l,[i]*len(l)) for i,l in enumerate(lists)]) #iterating through one_list takes 25 seconds!!
    previous = one_list.next()

    d = {i:i for i in range(len(lists))}
    for current in one_list:
        if current[0]==previous[0]:
            d[current[1]] = d[previous[1]]
        previous=current

    groups=[[] for i in range(len(lists))]
    for k in d:
        groups[d[k]].append(lists[k]) #add a each list to its group

    return [set(chain(*g)) for g in groups if g] #since each subroup in each g is sorted, it would be faster to merge these subgroups removing duplicates along the way.


lists = [[1,2,3],[3,5,6],[8,9,10],[11,12,13]]
print merge6(lists)
"[set([1, 2, 3, 5, 6]), set([8, 9, 10]), set([11, 12, 13])]""



import timeit
print timeit.timeit("merge1(lsts)", setup=setup, number=10)
print timeit.timeit("merge4(lsts)", setup=setup, number=10)
print timeit.timeit("merge6(lsts)", setup=setup, number=10)
5000 lists, 5 classes, average size 74, max size 1000
1.26732238315
5000 lists, 5 classes, average size 74, max size 1000
1.16062907437
5000 lists, 5 classes, average size 74, max size 1000
30.7257182826
于 2012-02-23T22:16:19.210 に答える
1
lists = [[1,2,3],[3,5,6],[8,9,10],[11,12,13]]

import networkx as nx
g = nx.Graph()

for sub_list in lists:
    for i in range(1,len(sub_list)):
        g.add_edge(sub_list[0],sub_list[i])

print nx.connected_components(g)
#[[1, 2, 3, 5, 6], [8, 9, 10], [11, 12, 13]]

パフォーマンス:

5000 lists, 5 classes, average size 74, max size 1000
15.2264976415

merge1 のパフォーマンス:

print timeit.timeit("merge1(lsts)", setup=setup, number=10)
5000 lists, 5 classes, average size 74, max size 1000
1.26998780571

したがって、最速よりも 11 倍遅くなります..しかし、コードははるかにシンプルで読みやすいです!

于 2012-02-21T23:40:20.237 に答える
1

これは私の更新されたアプローチになります:

def merge(data):
    sets = (set(e) for e in data if e)
    results = [next(sets)]
    for e_set in sets:
        to_update = []
        for i,res in enumerate(results):
            if not e_set.isdisjoint(res):
                to_update.insert(0,i)

        if not to_update:
            results.append(e_set)
        else:
            last = results[to_update.pop(-1)]
            for i in to_update:
                last |= results[i]
                del results[i]
            last |= e_set

    return results

注:マージ中に空のリストが削除されます。

更新:信頼性。

成功の 100% の信頼性を得るには、次の 2 つのテストが必要です。

  • 結果のすべてのセットが相互にばらばらであることを確認します。

    merged = [{0, 1, 3, 4, 5, 10, 11, 16}, {8, 2}, {8}]
    
    from itertools import combinations
    for a,b in combinations(merged,2):
        if not a.isdisjoint(b):
            raise Exception(a,b)    # just an example
    
  • マージされたセットが元のデータをカバーしていることを確認してください。(カトリエラレックスの提案による)

これには少し時間がかかると思いますが、100% 確実にしたい場合は、それだけの価値があるかもしれません。

于 2012-02-02T14:55:41.497 に答える
1

これは、Niklas が提供するソリューションよりも遅くなります (test.txt では、彼のソリューションでは 0.5 秒ではなく 3.9 秒でした) が、同じ結果が得られ、セットを使用しないため、Fortran などで実装する方が簡単な場合があります。 、要素の合計量を並べ替えてから、それらすべてを1回実行するだけです。

マージされたリストの ID を含むリストを返すため、空のリストも追跡され、マージされないままになります。

def merge(lsts):
        # this is an index list that stores the joined id for each list
        joined = range(len(lsts))
        # create an ordered list with indices
        indexed_list = sorted((el,index) for index,lst in enumerate(lsts) for el in lst)
        # loop throught the ordered list, and if two elements are the same and
        # the lists are not yet joined, alter the list with joined id
        el_0,idx_0 = None,None
        for el,idx in indexed_list:
                if el == el_0 and joined[idx] != joined[idx_0]:
                        old = joined[idx]
                        rep = joined[idx_0]
                        joined = [rep if id == old else id for id in joined]
                el_0, idx_0 = el, idx
        return joined
于 2012-02-07T08:58:38.833 に答える
1

これは、マージ関数の結果が OK かどうかを確認する関数 (Python 3.1) です。以下をチェックします。

  • 結果セットはばらばらですか? (和集合の要素数 == 要素数の和)
  • 結果セットの要素は入力リストの要素と同じですか?
  • すべての入力リストは結果セットのサブセットですか?
  • すべての結果セットは最小限ですか。つまり、結果セットを 2 つの小さなセットに分割することは不可能ですか?
  • 空の結果セットがあるかどうかはチェックしませ-必要かどうかはわかりません...

.

from itertools import chain

def check(lsts, result):
    lsts = [set(s) for s in lsts]
    all_items = set(chain(*lsts))
    all_result_items = set(chain(*result))
    num_result_items = sum(len(s) for s in result)
    if num_result_items != len(all_result_items):
        print("Error: result sets overlap!")
        print(num_result_items, len(all_result_items))
        print(sorted(map(len, result)), sorted(map(len, lsts)))
    if all_items != all_result_items:
        print("Error: result doesn't match input lists!")
    if not all(any(set(s).issubset(t) for t in result) for s in lst):
        print("Error: not all input lists are contained in a result set!")

    seen = set()
    todo = list(filter(bool, lsts))
    done = False
    while not done:
        deletes = []
        for i, s in enumerate(todo): # intersection with seen, or with unseen result set, is OK
            if not s.isdisjoint(seen) or any(t.isdisjoint(seen) for t in result if not s.isdisjoint(t)):
                seen.update(s)
                deletes.append(i)
        for i in reversed(deletes):
            del todo[i]
        done = not deletes
    if todo:
        print("Error: A result set should be split into two or more parts!")
        print(todo)
于 2012-02-20T03:21:46.583 に答える
-1

私のソリューションは、小さなリストでうまく機能し、依存関係なしで非常に読みやすいです。

def merge_list(starting_list):
    final_list = []
    for i,v in enumerate(starting_list[:-1]):
        if set(v)&set(starting_list[i+1]):
            starting_list[i+1].extend(list(set(v) - set(starting_list[i+1])))
        else:
            final_list.append(v)
    final_list.append(starting_list[-1])
    return final_list

それをベンチマークする:

リスト = [[1,2,3]、[3,5,6]、[8,9,10]、[11,12,13]]

%timeit merge_list(リスト)

100000 ループ、ベストオブ 3: ループあたり 4.9 µs

于 2015-02-23T22:11:29.017 に答える