有效地从第二列表（元组）过滤对于一个Python列表值

我试图找到最有效的解决方案，以做到以下几点：有效地从第二列表（元组）过滤对于一个Python列表值

我有两个长的名单：

a = [3, 7, 89, 1, ....] #list of user_ids 
b = [(2,t1),(3,t2),(2,t3),(89,t4), ....] # list of user_id, epoch_time pairs

目标是检索列表a的所有成员（如果它们存在于列表b中（即列表b中每个元组的第一个成员）。请注意0可能存在于b中的多个元组中。

一个能够满足像这样这个要求：

result = [] 
for user_id in a: 
    for uid,epoch_time in b: 
     if user_id == uid: 
      result.append(user_id) 
return result

的问题是，有没有办法做到这一点的速度比为O（n^2）？例如。例如通过重组b作为词典？

来源

2017-07-30 Hassan Baig

您可以重新组织b作为一本字典，正如你所说，然后检查是否user_id从a在字典可用。

a = [3, 7, 89, 1] 
b = [(2,'t1'),(3,'t2'),(2,'t3'),(89,'t4')] 
dic = {k: v for k, v in b} 
result = [x for x in a if dic.get(x)]

dic.get(x)回报None如果x不是关键

来源

2017-07-30 01:23:02

user_ids。 b'不是唯一的 - 注意'b'中'（2，'t1'）'和'（2，'t3'）'是如何出现的。这不会干净地翻译成像这样的字典，是吗？ –

它会保存最后一个'key'遇到的'key'，也就是'2：'t3''但是如果你使用dict只是为了查看用户ID是否存在，那就没问题了 –

如果你想将'b'永久转换为字典，您可以为每个用户分配一个'epoch_time'的列表并附加到它，例如：'{2：['t1'，'t2'，'t3']}' –

你可以使用一个允许O（1）检查一个元素是否属于它的集合。

result = [] 
set_a = set(a) 
for uid, epoch_time in b: 
    if uid in set_a: 
     result.append(uid)

如果你想在结果中唯一值，可以使用一组result还有：

result = set() 
set_a = set(a) 
for uid, epoch_time in b: 
    if uid in set_a: 
     result.add(uid)

它甚至可以在最后变成一个列表：

result = list(result)

来源

2017-07-30 00:21:29

这是不是允许重复值 –

@AnthonyPham：？它会，这个问题在'并没有真正说明什么期望，所以我已经更新了我关于这个问题的答案 –

对于O（1），只需检查值是否在列表中a开头：

result = [] 
for uid,epoch_time in b: 
    if uid in a: 
     result.append(uid)

如果你不想重复值，然后添加一个条件，不仅必须uid在a但在result已经存在：

result = [] 
for uid,epoch_time in b: 
    if uid in a and uid not in result: 
     result.append(uid)

Try it here!

来源

2017-07-30 00:24:49

我会用套。既然你只是放弃了时代日期。

a = [3, 7, 89, 1, ....] 
b = [(2,t1),(3,t2),(2,t3),(89,t4), ....] 

def fn(a, b): 
    a = set(a) 
    b_uid, trash = zip(*b) 
    b_uid = set(b_uid) 
    return a.intersection(b)

这是字典的所有速度而不涉及数值。也修复返回类型为任何你想要的。（把它包在一个列表中，如果这是你想要的东西回来。

来源

2017-07-30 00:46:10 Back2Basics

有效地从第二列表（元组）过滤对于一个Python列表值

回答

相关问题