Analysieren Sie die Liste der Zeichenfolgen auf Geschwindigkeit

Nov 30 2020

Hintergrund

Ich habe eine Funktion namens get_player_path, die eine Liste von Zeichenfolgen player_file_listund 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_listentweder hat ein year-date/player_id/some_random_file.file_extensionoderyear-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_idPfade 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

PedroLobito Nov 30 2020 at 21:08

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

1 janluke Nov 30 2020 at 22:25

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 LENGTHInitialisierung wurde behoben , ich hatte vergessen, 1 hinzuzufügen

AajKaal Nov 30 2020 at 21:19

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]