python中的Mime类型优化

Question

我想解决编码 games.com 中的哑剧挑战。我的代码可以通过所有测试，但不能通过优化测试。

我试图删除所有无用的函数，例如解析为字符串，但问题出在我的思考方式上。

import sys

import math

# Auto-generated code below aims at helping you parse

# the standard input according to the problem statement.

n = int(input())  # Number of elements which make up the association table.

q = int(input())

# Number Q of file names to be analyzed.

dico = {}

# My function

def check(word):

    for item in dico:

        if(word[-len(item)-1:].upper() == "."+item.upper()):

            return(dico[item])

    return("UNKNOWN")

for i in range(n):

    # ext: file extension

    # mt: MIME type.

    ext, mt = input().split()

    dico[ext] = mt

for i in range(q):

    fname = input()

    fname = fname

    print(check(fname))

# Write an action using print

# To debug: print("Debug messages...", file=sys.stderr)

#print("Debug message...", file=sys.stderr)

失败进程已超时。这可能意味着您的解决方案没有优化到足以处理某些情况。

Answer 1

这是正确的想法，但一个细节似乎正在破坏性能。问题是行for item in dico:，它不必要地遍历字典中的每个条目。这是一个线性搜索 O(n)，逐项检查目标。但这几乎违背了字典数据结构的目的，即提供恒定时间 O(1) 查找。“恒定时间”意味着无论字典有多大，查找项目所需的时间总是相同的（感谢hashing）。打个比方，想象一下你在厨房里找勺子。如果您提前知道所有器具、电器和炊具在哪里，您就不需要在每个抽屉里找器具。取而代之的是，您只需直接前往装有您想要的勺子的餐具抽屉，而且是一次性的！另一方面，如果你在别人的厨房里，就很难找到勺子。你必须从橱柜的一端开始检查每个抽屉，直到找到餐具。在最坏的情况下，您可能会很不走运，并且必须在找到器具抽屉之前检查每个抽屉。回到代码，上面的代码片段使用的是后一种方法，但我们正在处理试图在 10k 个不熟悉的厨房中找到一些东西，每个厨房都有 10k 个抽屉。很慢，对吧？如果您可以调整解决方案以在恒定时间内检查字典，而无需循环，那么您可以处理n = 10000并且q = 10000无需进行q * n迭代（您可以在q迭代中进行操作——快得多！）。

Answer 2

感谢您的帮助，我找到了解决方案。n = int(input())  # Number of elements which make up the association table.q = int(input())  # Number Q of file names to be analyzed.dico = {}# My functiondef check(word):    if("." in word):        n = len(word)-(word.rfind(".")+1)        extension = word[-n:].lower()        if(extension in dico):            return(dico[extension])    return("UNKNOWN")for i in range(n):    # ext: file extension    # mt: MIME type.    ext, mt = input().split()    dico[ext.lower()] = mtfor i in range(q):    fname = input()    print(check(fname))你的解释很清楚：D谢谢