Analizar lista de cadenas de velocidad

Nov 30 2020

Antecedentes

Tengo una función llamada get_player_pathque toma una lista de cadenas player_file_listy un valor int total_players. Por ejemplo, reduje la lista de cadenas y también establecí el valor int en un número muy pequeño.

Cada cadena en el player_file_listtiene un year-date/player_id/some_random_file.file_extensionoyear-date/player_id/IDATs/some_random_number/some_random_file.file_extension

Problema

Lo que esencialmente estoy tratando de lograr aquí es revisar esta lista y almacenar todas las year-date/player_idrutas únicas en un conjunto hasta que su longitud alcance el valor detotal_players

Mi enfoque actual no me parece el más eficiente y me pregunto si puedo acelerar mi función get_player_pathde todos modos.

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

Salida

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

Respuestas

PedroLobito Nov 30 2020 at 21:08

Dejaré esta solución aquí que se puede mejorar aún más, espero que ayude.

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'}

Demostración de Python

1 janluke Nov 30 2020 at 22:25

Primero analicemos su función:

  • su ciclo debe tomar tiempo lineal (O (n)) en la longitud de la lista de entrada, asumiendo que las longitudes de la ruta están limitadas por un número relativamente "pequeño";
  • la clasificación toma comparaciones O (n log (n)).

Por lo tanto, la clasificación tiene el costo dominante cuando la lista se vuelve grande. Puede micro-optimizar su ciclo tanto como desee, pero mientras mantenga esa clasificación al final, su esfuerzo no hará mucha diferencia con listas grandes.

Su enfoque está bien si solo está escribiendo un script de Python. Si realmente necesitaras actuaciones con listas enormes, probablemente estarías usando algún otro lenguaje. No obstante, si realmente te preocupan las actuaciones (o simplemente para aprender cosas nuevas), puedes probar uno de los siguientes enfoques:

  • reemplace el algoritmo de clasificación genérico con algo específico para cadenas; ver aquí por ejemplo
  • use un trie , eliminando la necesidad de clasificar; esto podría ser teóricamente mejor pero probablemente peor en la práctica.

Solo para completar, como una micro-optimización, asumiendo que la fecha tiene una longitud fija 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)

Si las ID también tienen una longitud fija, como en su lista de ejemplo, entonces no necesita ninguna división o búsqueda, solo:

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]
...

EDITAR: se arregló la LENGTHinicialización, me había olvidado de agregar 1

AajKaal Nov 30 2020 at 21:19

Use dict para no tener que ordenarlo ya que su lista ya está ordenada. Si aún necesita ordenar, siempre puede usar sorted en la declaración de devolución. Agregue import re y reemplace su función de la siguiente manera:

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]