在包含对对象的重复引用的列表中查找唯一对象的子集

Find the sub-set of unique objects in a list which contains duplicate references to the objects

提问人:Bill 提问时间:8/27/2023 更新时间:8/27/2023 访问量:38

问:

我有一个算法,可以在字典的值中创建一组列表。但是,列表数小于字典键数,因为某些值是对同一列表对象的引用。

算法完成后,我想提取仅包含其余唯一列表对象的列表。我想避免比较两个列表,因为这效率低下。

我想出了这种使用 id 函数的方法。也许这很好,但我不确定这是否是 id 的适当用法,并想知道是否有更简单的方法可以做到这一点。

# Start with a full set of unique lists
groups = {i: [i] for i in range(1, 6)}

# Algorithm joins some of the lists together which 
# reduces the total number
for a, b in [(1, 2), (2, 4)]:
    groups[a] += groups[b]
    groups[b] = groups[a]

print(groups)

输出:

{1: [1, 2, 4], 2: [1, 2, 4], 3: [3], 4: [1, 2, 4], 5: [5]}

注意:现在,字典的某些值包含相同的列表。[1, 2, 4]

# Find the remaining unique lists
all_values = list(groups.values())
ids = [id(x) for x in all_values]
result = [all_values[ids.index(a)] for a in set(ids)]

print(result)

输出:

[[1, 2, 4], [3], [5]]

这是其他语言中的常见问题,但我找不到如何在 Python 中做到这一点的问题。

Python 列表 对象 唯一

评论

0赞 Codist 8/27/2023
两个等效的列表(就其内容而言)不一定共享相同的 ID
0赞 rioV8 8/27/2023
id(obj)是要走的路
0赞 Bill 8/27/2023
@DarkKnight 我认为您关于两个具有相同值的列表可能具有不同 ID 的风险的观点是有效的。所以这种方法并不可靠。

答:

2赞 Codist 8/27/2023 #1

你所拥有的是一个字典,其中的值(列表)可能是重复的。

集对于减少重复数据很有用。但是,由于列表不可散列,因此您需要将它们转换为其他内容 - 例如元组

您可以这样做:

groups = {i: [i] for i in range(1, 6)}

# Algorithm joins some of the lists together which 
# reduces the total number
for a, b in [(1, 2), (2, 4)]:
    groups[a] += groups[b]
    groups[b] = groups[a]

print(groups)

result = list(map(list, {*(tuple(e) for e in groups.values())}))

print(result)

输出:

[[3], [1, 2, 4], [5]]

此技术的一个潜在缺点是输出顺序可能不是所需的

注意:

为了强调 idhash 的困境,请考虑以下几点:

a=(1,2,3,4,5)           
b=(1,2,3,4,5)
                   
id(a)              
4429940832

id(b)           
4429952432

hash(a)           
-5659871693760987716

hash(b) 
-5659871693760987716

评论

0赞 Bill 8/27/2023
这有效,但设置使用列表比较吗?为了提高效率,我想利用这样一个事实,即我知道许多列表是相同的对象(以及相同的值)。
0赞 Codist 8/27/2023
@Bill 集合中的值必须是可哈希的 - 这就是此代码将列表转换为元组的原因。这是比较的哈希值。如果性能是关键,那么我建议你尝试使用更大的数据集来测试此答案中的代码,看看它是否按要求执行
0赞 Bill 8/27/2023
好吧,元组比较也可能很昂贵。尽管在我的情况下,列表恰好包含唯一值,因此它实际上是有效的。我会做一些测试。
0赞 MatBailie 8/27/2023
使用地图来避免列表推导式。trinket.io/python/df28d50fe4
0赞 MatBailie 8/27/2023
如上所述,元组比较并不比任何其他对象比较更昂贵;设置 HASH 其成员并使用哈希表来检测冲突