Разобрать список строк на скорость

Nov 30 2020

Задний план

У меня есть функция, 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/']

Ответы

PedroLobito Nov 30 2020 at 21:08

Я оставлю здесь это решение, которое можно улучшить, надеюсь, оно поможет.

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

1 janluke Nov 30 2020 at 22:25

Давайте сначала проанализируем вашу функцию:

  • ваш цикл должен занимать линейное время (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

AajKaal Nov 30 2020 at 21:19

Используйте 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]