Nederlands
Menu

Datastructuren en algoritmen

Wat is de meest passende reden dat open adressering met lineair proberen bij een hashtabel met veel elementen en een bezettingsgraad van ongeveer 0,5 vaak sneller is dan chaining (elementen koppelen met gelinkte lijsten)?

  1. ANa een botsing is de volgende onderzochte positie het naburige element, dat vaak in dezelfde cacheregel of de volgende ligt, zodat er minder geheugentoegangen nodig zijn
  2. BBij open adressering treden helemaal geen botsingen op
  3. CBij chaining moet de hashfunctie twee of meer keer worden berekend
Antwoord en toelichting tonen

Antwoord: A. Na een botsing is de volgende onderzochte positie het naburige element, dat vaak in dezelfde cacheregel of de volgende ligt, zodat er minder geheugentoegangen nodig zijn

Op moderne CPU's duurt het lezen van het hoofdgeheugen na een cachemiss veel langer dan berekeningen zoals vergelijkingen. Lineair proberen onderzoekt na een botsing de naburige positie, dus de meeste pogingen blijven binnen dezelfde cacheregel, en ook prefetching helpt. Bij chaining ligt het volgende element van een lijst vaak elders in het geheugen, zodat elke gevolgde pointer waarschijnlijk een cachemiss veroorzaakt. Ook bij dezelfde complexiteit in O-notatie kan de werkelijke snelheid sterk verschillen, afhankelijk van hoe het geheugen wordt benaderd. Lineair proberen wordt echter bij een hoge bezettingsgraad sterk trager doordat bezette posities clusteren, dus de bezettingsgraad wordt vrij laag gehouden.

Dit onderwerp oefenen Naar de onderwerppagina

Meer vragen over Datastructuren en algoritmen

  1. Voor sorteren op parallelle hardware zoals GPU's worden soms sorteermethoden met een vaste reeks vergelijk-en-verwisselstappen (sorteernetwerken) gebruikt, zoals bitonic sort. Waarom?
  2. Wat is de tijdcomplexiteit van een bewerking die in een array van n elementen elk paar van twee verschillende elementen precies één keer vergelijkt (een dubbele lus die element i vergelijkt met alle elementen erna en i telkens één stap verder zet)?
  3. Een programma met tijdcomplexiteit O(n²) doet er 0,5 seconde over bij 1000 gegevens. Hoeveel seconden duurt het ongeveer bij 4000 gegevens?
  4. Lineair zoeken vergelijkt de elementen van een array met 100 verschillende waarden één voor één vanaf het begin om een gezochte waarde te vinden. De gezochte waarde staat altijd in de array en heeft op elke positie dezelfde kans. Wat is het gemiddelde aantal vergelijkingen?
  5. Welke beschrijving van een gelinkte lijst (een lijst waarin elk element een pointer naar het volgende element bevat) is juist in vergelijking met een array?