Разобрать список строк на скорость
Задний план
У меня есть функция, get_player_pathкоторая принимает список строк player_file_listи значение типа int total_players. Для примера я сократил список строк, а также установил значение int на очень маленькое число.
Каждая строка в player_file_listлибо имеет, year-date/player_id/some_random_file.file_extensionлибоyear-date/player_id/IDATs/some_random_number/some_random_file.file_extension
Проблема
То, что я, по сути, пытаюсь достичь здесь, - это просмотреть этот список и сохранить весь уникальный year-date/player_idпуть в наборе, пока его длина не достигнет значенияtotal_players
Мой нынешний подход не кажется мне самым эффективным, и мне интересно, могу ли я как- нибудь ускорить свою работу get_player_path?
Код
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))
Вывод
['2020-10-27/31001804320549/', '2020-10-28/31001804320548/']
Ответы
Я оставлю здесь это решение, которое можно улучшить, надеюсь, оно поможет.
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
Давайте сначала проанализируем вашу функцию:
- ваш цикл должен занимать линейное время (O (n)) по длине входного списка, предполагая, что длина пути ограничена относительно «небольшим» числом;
- сортировка занимает O (n log (n)) сравнений.
Таким образом, сортировка имеет основную стоимость, когда список становится большим. Вы можете сколь угодно оптимизировать свой цикл на микроуровне, но пока вы сохраняете эту сортировку в конце, ваши усилия не будут иметь большого значения для больших списков.
Ваш подход хорош, если вы просто пишете скрипт Python. Если вам действительно нужны выступления с огромными списками, вы, вероятно, использовали бы какой-нибудь другой язык. Тем не менее, если вы действительно заботитесь о выступлениях (или просто хотите узнать что-то новое), вы можете попробовать один из следующих подходов:
- заменить общий алгоритм сортировки чем-то особенным для строк; см. здесь например
- использовать дерево , избавляющее от необходимости сортировки; теоретически это могло быть лучше, но на практике, вероятно, хуже.
Просто для полноты, в качестве микрооптимизации, предполагая, что дата имеет фиксированную длину в 10 символов:
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)
Если идентификаторы также имеют фиксированную длину, как в вашем списке примеров, тогда вам не нужно никакого разделения или поиска, просто:
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]
...
РЕДАКТИРОВАТЬ: исправлена LENGTHинициализация, я забыл добавить 1
Используйте dict, чтобы вам не приходилось его сортировать, поскольку ваш список уже отсортирован. Если вам все еще нужно отсортировать, вы всегда можете использовать sorted в операторе возврата. Добавьте import re и замените вашу функцию следующим образом:
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]