Analysieren Sie die Liste der Zeichenfolgen auf Geschwindigkeit
Hintergrund
Ich habe eine Funktion namens get_player_path
, die eine Liste von Zeichenfolgen player_file_list
und einen int-Wert aufnimmt total_players
. Zum Beispiel habe ich die Liste der Strings reduziert und auch den int-Wert auf eine sehr kleine Zahl gesetzt.
Jeder String im player_file_list
entweder hat ein year-date/player_id/some_random_file.file_extension
oderyear-date/player_id/IDATs/some_random_number/some_random_file.file_extension
Problem
Was ich hier im Wesentlichen erreichen möchte, ist, diese Liste durchzugehen und alle eindeutigen year-date/player_id
Pfade in einem Satz zu speichern , bis ihre Länge den Wert von erreichttotal_players
Mein aktueller Ansatz scheint mir nicht der effizienteste zu sein und ich frage mich, ob ich meine Funktion überhaupt beschleunigen kann get_player_path
?
Code
def get_player_path(player_file_list, total_players):
player_files_to_process = set()
for player_file in player_file_list:
player_file = player_file.split("/")
file_path = f"{player_file[0]}/{player_file[1]}/"
player_files_to_process.add(file_path)
if len(player_files_to_process) == total_players:
break
return sorted(player_files_to_process)
player_file_list = [
"2020-10-27/31001804320549/31001804320549.json",
"2020-10-27/31001804320549/IDATs/204825150047/foo_bar_Red.idat",
"2020-10-28/31001804320548/31001804320549.json",
"2020-10-28/31001804320548/IDATs/204825150123/foo_bar_Red.idat",
"2020-10-29/31001804320547/31001804320549.json",
"2020-10-29/31001804320547/IDATs/204825150227/foo_bar_Red.idat",
"2020-10-30/31001804320546/31001804320549.json",
"2020-10-30/31001804320546/IDATs/123455150047/foo_bar_Red.idat",
"2020-10-31/31001804320545/31001804320549.json",
"2020-10-31/31001804320545/IDATs/597625150047/foo_bar_Red.idat",
]
print(get_player_path(player_file_list, 2))
Ausgabe
['2020-10-27/31001804320549/', '2020-10-28/31001804320548/']
Antworten
Ich werde diese Lösung hier lassen, die weiter verbessert werden kann, hoffe, es hilft.
player_file_list = (
"2020-10-27/31001804320549/31001804320549.json",
"2020-10-27/31001804320549/IDATs/204825150047/foo_bar_Red.idat",
"2020-10-28/31001804320548/31001804320549.json",
"2020-10-28/31001804320548/IDATs/204825150123/foo_bar_Red.idat",
"2020-10-29/31001804320547/31001804320549.json",
"2020-10-29/31001804320547/IDATs/204825150227/foo_bar_Red.idat",
"2020-10-30/31001804320546/31001804320549.json",
"2020-10-30/31001804320546/IDATs/123455150047/foo_bar_Red.idat",
"2020-10-31/31001804320545/31001804320549.json",
"2020-10-31/31001804320545/IDATs/597625150047/foo_bar_Red.idat",
)
def get_player_path(l, n):
pfl = set()
for i in l:
i = "/".join(i.split("/")[0:2])
if i not in pfl:
pfl.add(i)
if len(pfl) == n:
return pfl
if n > len(pfl):
print("not enough matches")
return
print(get_player_path(player_file_list, 2))
# {'2020-10-27/31001804320549', '2020-10-28/31001804320548'}
Python-Demo
Lassen Sie uns zuerst Ihre Funktion analysieren:
- Ihre Schleife sollte in der Länge der Eingabeliste eine lineare Zeit (O (n)) benötigen, vorausgesetzt, die Pfadlängen sind durch eine relativ "kleine" Zahl begrenzt.
- Für die Sortierung werden O (n log (n)) Vergleiche durchgeführt.
Somit hat die Sortierung die dominierenden Kosten, wenn die Liste groß wird. Sie können Ihre Schleife beliebig mikrooptimieren, aber solange Sie diese Sortierung am Ende beibehalten, macht Ihre Anstrengung bei großen Listen keinen großen Unterschied.
Ihr Ansatz ist in Ordnung, wenn Sie nur ein Python-Skript schreiben. Wenn Sie wirklich Leistungen mit riesigen Listen benötigen, würden Sie wahrscheinlich eine andere Sprache verwenden. Wenn Sie sich jedoch wirklich für Performances interessieren (oder einfach nur neue Dinge lernen möchten), können Sie einen der folgenden Ansätze ausprobieren:
- Ersetzen Sie den generischen Sortieralgorithmus durch etwas Spezielles für Zeichenfolgen. siehe hier zum Beispiel
- Verwenden Sie einen Versuch , um das Sortieren zu vermeiden. Dies könnte theoretisch besser sein, aber in der Praxis wahrscheinlich schlechter.
Der Vollständigkeit halber als Mikrooptimierung unter der Annahme, dass das Datum eine feste Länge von 10 Zeichen hat:
def get_player_path(player_file_list, total_players):
player_files_to_process = set()
for player_file in player_file_list:
end = player_file.find('/', 12) # <--- len(date) + len('/') + 1
file_path = player_file[:end] # <---
player_files_to_process.add(file_path)
if len(player_files_to_process) == total_players:
break
return sorted(player_files_to_process)
Wenn die IDs wie in Ihrer Beispielliste auch eine feste Länge haben, brauchen Sie keine Aufteilung oder Suche, nur:
LENGTH = DATE_LENGTH + ID_LENGTH + 1 # 1 is for the slash between date and id
...
for player_file in player_file_list:
file_path = player_file[:LENGTH]
...
EDIT: Die LENGTH
Initialisierung wurde behoben , ich hatte vergessen, 1 hinzuzufügen
Verwenden Sie dict, damit Sie es nicht sortieren müssen, da Ihre Liste bereits sortiert ist. Wenn Sie noch sortieren müssen, können Sie in der return-Anweisung immer sortiert verwenden. Fügen Sie import re hinzu und ersetzen Sie Ihre Funktion wie folgt:
def get_player_path(player_file_list, total_players):
dct = {re.search('^\w+-\w+-\w+/\w+',pf).group(): 1 for pf in player_file_list}
return [k for i,k in enumerate(dct.keys()) if i < total_players]