Python: объединение простых списков на основе пересечений

Ответ 1

Моя попытка:

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)

Benchmark:

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

Ответ 2

Я попытался суммировать все, что было сказано и сделано по этой теме в этом вопросе, и в дубликат.

Я попытался выполнить test и время каждое решение (весь код здесь).

Тестирование

Это 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

Среди тех, которые я смог проверить, два не удалось:

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

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

Timing

Показатели сильно связаны с используемым тестом данных.

До сих пор три ответа пытались найти свое решение и другие решения. Поскольку они использовали разные данные тестирования, у них были разные результаты.

• Тест Niklas очень дерзкий. С его banchmark можно было бы делать разные тесты, изменяя некоторые параметры.

  Я использовал те же три набора параметров, которые он использовал в своем собственном ответе, и я поместил их в три разных файла:

  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
  

• С 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
  

• И, наконец, с тестом 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, будет автоматически загружена во время тестов, поэтому не сложно добавить/проверить/улучшить собственное решение.

Позвольте мне также знать, если что-то не так, это было много кодирования, и я мог бы использовать пару свежих глаз:)

Ответ 3

Использование Матрификаций Матриц

Позвольте мне изложить этот ответ следующим комментарием:

ЭТО НЕПРАВИЛЬНЫЙ СПОСОБ ДЕЛАТЬ ЭТО. ЭТО ПРЕДОТВРАЩАЕТСЯ ЧИСЛЕННОЙ НЕСТАБИЛЬНОСТИ И БОЛЬШЕ СКОРОСТИ, ЧТО ДРУГИЕ МЕТОДЫ ПРЕДСТАВЛЕНЫ, ИСПОЛЬЗУЙТЕ НА СВОЙ СОБСТВЕННЫЙ РИСК.

Говоря, я не мог устоять перед решением проблемы с динамической точки зрения (и надеюсь, что вы получите свежую точку зрения на проблему). Теоретически это должно работать все время, но вычисления собственных значений могут часто терпеть неудачу. Идея состоит в том, чтобы рассматривать ваш список как поток от строк к столбцам. Если две строки имеют общую ценность, между ними существует соединительный поток. Если бы мы думали об этих потоках как о воде, мы бы увидели, что потоки кластеризуются в маленькие пулы, когда между ними существует соединительный путь. Для простоты я собираюсь использовать меньший набор, хотя он также работает с вашим набором данных:

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

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

Нам нужно преобразовать данные в потоковый граф. Если строка я втекает в значение 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)

Мы хотим сохранить только часть 3х3 этого ответа, поскольку он будет представлять поток пулов. На самом деле нам нужны только абсолютные значения этой матрицы; нам остается только, есть ли поток в этом кластерном пространстве.

M  = abs(S[2])

Мы можем представить эту матрицу M как марковскую матрицу и сделать ее явной с помощью нормировки строк. Как только мы это получим, мы вычисляем (слева) разложение собственного значения. этой матрицы.

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

Теперь несвязная (неэргодическая) марковская матрица обладает хорошим свойством, что для каждого несвязного кластера существует собственное значение единицы. Собственные векторы, связанные с этими значениями единства, являются теми, которые мы хотим:

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 имеет запись 3 80% времени - как бы вы обобщили проблему? Метод потока выше будет работать очень хорошо и будет полностью параметризован этим значением .999, чем дальше от единства, тем слабее будет ассоциация.

Визуальное представление

Поскольку изображение стоит 1K слов, вот графики матриц A и V для моего примера и вашего lst соответственно. Обратите внимание, как в V разбивается на два кластера (это блок-диагональная матрица с двумя блоками после перестановки), так как для каждого примера было только два уникальных списка!

Более быстрая реализация

Оглядываясь назад, я понял, что вы можете пропустить шаг SVD и вычислить только один decomp:

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

Преимущество этого метода (помимо скорости) заключается в том, что M теперь симметрично, поэтому вычисление может быть более быстрым и точным (о каких-либо мнимых значениях не беспокоиться).

Ответ 4

EDIT: ОК, остальные вопросы были закрыты, размещая здесь.

Хороший вопрос! Это намного проще, если вы думаете об этом как проблема связанных компонентов в графе. В следующем коде используется отличная 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 принимает два объекта, обрабатывает их как узлы (и добавляет их, если их еще нет), и добавляет ребро между ними.

Тогда мы просто находим компоненты связности графа - решаемую задачу! - и выводить их как наши пересекающиеся множества.

Ответ 5

Вот мой ответ. Я не проверил его против сегодняшней партии ответов.

Алгоритмы на основе пересечений - это O (N ^ 2), поскольку они проверяют каждый новый набор на все существующие, поэтому я использовал подход, который индексирует каждое число и работает на близком к O (N) (если мы примем это словарный поиск - O (1)). Затем я запустил тесты и почувствовал себя полным идиотом, потому что он работал медленнее, но при ближайшем рассмотрении оказалось, что тестовые данные заканчиваются только несколькими различными наборами результатов, поэтому квадратичные алгоритмы не имеют большой работы для делать. Протестируйте его более чем на 10-15 различных ящиков, и мой алгоритм выполняется намного быстрее. Попробуйте данные теста с более чем 50 отдельными ящиками, и это значительно быстрее.

(Edit: также была проблема с тем, как выполняется тест, но я ошибся в своем диагнозе. Я изменил свой код, чтобы работать с тем, как выполняются повторные тесты).

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

Ответ 6

Эта новая функция выполняет только минимальное необходимое количество тестов дизъюнкции, чего не могут сделать другие подобные решения. Он также использует 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 необходимо пройти повторную проверку, чтобы проверить, перекрывается ли он с 1, чтобы безопасно пропускать тестирование 2 против 3.

Есть два способа справиться с этим. Первый - перезапустить тестирование набора 1 по отношению к другим наборам после каждого совпадения и слияния. Во-вторых, продолжить тестирование путем сравнения 1 с 4, а затем вернуться и повторного тестирования. Последнее приводит к меньшему количеству тестов на дизъюнктность, так как больше слияний происходит за один проход, поэтому на переэкспертном проходе осталось меньше тестов для тестирования.

Проблема заключается в том, чтобы отслеживать, какие наборы должны быть повторно протестированы. В приведенном выше примере 1 необходимо повторно протестировать против 2, но не против 4, так как 1 уже находился в своем текущем состоянии до того, как 4 был протестирован в первый раз.

Счетчик 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

Не нужно использовать непитонические счетчики (i, range) или сложную мутацию (del, pop, 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)

Ответ 7

Это будет мой обновленный подход:

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% надежности успеха:

• Убедитесь, что все результирующие множества взаимно разделены:

  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
  

• Убедитесь, что объединенный набор охватывает исходные данные. (как предложено katrielalex)

Я думаю, что это займет некоторое время, но, возможно, это будет стоить того, если вы хотите быть на 100% уверенным.

Ответ 8

Это медленнее, чем решение Niklas (я получил 3,9 с на test.txt вместо 0.5s для своего решения), но дает тот же результат и может быть проще реализовать, например. Fortran, так как он не использует множества, сортируя только общее количество элементов, а затем пропустив их через все.

Он возвращает список с идентификаторами объединенных списков, поэтому также отслеживает пустые списки, они остаются невредимыми.

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

Ответ 9

Здесь функция (Python 3.1), чтобы проверить, является ли результат функции слияния ОК. Он проверяет:

• Являются ли результирующие множества непересекающимися? (количество элементов объединения == сумма чисел элементов)
• Являются ли элементы результата такими же, как и для входных списков?
• Является ли каждый входной список подмножеством результирующего набора?
• Является ли каждый результат минимальным, т.е. невозможно разбить его на два меньших множества?
• Он не проверяет наличие пустых наборов результатов - я не знаю, хотите ли вы их или нет...

.

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)

Ответ 10

Просто для удовольствия...

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

Ответ 11

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 раз медленнее, чем самый быстрый, но код намного проще и читабельнее!

Ответ 12

Во-первых, я не совсем уверен, справедливы ли тесты:

Добавление следующего кода в начало моей функции:

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

Это означает, что из всех значений во всех списках всего 88 различных значений. Обычно в реальном мире дубликаты встречаются редко, и вы ожидаете гораздо более отличных значений. (конечно, я не знаю, откуда ваши данные не могут делать предположения).

Поскольку Duplicates более распространены, это означает, что наборы с меньшей вероятностью будут непересекающимися. Это означает, что метод set.isdisjoint() будет намного быстрее, потому что только после нескольких тестов он обнаружит, что наборы не пересекаются.

Сказав все это, я верю, что представленные методы, которые используют disjoint, являются самыми быстрыми в любом случае, но я просто говорю, вместо того, чтобы быть в 20 раз быстрее, возможно, они должны быть только в 10 раз быстрее, чем другие методы с различным тестовым тестированием.

Во всяком случае, я подумал, что попробую несколько другую технику для решения этой проблемы, однако сортировка слияния была слишком медленной, этот метод примерно на 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

Ответ 13

Здесь реализована реализация с помощью структуры данных с несвязанными наборами (в частности, непересекающийся лес) благодаря подсказка о предстоящем шторме в слияниях наборов, которые имеют даже один элемент в целом. Я использую сжатие пути для улучшения скорости (~ 5%); это не совсем необходимо (и это предотвращает find хвост рекурсивный, что может замедлить работу). Обратите внимание, что я использую dict для представления непересекающегося леса; учитывая, что данные int s, также будет работать массив, хотя он может быть не намного быстрее.

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.

Ответ 14

Мое решение, хорошо работает в небольших списках и вполне читается без зависимостей.

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

Сравнительный анализ:

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

% timeit merge_list (списки)

100000 циклов, лучше всего 3: 4,9 мкс на петлю

Ответ 15

Это можно решить в O (n), используя алгоритм объединения-поиска. Учитывая первые две строки ваших данных, ребрами, используемыми в union-find, являются следующие пары: (0,1), (1,3), (1,0), (0,3), (3,4), (4,5), (5,10)