## ★ Aan de slag 50

Zoals we gezien hebben, heeft het gegeven algoritme voor het sorteren van een reeks van N getallen N stappen nodig.
Hoeveel extra vergelijkingen heb je nodig als je de reeks 1 langer maakt?

In dit gedeelte behandelen we enkele patronen voor het rekenen met rijen van waarden zoals je die in bijvoorbeeld spreadsheets vaak tegenkomt.
De twee belangrijke patronen zijn:

- map: bereken voor elke waarde een bijbehorende andere waarde
  - voorbeeld: bereken voor elk bedrag de bijbehorende BTW
  - (a0,a1,a2,...,an)⇒(b0,b1,b2,...,bn)
- reduce: vat een rij waarden samen in een enkele waarde
  - voorbeeld: sommeer alle waarden.
  - (a0,a1,a2,...,an)⇒(a0+a1+a2+...+an)

We behandelen deze patronen in de context van spreadsheets.
De online-versie van de voorbeelden vind je via: map-reduce spreadsheet.
Download het bestand en open deze in excel.
Je kunt het Excel-bestand ook vinden onder Bijlagen.

Map
Je kunt in een spreadsheet met een kolom van getallen een nieuwe kolom van afgeleide waarden maken.
Bijvoorbeeld: bij een kolom met bedragen exclusief 21% BTW, maak je een kolom met deze bedragen inclusief 21% BTW.
De formules in deze extra kolom zijn berekeningen met de waarde in dezelfde rij.
Als x het bedrag exclusief BTW is, en y het bedrag inclusief BTW, dan:

- Stap n: y[n] = x[n]∗1.21

In een spreadsheet wordt dit bijvoorbeeld:

| A | B | C
--- | --- | --- | ---
1 | n | x | y
2 | 0 |  |
3 | 1 | 42 | =B3 * 1.21
4 | 2 | 13 | =B4 * 1.21
... | ... | ... | ...

Samenvatten (reduce)
In een spreadsheetprogramma heb je ingebouwde functies om een reeks getallen samen te vatten: je reduceert een rij waarden tot 1 waarde.
Voorbeelden hiervan zijn: som, maximum, minimum, gemiddelde.
Dit zijn opdrachten om een operatie voor twee waarden, bijvoorbeeld optellen, uit te voeren voor alle elementen in een rij.
Dit reductiepatroon kun je ook gebruiken voor andere waarden dan getallen.
Voorbeelden: het samenvoegen van een rij strings tot één lange string; een and-operatie voor een rij boolean waarden.
In dit gedeelte maak je zelf zo’n reductie-algoritme voor een rij, met behulp van de basisoperatie voor twee waarden.

Voorbeeld 1: som
Als eerste voorbeeld geven we som, voor het optellen van een rij getallen x[1..N]x[1..N].
Opmerking: in veel programmeertalen, zoals Python en Java, beginnen rijen met index 0; in spreadsheets tellen de rijen en kolommen vanaf 1 (vanwege historische redenen).
In de kolom som houden we de som van de rij waarden tot nu toe bij:
som[n]=x[1]+x[2]+...+x[n]
We beginnen met som[0] als som van de getallen x[1..0]x[1..0]: deze rij bevat geen getallen, de som is dan 0.
Voor een willekeurige waarde n,n>0n,n>0 geldt:

- som[n]=x[1]+x[2]+...+x[n−1]+x[n], ofwel:
- som[n]=som[n−1]+x[n]

We drukken de volgende waarde van som uit in de voorafgaande waarde van som.
Samenvattend:

- Stap 0: som[0]=0som[0]=0
- Stap n: som[n]=som[n−1]+x[n](voor n>0)

In een spreadsheet wordt dit:

| A | B | C
--- | --- | --- | ---
1 | n | x | som
2 | 0 |  | 0
3 | 1 | 42 | =C2+B3
4 | 2 | 13 | =C3+B4
... | ... | ... | ...

Voorbeeld 2: maximum
Als tweede voorbeeld bepalen we het maximum van een rij getallen. Het belangrijkste verschil met het som-voorbeeld is dat we geen maximum voor een lege rij getallen kunnen bepalen: er is geen “stap 0”, we moeten met “stap 1” beginnen.
We gebruiken de functie MAX voor het maximum van 2 getallen.

- Stap 1: max[1]=x[1]max[1]=x[1]
- Stap n: max[n]=MAX(max[n−1],x[n])max[n]=MAX(max[n−1],x[n])

In een spreadsheet wordt dit:

| A | B | C
--- | --- | --- | ---
1 | n | x | max
2 | 0 |  | 0
3 | 1 | 42 | =MAX(C2,B3)
4 | 2 | 13 | =MAX(C3,B4)
... | ... | ... | ...

In plaats van =MAX(C2,B3) kun je ook schrijven: =IF(C2 >= B3, C2, B3).

Map/reduce
Je kunt deze map- en reduce-patronen op veel manieren combineren.
We geven hier als voorbeeld het bepalen van de som van een reeks kwadraten.
Als eerste proberen we Stap 0 (de initialisatie) en Stap 1 te formuleren.

- Stap 0: som[0]=0
- Stap n: x[n]=n∗n,som[n]=som[n−1]+x

Dit werken we uit in een spreadsheet:

| A | B | C
--- | --- | --- | ---
1 | n | x | som
2 | 0 |  | 0
3 | 1 | =A3 * A3 | =C2 + B3
4 | 2 | =A4 * A4 | =C3 + B4
... | ... | ... | ...

Links en verdieping
De begrippen map en reduce komen uit de wereld van functioneel programmeren. Maar het toepassingsgebied is veel groter: hiermee kun je efficiënt rekenen met grote hoeveelheden waarden in lijsten (rijen).
In het bijzonder maakt dit parallelle verwerking van de berekeningen mogelijk: de berekeningen worden verdeeld over meerdere rekeneenheden of over meerdere computers.
Zie ook: Wikipedia - MapReduce
Ook voor het werken met gegevens in spreadsheets is dit een handige aanpak.

1. (map)
   Maak een spreadsheet volgens onderstaand patroon, met in kolom x de kwadraten van n.
   - Bereken op deze manier in elk geval de kwadraten van 1..20.
   - Maak een grafiek van de kolommen n (x-as) en x (y-as).

   | A | B
   --- | --- | ---
   1 | n | x
   2 | 0 |
   3 | 1 | = ...
   4 | 2 | = ...
   ... | ... | ...

2. (reduce)
   Maak aan de hand van de voorbeelden voor som een spreadsheet-programma voor prod: het product van alle getallen in de rij x.
   prod[n]=x[1]∗x[2]∗...∗x[n]
   - Welke waarde kies je voor prod[0]?
   - Wat kies je voor prod[n]?
   - Maak de spreadheet, voor een rij van tenminste 20 getallen.

(Plaats n (0..) in kolom A, plaats de getallen in kolom B (vanaf positie n=1; en het product in kolom C, vanaf positie n=0)

(map/reduce)
Maak een spreadsheet-programma voor het uitrekenen van de gemiddelde waarde van een rij getallen (gemiddelde[n]=som[n]/n), waarin som[n] de som is zoals in het som-voorbeeld hierboven gegeven is.
Hint: ga uit van het som-voorbeeld, en voeg een extra kolom gemiddelde toe: een combinatie van de waarden n en som.