python - 将查询与已知列表匹配的算法，根据词典顺序呈现结果

Question

我正在设计一种算法，在给定查询的情况下在列表中查找字符串，并返回列表中与查询匹配的字符串。这是根据字典顺序中的第一个匹配项来回答。如果查询是一个空字符串，我返回一个空字符串，如果查询不是已知列表中任何项目开头的内容，我返回 -1。到目前为止，这是我的算法。有什么方法可以修改我的算法以使其运行得更快？

示例输入:

usernames: ["jBlame", "jannet"]
queries: ["j", "jm", "jbl", "JB"]

示例输出:

jannet
-1
jBlame
jBlame

这是我当前的实现。我一直在绞尽脑汁试图找到一种方法来提高这段代码的速度，但我没有找到办法。

def name_finder(usernames, queries):
    users = sorted(usernames,key=lambda m:m.upper())
    for q in queries:
        if q=='':
            print ''
            break
        for user in users:
            if q.upper()==user.upper()[:len(q)]: 
                print user
                break
        else: print -1

Answer 1

进行速度-时间权衡。先建立一个索引，这会花费更多的空间和一些时间。使用该索引进行查询，每个 find_name() 调用都将获得 O(1) 时间复杂度的好处。

usernames = ["jBlame", "jannet"]
queries = ["j", "jm", "jbl", "JB"]

def build_index(usernames):
    """Build an index by given usernames

    :returns: index dict
    """
    result = {}
    # Sort should ignore cases
    for username in sorted(usernames, key=lambda x: x.lower()):
        for i in range(len(username)):
            # TODO: If you only want the first result matched, modify this line to 
            # let the index consumes less space
            result.setdefault(username[:(i + 1)].lower(), []).append(username)
    return result


def find_name(query, index):
    """return the matched username by given query and index
    """
    if not query:
        return ''
    result = index.get(query.lower())
    return result[0] if result else -1

index = build_index(usernames)
for query in queries:
    print find_name(query, index)