二进制序列S存储在文本文件中。我们对频率感兴趣S中的分段：我们记得分段是由连续元素；其频率表示段出现在S中。以下面的文本文件为例，名为"ft1.txt"。该文件包含以下序列：
01010010010001000111101100001010011001111000010010011110010000000
段"00"的频率为23。段"1000"的频率为5。请注意，序列被拆分为三个连续的行。
设min_len和max_len是两个整数，使得min_len<=max_len。我们的目标提取长度在min_ len和min_max_len。此外，我们想列出n个最高频率和相关段，其中n是给定的整数。应该只有m<长度在min_len和max_len之间的n个不同段如果发生，输出应该包含更少的元素(即只有m条目)。
设计一个函数ex1(text_f，min_len，max_len，n)，它以以下参数为参数：-text_f：二进制序列所在的文本文件的路径存储在一个或多个连续行中；-min_len，max_len：两个整数，使得min_lem<=max_len，表示我们想要的线段的最小和最大长度分别计算频率；-n：一个整数，表示我们想要的最高频率的最大数量报告；并返回：-如下定义的对(arity为2的元组)的列表。
列表中的每一对都包括：1) 频率，以及2) 以该频率出现的分段的列表。我们记得，该列表最多应包含最高n个频率(或者更少，如果不同频率少于n个)。该列表是根据的第一个元素按字典顺序排序的元组。对每对中第二个元素中的列表进行排序词典学上也是如此。
例如，ex1('tf1.txt'，2，4，20)返回以下列表：
[ (1, ['1011', '1101']),
(2, ['0101', '0110', '1010']),
(3, ['0111', '101', '1110', '1111']),
(4, ['0001', '0011', '1100' ]),
(5, ['011', 1000', '110' ]),
(6, ['0000', '111']),
(7, ['0010','1001' ]),
(8, ['0100']),
(10,['010']),
(11,['000', '001', '11']),
(12,['100']),
(15,['01','10']),
(23,['00'])
]
注：每次测试的超时时间为0.5秒。
这就是我努力让它发挥作用的方式。该问题基本上发生在length>我基本上没有得到答案。正如你在练习中所读到的，要求我尊重失败的超时。所以我的问题是如何改进它，使它更快？如果你认为我的方法是错误的，建议一个更好的方法，我会努力的
def ex1(ftesto, min_len, max_len, n):
result_list = []
my_dict = {}
file = open(ftesto)
multilines = file.read()
my_string = multilines.replace('n', '')
file.close()
# creating b-combinations
for lenght in range(min_len, max_len + 1):
for i in range(2 ** lenght):
b = f'{i:0{lenght}b}'
# checking combinations
for index in range(len(my_string) - 1):
if my_string[index:index + lenght] == b:
my_dict[b] = my_dict.get(b, 0) + 1
# formatting result_list
# grouping by frequency
def storage_system(sub_s, f):
behave = False # True for extending, False for appending
my_tuple = (f, [sub_s])
if result_list:
for i in result_list.copy():
if i[0] == f:
i[1].extend(my_tuple[1])
behave = True
break
if not behave:
result_list.append(my_tuple)
for k,v in my_dict.items():
storage_system(k, v)
result_list.sort()
actual_list = []
if n > len(result_list):
for i in range(len(result_list)):
result_list[i][1].sort() #result_list[i][1].sort()
actual_list = result_list
else:
for i in range(len(result_list) - n,len(result_list)):
result_list[i][1].sort()
actual_list.append(result_list[i])
return actual_list
这里有一个几乎可以立即运行的解决方案：
from collections import defaultdict
def sub_freq(text_f: str, min_len: int, max_len: int, n: int) -> list[tuple[int, list[str]]]:
with open(text_f) as f:
text = f.read().strip()
frequencies = defaultdict(int)
for part_len in range(min_len, max_len + 1):
for i in range(len(text) + 1 - part_len):
frequencies[text[i:i+part_len]] += 1
return list(sorted(
(f, list(sorted(k for k, v in frequencies.items() if v == f)))
for f in sorted(set(frequencies.values()), reverse=True)[:n]
))
print(sub_freq('bin.txt', 2, 4, 20))
这采用的方法是从源字符串中提取所有长度匹配的子字符串，并在进行过程中计算它们的频率。而不是想出所有可能的字符串，然后计算它们出现的频率。毕竟，为什么要寻找不存在的字符串呢？你不必在文本中想出所有的字符串，你可以从文本中得到它们。
A细分：
with open(text_f) as f:
text = f.read().strip()
读取文本并删除多余的空白(如行尾)。
frequencies = defaultdict(int)
for part_len in range(min_len, max_len + 1):
for i in range(len(text) + 1 - part_len):
frequencies[text[i:i+part_len]] += 1
defaultdict确保我们可以添加到字典中的任何位置，如果它还不存在，它将被初始化为默认的整数值0。
外循环在我们感兴趣的所有长度的子字符串上循环，从min_len到max_len。内部循环从字符串的开头开始，一直到最后一个索引，该索引仍然允许提取长度为part_len的字符串。
然后，它只是增加提取的每个子字符串的计数。每个子字符串只提取一次，因为我们只使用每个part_len和每个起始索引运行一次text。
return list(sorted(
(f, list(sorted(k for k, v in frequencies.items() if v == f)))
for f in sorted(set(frequencies.values()), reverse=True)[:n]
))
一旦对频率进行了计数，我们需要返回到找到的频率的n。通过将值转换为一个集合，按相反的顺序(降序)对它们进行排序，并使用n元素，我们就拥有了for f in sorted(set(frequencies.values()), reverse=True)[:n]所需的所有频率。
循环这些元组，可以构建所需的元组，从frequencies字典中获取具有匹配值的所有关键字，即具有该频率的所有片段，对它们进行排序，并将结果转换为具有list(sorted(k for k, v in frequencies.items() if v == f)))的列表。
然后对生成的列表进行排序。
顺便说一句，你可能想向你的老师指出，外部列表没有排序；字典式地"；在他们的例子中，因为字典排序将把11放在2之前。然而，我保留了你在示例中提供的排序，因为我希望这就是你的老师测试的目的。
通过替换最后一部分，可以进一步简化：
return [
(f, list(sorted(k for k, v in frequencies.items() if v == f)))
for f in sorted(set(frequencies.values()))[-n:]
]
通过取按升序排序的频率值的最后一个n元素，频率将已经按我们需要的顺序进行排序，从而无需对外部列表进行排序。
解决方案：
def sub_freq(text_f: str, min_len: int, max_len: int, n: int) -> list[tuple[int, list[str]]]:
from collections import defaultdict
with open(text_f) as f:
text = f.read().strip()
frequencies = defaultdict(int)
for part_len in range(min_len, max_len + 1):
for i in range(len(text) + 1 - part_len):
frequencies[text[i:i+part_len]] += 1
return [
(f, list(sorted(k for k, v in frequencies.items() if v == f)))
for f in sorted(set(frequencies.values()))[-n:]
]
编辑：由于你要求加速，我很快在你和我的解决方案上运行了timeit，结果是我的速度大约是你提供的示例(在我的机器上)的两倍：
from timeit import timeit
print(timeit(lambda: sub_freq('bin.txt', 2, 4, 20), number=10000))
print(timeit(lambda: ex1('bin.txt', 2, 4, 20), number=10000))
结果：
1.039986400000089
2.2731566000002204
我还运行了一个测试，随机化字符串并改变参数(为此，我更改了您和我的代码，不从文件中读取，而是直接接受文本)：
from random import choice
sfc = 0
ex1c = 0
for _ in range(100):
text = ''.join(choice('01') for _ in range(100))
min_len = choice(range(2, 10))
max_len = min_len + choice(range(2, 10))
sfc += timeit(lambda: sub_freq(text, min_len, max_len, 20), number=10)
ex1c += timeit(lambda: ex1(text, min_len, max_len, 20), number=10)
print (sfc, ex1c)
结果：
0.02489419999801612 7.395662600000833
这表明我的解决方案在许多情况下都能很好地使用更大的数据集，而您的解决方案却开始像您所经历的那样陷入困境。(注意，这也不再包括在I/O上花费的时间，因此计算差异被放大)