python - 基于子集的递归python匹配算法工作太慢

问题描述

我正在构建一个网络应用程序，以根据标签表示的兴趣将考虑间隔年的高中学生与已经过间隔年的学生进行匹配。covidgapyears.com上有一个原型。我从来没有写过匹配/推荐算法，所以尽管人们提出了诸如协同过滤和关联规则挖掘之类的建议，或者适应稳定的婚姻问题，但我认为这些都行不通，因为它是一个小数据集（几百个用户现在，很快几千）。所以我用常识编写了自己的算法。

它本质上是接收学生感兴趣的标签列表，然后搜索这些标签与已经过了间隔年并在网站上注册的人（他们也在注册时选择了标签）的完全匹配。如下所示，精确匹配是用户指定的标签全部包含在某个配置文件中（即，是一个子集）。如果找不到与用户输入的所有标签的完全匹配，它将检查标签列表本身的所有 n-1 长度子集，以查看是否有任何选择性较低的查询匹配. 它递归地执行此操作，直到找到至少 3 个匹配项。虽然它适用于小标签选择（最多 5-7），但对于较大的标签选择（7-13）会变慢，需要几秒钟才能返回结果。When 11-13 tags are selected, hits a Heroku error due to worker timeout.

我通过将变量放入算法中以计算计算量进行了一些测试，似乎当它深入递归堆栈时，它每次检查几百个子集（查看该子集是否有一个精确匹配，如果有即，将其添加到结果列表以输出），并且当您再添加一个标签时，计算总数加倍（对于越来越多的标签，它进行了 54、150、270、500、1000、1900、3400 次操作）。确实，每个深度都有几百个子集。但是我写的exactMatches是O（1）（没有迭代），除了像IF这样的其他O（1）操作之外，子集循环内的FOR最多会经历大约10次。这与每次数千次计算的测量结果一致。

这并不让我感到惊讶，因为选择和迭代所有子集似乎不会变得更难，但我的问题是为什么它这么慢，尽管只进行了几千次计算。我知道我的计算机在 GHz 下运行，并且我希望 Web 服务器是类似的，所以几千次计算肯定会接近瞬时？我错过了什么，我该如何改进这个算法？我应该研究其他任何方法吗？

# takes in a list of length n and returns a list of all combos of subsets of depth n
def arbSubsets(seq, n):
    return list(itertools.combinations(seq, len(seq)-n))

# takes in a tagsList and check Gapper.objects.all to see if any gapper has all those tags
def exactMatches(tagsList):
    tagsSet = set(tagsList)
    exactMatches = []
    for gapper in Gapper.objects.all():
        gapperSet = set(gapper.tags.names())
        if tagsSet.issubset(gapperSet):
            exactMatches.append(gapper)
    return exactMatches

# takes in tagsList that has been cleaned to remove any tags that NO gappers have and then checks gapper objects to find optimal match
def matchGapper(tagsList, depth, results):
    # handles the case where we're only given tags contained by no gappers
    if depth == len(tagsList):
        return []
    # counter variable is to measure complexity for debugging
    counter += 1
    # we don't want too many results or it stops feeling tailored
    upper_limit_results = 3
    # now we must check subsets for match
    subsets = arbSubsets(tagsList, depth)
    for subset in subsets:
        counter += 1
        matches = exactMatches(subset)
        if matches:
            for match in matches:
                counter += 1
                # new need to check because we might be adding depth 2 to results from depth 1
                #  which we didn't do before, to make sure we have at least 3 results
                if match not in results:
                    # don't want to show too many or it doesn't feel tailored anymore
                    counter += 1
                    if len(results) > upper_limit_results: break
                    results.append(match)
    # always give at least 3 results
    if len(results) > 2:
        return results
    else:
        # check one level deeper (less specific) into tags if not enough gappers that match to get more results
        counter += 1
        return matchGapper(tagsList, depth + 1, results)

# this is the list of matches we then return to the user 
matches = matchGapper(tagsList, 0, [])

标签： pythonalgorithmtime-complexitymatchsubset

python - 基于子集的递归python匹配算法工作太慢

问题描述

解决方案

推荐阅读