Przeanalizuj listę ciągów pod kątem szybkości

Nov 30 2020

tło

Mam funkcję o nazwie, get_player_pathktóra przyjmuje listę ciągów player_file_listi wartość int total_players. Na przykład zmniejszyłem listę ciągów i ustawiłem wartość int na bardzo małą liczbę.

Każdy ciąg w player_file_listalbo ma year-date/player_id/some_random_file.file_extensionlubyear-date/player_id/IDATs/some_random_number/some_random_file.file_extension

Kwestia

To, co zasadniczo próbuję tutaj osiągnąć, to przejrzeć tę listę i przechowywać wszystkie unikalne year-date/player_idścieżki w zestawie, dopóki jej długość nie osiągnie wartościtotal_players

Moje obecne podejście nie wydaje mi się najbardziej wydajne i zastanawiam się, czy i tak mogę przyspieszyć moją funkcję get_player_path?

Kod

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

Wynik

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

Odpowiedzi

PedroLobito Nov 30 2020 at 21:08

Zostawię tutaj to rozwiązanie, które można jeszcze ulepszyć, mam nadzieję, że pomoże.

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

Najpierw przeanalizujmy twoją funkcję:

  • twoja pętla powinna zająć liniowy czas (O (n)) w długości listy wejściowej, zakładając, że długości ścieżek są ograniczone przez stosunkowo „małą” liczbę;
  • sortowanie wymaga porównań O (n log (n)).

Tak więc sortowanie ma dominujący koszt, gdy lista staje się duża. Możesz optymalizować swoją pętlę tak bardzo, jak chcesz, ale tak długo, jak zachowasz sortowanie na końcu, twój wysiłek nie będzie miał większego znaczenia w przypadku dużych list.

Twoje podejście jest w porządku, jeśli piszesz tylko skrypt w Pythonie. Jeśli naprawdę potrzebujesz występów z ogromnymi listami, prawdopodobnie używałbyś innego języka. Niemniej jednak, jeśli naprawdę zależy Ci na występach (lub po prostu chcesz nauczyć się nowych rzeczy), możesz wypróbować jedno z następujących podejść:

  • zamień ogólny algorytm sortowania na coś specyficznego dla łańcuchów; zobacz tutaj na przykład
  • użyj trie , eliminując potrzebę sortowania; mogłoby to być teoretycznie lepsze, ale prawdopodobnie gorsze w praktyce.

Dla kompletności, jako mikro-optymalizacja, zakładając, że data ma stałą długość 10 znaków:

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)

Jeśli identyfikatory również mają stałą długość, jak na przykładowej liście, nie potrzebujesz żadnego podziału ani wyszukiwania, po prostu:

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

EDYCJA: naprawiono LENGTHinicjalizację, zapomniałem dodać 1

AajKaal Nov 30 2020 at 21:19

Użyj dict, aby nie musieć jej sortować, ponieważ lista jest już posortowana. Jeśli nadal potrzebujesz sortowania, zawsze możesz użyć sortowania w instrukcji return. Dodaj import re i zamień swoją funkcję w następujący sposób:

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]