Python字典/哈希映射搜索优化问题

Question

我试图用Python解决这个问题，它的CPU时间限制为1秒，内存限制为1024兆字节：https://open.kattis.com/contests/v4xrif/problems/grandpabernie

多年来，伯尼爷爷周游世界。他不再经常旅行了，但他喜欢给孙子们讲这些旅行的故事。他会告诉他们他第一次去以色列，或者第三次去希腊时的故事

他的记忆力很好。他很容易记住他第k次去某个国家的旅行，但他很难记住他是在哪一年去的。给出伯尼爷爷所有旅行的清单，你能回答一些问题吗？这些问题问伯尼爷爷是哪一年去某个国家的第k次旅行的

输入输入包括：

一行一整数n（1≤N≤100000），伯尼爷爷的旅行次数

n行，每行包含名称s（1≤||≤20） 一个国家和一个整数y（1≤Y≤代表伯尼爷爷在y年去的s国旅行

一行带一个整数q（1≤Q≤100000），查询数量

q行，每个行包含一个国家的名称s和一个整数k，表示伯尼爷爷第k次去国家s的查询

每个国家的名称仅由英文字母组成。还可以保证，对于要求第k次访问s国的每个查询，k至少为1，且不大于伯尼爷爷访问s国的次数。特别是，伯尼爷爷至少访问过这个国家一次

输出 对于伯尼爷爷第k次旅行的每个查询，输出一行，其中包含伯尼爷爷旅行的年份

样本输入1

4
Iceland 2016
Sweden 2015
Iceland 1982
Norway 1999
3
Sweden 1
Iceland 1
Iceland 2

样本输出1

2015
1982
2016

样本输入2

4
Iceland 2014
Iceland 2015
Iceland 2015
Iceland 2016
4
Iceland 4
Iceland 3
Iceland 2
Iceland 1

样本输出2

2016
2015
2015
2014

我解决这个问题的策略是创建一个字典/哈希图，以国家名称为键，以他去该国的日期为值列表。然后，我将遍历每个查询，并从对应于查询的dictionary/hashmap中获取值

我的代码：

dates = {}
for i in range(int(input().strip())):
    line = input().strip().split()
    city = line[0]
    year = int(line[1])
    if city in dates:
        dates[city].append(year)
    else:
        dates[city] = [year]

for i in range(int(input().strip())):
    line = input().strip().split()
    print(sorted(dates[line[0]])[int(line[1])-1])

如您所见，这是一个相对较短的程序，但速度不够快。有没有办法加快速度

Answer 1

程序中最慢的部分是每次查询时重复排序

为了让事情加快一点-

from collections import defaultdict

trips = defaultdict(list)

num_trips = int(input())
for _ in range(num_trips):
    destination, year = input().strip().split()
    trips[destination].append(year)

for years in trips.values():
    years.sort()

num_queries = int(input())
for _ in range(num_queries):
    destination, occurance = input().strip().split()
    year = trips[destination][int(occurance)-1]
    print(year)

此外，您可以延迟对年份进行排序，直到查询到达该国家，并保留已排序国家的列表，但是，除非您有一个输入，该输入在一个国家中为您提供大量条目，然后从不查询该国家，否则您将看不到加速

如果您知道查询列表不太长，您还可以对其进行预处理，以提前找出需要排序的唯一国家集，但事实并非如此，这会导致您超出内存限制