我想解決編碼 games.com 中的啞劇挑戰(zhàn)。我的代碼可以通過所有測(cè)試，但不能通過優(yōu)化測(cè)試。我試圖刪除所有無用的函數(shù)，例如解析為字符串，但問題出在我的思考方式上。import sysimport 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 functiondef 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] = mtfor 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)失敗進(jìn)程已超時(shí)。這可能意味著您的解決方案沒有優(yōu)化到足以處理某些情況。
2 回答
紅糖糍粑
TA貢獻(xiàn)1815條經(jīng)驗(yàn) 獲得超6個(gè)贊
這是正確的想法，但一個(gè)細(xì)節(jié)似乎正在破壞性能。問題是行for item in dico:，它不必要地遍歷字典中的每個(gè)條目。這是一個(gè)線性搜索 O(n)，逐項(xiàng)檢查目標(biāo)。但這幾乎違背了字典數(shù)據(jù)結(jié)構(gòu)的目的，即提供恒定時(shí)間 O(1) 查找?！昂愣〞r(shí)間”意味著無論字典有多大，查找項(xiàng)目所需的時(shí)間總是相同的（感謝hashing）。
打個(gè)比方，想象一下你在廚房里找勺子。如果您提前知道所有器具、電器和炊具在哪里，您就不需要在每個(gè)抽屜里找器具。取而代之的是，您只需直接前往裝有您想要的勺子的餐具抽屜，而且是一次性的！
另一方面，如果你在別人的廚房里，就很難找到勺子。你必須從櫥柜的一端開始檢查每個(gè)抽屜，直到找到餐具。在最壞的情況下，您可能會(huì)很不走運(yùn)，并且必須在找到器具抽屜之前檢查每個(gè)抽屜。
回到代碼，上面的代碼片段使用的是后一種方法，但我們正在處理試圖在 10k 個(gè)不熟悉的廚房中找到一些東西，每個(gè)廚房都有 10k 個(gè)抽屜。很慢，對(duì)吧？
如果您可以調(diào)整解決方案以在恒定時(shí)間內(nèi)檢查字典，而無需循環(huán)，那么您可以處理n = 10000并且q = 10000無需進(jìn)行q * n迭代（您可以在q迭代中進(jìn)行操作——快得多?。?。
SMILET
TA貢獻(xiàn)1796條經(jīng)驗(yàn) 獲得超4個(gè)贊
感謝您的幫助，我找到了解決方案。
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):
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()] = mt
for i in range(q):
fname = input()
print(check(fname))
你的解釋很清楚：D謝謝
添加回答
舉報(bào)
0/150
提交
取消