優化Python腳本

我一直在試圖完成在Python以下任務：優化Python腳本

http://codeforces.com/problemset/problem/4/C

我創建了一個簡單的腳本，它可以看到下面，但它返回一個運行時錯誤的第七次測試。我相信這是由於代碼耗時過長，所以我需要優化它的幫助。我已經看過地圖和過濾器命令，並試圖實現它們，但沒有成功。

a=int(input()) 
entered_usernames=[] 
n=0 
while n<a: 
    y=input() 
    entered_usernames.append(y) 
    n+=1 

valid_usernames=[] 
for i in entered_usernames: 
    if i not in valid_usernames: 
     valid_usernames.append(i) 
     print('OK') 
    else: 
     count=1 
     while i+str(count) in valid_usernames: 
      count+=1 
     valid_usernames.append(i+str(count)) 
     print(i+str(count))

來源

2017-07-25 Sharky Kesa

什麼是錯誤？發佈整個錯誤 –

而我在valid_usernames比打印i +計數 – Vaibhav

這種類型的練習通常是爲學生使用散列表，在Python中稱爲dictionnaries。請參閱@zwer響應。 – Wli

你可以嘗試改變valid_usernames到set而不是list。

對於一個列表list_a操作x in list_a需要（平均）線性時間。

對於一套set_a操作x in set_a需要（平均）恆定時間。

（來源：https://wiki.python.org/moin/TimeComplexity）

這個簡單的變化可以提高運行了一下。

什麼也令我可能很慢是這樣的片段：

while i+str(count) in valid_usernames: 
     count+=1

但是，如果你想改善這一點，你需要考慮使用一個完全不同的數據結構。

來源

2017-07-25 10:37:57 maestromusica

你爲什麼不嘗試

valid_usernames.append(i+str(valid_usernames.count(i))) 
print(i+str(valid_usernames.count(i))

來源

2017-07-25 10:39:07

你爲什麼不使用查找dict用計數器和O（n）的時間解決這個問題？

total = int(input()) # get the first input (total usernames) 
database = {} # our 'database'/lookup dict 
candidates = [input() for _ in range(total)] # pick usernames from the input 
for candidate in candidates: # loop through each candidate 
    if candidate in database: # already used, print with a counter 
     print(candidate + str(database[candidate])) 
     database[candidate] += 1 # increase the counter 
    else: # the candidate doesn't exist in the 'database'... 
     print("OK") 
     database[candidate] = 1 # initialize counter for the next time

來源

2017-07-25 10:44:04 zwer

這可能是最好的解決方案，存儲發生次數而不是名稱本身 –

優化Python腳本

回答

相關問題