如何创建一个字母分类器。从任何字母到任何字母?(在python 3中)实际上写了代码:
list=["e","r","t","y","w"]
h=0
list2=["write","english","teacher","read","yellow"]
enter=[]
for u in range(1000): #while len(enter)<=4:
for qw in list2:
try:
if qw[0]==list[h]:
enter.append(qw)
h=h+1
except IndexError:
pass
print(enter)
但是这段代码的缺点是,如果碰巧在我们遇到的列表 2 中,让我们为字母 r 说两个单词,那么它会为字母 r 打印一个单词,它更接近列表的开头,这是由于我创建了一个变量 h 来显示哪个是下一个字母。
使用 Python 3.6.1
要按第一个字母对单词列表进行排序,使用另一个列表(字母表)给出的字母顺序,假设字母表很小并且它的长度与输入无关,有一个简单的 O(n * log n)解决方案:
如果调用的结果
alphabet.index()
被缓存,那么将获得@MaxU 的答案的解决方案。对于更多输入,有一个线性 O(n + m) 算法:
其中
n
是单词m
的数量,是字母表中的字母数。例子:性能比较
简而言之:没有惊喜。在小输入上,执行时间没有太大差异(因此,最好使用最简单的解决方案)。在大输入时,解决方案的渐近性会让人感觉到(如果性能很重要,请使用适当的算法)。
ñ,米〜1
对于少量输入,所有实现(
sorted_by_first_char()
上述 + 问题的其他 解决方案 )在我的机器上花费大致相同的 3-5 微秒时间:m ~ 10, n ~ 10_000*m
二次解开始滞后。
n, m ~ 1000_000
对于大字母表(所有 Unicode 字符),使用字典的非二次解决方案要快得多。它们按一秒的顺序执行:
二次算法(来自@Dmitry Erohin 的回答和我的评论的解决方案)在这种情况下需要大约 10 12次操作,即如果以每秒十亿次操作执行,则需要大约一个小时才能完成,这明显比非二次算法差解决方案。
请注意,@MaxU 答案
O(n log n + m)
中的解决方案在已经排序的输入(Python 中 sorted() 中使用的 timsort 算法的一个特性)上的运行速度比来自此答案的解决方案更快。O(n + m)
这通过对混合输入的测量得到证实(时间上的差异较小):
m ~ 1000_000, n ~ 10*m
作为
n
,线性解胜出:非标准(“自定义”)排序示例:
辅助词典: