Sets — een verzameling zonder duplicaten

Het probleem dat we oplossen

De verkoop van een dag komt binnen als een lijst, één verkoop per item:

sold = ["pen", "bag", "pen", "ink", "pen"]

De vraag: hoeveel verschillende producten zijn er verkocht? len(sold) zegt vijf, maar dat is het aantal verkopen. Er waren drie verschillende producten.

Met de vorige hoofdstukken lukt het ook — begin met een lege lijst en check voor elk item if item not in unique: voordat je het toevoegt. Zes regels, en het werkt.

Maar als de vraag is "welke producten zijn er op maandag én dinsdag verkocht?", dan heb je twee geneste lussen nodig. "Alleen maandag?" — er is nog een nodig. Deze vragen komen zo vaak voor dat ze een eigen tak van de wiskunde hebben, en in Python kan die wiskunde rechtstreeks geschreven worden.

Een set is de container daarvoor: hij houdt geen duplicaten bij en beantwoordt "in beide" en "in het ene maar niet in het andere" met één teken.

Aan het einde van dit hoofdstuk kun je

• Een set bouwen en duplicaten uit een lijst halen
• Twee sets vergelijken met |, &, - en ^
• Uitleggen waarom {} geen lege set is
• Weten dat een set geen volgorde heeft, en wanneer dat uitmaakt
• Het patroon schrijven dat duplicaten verwijdert en de volgorde behoudt

Voorkennis: Dictionaries — paren van key en value.

Een set — een verzameling zonder duplicaten

sold = ["pen", "bag", "pen", "ink", "pen"]

unique = set(sold)
print(sorted(unique))
print(len(unique))

['bag', 'ink', 'pen']
3

set(...) neemt een lijst en gooit de duplicaten eruit. Drie keer pen wordt één.

Let op sorted() rondom het printen — dat is met opzet. De reden komt zo meteen.

Je kunt er ook direct een schrijven, met accolades:

letters = {"a", "b", "a"}
print(sorted(letters))
print(len(letters))

['a', 'b']
2

De tweede "a" verdween stilzwijgend. Geen fout — een set kent het idee van "hetzelfde ding twee keer" niet.

{} is geen lege set

not_a_set = {}
real_set = set()

print(type(not_a_set))
print(type(real_set))

<class 'dict'>
<class 'set'>

Accolades betekenden eerst dictionaries, dus een lege {} bleef een dictionary. Voor een lege set moet je set() schrijven.

De fout blijft eerst stil: begin met {}, roep .add() aan, en je krijgt een AttributeError waardoor het lijkt alsof add het probleem is.

Er is geen volgorde

Dit is de belangrijkste beperking van een set, en de eigenschap die het vaakst verkeerd begrepen wordt.

De dingen in een set staan in geen enkele volgorde. Er zijn geen indexen en geen slices:

tags = {"new", "sale"}
print(tags[0])

TypeError: 'set' object is not subscriptable

En de volgorde die je ziet als je er een print, is niet te vertrouwen — voer hetzelfde programma twee keer uit en die kan verschillen. Daarom sorteert elk voorbeeld in dit hoofdstuk voor het printen: wat je ziet als je een set direct print, is niet gegarandeerd wat je de volgende keer ziet.

De kortste manier om duplicaten uit een lijst te halen is list(set(sold)), en die gooit de oorspronkelijke volgorde weg. Als de volgorde belangrijk is, gebruik je een set en een lijst samen:

sold = ["pen", "bag", "pen", "ink", "bag"]
seen = set()
unique = []

for item in sold:
    if item not in seen:
        seen.add(item)
        unique.append(item)

print(unique)

['pen', 'bag', 'ink']

De lijst bewaart de volgorde en de set onthoudt wat er al voorbij gekomen is. Die combinatie is een heel veelvoorkomend patroon.

Toevoegen en verwijderen

tags = {"new"}

tags.add("sale")
tags.add("new")
print(sorted(tags))

tags.discard("gone")
tags.remove("sale")
print(sorted(tags))

['new', 'sale']
['new']

add stopt er één ding in — en als het er al is, gebeurt er niets en klaagt niemand. De append van een lijst zou een tweede kopie gemaakt hebben; een set doet dat niet.

Verwijderen komt in twee vormen, en het verschil is handig:

tags = {"new"}
tags.remove("gone")

KeyError: 'gone'

remove stopt als hij het ding niet vindt; discard doet stilzwijgend niets. Als het ding er zou moeten zijn, schrijf je remove zodat het ontbreken opvalt.

Twee sets vergelijken

Hier worden sets echt handig:

monday = {"rafi", "ahmed", "bilal"}
tuesday = {"ahmed", "dia"}

print(sorted(monday | tuesday))
print(sorted(monday & tuesday))
print(sorted(monday - tuesday))
print(sorted(monday ^ tuesday))

['ahmed', 'bilal', 'dia', 'rafi']
['ahmed']
['bilal', 'rafi']
['bilal', 'dia', 'rafi']

Vier symbolen, vier vragen:

• | — in één van beide (union). Iedereen die over die twee dagen heen kwam.
• & — in beide (intersection). Wie er op beide dagen kwam.
• - — in de eerste maar niet in de tweede (difference). Wie er alleen op maandag kwam.
• ^ — in precies één (symmetric difference). Wie er op één van de twee dagen kwam, maar niet op allebei.

Merk op dat - rekening houdt met de volgorde: monday - tuesday en tuesday - monday geven verschillende antwoorden. De andere drie lezen van beide kanten hetzelfde.

Die vier met lussen schrijven zou elk meerdere regels kosten, met een goede kans om er minstens één verkeerd te hebben.

Wat erin kan

Dezelfde regel als bij dictionary keys: wat je erin stopt moet onveranderlijk zijn.

s = set()
s.add([1, 2])

TypeError: unhashable type: 'list'

Letterlijk hetzelfde bericht, om dezelfde reden — onder de motorkap gebruikt een set ook hashing. Strings, getallen en tuples mogen wel; lijsten en dictionaries niet.

Een compleet voorbeeld

sales.py:

# Which products sold on both days, and which only on one
monday = ["pen", "bag", "pen", "ink"]
tuesday = ["ink", "bottle", "pen", "ink"]

mon = set(monday)
tue = set(tuesday)

print("Monday sold    :", sorted(mon), f"({len(monday)} sales, {len(mon)} products)")
print("Tuesday sold   :", sorted(tue), f"({len(tuesday)} sales, {len(tue)} products)")
print()
print("Either day     :", sorted(mon | tue))
print("Both days      :", sorted(mon & tue))
print("Monday only    :", sorted(mon - tue))
print("Exactly one day:", sorted(mon ^ tue))
print()
print("Was ink sold on Monday?", "ink" in mon)

Monday sold    : ['bag', 'ink', 'pen'] (4 sales, 3 products)
Tuesday sold   : ['bottle', 'ink', 'pen'] (4 sales, 3 products)

Either day     : ['bag', 'bottle', 'ink', 'pen']
Both days      : ['ink', 'pen']
Monday only    : ['bag']
Exactly one day: ['bag', 'bottle']

Was ink sold on Monday? True

Drie dingen die het vermelden waard zijn.

De oorspronkelijke lijsten zijn bewaard gebleven. len(monday) meldt vier verkopen, len(mon) drie producten. Zodra het naar een set omgezet is, is het aantal verkopen verdwenen — de set is dus geen vervanging van de data, maar een gereedschap om één soort vraag over die data te stellen.

sorted() voor elke print. Zonder dat zou de volgorde willekeurig lijken, en zou die tussen twee uitvoeringen kunnen veranderen.

Er staat "ink" in mon, niet "ink" in monday. Allebei geeft True, maar zoeken in een set is sneller dan zoeken in een lijst — in een lijst vergelijkt Python één item per keer, in een set hash't hij rechtstreeks naar de goede plek. Met vier dingen maakt dat niets uit; met veertigduizend wel.

Wanneer het misgaat

AttributeError: 'dict' object has no attribute 'add' Iemand schreef s = {} met de bedoeling een set, maar dat is een lege dictionary. Schrijf s = set().

TypeError: 'set' object is not subscriptable Iemand schreef s[0]. Een set heeft geen volgorde, dus geen indexen. Als je een bepaald item nodig hebt, wilde je waarschijnlijk een lijst of een dictionary; anders geeft sorted(s) je een lijst.

KeyError: 'gone' Er werd aan remove gevraagd om iets te verwijderen dat niet in de set zit. Als één van beide situaties normaal is, gebruik je discard.

TypeError: unhashable type: 'list' Een poging om een lijst in een set te stoppen. Zet hem om met tuple(...).

De volgorde liep door elkaar na list(set(...)) Dat is te verwachten; sets hebben geen volgorde. Als je die nodig hebt, gebruik je het seen-patroon hierboven, of sorted().

Ik vergeleek twee sets met == en kreeg True terwijl de volgorde anders was Terecht. Twee sets zijn gelijk als ze dezelfde dingen bevatten — de volgorde speelt geen rol. [1, 2] == [2, 1] is False bij lijsten; {1, 2} == {2, 1} is True bij sets.

Jouw beurt

Schrijf een bestand genaamd visitors.py met drie lijsten met bezoekers, één per dag, waarin sommige namen op meer dan één dag voorkomen.

Print daarna:

1. Hoeveel bezoeken elke dag, en hoeveel verschillende mensen
2. Hoeveel verschillende mensen over alle drie de dagen
3. De mensen die op alle drie de dagen kwamen
4. De mensen die alleen op de eerste dag kwamen
5. De mensen die op precies één van de eerste twee dagen kwamen

Daarna twee experimenten:

• Haal duplicaten op twee manieren weg — list(set(...)) en het seen-patroon hierboven — en print beide resultaten naast elkaar. Wat is het verschil?
• Probeer een lege set te maken met {} en roep .add() erop aan. Welke fout komt terug, en welk type object noemt het bericht?

De tweede is klein, en hem één keer met je eigen ogen zien betekent dat die fout je nooit meer tien minuten kost.