1

Существует некоторый большой список, содержащий в себе множества. В качестве примера возьмем такой вид:

a = [{0, 1, 2, 3}, {4, 5, 6, 7}, {8, 20}, {5, 9}, {1, 8}].

Каким образом можно избавиться от дублирующихся чисел в этих множествах, чтобы получился такой список:

a = [{0, 1, 2, 3, 8, 20}, {4, 5, 6, 7, 9}]

Пробовал следующий способ:

a = [{0, 1, 2, 3}, {4, 5, 6, 7}, {8, 20}, {5, 9}, {1, 8}]
new = []
for _i in range(len(a)):
    tmp = a[_i]
    for _j in range(len(a)):
        if tmp.isdisjoint(a[_j]) == False:
            tmp = tmp.union(a[_j])
    new.append(tmp)
test = []
for _i in new:
    if _i not in test:
        test.append(_i)
print(test)

Но он оказался: во-первых, слишком медленным, а во-вторых он не учитывает ситуацию, когда множество1 имеет пересечение с множеством2, а множество2 имеет пересечение с множеством3 и так далее, так что он выдает результат:

[{0, 1, 2, 3, 8}, {4, 5, 6, 7, 9}, {8, 1, 20}, {0, 1, 2, 3, 20, 8}]

Тестировал на списке из 800 тысяч множеств, ожидаемое время обработки оказалось 24 часа.

9
  • Непонятен принцип, по которому вы собираете множества из списков. Напишите в явном виде алгоритм словами. Например, я не понимаю, почему вы присоединили 3-е множество к 1-му, а 2-е множество не стали присоединять к 1-му множеству. Каков вообще принцип работы вашего алгоритма?
    – CrazyElf
    21 фев 2020 в 14:38
  • А, вы сначала присоединили 5 множество к 3, а потом уже 3 к 1? Кажется, понятно, но хитро. Попробую что-то придумать, если успею.
    – CrazyElf
    21 фев 2020 в 14:40
  • Каков диапазон элементов множеств?
    – MBo
    21 фев 2020 в 17:39
  • @CrazyElf, я проверяю, пересекаются ли данные множества, то есть, имеются ли у них общие элементы. Таким образом, множества {2,5} и {5,7} будут объединены в множество {2,5,7}, а множества {2,5} и {6,7} так и останутся не объединенными, потому что у них нет общих элементов. И по второму вашему уточнению, да, правильно, потому что в начале у них нет общих элементов, но после первого прохода они появятся. 22 фев 2020 в 7:33
  • @MBo Элементы множеств всегда представляют собой int. По сути, там находятся айдишники вида 5434873, 69785421 и так далее. 22 фев 2020 в 7:35

1 ответ 1

0

Вот вроде получилось. Наверняка через itertools можно как-то проще сделать, но так вроде работает.

def flatten_setlist(old):
  new = []
  # идем по списку set-ов
  for o in old:
    found = False
    # если новый список пока пустой, то добавляем туда set без всяких проверок
    if len(new) == 0:
      new.append(o)
      continue
    # перебираем set-ы из нового списка
    for n in new:
      # если есть пересечение
      if len(n & o) > 0:
        found = True
        # то добавляем set в имеющийся set
        n |= o
        break
    # если не найдено ни одного пересечения с сетами из нового списка, то добавляем set в список новых set-ов
    if(not found):
      new.append(o)
  return new

old = [{0, 1, 2, 3}, {4, 5, 6, 7}, {8, 20}, {5, 9}, {1, 8}]
# процесс "схлопывания" списка сходится не сразу, поэтому нужен ещё один цикл
while True:
  new = flatten_setlist(old)
  # если работа алгоритма не привела к изменениям в списке, то работу цикла прекращаем
  if(len(new) == len(old)):
    break
  old = new

print(new)

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

from tqdm import tqdm_notebook

def flatten_setlist(old):
  print('old list len = ', len(old))
  # процесс "схлопывания" списка сходится не сразу, поэтому нужен ещё один цикл
  with tqdm_notebook(total=len(old)) as pbar:
    while True:
      new = []
      new_all = set()
      # идем по списку set-ов
      for o in tqdm_notebook(old, leave=False):
        #found = False
        # если новый список пока пустой, то добавляем туда set без всяких проверок
        if len(new) == 0:
          new.append(o)
          new_all |= o
          continue
        if len(new_all & o) > 0:
          # перебираем set-ы из нового списка
          for n in new:
            # если есть пересечение
            if len(n & o) > 0:
              #found = True
              # то добавляем set в имеющийся set
              n |= o
              new_all |= o
              break
        else:
          # если не найдено ни одного пересечения с сетами из нового списка, то добавляем set в список новых set-ов
          new.append(o)
          new_all |= o
      # если работа алгоритма не привела к изменениям в списке, то работу цикла прекращаем
      if(len(new) == len(old)):
        print('new list len = ', len(new))
        return new
      pbar.update(len(old)-len(new))
      old = new

old = [{0, 1, 2, 3}, {4, 5, 6, 7}, {8, 20}, {5, 9}, {1, 8}]
print(flatten_setlist(old))
16
  • Спасибо! Решение работает, но столкнулся со странной проблемой, если в начале работы данного метода скорость составляет около 1500 итераций в секунду (оценивал с помощью tqdm), то уже через 3 минуты скорость становится 130 итераций в секунду и продолжает падать. Таким образом, время выполнения оценивается как ~2 часа. Есть ли способы увеличить скорость? 25 фев 2020 в 9:52
  • @Сергей Я бы попробовал обернуть функцию в numba, она вложенные циклы иной раз хорошо ускоряет. Но там нужно разбираться с типами аргументов, в последних версиях там нетривиально как-то всё стало. Вообще, наверняка для вашей задачи есть готовое решение, я просто не соображу, как его искать. Я бы вообще посмотрел в сторону itertools, но там такая сильная магия, что я сходу не смогу подсказать, что оттуда использовать и как.
    – CrazyElf
    25 фев 2020 в 10:18
  • На 30 минуте скорость доходит до 40 итераций в секунду, ожидаемое время выполнения уже 4,5 часа. Скорость продолжает падать. К сожалению, время работы непозволительно большое. Глянул itertools, не совсем ясно, чем это может помочь, если они по сути представляют собой итераторы, поэтому пока курю numba. 25 фев 2020 в 10:25
  • @Сергей Я посмотрел, в Numba, к сожалению, не сделали ещё нормальный set нативный, а если переводить всё в её List, то всё преимущество теряется. Прямо не знаю пока что делать. А какой длины у вас множества и какие границы чисел в них? Чтобы я мог нормально промоделировать.
    – CrazyElf
    25 фев 2020 в 11:56
  • @Сергей Учтите, кстати, что tqdm тоже может изрядно замедлять процесс, лучше делать простой print раз в сколько-то итераций
    – CrazyElf
    25 фев 2020 в 12:11

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.