Implementacija s tabelo logičnih vrednosti

Denimo, da se omejimo na množice, ki vsebujejo kvečjemu cela števila med 0 in vključno Z − 1, pri čemer je Z neko ne preveliko celo število. Takšno množico lahko predstavimo s tabelo z Z elementi logičnega tipa. Če število i pripada množici, ima element tabele na indeksu i vrednost True, sicer pa False. Na primer če vzamemo Z = 10, potem množico {0, 2, 3, 7} predstavimo s to tabelo:

[True, False, True, True, False, False, False, True, False, False]

Vaja

Tovrstna predstavitev množice je časovno izjemno učinkovita. Prisotnost števila x ∈ {0, 1, ... , Z − 1} preverimo tako, da preverimo vrednost elementa v tabeli na indeksu x. Število x v množico dodamo tako, da element tabele na indeksu x postavimo na True, pri odstranjevanju pa pripadajoči element tabele postavimo na False. Časovna zahtevnost vseh treh operacij znaša O(1), saj je čas, ki ga potrebujejo operacije, povsem neodvisen od števila elementov v množici, pa tudi od velikosti tabele. Oglejmo si modul mnozicaTabelaLogicnih.py (glej kodo).

V razmislek


 
1
# Implementacija množice s tabelo logičnih
2
# vrednosti
3
​
4
# Vrne prazno množico, ki lahko vsebuje kvečjemu
5
# števila od 0 do vključno Z - 1.
6
def Ustvari(Z):
7
  # Na naslednji način najlažje ustvarimo tabelo,
8
  # sestavljeno iz Z elementov False.
9
  return [False] * Z
10
​
11
# Vrne True, če je podani element prisoten v
12
# podani množici, sicer pa vrne False.
13
def JePrisoten(mnozica, element):
14
  return mnozica[element]
15
​
16
# Doda podani element v podano množico.
17
def Dodaj(mnozica, element):
18
  mnozica[element] = True
19
​
20
# Odstrani podani element iz podane množice.
21
def Odstrani(mnozica, element):
22
  mnozica[element] = False
23
​
24
# Vrne niz, ki predstavlja podano množico;
25
# npr. '{1, 2, 3}' za množico, ki vsebuje
26
# elemente 1, 2 in 3.
27
def NizElementov(mnozica):
28
  # Elementi množice so sestavljeni iz indeksov
29
  # vseh elementov z vrednostjo True.
30
  izpis = []
31
  for indeks in range(len(mnozica)):
32
    if mnozica[indeks]:
33
      izpis.append(str(indeks))
34
  # Združimo nize iz tabele in niz izpišemo.
35
  return ('{' + ', '.join(izpis) + '}')
36
​
37
def main():
38
  razpon = 20
39
  s = 'Množica lahko vsebuje števila od 0 do '
40
  s += str(razpon - 1) + '.'
41
  print(s)
42
  t = [5, 2, 5, 5, 1, 6, 8, 3, 2, 3]
43
  print('Ustvarjam prazno množico m ...')
44
  m = Ustvari(razpon)
45
  for element in t:
46
    print('Dodajam element: ' + str(element))
47
    Dodaj(m, element)
48
​
49
  print('Množica m: ' + NizElementov(m))
50
  print('JePrisoten(m, 3): ' +
51
        str(JePrisoten(m, 3)))
52
  print('JePrisoten(m, 5): ' +
53
        str(JePrisoten(m, 5)))
54
  print('JePrisoten(m, 6): ' +
55
        str(JePrisoten(m, 6)))
56
  print('JePrisoten(m, 7): ' +
57
        str(JePrisoten(m, 7)))
58
​
59
  print('Odstranjujem element: 3')
60
  Odstrani(m, 3)
61
  print('JePrisoten(m, 3): ' +
62
        str(JePrisoten(m, 3)))
63
  print('Množica m: ' + NizElementov(m))
64
​
65
# Spomnimo se: s spodnjima vrsticama dosežemo,
66
# da lahko modul uporabljamo tudi kot samostojen
67
# program.
68
if __name__ == '__main__':
69
  main()

Izvedi Počisti