Przeanalizuj listę ciągów pod kątem szybkości
tło
Mam funkcję o nazwie, get_player_path
która przyjmuje listę ciągów player_file_list
i 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_list
albo ma year-date/player_id/some_random_file.file_extension
lubyear-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
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
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 LENGTH
inicjalizację, zapomniałem dodać 1
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]