如何使这个python函数更快？

Question

我编写的以下代码接受一组68000项，并尝试根据字符串中的文本位置查找类似项。这个过程需要一点对这个i34130我暂时使用的代码-有没有任何方法来加快这一点？我在做一种“你是说？”函数，所以我需要对用户输入的内容进行排序。你知道吗

我不是在用关键字创建的字典中通过相似性来比较，而是在动态地比较用户输入和所有现有键之间的相似性。用户可能会键入错误的密钥，所以它会说“Doyoumean？”，就像谷歌搜索一样。你知道吗

根据平均测试，排序不影响时间。你知道吗

def similar_movies(movie):
    start=time.clock()
    movie=capitalize(movie)
    similarmovies={}
    allmovies=all_movies() #returns set of all 68000 movies
    for item in allmovies:
        '''if similar(movie.lower(),item.lower())>.5 or movie in item: #older algorithm
            similarmovies[item]=similar(movie.lower(),item.lower())'''
        if movie in item: #newer algorithm,
                similarmovies[item]=1.0
                print item
        else:
            similarmovies[item]=similar(movie.lower(),item.lower())
    similarmovieshigh=sorted(similarmovies, key=similarmovies.get, reverse=True)[:10]
    print time.clock()-start
    return similarmovieshigh

使用的其他功能：

from difflib import SequenceMatcher
def similar(a, b):
    output=SequenceMatcher(None, a, b).ratio()
    return output

def all_movies(): #returns set of all keys in sub dicts(movies)
    people=list(ratings.keys())
    allmovies=[]
    for item in people:
        for i in ratings[item]:
            allmovies.append(i)
    allmovies=set(allmovies)
    return allmovies

字典采用这种格式，但有数千个名称：

收视率={'Shane'：{'Avatar'：4.2，'127小时'：4.7}，'Joe'：{'Into The Wild'：4.5，'Unstopped'：3.0}

Answer 1

您的算法将是O（n²），因为在每个标题中，in操作符必须检查标题的每个子字符串，以确定输入的文本是否在其中。所以是的，我能理解你为什么想让它跑得更快。你知道吗

i3没有提供太多的计算能力，所以尽可能多的预计算是唯一的解决方案，而运行额外的软件（如数据库）可能会提供很差的结果，同样是由于它的能力。你知道吗

您可以考虑使用标题词词典（可能有预先计算的语音变化，以消除最常见的拼写错误-波特词干分析器算法应提供一些有用的缩减规则，例如，允许“unstop”匹配“unstoppen”）。你知道吗

因此，例如，词典中的一个键是“wild”（或语音调整），与该键相关联的值将是包含“wild”的所有标题的列表；对于“the”、“into”、“avatar”、“hours”、“127”以及68000个标题列表中的所有其他单词，都将具有相同的值。举个例子，你字典里的“狂野”词条可能看起来像：

"wild": ["Into The Wild", "Wild Wild West", "Wild Things"]

（是的，我在IMDB上搜索了“wild”，只是为了让这个列表有更多的条目——可能不是最好的选择，但没有多少标题中有“avatar”、“unstoppable”或“hours”）。你知道吗

像“the”这样的常用词可能有足够的条目，您可能希望将它们排除在外，因此词典的持久副本可能有助于您进行特定的调整，尽管这不是必需的，而且启动时计算时间应该相对较快。你知道吗

当用户键入某些文本时，您可以将文本拆分为单词，如果选择使用它们，则应用任何拼音缩减，然后将来自用户的所有单词的所有标题列表（包括重复的）串联起来。你知道吗

然后，计算重复项并按标题匹配的次数排序。如果用户键入“The Wild”，那么在“Into The Wild”（“The”和“Wild”）上会有两个匹配项，因此它的排序应该高于仅包含“The”或“Wild”的标题，但不能同时包含这两个标题。你知道吗

在生成最终排序的列表后，可以搜索评分列表，并将评分附加到每个条目中；此操作应该很快，因为您的评分已经在字典中，由名称键入。你知道吗

这就把O（n²）搜索变成了O（log（n））搜索，搜索每个输入的单词，如果它适合您的需要，性能会有很大的不同。你知道吗

Answer 2

如果您是为生产系统开发的，我建议您使用像Whoosh (Python)、Elastic Search (Java)或Apache Solr (Java)这样的全文搜索引擎。全文搜索引擎是一个服务器，建立一个索引，以实现全文搜索，包括模糊或接近搜索有效。许多流行的数据库系统还具有像PostgreSQL FTS和MySQL FTS这样的全文搜索引擎，如果您已经在使用这些数据库引擎，这可能是一个可接受的替代方案。你知道吗

如果此代码主要是为自学习而开发的，并且您希望学习如何实现模糊搜索，那么您可能希望查看索引和搜索项中电影标题的规范化。有像Soundex和Metaphone这样的方法可以根据搜索词在英语中的发音来规范化搜索词，这个规范化的词可以用来创建搜索索引。PostgreSQL有implementation of these algorithms。请注意，这些算法是非常基本的构建块，一个适当的全文搜索引擎将考虑拼写错误、同义词、停止词、特定语言的怪癖以及并行/分布式处理等优化

Answer 3

在all_movies()：您可以添加到集合而不是将keys（）强制转换到列表，而不是附加到列表：

def all_movies():
    allmovies = set()
    for item in ratings.keys():
        for i in ratings[item]:
            allmovies.add(i)
    return allmovies

编辑：或仅使用一个for循环：

def all_movies():
    result = []
    for rating_dict in ratings.values()
        result += rating_dict.keys()
    return result

我在similar_movies里什么也看不见。你知道吗

还可以看看芹菜：http://docs.celeryproject.org/en/latest/多加工，
尤其是chunks概念：http://docs.celeryproject.org/en/latest/userguide/canvas.html#chunks