分析字符串列表的速度

Question

背景

我有一个名为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/']

Answer 1

让我们先分析一下您的函数：

• 您的循环应该在输入列表的长度中占用线性时间(O(n((，假设路径长度由相对的"；"小"；数字
• 排序进行O(n-log(n((比较

因此，当列表变大时，排序具有主要成本。你可以随心所欲地对你的循环进行微观优化，但只要你在最后保持这种排序，你的努力就不会对大列表产生太大影响。

如果您只是在编写一个Python脚本，那么您的方法是很好的。如果你真的需要大量列表的性能，你可能会使用其他语言。尽管如此，如果你真的很关心表现(或者只是为了学习新东西(，你可以尝试以下方法之一：

• 用特定于字符串的东西替换通用排序算法；例如，请参见此处
• 使用trie，无需排序；这在理论上可能更好，但在实践中可能更糟

为了完整性，作为一种微观优化，假设日期的固定长度为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)

如果ID也有固定的长度，如您的示例列表中所示，那么您不需要任何拆分或查找，只需：

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个

Answer 2

我将把这个可以进一步改进的解决方案留在这里，希望它能有所帮助。

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演示

Answer 3

使用dict，这样您就不必对其进行排序，因为您的列表已经排序了。如果您仍然需要排序，您可以在return语句中始终使用sorted。添加导入重新并替换您的功能如下：

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]