Mengder

Se også offisiell dokumentasjon for set.

Enkelt eksempel

En mengde (engelsk: set) er en datastruktur som kan holde på mange verdier (i likhet med lister, tupler og oppslagsverk). Det er noen forskjeller:

Med en mengde kan man i hovedsak gjøre fire ting:

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

# Legg til en verdi i mengden (muterer 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 (muterer 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)
# Legg merke til at mengden kun inneholder hvert element én gang
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 rekkefølge. Når du går igjennom elementene i en mengde med en for-løkke eller du printer ut mengden vil det selvfølgelig være en eller annen rekkefølge, men: du kan ikke gjøre noen antakelser om hvilken rekkefølge dette er. Den kan variere fra maskin til maskin og Python-versjon til Python-versjon og fra kjøring til kjøring.

To mengder er ansett for å være like dersom de inneholder de samme elementene, uavhengig av hvilken rekkefølge elementene ble lagt til i mengdene.

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