python - 在Python中高效创建字典并读取查询字典的输入

Question

我正在尝试解决的问题

我正在尝试解决this challenge使用Python。

我正在使用的解决方案

N = int(raw_input().strip())
phoneBook = {}
for i in range(N):
    name, number = raw_input().strip().split()
    phoneBook[name] = number

s = str(raw_input().strip())
while True:
    if s in phoneBook.keys():
        print "{}={}".format(s, phoneBook[s])
    else:
        print "Not found"
    try:
        s = str(raw_input().strip())
    except EOFError:
        break

我的解决方案有问题

问题出现在后面的测试用例中，其中字典中有 100,000 个条目，然后针对字典的查询数量未知。该网站表示代码在处理时超时，这似乎意味着有一种更有效的方式来执行此操作。

问题

如果可以的话，如何降低该算法的复杂性，使其运行得更快？

Answer 1

通过在phoneBook.keys()中执行if s:，您没有利用Python字典搜索(在Python 2中，keys()返回一个列表)

就这样做:

if s in phoneBook:

启用字典搜索性能

旁白:raw_input().strip().split() 可以替换为 raw_input().split()，因为 strip已经丢弃空白字段。

我会像这样的字典理解中获取所有数据(python 2):

phoneBook = dict(raw_input().split() for _ in xrange(N)) # xrange because it's faster in python 2

或者在Python 3中:

phoneBook = dict(input().split() for _ in range(N))