• 1000 Прототип находится по адресу
covidgapyears.com . Я никогда не писал алгоритм сопоставления / рекомендации, поэтому, хотя люди предлагали такие вещи, как совместная фильтрация и поиск правил ассоциации или адаптация проблемы стабильного брака, я не думаю, что что-либо из этого будет работать, потому что это небольшой набор данных (несколько сотен пользователей щас скоро несколько тысяч). Поэтому я написал свой собственный алгоритм, руководствуясь здравым смыслом.
По сути, он берет список тегов, которые интересуют студента, а затем ищет точное совпадение этих тегов с кем-то, кто взял годовой перерыв и зарегистрировался на сайте ( кто также выбрал теги при регистрации). Как показано ниже, точное совпадение - это когда теги, указанные пользователем, ВСЕ содержатся в каком-то профиле (т. Е. Являются подмножеством). Если он не может найти точное совпадение со ВСЕМИ введенными пользователем тегами, , он проверит все подмножества длины n-1 в самом списке тегов, чтобы увидеть, есть ли совпадения для каких-либо менее избирательных запросов . Он делает это рекурсивно, пока не будет найдено по крайней мере 3 совпадения. Хотя он отлично работает для выбора небольших тегов (до 5-7), он становится медленным для выбора более крупных тегов (7-13), возвращая результат за несколько секунд. Когда выбрано 11-13 тегов, выдает ошибку Heroku из-за тайм-аута рабочего.
Я провел несколько тестов, поместив переменные внутри алгоритма для подсчета вычислений, и кажется, что когда он немного углубляется в рекурсивный стек, он каждый раз проверяет несколько сотен подмножеств (чтобы увидеть, есть ли точное соответствие для это подмножество, и если есть, добавьте его в список результатов для вывода), и общее количество вычислений удваивается, когда вы добавляете еще один тег (было выполнено 54, 150, 270, 500, 1000, 1900, 3400 операций для большего количества и больше тегов). Это правда, что на каждой глубине есть несколько сотен подмножеств. Но точное соответствие - это O (1), как я его написал (без итераций), и помимо других операций O (1), таких как IF, FOR внутри подмножества l oop будет, самое большее, проходить через 10 раз. Это согласуется с измеренным результатом нескольких тысяч вычислений каждый раз.
Это меня не удивило, так как выбор и повторение всех подмножеств, кажется, может стать не сложнее, но мой вопрос в том, почему это так медленно, несмотря на то, что выполняется всего несколько тысяч вычислений. Я знаю, что мой компьютер работает на частоте ГГц, и я ожидаю, что веб-серверы похожи, так что наверняка несколько тысяч вычислений будут почти мгновенными? Что мне не хватает и как я могу улучшить этот алгоритм? Любые другие подходы, которые мне следует изучить?
# 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, [])