Объединение всех вложенных массивов с взаимными элементами в один вложенный массив

Question

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

Структура многомерного массива:

categories = {'car':['automobile','auto'],
             'bike':['vehicle','motorcycle','motorbike','automobile'],
             'software':['computer','macbook','apple','microsoft','mozilla'],
             'firefox':['internet','mozilla','browser']
             'bicycle':['vehicle']}

Я бы хотел объединить 'car', 'bike' и 'bike' водин список ( сохранить ключ первого списка ключом нового списка может быть любой из соответствующих ключей), а также «программное обеспечение» и «firefox» объединены в один список.

Производительность имеет решающее значение.

Лучшее решение, которое я мог бы найти до сих пор, - это сохранить сплющенный одномерный массив из element => list_key (например, ' automotive '=>' car ') и затем запустить следующую рекурсивную функцию для каждого списка в многомерном массиве (псевдокод):

function merge_similar(list_key):
    For each element in categories[list_key]:
        If flatten_array.has_key(element):
            list_to_merge = flatten_array[element]
            merge_similar(list_to_merge) /* merge other lists which share an element with our newly found similar list */
            categories[list_key] = merge(categories [list_key], categories[list_to_merge])
            delete categories[list_to_merge]

Есть идеи, как улучшить его производительность?

Спасибо!

Answer 1

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

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

def merged(dictoflists):
  result = dict()
  reversed = dict()
  for k, l in dictoflists.iteritems():
    intersecting = set(reversed.get(w) for w in l) - set([None])
    if intersecting:
      pickone = intersecting.pop()
      into = result[pickone]
    else:
      pickone = k
      into = result[k] = set()
    for ok in intersecting:
      into.update(result.pop(ok))
    into.update(l)
    for w in into:
      reversed[w] = pickone
  return dict((k, sorted(l)) for k, l in result.iteritems())

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

Answer 2

>>> categories = {'car':['automobile','auto'],
             'bike':['vehicle','motorcycle','motorbike','automobile'],
             'software':['computer','macbook','apple','microsoft','mozilla'],
             'firefox':['internet','mozilla','browser'],
             'bicycle':['vehicle']}
>>> # Use sets for values
>>> for k,v in categories.items(): categories[k] = set(v)

>>> # Acumulate
>>> for k1, v1 in categories.items():
    if v1:
        for k2,v2 in categories.items():
            if v2 and k1 != k2 and v1 & v2:
                v1 |= v2
                categories[k2] = None
        categories[k1] = v1


>>> # Print
>>> for k1, v1 in categories.items():
    if v1: print('%s: %r' %(k1,v1))


bicycle: {'motorbike', 'vehicle', 'auto', 'automobile', 'motorcycle'}
firefox: {'apple', 'mozilla', 'macbook', 'computer', 'internet', 'microsoft', 'browser'}
>>> 

Answer 3

Я не могу представить, что рекурсивное решение будет быстрым.
Использует list.extend () слишком медленно?
Вы можете сделать что-то вроде этого:

categories['car'].extend(categories['bike']);
categories['car'].extend(categories['bicycle']);

Или, если быть более общим, если вы передадите список ключей, которые вы хотите объединить:

first_key=None;
for key in keys_whose_lists_I_want_to_merge:
    if first_key is None:
        first_key=key;
    else:
        categories[first_key].extend(categories[key]);

Если вы объединяете тонну списков, вы можете оптимизировать этот цикл, чтобы он не выполнялсяНет проверки после первого раза.См. Совет «Переопределение функций во время выполнения» на странице Советы по производительности Python .