Bouwsteen 4 — itereren tot het stabiel is

Hier bouw je op verder: De while-loop

Weet je dit niet meer zeker? Lees het terug voordat je verdergaat.

• Python De while-loop

Leerdoel: je herhaalt de update voor alle pagina's tot de ranks nauwelijks nog veranderen. Dan heb je de PageRank.

Het kip-ei-probleem oplossen

Je kunt de rank van een pagina pas goed berekenen als je de ranks van de anderen kent. Dus begin je met de startverdeling en reken je een hele ronde uit: alle pagina's, met de waarden uit de vorige ronde. Dat herhaal je. Elke ronde veranderen de waarden minder, en zodra de grootste verandering kleiner is dan een klein getal epsilon, stop je.

Maak elke ronde een nieuwe dict en laat rank staan tot de ronde af is. De oude waarden heb je nog nodig om het verschil te meten.

Een lus die stopt met return

Je weet niet vooraf hoeveel rondes nodig zijn. Daarom gebruik je een lus zonder eigen einde:

def eerste_boven(grens):
    getal = 1
    while True:
        getal = getal * 2
        if getal > grens:
            return getal

print(eerste_boven(100))   # 128

True is altijd waar, dus while True stopt nooit uit zichzelf. De enige uitgang is de return: die beëindigt de functie, en de lus meteen mee.

Voor het verschil heb je nog twee ingebouwde functies nodig:

print(abs(-0.2))       # 0.2
print(max(0.1, 0.3))   # 0.3

abs geeft de afstand tot nul, zonder min-teken. Of een rank stijgt of daalt, maakt voor het verschil niet uit. max met twee getallen geeft de grootste van de twee; zo houd je de grootste verandering bij.

Bouw en test

Python

Code-omgeving wordt voorbereid…

Haal je de return weg zonder er een if omheen te zetten, dan loopt de lus oneindig door en de tab bevriest: Python draait in dezelfde tab als de pagina. Kopieer je code daarom eerst naar een kladblok voordat je op Voer uit drukt.

Antwoord

def pagerank(web, d=0.85, epsilon=1e-9):
    rank = startverdeling(web)
    while True:
        nieuw = {}
        for p in web:
            nieuw[p] = nieuwe_rank(web, rank, p, d)
        verschil = 0.0
        for p in web:
            verschil = max(verschil, abs(nieuw[p] - rank[p]))
        rank = nieuw
        if verschil < epsilon:
            return rank

De eerste loop bouwt alle nieuwe ranks uit de oude rank, en pas daarna overschrijf je rank. Zo kun je het verschil nog meten.

Door naar compleet →.