获取 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 defaultdictmin_pos = defaultdict(int)traversal_dict = defaultdict(set)for ll in lll:&nbsp; # assume this is streamed / iterated&nbsp; &nbsp; for l in ll:&nbsp; &nbsp; &nbsp; &nbsp; for (i, val) in enumerate(l):&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if val not in min_pos:&nbsp; # O(1) to update both dictionaries&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; min_pos[val] = i&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; traversal_dict[i].add(val)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; elif i < min_pos[val]:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; traversal_dict[min_pos[val]].remove(val)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; min_pos[val] = i&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; traversal_dict[i].add(val)&nbsp; &nbsp; print traversal_dict&nbsp; # 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]],&nbsp; &nbsp; &nbsp; &nbsp;[[4, 1, 19], [11, 18, 3], [8, 14, 6]],&nbsp; &nbsp; &nbsp; &nbsp;[[17, 8, 4], [1, 16, 3], [19, 13, 11]]]def flatten(lst):&nbsp; &nbsp; """Flatten an arbitrary nested list, if the element is not a list return its position"""&nbsp; &nbsp; for i, e in enumerate(lst):&nbsp; &nbsp; &nbsp; &nbsp; if isinstance(e, list):&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; yield from flatten(e)&nbsp; &nbsp; &nbsp; &nbsp; else:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; yield (i, e)# create a dictionary of value -> min-posd = {}for i, e in flatten(lll):&nbsp; &nbsp; d[e] = i if e not in d else min(d[e], i)# reverse the dictionaryreverse = {}for key, value in d.items():&nbsp; &nbsp; 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}}