У меня есть список любимых фильмов, и я бы хотел отсортировать их по своему вкусу: от лучших фильмов (больше всего баллов) до худших фильмов (всего 1 балл).
Допустим,Список содержит уже 300 отсортированных фильмов, и вы хотите определить баллы для нового фильма.Вы можете сравнить новый фильм с каждым фильмом в отсортированном списке или использовать знания о том, что список отсортирован.
Я пытался реализовать его как бинарный поиск, чтобы каждая вставка (нового фильма) имела логарифмическийсложность.Реализация бинарного поиска была для меня легкой:
def binSearch(lst, number):
left = 0
right = len(lst) - 1
while left <= right:
middle = left + ((right - left) / 2)
if number == lst[middle]:
return True
else:
if number < lst[middle]:
right = middle - 1
else:
left = middle + 1
return False
Но определение точек довольно сложно для меня.Я уже отлаживаю его в течение нескольких часов, и все же некоторые ошибки происходят.Я много раз менял реализацию, но ничего не помогает.Вот мое последнее решение (возможно, алгоритм находится в худшем состоянии, чем было в начале)
def determinePoints(lst, new):
# lst is a list of tuples with movies
# new is a tuple with new movie (has no point associated yet)
if not lst: # no movie has points so far
return 1 # now exists only one movie with associated points
newTitle = new[0]
newGenre = new[1]
atMost = len(lst)
atLeast = 0
while atLeast < atMost - 1: # algorithm doesn't work
# if only two movies have associated points
center = twoPointsCenter(atLeast, atMost)
(title, genre) = lst[center]
os.system("clear")
competitionStrings = [ newTitle, newGenre, "\n" * 10, title, genre ]
print "\n".join([ x.center(150) for x in competitionStrings ])
c = getch()
if c == "j": # new movie is worse than this
atMost = center - 1
if atMost <= 1:
return 1
else: # new movie is better than this
atLeast = center + 1
if atLeast >= len(lst):
return max(atLeast, 1)
return max(twoPointsCenter(atLeast, atMost), 1)
def twoPointsCenter(left, right):
return left + ((right - left) / 2)
Не могли бы вы исправить мое решение (или реализовать его лучше), чтобы оно сходилось и заканчивалось с правильным результатом?
Он должен работать с lst длины от 0, 1, 2, ... и т. Д. Он не должен возвращать значение меньше 1. В списке фильмов не должно быть двух фильмов с одинаковымиколичество точек.
Когда функция determinePoints возвращает точки, я обновлю базу данных для этого фильма и увеличу количество точек на 1 для каждого фильма с> = точками, чем у этого нового фильма.
Спасибо