Analise a lista de strings para velocidade

Nov 30 2020

fundo

Eu tenho uma função chamada get_player_pathque leva em uma lista de strings player_file_liste um valor int total_players. Para fins de exemplo, reduzi a lista de strings e também defini o valor int para um número muito pequeno.

Cada string no player_file_listtem um year-date/player_id/some_random_file.file_extensionouyear-date/player_id/IDATs/some_random_number/some_random_file.file_extension

Questão

O que estou essencialmente tentando alcançar aqui é percorrer essa lista e armazenar todos os year-date/player_idcaminhos exclusivos em um conjunto até que seu comprimento alcance o valor detotal_players

Minha abordagem atual não parece a mais eficiente para mim e estou me perguntando se posso acelerar minha função de alguma forma?get_player_path

Código

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))

Resultado

['2020-10-27/31001804320549/', '2020-10-28/31001804320548/']

Respostas

PedroLobito Nov 30 2020 at 21:08

Vou deixar essa solução aqui, que pode ser melhorada ainda mais, espero que ajude.

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

Vamos analisar sua função primeiro:

  • seu loop deve levar um tempo linear (O (n)) no comprimento da lista de entrada, assumindo que os comprimentos do caminho são limitados por um número relativamente "pequeno";
  • a classificação leva O (n log (n)) comparações.

Assim, a classificação tem o custo dominante quando a lista se torna grande. Você pode microotimizar seu loop o quanto quiser, mas contanto que mantenha essa classificação no final, seu esforço não fará muita diferença com listas grandes.

Sua abordagem é adequada se você estiver apenas escrevendo um script Python. Se você realmente precisasse de apresentações com listas enormes, provavelmente estaria usando alguma outra linguagem. No entanto, se você realmente se preocupa com performances (ou apenas para aprender coisas novas), você pode tentar uma das seguintes abordagens:

  • substitua o algoritmo de classificação genérico por algo específico para strings; veja aqui por exemplo
  • use um trie , eliminando a necessidade de classificação; isso poderia ser teoricamente melhor, mas provavelmente pior na prática.

Apenas para completar, como uma microotimização, assumindo que a data tem um comprimento fixo de 10 caracteres:

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)

Se os IDs também têm comprimento fixo, como em sua lista de exemplos, você não precisa de nenhuma divisão ou localização, apenas:

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: consertou a LENGTHinicialização, esqueci de adicionar 1

AajKaal Nov 30 2020 at 21:19

Use dict para que você não precise classificá-lo, pois sua lista já está classificada. Se você ainda precisa classificar, você sempre pode usar classificado na instrução de retorno. Adicione import re e substitua sua função da seguinte maneira:

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]