Python: fusion de liste simple basée sur des intersections

Question

Envisager il y a quelques listes d'entiers:

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

La question est de fusionner des listes ayant au moins un élément en commun. Donc uniquement les résultats de la partie donnée sera comme suit:

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

Quel est le moyen le plus efficace pour ce faire sur des données de grande taille (les éléments sont juste des chiffres)? Est - tree de la structure de quelque chose à penser? - Je faire le travail maintenant, par la conversion de listes d' sets et d'itération pour les intersections, mais il est lent! En outre, j'ai un sentiment qui est si-élémentaire! En outre, la mise en œuvre manque de quelque chose (inconnu) parce que certaines listes restent dissociées parfois! Ceci étant dit, si vous avez été en proposant de l'auto-mise en œuvre s'il vous plaît être généreux et de fournir un exemple simple de code [apparemment Python est mon favoriate :)] ou pesudo-code.
Mise à jour 1: Voici le code que j'utilisais:

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

La fonction est (buggy!!):

#--------------------------------------
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
#--------------------------------------

Le résultat est:

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

Mise à jour 2: Mon expérience le code donné par Niklas Baumstark ci-dessous ont montré pour être un peu plus rapide pour les cas simples. Pas testé la méthode donnée par une "Accro" pourtant, depuis qu'il est tout à fait différent (par la façon dont il semble intéressant). La procédure de test pour l'ensemble de ces pourrait être vraiment difficile, voire impossible, de s'assurer de résultats. Le jeu de données réelles, je vais utiliser est si vaste et complexe, de sorte qu'il est impossible de remonter toute erreur juste en répétant. C'est j'ai besoin d'être satisfait à 100% de la fiabilité de la méthode avant de le pousser à sa place au sein d'un grand code dans un module. Simplement pour l'instant Niklass'méthode est plus rapide et la réponse à de simples jeux est correct, bien sûr.
Cependant comment puis-je être sûr qu'il fonctionne bien pour de vrai grand ensemble de données? Depuis, je ne vais pas être en mesure de tracer les erreurs visuellement!

Mise à jour 3: Notez que la fiabilité de la méthode est beaucoup plus importante que la vitesse de ce problème. Je vais être espérons-le, en mesure de traduire le code Python pour Fortran pour le maximum de performance, enfin.

Mise à jour 4:
Il y a beaucoup de points intéressants dans ce post et généreusement donné les réponses, les commentaires constructifs. Je vous recommande de lire tout à fond. Veuillez accepter mes remerciements pour le développement de la question, étonnantes réponses et des commentaires constructifs et de discussion.

Answer 1

Ma tentative:

def merge(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

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)

Référence:

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)

Ces timings sont évidemment dépendants sur les paramètres spécifiques à l'indice de référence, à l'instar de nombre de classes, nombre de listes, de la taille de la liste, etc. Adapter ces paramètres à votre besoin pour obtenir plus de résultats utiles.

Ci-dessous sont quelques exemples de sorties sur ma machine pour les différents paramètres. Ils montrent que tous les algorithmes ont leurs forces et leurs faiblesses, en fonction du type d'entrée qu'ils obtiennent:

=====================
# 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

Answer 2

J'ai essayé de summurize tout ce qui a été dit et fait sur ce sujet dans cette question et dans le double emploi.

J'ai essayé de test et le temps de chaque solution (tout le code ici).

Les tests

C'est l' TestCase à partir du module de test:

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))

Ce test est en supposant une liste de jeux comme résultat, donc je ne pouvais pas tester un couple de sulutions qui a travaillé avec des listes.

Je ne pouvais pas tester la suivante:

katrielalex
steabert

Parmi ceux que j'ai pu tester, la panne de deux:

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

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

Calendrier

Les performances sont fortement corrélées avec les données de test utilisé.

Jusqu'à présent, trois réponses essayé de leur temps et d'autres solution. Depuis qu'ils ont utilisé différentes données des essais ils ont eu des résultats différents.

1. Niklas référence est très twakable. Avec son banchmark que l'on peut faire différents tests de changer certains paramètres.

   J'ai utilisé la même à trois jeux de paramètres qu'il utilise dans sa propre réponse, et je les ai mis dans trois fichiers différents:

   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,
   

   Ce sont les résultats que j'ai obtenu:

   À partir d'un fichier: 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
   

   À partir d'un fichier: 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
   

   À partir d'un fichier: 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. Avec Sven's de données de test, j'ai obtenu les résultats suivants:

   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. Et enfin avec Agf's de référence que j'ai obtenu:

   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
   

Comme je l'ai dit au début, tout le code est disponible à ce dépôt git. Tous la fusion des fonctions dans un fichier appelé" core.py, chaque fonction avec son nom se terminant par _merge sera automatiquement chargé lors des tests, donc il ne devrait pas être dur à ajouter/tester/améliorer votre propre solution.

Permettez-moi aussi de savoir si il ya quelque chose de mal, ça fait beaucoup de codage et j'ai pu utiliser une paire de yeux frais :)

Answer 3

En Utilisant La Matrice De Manipulations

Permettez-moi de commencer cette réponse avec le commentaire suivant:

C'EST LA MAUVAISE FAÇON DE LE FAIRE. ELLE EST SUJETTE À L'INSTABILITÉ NUMÉRIQUE ET EST BEAUCOUP PLUS LENT QUE LES AUTRES MÉTHODES PRÉSENTÉES, UTILISEZ À VOS PROPRES RISQUES.

Cela étant dit, je ne pouvais pas résister à la résolution du problème à partir d'une dynamique de point de vue (et j'espère que vous allez obtenir une nouvelle perspective sur le problème). En théorie cela devrait fonctionner tout le temps, mais des valeurs propres calculs peuvent souvent échouer. L'idée est de penser à votre liste de diffusion en flux à partir des lignes et des colonnes. Si deux lignes partagent une valeur commune il y a une connexion entre eux. Si nous pensons de ces flux de l'eau, nous voyons que le flux de cluster dans de petites piscines lorsqu'ils il existe un chemin reliant entre eux. Pour des raisons de simplicité, je vais utiliser un plus petit, bien que cela fonctionne avec votre jeu de données ainsi:

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

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

Nous avons besoin de convertir les données dans un graphe de flot. Si la ligne que je jette dans la valeur de j nous l'avons mis dans la matrice. Ici, nous avons 3 lignes et 4 valeurs uniques:

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

En général, vous aurez besoin de changer la 4 pour capturer le nombre de valeurs uniques que vous avez. Si l'ensemble est une liste d'entiers à partir de 0 comme nous l'avons, vous pouvez tout simplement faire le plus grand nombre. Nous avons maintenant effectuer une valeur propre décomposition. Un SVD pour être exact, depuis notre matrice n'est pas carrée.

S  = linalg.svd(A)

Nous voulons garder seulement le 3x3 partie de cette réponse, car elle représente le flux de la piscine. En fait, nous voulons seulement que les valeurs absolues de cette matrice; nous en charge uniquement si il y a un flux dans ce cluster de l'espace.

M  = abs(S[2])

Nous pouvons penser de cette matrice M de Markov de matrice et de la rendre explicite par ligne d'une normalisation. Une fois que nous avons cela, nous calculons l' (à gauche) valeur propre decomp. de cette matrice.

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

Maintenant déconnecté (non-ergodique) de Markov de matrice de a la belle propriété que, pour chaque non-connecté cluster, il est une valeur propre de l'unité. Les vecteurs propres associés à ces unité valeurs sont celles que nous voulons:

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

J'ai utiliser .999 en raison de cette instabilité numérique. À ce stade, nous sommes en fait! Chaque cluster peut maintenant tirer les lignes correspondantes de sortir:

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

Ce qui donne, comme prévu:

[0 1 3]
[2]

Variation X votre lst et vous obtiendrez: [ 0 1 3 4 5 10 11 16] [2 8].

---

Addendum

Pourquoi cela peut-il être utile? Je ne sais pas où les données sous-jacentes vient, mais ce qui arrive quand les connexions ne sont pas absolus? Dire ligne 1 a l'entrée 3 80% du temps - comment voulez-vous généraliser le problème? Le flux de la méthode ci-dessus fonctionne très bien, et ce serait complètement paramétrées par l' .999 de la valeur, le plus loin de l'unité, c'est le looser de l'association.

---

Représentation Visuelle

Puisqu'une image vaut 1K mots, voici les parcelles des matrices A et V pour mon exemple, et votre lst respectivement. Remarquez comment, en V se divise en deux groupes (c'est un bloc-diagonale de la matrice avec deux blocs après permutation), puisque, pour chaque exemple, il n'y avait que deux listes!

---

La Mise En Œuvre Rapide

Avec le recul, j'ai réalisé que vous pouvez sauter la SVD étape et de ne calculer qu'une seule decomp:

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

L'avantage avec cette méthode (en plus de la vitesse) est qu' M est maintenant symétrique, d'où le calcul peut être plus rapide et plus précis (pas imaginaire valeurs à s'inquiéter).

Answer 4

EDIT: OK, les autres questions a été fermé, de poster ici.

Belle question! C'est beaucoup plus simple si vous pensez à elle comme un-composants problème dans un graphe. Le code suivant utilise l'excellent networkx graphique de la bibliothèque et de l' pairs fonction de cette question.

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]]

---

Explication

Nous allons créer un nouveau (vide) graphique g. Pour chaque sous-liste dans lists, examiner ses éléments comme des nœuds du graphe et ajouter une arête entre eux. (Puisque nous ne se soucient que de la connectivité, nous n'avons pas besoin d'ajouter tous les bords -- seuls les plus proches!) Notez que add_edge prend deux objets, les traite comme des nœuds (et les ajoute si elles ne sont pas déjà là), et ajoute une arête entre eux.

Ensuite, nous retrouvons les composantes connexes du graphe -- un problème résolu! -- et de sortie comme intersection d'ensembles.

Answer 5

Cette nouvelle fonction ne fait que le minimum nécessaire le nombre de disjointness tests, quelque chose que les autres solutions similaires ne parviennent pas à le faire. Il utilise également un deque afin d'éviter que de nombreux linéaire dans le temps des opérations que possible, comme la liste de tranchage et de suppression à partir du début de la liste.

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

Le moins de chevauchement entre les ensembles dans un ensemble de données, le mieux ce sera faire par rapport aux autres fonctions.

Voici un exemple de cas. Si vous avez des 4 jeux, vous devez comparer:

1, 2
1, 3
1, 4
2, 3
2, 4
3, 4

Si 1 chevauchements avec 3, puis 2 doit être re-testé pour voir si maintenant les chevauchements avec 1, afin d'ignorer les tests 2 contre 3.

Il y a deux façons de traiter ce. La première est de redémarrer les essais de la série 1 contre les autres séries après chaque chevauchement et de fusion. La deuxième est de continuer l'expérimentation en comparant 1 à 4, puis aller en arrière et re-tester. Les derniers résultats en moins de disjointness tests, plus fusionne arriver en un seul passage, de sorte que le re-test, il y a de moins en moins de jeux de gauche à tester.

Le problème est de savoir quels ensembles doivent être testés à nouveau. Dans l'exemple ci-dessus, 1 a besoin d'être re-testé contre 2, mais pas à l'encontre de 4, depuis le 1er était déjà dans son état actuel avant 4 a été testé pour la première fois.

L' disjoint compteur permet de le suivre.

---

Ma réponse n'est pas aider avec le problème de trouver un algorithme amélioré pour recoder en FORTRAN; c'est juste ce qui me semble être la plus simple et la plus élégante façon de mettre en œuvre l'algorithme en Python.

Selon mes tests (ou le test dans l'acceptation de réponse), c'est légèrement (jusqu'à 10%) plus rapide que la prochaine solution la plus rapide.

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

Pas de nécessité pour l'onu-Pythonic compteurs (i, range) ou compliqué mutation (del, pop, insert) utilisé dans les autres implémentations. Il utilise seulement la simple itération, fusionne le chevauchement des ensembles dans la manière la plus simple, et construit une nouvelle liste à chaque passage à travers les données.

Mon (plus rapide et plus simple) de la version du code de test:

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)