logo标签列表

如何在Python中高效地搜索一组列表？

pythondata-structures
3

我在Python中有一组列表，用于跟踪一些用户的信息:

user_id = [1,2,3,4,5]
user_name = ['bob', 'alice', 'jerry', 'lisa', 'tom']
user_email = ['bob@email.com', 'alice@email.com', 'jerry@email.com', 'lisa@email.com', 'tom@email.com']
...

我想通过信息"y"获取用户信息"x"。在大多数情况下，我会使用字典来进行这个操作以获得恒定的查找时间，但是我不想创建和维护大量的字典。

如果我为上述每一对列表都创建一个字典，那么我就需要:

其中第 i 个元素在每个列表中相互对应。

name:email
email:name
name:id
id:name
email:id
id:email

这些属性已经变得难以管理，而且随着属性数量的增加，它们的增长速度非常快。
我可以让所有东西都映射到用户ID，然后只有2n个字典，但很高兴了解这种用例的更合适的数据结构。
为了说明目前代码是如何实现的：
def get_email_by_user_id(user_id):
   return [email for email, uid in zip(user_email, user_id) if uid == user_id][0]

正如你所想象的那样，非常缓慢 :P

4
数据库也存在这个问题，它们通过为常搜索字段创建索引来解决。这类似于您的查找字典。如果要在字段上进行恒定时间查找，则需要索引；否则必须按线性时间扫描数据。但是，您可能不需要那么多索引。如果将用户存储为单个对象，则可以仅使用一个“名称->对象”查找，而不是“名称-> ID”、“名称->电子邮件”等。 - Mark
2
只需创建一个字典列表，并编写一个“查询”函数，其中传递您想要的键和值即可。除非您有数百万用户，否则这将很好地工作。如果不是这样，则使用数据库（sqlite3？），它将完全执行相同的操作。 - Tim Roberts
2
或者把记录存储在一个字典中，以 id 作为键，并且有字典将用户名映射到 id，或将电子邮件映射到 id。 - Tim Roberts
2
列表推导式不会提前返回。不要在此情况下使用列表推导式（除其他事项外）。 - Keith
3个回答
1
最终我采取了唯一能提供所需性能的选项。
我决定user_id的内容是规范标识符。
然后我创建了以下字典：
def make_dictionaries(user_id, other_lists=[('user_name', user_name), ('user_email', user_email)]):
   to_id_dictionary = {}
   from_id_dictionary = {}

   for list_name, list_content in other_lists:
      from_id_dictionary[list_name] = {uid:cont for uid,cont in zip(user_id, list_content)}
      to_id_dictionary[list_name] = {cont:uid for uid,cont in zip(user_id, list_content)}

   return to_id_dictionary, from_id_dictionary

我可以做以下操作：
def get_email_by_user_name(user_name):

   uid = to_id_dictionary['user_name'][user_name] # Get UID from name
   return from_id_dictionary[user_email][uid] # Get email from UID
0
# Dict for holding your data
data = dict()
    
# Put all your stuff into data 
for id, name, email in zip( user_id, user_name , user_email):
    data[ id ] = { "id": id , "username" : name , "email" : email }

# Function for lookup up by key and value 
def lookup_info( key_name , lookup_value , data ):
    '''
    Takes a key name, a lookup value and a dictionary of data.

    Returns the dictionary item
    '''
    for k,v in data.items():
        
        if v[ key_name ] == lookup_value:
            return( data[ k ] )
1
这仍然会在O(n)中运行。 - DimG
比之前的代码更加有条理，但也可以使用二进制/深度优先搜索算法吗？ - user3234810
如果数据没有排序，我认为二分查找并没有多大帮助。 - Mark
可以按查找键对“data”数组中的字典进行排序，具体取决于排序+搜索是否比简单循环更快-此时建议使用数据库。 - user3234810
0

由于这些数据是相关的，因此可以将它们组织成一个相关列的元组列表。

DATA = [
    (1, 'bob', 'bob@email.com'),
    (2, 'alice', 'alice@email.com'),
    (3, 'jerry', 'jerry@email.com'),
    (4, 'lisa', 'lisa@email.com'),
    (5, 'tom', 'tom@email.com'),
]

然后，可以制作一个通用函数，仅考虑您感兴趣的列。

def find_user(user_id=None, user_name=None, user_email=None):
    """Find first user matching given criteria.

    A None value means "don't care".

    Returns tuple of (id, name, email) if found, otherwise None.
    """
    # Collect desired criteria into mapping of record index to desired index value.
    criteria_cols = {i: c for (i, c) in enumerate((user_id, user_name, user_email)) if c is not None}
    for rec in DATA:
        if all(rec[idx] == criteria for (idx, criteria) in criteria_cols.items()):
            return rec  # return early if found.

此函数将考虑任何非 None 值，并返回匹配的记录。如果没有记录匹配，则继续执行并返回默认的 None 值。

print(find_user(user_id=1))
print(find_user(user_id=2))
print(find_user(user_name="alice"))
print(find_user(user_email="jerry@email.com"))
print(find_user(user_id=3, user_email="jerry@email.com"))
print(find_user(user_id=2, user_email="jerry@email.com"))
print(find_user(user_id=3, user_name="jerry"))

结果为

(1, 'bob', 'bob@email.com')
(2, 'alice', 'alice@email.com')
(2, 'alice', 'alice@email.com')
(3, 'jerry', 'jerry@email.com')
(3, 'jerry', 'jerry@email.com')
None
(3, 'jerry', 'jerry@email.com')
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接