获取 3d 列表中唯一元素的最低索引的有效算法

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 个子列表中。但它在单个子列表中的最低位置是 at 0，这就是它在最终字典中 key 的原因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}}