Analyser la liste des chaînes pour la vitesse
Contexte
J'ai une fonction appelée get_player_path
qui prend dans une liste de chaînes player_file_list
et une valeur int total_players
. Par exemple, j'ai réduit la liste des chaînes et défini la valeur int à un très petit nombre.
Chaque chaîne du player_file_list
soit a un year-date/player_id/some_random_file.file_extension
ouyear-date/player_id/IDATs/some_random_number/some_random_file.file_extension
Problème
Ce que j'essaie essentiellement de réaliser ici, c'est de parcourir cette liste et de stocker tous les year-date/player_id
chemins uniques dans un ensemble jusqu'à ce que leur longueur atteigne la valeur detotal_players
Mon approche actuelle ne me semble pas la plus efficace et je me demande si je peux get_player_path
quand même accélérer ma fonction ??
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))
Production
['2020-10-27/31001804320549/', '2020-10-28/31001804320548/']
Réponses
Je laisse ici cette solution qui peut être encore améliorée, j'espère que cela vous aidera.
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'}
Démo Python
Analysons d'abord votre fonction:
- votre boucle doit prendre un temps linéaire (O (n)) dans la longueur de la liste d'entrée, en supposant que les longueurs de chemin sont limitées par un nombre relativement "petit";
- le tri prend O (n log (n)) comparaisons.
Ainsi, le tri a le coût dominant lorsque la liste devient grande. Vous pouvez micro-optimiser votre boucle autant que vous le souhaitez, mais tant que vous gardez ce tri à la fin, vos efforts ne feront pas beaucoup de différence avec les grandes listes.
Votre approche est bonne si vous écrivez simplement un script Python. Si vous aviez vraiment besoin de performances avec d'énormes listes, vous utiliseriez probablement un autre langage. Néanmoins, si vous vous souciez vraiment des performances (ou simplement pour apprendre de nouvelles choses), vous pouvez essayer l'une des approches suivantes:
- remplacer l'algorithme de tri générique par quelque chose de spécifique pour les chaînes; voir ici par exemple
- utiliser un trie , éliminant le besoin de tri; cela pourrait être théoriquement meilleur mais probablement pire dans la pratique.
Juste pour être complet, en tant que micro-optimisation, en supposant que la date a une longueur fixe de 10 caractères:
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)
Si les identifiants ont également une longueur fixe, comme dans votre liste d'exemples, vous n'avez pas besoin de fractionner ou de trouver, juste:
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: correction de l' LENGTH
initialisation, j'avais oublié d'ajouter 1
Utilisez dict pour ne pas avoir à le trier puisque votre liste est déjà triée. Si vous avez encore besoin de trier, vous pouvez toujours utiliser trié dans l'instruction return. Ajoutez import re et remplacez votre fonction comme suit:
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]