Het complete algoritme

Leerdoel: je ziet alle bouwstenen samen en onderzoekt het algoritme.

Alles samen

def max_en_min(lijst):
    klein = groot = lijst[0]
    for waarde in lijst:
        if waarde < klein:
            klein = waarde
        elif waarde > groot:
            groot = waarde
    return klein, groot

1. Regel 2:

   Beide accumulators starten op lijst[0] — één regel, twee namen, allebei een echte waarde uit de lijst.

2. Regel 4-5:

   Kleiner dan de kleinste tot nu toe? Nieuwe kleinste.

3. Regel 6-7:

   De elif doet het spiegelbeeld, en alleen als de waarde géén nieuwe kleinste was — één waarde kan nooit allebei tegelijk zijn.

4. Regel 8:

   Eén return, twee waardes: Python maakt er een tuple van.

Acht regels, met één for-lus. Zet je vind-maximum en vind-minimum los naast elkaar, dan heb je er twee nodig en lees je de lijst twee keer.

Run

Python

Code-omgeving wordt voorbereid…

Interactief model

Max en min in een pass

Werk twee accumulators tegelijk bij.

LijstGebruik een niet-lege lijst voor hetzelfde gedrag als de lescode.

Bron referentieStap 0/6Vergelijkingen 0Resultaat min 5, max 5

05min max

12

28

31

47

54

Startwaardes

We starten met 5 als minimum en maximum.

Onderzoek — tel de vergelijkingen

Hoeveel werk doet ons algoritme? We bouwen een teller-versie en vergelijken hem met twee-aparte-passes. De else met een if erin is hetzelfde als de elif uit het algoritme, alleen kun je zo de tweede vergelijking tellen.

Python

Code-omgeving wordt voorbereid…

Wat zie je?

• Twee passes: altijd precies 2n vergelijkingen, 2000 hier.
• Eén pass, willekeurig: bijna 2000. klein is na een paar elementen al heel klein, dus waarde < klein is bijna nooit waar en de tweede vergelijking is bijna altijd nodig.
• Eén pass, aflopend: precies 1000. Elke waarde is kleiner dan de vorige, dus de eerste vergelijking is elke keer raak en de tweede wordt overgeslagen.

In vergelijkingen scheelt één pass dus tussen niets en de helft, en op gewone data bijna niets. De echte winst zit ergens anders: elk element wordt één keer gelezen in plaats van twee keer. Bij grote data, of data die van een trage bron komt, is dat wat telt.

Door naar aanpassen.