Тренажёр

Нашли ошибку?

Рекомендации книг по похожим читателям

СложнаяРеализацияГлава 10

РешеноНашли ошибку?

#k ближайших соседей#косинусное сходство#хеш-таблицы#рекомендацииid: ga-book-recommend

Оценки читателей хранятся так: ratings[читатель][книга] = оценка (от 1 до 5). Напишите recommend(ratings, user, k): функция рекомендует читателю user книги по оценкам похожих на него читателей.

Правила

Сходство двух читателей — косинусное сходство их оценок, но только по книгам, которые оценили оба: Σ aᵢ·bᵢ / (√Σ aᵢ² · √Σ bᵢ²). Если общих книг нет — 0.
Соседи — k других читателей с наибольшим сходством. Читатели со сходством 0 соседями не считаются. При равном сходстве выбирается тот, чьё имя меньше по алфавиту.
Кандидаты — книги, которые оценил хотя бы один сосед, но не оценил user. Оценка кандидата — среднее оценок соседей, которые его читали.
Ответ — названия кандидатов по убыванию оценки, при равенстве — по алфавиту.
Если user нет в ratings или рекомендовать нечего, ответ — [].

Пример

ratings = {
    "Аня":   {"Дюна": 5, "Солярис": 4, "Пикник": 1},
    "Боря":  {"Дюна": 5, "Солярис": 5, "Гиперион": 4},
    "Вика":  {"Дюна": 1, "Пикник": 5, "Мастер": 5},
    "Гоша":  {"Солярис": 4, "Гиперион": 2, "Мастер": 3},
}
recommend(ratings, "Аня", 2)   # ["Гиперион", "Мастер"]

Решение

def recommend(ratings: dict[str, dict[str, float]], user: str, k: int) -> list[str]:
    """Книги для user по оценкам k самых похожих читателей (косинусное сходство)."""
    # ваш код
    raise NotImplementedError

Вывод

tests.py — только для чтения
RATINGS = {
    "Аня": {"Дюна": 5, "Солярис": 4, "Пикник": 1},
    "Боря": {"Дюна": 5, "Солярис": 5, "Гиперион": 4},
    "Вика": {"Дюна": 1, "Пикник": 5, "Мастер": 5},
    "Гоша": {"Солярис": 4, "Гиперион": 2, "Мастер": 3},
}


def test_example():
    """Пример из условия"""
    got = recommend(RATINGS, "Аня", 2)
    assert got == ["Гиперион", "Мастер"], f"получено {got!r}"


def test_k_one():
    """k = 1: сосед — Гоша (одна общая книга даёт сходство 1.0, у Бори ≈ 0.994)"""
    got = recommend(RATINGS, "Аня", 1)
    assert got == ["Мастер", "Гиперион"], f"получено {got!r} (оценки Гоши: Мастер 3, Гиперион 2)"


def test_average_and_order():
    """Средняя оценка по соседям, сортировка по убыванию"""
    ratings = {
        "u": {"a": 5},
        "n1": {"a": 5, "x": 4, "y": 2},
        "n2": {"a": 4, "x": 2, "z": 5},
    }
    got = recommend(ratings, "u", 2)
    assert got == ["z", "x", "y"], f"получено {got!r} (оценки: z 5, x 3, y 2)"


def test_alphabetical_tie():
    """Равные оценки — по алфавиту"""
    ratings = {"u": {"a": 3}, "n": {"a": 3, "в": 4, "б": 4}}
    got = recommend(ratings, "u", 1)
    assert got == ["б", "в"], f"получено {got!r}"


def test_zero_similarity_ignored():
    """Читатели без общих книг — не соседи"""
    ratings = {"u": {"a": 5}, "stranger": {"b": 5, "c": 5}}
    got = recommend(ratings, "u", 3)
    assert got == [], f"ожидалось [], получено {got!r}"


def test_neighbor_tie_by_name():
    """Равное сходство — сосед с меньшим именем"""
    ratings = {"u": {"a": 4}, "Яна": {"a": 2, "y": 5}, "Ада": {"a": 1, "x": 5}}
    got = recommend(ratings, "u", 1)
    assert got == ["x"], f"получено {got!r} — у обоих сходство 1.0, выбирается Ада"


def test_unknown_user_and_nothing_new():
    """Неизвестный читатель и нечего рекомендовать → []"""
    assert recommend(RATINGS, "Никто", 2) == [], "неизвестный читатель"
    ratings = {"u": {"a": 5, "b": 3}, "v": {"a": 4, "b": 4}}
    assert recommend(ratings, "u", 1) == [], "все книги соседа уже прочитаны"

Можно решать и в своём редакторе: «Скопировать с тестами» и запустите python3 book_recommend.py — тесты те же, результат покажет ✓ / ✗ и итог.

Подсказка 1
Разбейте задачу на функции: similarity(a, b) по общим книгам → k самых похожих читателей → кандидаты и их средние оценки → сортировка.
Подсказка 2
Косинусное сходство по общим книгам: сумма произведений оценок / (корень суммы квадратов оценок a × корень суммы квадратов оценок b). Суммы только по общим книгам.
Подсказка 3
Сортировка с несколькими правилами: key=lambda x: (-score, name) — сначала по убыванию score, при равенстве по имени.

solution.py

import math


def similarity(a: dict[str, float], b: dict[str, float]) -> float:
    """Косинусное сходство по книгам, которые оценили оба."""
    common = a.keys() & b.keys()
    if not common:
        return 0.0
    dot = sum(a[x] * b[x] for x in common)
    norm_a = math.sqrt(sum(a[x] ** 2 for x in common))
    norm_b = math.sqrt(sum(b[x] ** 2 for x in common))
    return dot / (norm_a * norm_b)


def recommend(ratings: dict[str, dict[str, float]], user: str, k: int) -> list[str]:
    """Книги для user по оценкам k самых похожих читателей (косинусное сходство)."""
    if user not in ratings:
        return []
    mine = ratings[user]
    scored = [(similarity(mine, theirs), name) for name, theirs in ratings.items() if name != user]
    neighbors = [name for sim, name in sorted(scored, key=lambda x: (-x[0], x[1])) if sim > 0][:k]

    collected: dict[str, list[float]] = {}
    for name in neighbors:
        for book, score in ratings[name].items():
            if book not in mine:
                collected.setdefault(book, []).append(score)
    averages = {book: sum(s) / len(s) for book, s in collected.items()}
    return sorted(averages, key=lambda book: (-averages[book], book))