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

Question

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

它本质上是接收学生感兴趣的标签列表，然后搜索那些标签的精确匹配，这些标签与在该站点注册的间隔年（注册时也选择了标签）的人。下面给出的exactMatch是指用户指定的标记都包含在某个概要文件中（即，是子集）。如果找不到与用户输入的所有标记完全匹配的标记，它将检查标记列表本身的所有n-1长度子集，以查看选择性较低的查询是否匹配。它递归地执行此操作，直到找到至少3个匹配项。虽然它对小标记选择（最多5-7个）效果很好，但对较大的标记选择（7-13个）效果很慢，需要几秒钟才能返回结果。当选择11-13个标记时，由于工作超时，会出现Heroku错误

我做了一些测试，在算法中加入变量来计算，似乎当它深入到递归堆栈中时，每次都会检查几百个子集（查看该子集中是否存在精确匹配，如果存在，则将其添加到结果列表以输出），当您再添加一个标记时，计算的总数将翻倍（对于越来越多的标记，它进行了5415027050010001900和3400次操作）。每个深度上确实有几百个子集。但是exactMatches是O（1），正如我所写的（没有迭代），除了其他O（1）操作，比如IF，子集循环中的FOR最多将经历10次。这与每次数千次计算的测量结果一致

这并没有让我感到惊讶，因为选择和迭代所有子集似乎变得不难，但我的问题是，尽管只做了几千次计算，但为什么它如此缓慢。我知道我的电脑是GHz运行的，我希望网络服务器也是类似的，所以几千次计算肯定是瞬间完成的吧？我遗漏了什么？如何改进该算法？我还应该研究其他方法吗

# 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, [])

Answer 1

看起来你没有做几百个计算步骤。事实上，对于每个深度，您有几百个选项，因此您不应该添加，而应该乘以每个深度的步数来估计解决方案的复杂性

此外，这句话：This or adapting the stable marriage problem, I don't think any of those will work because it's a small dataset显然也不正确。虽然这些算法对于一些非常简单的情况来说可能有些过分，但它们仍然有效，并将对它们起作用

Answer 2

好吧，在反复摆弄计时器之后，我终于明白了。匹配时有几个功能：exactMatches、matchGapper和arbSubset。当我将计数器放入全局变量并测量操作时（以执行的我的代码的行来测量，对于大输入约为2-10K（约为10个标记））

的确，返回子集列表的arbSubset一开始似乎是一个看似合理的瓶颈。但是如果你仔细观察，我们1）处理少量的标记（顺序为10-50），更重要的是，2）我们在递归matchGapper时只调用arbSubset，这最多只发生10次，因为tagsList只能在10左右（顺序为10-50，如上所述）。当我检查生成仲裁子集所需的时间时，它的顺序是2e-5。因此，生成任意大小的子集所花费的总时间仅为2e-4。换句话说，不是web应用程序中5-30秒等待时间的来源

因此，撇开这一点不谈，我知道arbSubset只被调用了10次，而且调用速度很快，而且知道在我的代码中最多只进行了10K次计算，我开始清楚地意识到我必须使用一些开箱即用的函数，我不知道像set（）或.issubset（）或者类似的东西，需要大量的时间来计算，并且执行了很多次。在更多的地方添加一些计数器，很明显exactMatch（）占发生的所有计算的95-99%左右（如果我们必须检查各种大小的子集的所有组合以获得exactMatch，这是意料之中的）

因此，在这一点上，问题归结为这样一个事实：exactMatch在实现时大约需要0.02秒（经验上），并且被称为数千次。因此，我们可以尝试通过几个数量级使其更快（这已经是非常优化的），或者采取另一种不涉及使用子集查找匹配的方法。我的一个朋友建议创建一个包含所有标记组合（so2^len（tagsList）键）的dict，并将它们设置为具有该精确组合的已注册配置文件列表。这样，查询就是遍历一个（巨大的）dict，这可以很快完成。欢迎提出任何其他建议