Analyser la liste des chaînes pour la vitesse

Nov 30 2020

Contexte

J'ai une fonction appelée get_player_pathqui prend dans une liste de chaînes player_file_listet 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_listsoit a un year-date/player_id/some_random_file.file_extensionouyear-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_idchemins 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_pathquand 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

PedroLobito Nov 30 2020 at 21:08

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

1 janluke Nov 30 2020 at 22:25

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' LENGTHinitialisation, j'avais oublié d'ajouter 1

AajKaal Nov 30 2020 at 21:19

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]