Mengder

Se også offisiell dokumentasjon for set.

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)

# Antall elementer i mengden
print(len(s))              # 4

# Spør om en verdi er i mengden
print(3 in s)              # True
print(4 in s)              # False

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

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

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

# Opprett en mengde statisk (med verdier angitt direkte i kildekoden)
s = {2, 3, 5}
print(s)

# Opprett en mengde fra en liste (eller annen samling med elementer)
a = [2, 3, 3, 5]
s = set(a)
print(s) # {2, 3, 5}

greeting = 'hello'
required_letters = set(greeting)
print(required_letters) # {'h', 'e', 'l', 'o'}

# Mengdeinklusjon.
# Vi tar utgangspunkt i en annen samling (her a), og bruker deretter
# benytte en inklusjons-for-løkke mellom krølleparentesene
a = ['foo', 'bar', 'baz', 'qatchita']
myset = {s[0] for s in a}
print(myset) # {'f', 'b', 'q'}

# Vi kan også legge til en betingelse for inklusjon etter 'if'
myset = {s[0] for s in a if len(s) <= 3}
print(myset) # {'f', 'b'}
Egenskaper ved mengder

Elementene i en mengde har ingen (meningsfull/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 kan være ulik fra maskin til maskin
print()

print({2, 3, 5} == {5, 3, 2}) # True

Elementer er unike (én 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}
alias = s

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

Elementene i en mengde må ikke være mulig å mutere.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')
Operasjoner på mengder

Det finnes flere måter å manipulere mengder på. For hver av operasjonene her finnes det destruktive metoder som muterer mengden vår, i tillegg finnes også ikke-destruktive alternativer som oppretter en helt nytt objekt i minnet. Det destruktive alternativet vil ofte være mer effektivt med tanke på minnebruk og kjøretid – samtidig er det av og til nødvendig for korrektheten i programmet ditt for øvrig at du benytter en ikke-destruktiv variant.

Se mer detaljer om operasjoner på mengder i den offisielle dokumentasjonen.

Legg til elementer (add/update/union/|)
# Legg til elementer
# destruktivt (ved mutasjon)
myset = {1, 2}
alias = myset

myset.add(6)         # ett
myset.update([2, 8]) # flere
myset |= {1, 2, 9}   # flere

print(myset) # {1, 2, 6, 8, 9}
print(alias) # {1, 2, 6, 8, 9}

# Legg til elementer
# ikke-destruktivt (nytt objekt)
myset = {1, 2}
alias = myset


myset = myset.union([2, 8])
myset = myset | {1, 2, 9}

print(myset) # {1, 2, 8, 9}
print(alias) # {1, 2}
Fjerne elementer (remove/discard/difference/-/mengdeinklusjon)
# Fjern elementer
# destruktivt (ved mutasjon)
myset = {1, 2, 3, 4, 5}
alias = myset

# 'remove' fjerner ett element
# (ikke funnet -> krasjer)
myset.remove(1)

# 'discard' fjerner ett element
# (ikke funnet -> ignorer)
myset.discard(2)
myset.discard(42)   

# difference_update/-= fjerner
# flere elementer hvis de finnes
myset.difference_update([4, 6])
myset -= {5, 7, 9}

print(myset) # {3}
print(alias) # {3}

# Fjern elementer
# ikke-destruktivt (nytt objekt)
myset = {1, 2, 3, 4, 5}
alias = myset






# Mengdeinklusjon med betingelse
myset = {x for x in myset if x != 2}
myset = {x for x in myset if x != 42}

# difference/- fjerner elementer
# hvis de finnes
myset = myset.difference([4, 6])
myset = myset - {5, 7, 9}

print(myset) # {1, 3}
print(alias) # {1, 2, 3, 4, 5}
Beholde elementer (intersection/&)
# Behold kun elementer som er
# i begge mengdene.
# destruktivt (ved mutasjon)
myset = {1, 2, 3, 4, 5}
alias = myset

a = [3, 4, 5, 6, 7]
myset.intersection_update(a)
# myset er nå {3, 4, 5}

myset &= {1, 3, 5, 7, 9}

print(myset) # {3, 5}
print(alias) # {3, 5}

# Behold kun elementer som er
# i begge mengdene.
# ikke-destruktivt (nytt objekt)
myset = {1, 2, 3, 4, 5}
alias = myset

a = [3, 4, 5, 6, 7]
myset = myset.intersection(a)
# myset er nå {3, 4, 5}

myset = myset & {1, 3, 5, 7, 9}

print(myset) # {3, 5}
print(alias) # {1, 2, 3, 4, 5}
Symetrisk forskjell (symmetric_difference/^)
# Behold kun elementer som er
# i akkurat én av mengdene
# destruktivt (ved mutasjon)
myset = {1, 2, 3, 4, 5}
alias = myset

a = [3, 4, 5, 6, 7]
myset.symmetric_difference_update(a)
# myset er nå {1, 2, 6, 7}

myset ^= {1, 3, 5, 7, 9}

print(myset) # {2, 3, 5, 6, 9}
print(alias) # {2, 3, 5, 6, 9}

# Behold kun elementer som er
# i begge mengdene.
# ikke-destruktivt (nytt objekt)
myset = {1, 2, 3, 4, 5}
alias = myset

a = [3, 4, 5, 6, 7]
myset = myset.symmetric_difference(a)
# myset er nå {1, 2, 6, 7}

myset = myset ^ {1, 3, 5, 7, 9}

print(myset) # {2, 3, 5, 6, 9}
print(alias) # {1, 2, 3, 4, 5}
Frozenset

Det finnes en type mengder som ikke kan muteres, kalt frozenset. De fungerer nøyaktig som set, men operasjonene som ville mutert set vil nå enten opprette et nytt objekt eller det vil krasje.

Fordelen med frozenset er at de kan brukes som nøkler i oppslagsverk, eller de kan legges som elementer i andre mengder (siden de ikke kan muteres, tilfredstiller de kravet).

# Opprett et frozenset
myset = frozenset({2, 3, 5})
alias = myset

myset |= {42, 43} # muterer ikke, men oppretter nytt objekt

print(myset) # {2, 3, 5, 42, 43}
print(alias) # {2, 3, 5}

myset.discard(2) # Krasjer

  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. ↩︎