Mengder

Enkelt eksempel

En mengde (engelsk: set) er en datastruktur som kan holde mange verdier, men uten at det finnes noen rekkefølge på verdiene. Verdiene har ingen indeks/posisjon, slik de har i en liste. Med en mengde kan man i hovedsak gjøre fire ting:

# Opprett en mengde
s = {2, 3, 5}

# Legg til en verdi i mengden
s.add(6)

# Spør om en verdi er i mengden
print(3 in s)          # True
print(4 in s)          # False
for x in range(7):
    if (x not in s):
        print(x, end=" ")       # 0 1 4
print()

# Se gjennom verdiene i mengden
for x in s:
    print(x, end=" ")           # 2 3 5 6
print()

# Fjern en verdi fra mengden
s.remove(3)
print(s)                        # {2, 5, 6}
Opprette mengder
# Opprett en tom mengde
s = set()
print(s)

# Opprett en mengde fra en liste
a = [2, 3, 5]
s = set(a)
print(s)

# Opprett en mengde statisk
s = {2, 3, 5}
print(s)

# PS: MISLYKKET forsøk på å opprette en tom mengde:
s = {} # dette oppretter et oppslagsverk, ikke en mengde!
print(type(s))
Egenskaper ved mengder

Elementene i en mengde har ingen (forutsigbar) rekkefølge.

s = set()
s.add(2)
s.add(44)
s.add(11)
s.add(5)
s.add(33)

for e in s:
    print(e, end=" ") # Rekkefølge er forskjellig fra maskin til maskin
print()

Elementer er unike (en verdi finnes bare én gang i mengden).

# Duplikater blir borte
s = set([2, 2, 2])
print(s)          # {2}
print(len(s))     # 1

Mengder kan muteres.

s = {2, 3, 5}
r = s

r.add(9)
print(s) # {2, 3, 5, 9}

Elementene i en mengde kan ikke muteres.1

s = set()
s.add(42)       # int OK
s.add("foo")    # str er OK
s.add(False)    # bool er OK
s.add(1.4)      # float er OK
s.add((2, 3))   # tupler er OK 
print(s)

s.add([2, 3])   # Krasj! lister er IKKE OK (lister kan muteres)
s.add({2, 3})   # Ville også krasjet! (mengder kan også muteres)

Mengder er svært effektive.

# En liste kan brukes for samme formål som en mengde. La oss sammenligne
# hvor effektive de er til oppgaven "spør om en verdi er tilstede"
n = 2000
trails = 1000 # Flere forsøk utjevner forskjeller som skyldes forstyrrelser
a = list(range(n))
s = set(range(n))

import time
time_before = time.time()
for _ in range(trails):
    does_contain_minus_one = -1 in a
time_after = time.time()
elapsed_a = (time_after - time_before) * 1000
print(f"Det tok {elapsed_a:.0f}ms å sjekke listen {trails} ganger")

time_before = time.time()
for _ in range(trails):
    does_contain_minus_one = -1 in s
time_after = time.time()
elapsed_s = (time_after - time_before) * 1000
print(f"Det tok {elapsed_s:.0f}ms å sjekke mengden {trails} ganger")
ratio = elapsed_a/elapsed_s
print(f"Mengder var {ratio:.1f} ganger raskere enn lister for {n=}")
print("Prøv større verdi for `n` for å se større forskjeller")

  1. Det er ikke heelt sant at elementene i en mengde ikke kan muteres, men det er en hvit løgn vi lever godt med i INF100. ↩︎