我正在构建一个网络应用程序，以根据标记所表示的兴趣，将考虑间隔年的高中学生与经历间隔年的学生进行匹配。原型位于covidgapyears.com。我从未编写过匹配/推荐算法，因此尽管人们提出了诸如协作过滤和关联规则挖掘或适应稳定婚姻问题之类的建议，但我认为其中任何一个都不可行，因为它的数据集很小（数百个用户现在，几千个）。所以我用常识写了自己的算法。
本质上是获取学生感兴趣的标签列表，然后搜索与[[这些标签]完全匹配的人]，该人已经间隔了一年并在网站上进行了注册（注册时也选择了标签） ）。如下所述，精确匹配是指用户指定的标签是某个配置文件包含的所有标签（即是子集）。如果找不到与用户输入的所有标签完全匹配的内容，它将检查标签的所有n-1个长度子集本身，以查看是否有选择性较低的查询是否具有匹配项。它会递归执行此操作，直到找到至少3个匹配项。虽然它对于较小的标签选择（最多5-7）工作正常，但对于较大的标签选择（7-13）却变慢，需要几秒钟才能返回结果。选择11-13个标签后，由于工作程序超时而导致Heroku错误。 我通过将变量放入算法中以进行计算来进行一些测试，似乎当它深入到递归堆栈中时，它每次都会检查数百个子集（以查看该子集是否有精确匹配，并且如果有的话，将其添加到结果列表以输出），并且在您再添加一个标签时，计算总数就会加倍（对于越来越多的标签，分别进行了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, [])
我正在构建一个网络应用程序，以根据标记所表示的兴趣，将考虑间隔年的高中学生与经历间隔年的学生进行匹配。原型可在covidgapyears.com上找到。我有...
我的代码