Ben je bekend met 'sets'? Zo maak je van jaren, seconden

Gepubliceerd: 6 december 2019

Wout Werkman

Developer

Je hoeft niet lang geprogrammeerd te hebben om het volgende probleem al eens tegen te zijn gekomen: Je hebt een array en je wilt weten of die een bepaalde waarde bevat.
 Dit kun je op veel verschillende manieren doen en elke taal heeft wel functionaliteit om het makkelijker te maken. Hieronder zie je 3 voorbeelden.

C#

1var numbers = new List<int>{1, 3, 4, 5};
2numbers.Contains(9); // output: false
3numbers.Contains(5); // output: true
4

JavaScript

1const numbers = [1, 3, 4, 5];
2numbers.includes(9); // output: false
3numbers.includes(5); // output: true
4

Python

1numbers = [1, 3, 4, 5]
29 in numbers // output: false
35 in numbers // output: true

Dit is in elke taal erg leesbaar en makkelijk op te zetten. Maar er is een data structuur die speciaal hiervoor is gemaakt, namelijk: de Set. Echter is bij het kiezen van een datastructuur, belangrijk om de volgende drie vragen te beantwoorden:


  • Is het snel?
  • Is het makkelijk?
  • Is het leesbaar?

Deze vragen beantwoorden we met een vaak voorkomend probleem tijdens development. Dit probleem kan met zowel sets als lists worden opgelost.

Problemen oplossen door lists te gebruiken

Je hebt twee verzamelingen en wilt daarvan de waarden weten die in beide voorkomen. Ook wel een whitelist genoemd. Dit kun je oplossen door lists te gebruiken. Je filtert de ene verzameling door elke keer aan de andere verzameling te vragen of die de waarde heeft.
Dit kun je ook oplossen door sets te gebruiken. Hier doe je hetzelfde, maar maak je eerst van de ene verzameling een set. Dan vraag je tijdens het filteren van de andere verzameling voor elke waarde of de set hem heeft.

Is het snel?

De eerste vraag waar we een antwoord voor zoeken is: is het snel?
Hiervoor werken we het uit in javascript omdat dit een makkelijke taal is die iedereen in de browser kan uitvoeren en kijken we naar de performance. In deze test bouwen we twee arrays met willekeurige getallen en vervolgens kijken we hoelang het duurt om de whitelist te vinden met het gebruik van de native JavaScript Array en Set. Dit wordt uitgevoerd met een data grootte die elke keer twee keer zo groot wordt. Hieronder vind je de resultaten. (Neem de resultaten met een korrel zout omdat dit in een browser is uitgevoerd, dit is geen goed geïsoleerde test omgeving)
(code: https://jsbin.com/pivocudalu/1/edit?js )

Grafiek Logaritmische schaal
Grafiek Logaritmische schaal
Grafiek Lineaire schaal
Grafiek Lineaire schaal

Uit de gegevens kun je zien dat de de array methode naarmate de data groter wordt steeds slechter presteert dan de set. De array methode groeit kwadratisch terwijl de set methode lineair groeit. Als je N gebruikt voor de grootte van je data, dan kun je de hoeveelheid vergelijkingen uitdrukken als N * N voor de array methode en N + N voor de set methode.
 Zo kun je zien dat als N twee keer zo groot wordt, de tijd voor de array methode vier keer zo lang duurt. Terwijl de set Methode 2 keer zo lang duurt.
 Dit betekent dat als je een grootte van 100.000.000 hebt, dan zijn dat 100.000.000 * 100.000.000 vergelijkingen met de array methode terwijl het 100.000.000 + 100.000.000 vergelijkingen zijn met de set methode.
 Dit resulteert in 10.000.000.000.000.000 vergelijkingen met de array methode tegen 200.000.000 vergelijkingen met de set methode. Als je een miljard vergelijkingen per seconden doet dan is dat het verschil tussen een jaar en een seconde wachten op je resultaat! Het is dus duidelijk dat als de data groeit, sets veel sneller zijn. Maar waarom zou je het gebruiken met kleine data sets? Daarvoor gaan we naar de volgende vraag.

Is het gemakkelijk?

Om de vraag te beantwoorden of het makkelijk is, is de voornaamste vraag of het verschil in code groot is om van array naar set te gaan. Hiervoor kijken we naar een aantal voorbeelden van code in een paar populaire talen die meer om leesbaarheid en gemak draaien dan om performance. Hieronder zie je de voorbeelden voor C#, JavaScript en Python 3.

C#

1Array
2
3var allowedIds = new List<int>{1, 3, 4, 5};
4var selectedIds = new List<int>{0, 1, 2, 3, 5, 6};
5
6selectedIds.Where(id => allowedIds.Contains(id)); // output: {1, 3, 5}
7

C#

1Set
2
3var allowedIds = new HashSet<int>{1, 3, 4, 5};
4var selectedIds = new List<int>{0, 1, 2, 3, 5, 6};
5
6selectedIds.Where(id => allowedIds.Contains(id)); // output: {1, 3, 5}
7

JavaScript

1Array
2
3const allowedIds = [1, 3, 4, 5];
4const selectedIds = [0, 1, 2, 3, 5, 6];
5
6selectedIds.filter(id => allowedIds.includes(id)); // output: [1, 3, 5]
7

JavaScript

1Set
2
3const allowedIds = new Set([1, 3, 4, 5]);
4const selectedIds = [0, 1, 2, 3, 5, 6];
5
6selectedIds.filter(id => allowedIds.has(id)); // output: [1, 3, 5]
7

Python

1Array
2
3allowedIds = [1, 3, 4, 5];
4selectedIds = [0, 1, 2, 3, 5, 6];
5
6filter(lambda id : id in allowedIds, selectedIds) // output: [1, 3, 5]

Python

1Set
2
3allowedIds = {1, 3, 4, 5};
4selectedIds = [0, 1, 2, 3, 5, 6];
5
6filter(lambda id : id in allowedIds, selectedIds) // output: [1, 3, 5]
7

Is het leesbaar?

In deze voorbeelden kun je zien dat het maar heel kleine verschillen zijn. Python heeft zelfs syntax gemaakt specifiek voor sets!
 Hieruit kun je zien dat sets brede support hebben verspreid over vele talen. Volgens de Java conventie moet je zelfs elke class compatible maken voor sets. Maar dan kan het nog wel sneller en net zo makkelijk zijn. Maar als je collega’s het niet leesbaar genoeg vinden, zullen ze je code nooit accepteren. Leesbaarheid is altijd een mening die zeer verschilt voor ieder persoon. Maar sets kunnen leesbaar zijn als iedereen in een team het kent en weet waar ze voor staan.

Dus, wat is een set?

De term ‘set’ komt vanuit de wiskunde en staat voor een verzameling van unieke waarden. Hieronder volgt een lijst met eigenschappen van een (ongeordende) set in computers:

  • Alleen unieke waarden
  • Het is Iterable (iteratie is mogelijk)
  • Geen volgorde (je kan geen eerste, laatste of 5e opvragen)
  • Het duurt altijd net zo lang om een waarde toe te voegen of verwijderen (ongeacht de grootte van de set)
  • Het duurt altijd net zo lang om te vragen of de set een waarde heeft (ongeacht de grootte van de set)

Er zijn dus situaties waar je geen (ongeordende) Set wilt gebruiken, zoals hieronder opgenoemd:

  • Je wilt meerdere dezelfde waarden opslaan
  • Volgorde is belangrijk
  • Je vraagt niet vaak of die een bepaalde waarde heeft
  • De data is klein en performance is cruciaal

Dit zijn heel specifieke eigenschappen en dat is precies datgene dat een set leesbaar kan maken.
 Voortaan als je een set ziet, dan weet je al meer wat zijn doel is dan wanneer je een array ziet. Het is belangrijk dat iedereen in een team op de hoogte is van de functionaliteit die een set aanbiedt. Dan kan het zelfs zijn dat je sets gebruikt om het nog leesbaarder en minder complex te maken.

Een set is sneller, net zo makkelijk en leesbaar

Nu staan de feiten op een rij, een set is sneller, net zo makkelijk en kan zelfs leesbaarder zijn. Waarom gebruik jij nog geen sets?

Opmerkingen

Er zijn momenteel nog geen opmerkingen geplaatst onder deze blog.
Wil jij als eerste een bericht achter laten?

Laat een bericht achter
Aantal tekens:0 / 500

Beveiligd met reCAPTCHA.PrivacyVoorwaarden