正在处理下面的问题分组变音图。我目前的解决方案是按单个字符对每个单词进行排序,然后将相同的排序值映射到字典中。在
想知道有没有更好的方法可以减少算法时间复杂度?我在想一些不做排序的方法,比如散列,但是散列也需要单词的顺序字符。在
发布问题和我的代码,用Python2.7编写。在
问题
给出一个单词列表,比如[老鼠,星星,艺术,cie,ice],把相同的假名组合成桶并输出。 [老鼠,明星,艺术] [冰,冰]
源代码
from collections import defaultdict
def group_anagram(anagrams):
result = defaultdict(list)
for a in anagrams:
result[''.join(sorted(list(a)))].append(a)
return result
if __name__ == "__main__":
anagrams = ['rats', 'star', 'arts', 'cie', 'ice']
print group_anagram(anagrams)
你现在的方法可能是最好的。为了测试东西,我使用了你的方法,这个方法来自@bigballer的优秀答案,还有第三种方法,它使用一组计数作为键。为了对这些方法进行压力测试,我在大量(264097个单词)单词列表yawl上使用了它们,运行每个函数100次,并计算了每种方法的平均时间:
输出(在我的机器YMMV上):
^{pr2}$实际上,考虑到}字母表。至于为什么它是最好的,密钥是由Python内置的(运行优化的C代码)直接构造的,但是其他方法使用解释的Python代码。它是很难击败内置的。在
yawl
的大小,所有方法都非常快,每个方法处理超过25万个单词的时间不到一秒钟。然而,你最初的方法显然是赢家。此外,它不局限于拉丁语'a'
到{编辑时:我使用这个素数列表重新实现了第二种方法,对更频繁的字母(在英语中)分配较小的素数:
它可以节省几分之一秒的时间,但不足以使它比第一种方法快。在
进一步编辑时:
我重新运行上述代码,并对第二个方法进行了以下调整(如@bigballer所建议的):
在这个版本中,前两种方法变成了虚拟的平局,在我有限的测试中,基于prime的方法稍微快一点(快了大约8%)。尽管如此,我仍然认为第一种方法更可取,因为它不依赖于固定的字母表。在
素数因式分解是唯一的,乘法的顺序并不重要。在
您可以分配
a = 2, b = 3, c = 5, d = 7
等那么dab=7*2*3=42=3*2*7=bad,那么你的哈希值就是42。在
另一个选择是
hash(frozenset(collections.Counter(word).items()))
的有效实现编辑:最快的可能是使用26位。对于单词中的每个字符,翻转对应的位。您可能会遇到一些冲突,在这种情况下,可以在查找时删除重复数据
相关问题 更多 >
编程相关推荐