Эффективный алгоритм для получения наименьшего индекса уникальных элементов в трехмерном списке

Question

Настройка

Приведен список списков списков, например, приведенный ниже:

lll = []
for _ in range(5):  
    ll = [random.sample(range(1, 20), 5),
         random.sample(range(1, 20), 5),
         random.sample(range(1, 20), 5)]
    lll.append(ll)

Что может дать:

[[[1, 15, 12], [8, 5, 13], [1, 9, 12]],
 [[4, 1, 19], [11, 18, 3], [8, 14, 6]],
 [[17, 8, 4], [1, 16, 3], [19, 13, 11]]]

Конечная цель

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

{0: {1, 17, 19, 4, 8, 11}, 1: {5, 9, 13, 14, 15, 16, 18}, 2: {3, 12, 6}}

Например, в lll выше, 8 появляется в 3 подсписках. Но его самая низкая позиция в отдельном подсписке - 0, поэтому она находится в последнем словаре с ключом 0.

Ограничение

Я должен повторить более lll (в моем сценарии использования предполагается, что я не знаю полного lll). Поэтому traversal_dct будет расти со временем. lll, показанный выше, является фиктивными данными для демонстрационных целей

Рабочий раствор

Этот текущий подход работает, но я уверен, что он мог бы быть более эффективным.

traversal_dct = {}

for ll in lll:

    llT = [*map(list, zip(*ll))]

    for i,xs in enumerate(llT):
        if i not in traversal_dct.keys():
            traversal_dct[i] = set()
        traversal_dct[i] = traversal_dct[i].union(set(xs))

    for i1,key1 in enumerate(traversal_dct.keys()):
        for i2,key2 in enumerate(traversal_dct.keys()):
            if i2 > i1:
                traversal_dct[i2] = traversal_dct[i2] - traversal_dct[i1]

Answer 1

Я думаю, вы делаете это сложнее, чем нужно.

Сколько бы у вас ни было измерений, сведите это к 2D;вы не используете ничего более глубокого, чем список из трех элементов.

Теперь просто создайте список наборов, элементов в каждом измерении

e = [set(row[col] for row in 2d_list) for col in range(len(2d_list[0]))]

Теперь из каждого из этихнаборы, вычитайте (разность наборов) каждый из предыдущих наборов.

e[1] -= e[0]
e[2] -= e[0] + e[1]

... который вы также можете параметризовать в цикле.

Answer 2

Вы можете поддерживать 2 словаря:

• Один для отслеживания минимальных индексов для каждого значения
• Один для отслеживания индекса -> отображения набора значений

Затем для каждого полученного вами ll вы можете обновить оба значения во времени, пропорциональном длине (сплющенного) ll, без необходимости восстановления всего словаря traversal_dict:

from collections import defaultdict

min_pos = defaultdict(int)
traversal_dict = defaultdict(set)

for ll in lll:  # assume this is streamed / iterated
    for l in ll:
        for (i, val) in enumerate(l):
            if val not in min_pos:  # O(1) to update both dictionaries
                min_pos[val] = i
                traversal_dict[i].add(val)
            elif i < min_pos[val]:
                traversal_dict[min_pos[val]].remove(val)
                min_pos[val] = i
                traversal_dict[i].add(val)
    print traversal_dict  # retrieve answer after each iteration

Вывод (для данного lll в вашем вопросе после каждой итерации):

defaultdict(<class 'set'>, {0: {8, 1}, 1: {9, 5, 15}, 2: {12, 13}})
defaultdict(<class 'set'>, {0: {8, 1, 11, 4}, 1: {5, 9, 14, 15, 18}, 2: {3, 6, 12, 13, 19}})
defaultdict(<class 'set'>, {0: {1, 4, 8, 11, 17, 19}, 1: {5, 9, 13, 14, 15, 16, 18}, 2: {3, 6, 12}})

Answer 3

IIUC, вы можете сделать следующее:

lll = [[[1, 15, 12], [8, 5, 13], [1, 9, 12]],
       [[4, 1, 19], [11, 18, 3], [8, 14, 6]],
       [[17, 8, 4], [1, 16, 3], [19, 13, 11]]]


def flatten(lst):
    """Flatten an arbitrary nested list, if the element is not a list return its position"""
    for i, e in enumerate(lst):
        if isinstance(e, list):
            yield from flatten(e)
        else:
            yield (i, e)


# create a dictionary of value -> min-pos
d = {}
for i, e in flatten(lll):
    d[e] = i if e not in d else min(d[e], i)

# reverse the dictionary
reverse = {}
for key, value in d.items():
    reverse.setdefault(value, []).append(key)

print(reverse)

Вывод

{0: [1, 8, 4, 19, 11, 17], 1: [15, 5, 13, 9, 18, 14, 16], 2: [12, 3, 6]}

Если вы хотите преобразовать список в набор:

result = {key : set(value) for key, value in reverse.items()}
print(result)

Выход

{0: {1, 4, 8, 11, 17, 19}, 1: {5, 9, 13, 14, 15, 16, 18}, 2: {3, 12, 6}}