Algoritmusok Python nyelven

3. Előadás, egyszerű adattípusok, adatszerkezetek folytatás.

2020. február 7.

Technikai információk

Diák elérhetősége:

damasdigabor.web.elte.hu/teaching

Óra kezdés: 14:00

Python

• Indentálás, nem kell pontosvessző
• Dinamikus típusok
• Értékadásnál először a jobb oldal kiértékelődik, majd a bal oldalon lévő nevet hozzárendeljük az eredményhez.
• Mutable vs immutable

tuple

• a tuple egy immutable sorozat

t = ()  # empty tuple
print(type(t), len(t))

t = ([1, 2, 3], "foo")
type(t), len(t)

t

indexelés azonos a listákkal

t[1], t[-1]

a tuple immutable referenciákat tartalmaz, de, a benne lévő objektum lehet mutable

t = ([1, 2, 3], "foo")
#t[0]= "bar"  # this raises a TypeError

for e in t:
    print(id(e))
    
print("\nMegváltoztatjuk t[0] egy elemét\n")
t[0][1] = 11

for e in t:
    print(id(e))

print("\n", t)

Mire jó a tuple, ha kevesebbet tud mint a lista?

• gyorsabb
• segít a biztonságos kód írásban.
• néha szükség van arra, hogy egy objektum immutable legyen. Pl a most következő dictionaryk kulcsai csak imutable objektumok lehetnek

Mit kapunk?

print([1+2,1+2])
print([1+2])
print("[1+2,1+2]")
print("[1+2]")
print((1+2,1+2))
print((1+2))

dictionary

• beépített szótár típus (map)
• kulcsokat képez le értékekre

(Valójáőban ez sokkal inkább hasonlít a matematikai függvény fogalomhoz, mint a python függvényei.)

d = {}  # üres szótár, ekvivalens: d = dict()
d["apple"] = 12
d["plum"] = 2
d

másik megadás

d = {"apple": 12, "plum": 2}
d

muveletek={'+':lambda x,y:x+y,'-':lambda x,y:x-y,'*':lambda x,y:x*y,'/':lambda x,y:x/y }
def muvelet(a,b,operator):
    return muveletek[operator](a,b)

muvelet(3,4,"/")

kulcs törlése

del d["apple"]
d

dictionary bejárása

• a kulcsok és az értékek külön és együtt is bejárhatóak
• kulcsok iterálása

d = {"apple": 12, "plum": 2}
for key in d.keys():
    print(key, d[key])

értékek iterálása

for value in d.values():
    print(value)

közös iterálás

for key, value in d.items():
    print(key, value)

Mi történik a háttérben?

• a háttérben egy hash table jön létre
  • ennek az a lényege, hogy minden kulcshoz hozzárendelünk egy hash értéket, ami egyenlő objektumoknál azonos és az objektumok helyett a hash értéket hasonlítjuk össze. Így gyorsabb lesz a rendszer, mert egy olyan adatstruktúrát alkalmazhatunk, amin ritkán kell változtatni.
  • ezért a kulcsok nem lehetnek és nem tartalmazhatnak mutable objektumokat
  • de lehetnek különböző tipusú kulcsok

d = {}
d[1] = "a"  # numeric types are immutable
d[3+2j] = "b"
d["c"] = 1.0
d

hash(1), hash(1000), hash((100,100,1))

#hash([21,1])

• a tuple típus immutable

d[("apple", 1)] = -2
d

• de a list mutable

# d[["apple", 1]] = 12  # raises TypeError

Q. Lehetnek-e ezek dictionary kulcsok?

key1 = (2, (3, 4))
key2 = (2, [], (3, 4))

d = {}
#d[key1] = 1
#d[key2] = 2
d

Függvények újra. args és kwargs

• mind a pozíciós és a kulcsszavas argumentumok is összegyűjthetőek a * és ** operátorokkal
• a pozíciós argumentumok tuplebe kerülnek

def arbitrary_positional_f(*args):
    print(type(args))
    for arg in args:
        print(arg)
        
arbitrary_positional_f(1, 2, -1)
# arbitrary_positional_f(1, 2, arg=-1)  # raises TypeError

• kulcsszavas argumentumok egy dictionarybe kerülnek

def arbitrary_keyword_f(**kwargs):
    print(type(kwargs))
    for argname, value in kwargs.items():
        print(argname, value)
        
arbitrary_keyword_f(arg1=1, arg2=12)
# arbitrary_keyword_f(12, arg=12)  # TypeError

• általában mindkettőt begyűjtjük

def arbitrary_arg_f(*args, **kwargs):
    if args:
        print("Pozíció szerinti")
        for arg in args:
            print(arg)
    else:
        print("Nincs pozíció szerinti")
    if kwargs:
        print("Kulcsszavas")
        for argname, value in kwargs.items():
            print(argname, value)
    else:
        print("Nincs kulcsszavas")
        
arbitrary_arg_f()
arbitrary_arg_f(12, -2, param1="foo")

def arbitrary_arg_f(pos_arg,def_arg="default",*args, **kwargs):
    print(pos_arg,def_arg)
    if args:
        print("Pozíció szerinti")
        for arg in args:
            print(arg)
    else:
        print("Nincs pozíció szerinti")
    if kwargs:
        print("Kulcsszavas")
        for argname, value in kwargs.items():
            print(argname, value)
    else:
        print("Nincs kulcsszavas")
    print("\n")        
arbitrary_arg_f(1,2)
arbitrary_arg_f(12, param1="foo")

set

• egyedi, hash-elhető elemek (így ebben sem nem lehet mutable)
• alapvető halmazműveletek használhatóak

s = set()
s.add(2)
s.add(3)
s.add(2)
s

s = {2, 3, 2}  #d={'a':2}
type(s), s

#s = {[1,2]}

deleting elements

s.add(2)
s.remove(2)
# s.remove(2)  #  KeyErrort kapunk mert már töröltük
s.discard(2)  # töröl, ha benne van, különben semmit sem csinál

set operációk

• két féle jelölés van rájuk
  1. függvények
  2. operátorok

s1 = {1, 2, 3, 4, 5}
s2 = {2, 5, 6, 7}

s1 & s2  # s1.intersection(s2) vagy s2.intersection(s1)

s1 | s2  # s1.union(s2) vagy s2.union(s1)

s1 - s2, s2 - s1  # s1.difference(s2), s2.difference(s1)

• ezek az operációk egy új set-tel térnek vissza.

s3 = s1 & s2
type(s3), id(s3) == id(s1), id(s3) == id(s2)

issubset és issuperset

s1 < s2, s1.issubset(s2)

s1

{1, 2} < s1

s1.issuperset({1, 6})

hasznos tulajdonságok

• egy set létrehozásával megszüntethetjük a duplikációkat egy listában

l = [1, 2, 3, -1, 1, 2, 1, 0]
uniq = set(l)
uniq

• set-ek és dictionary-k O(1) időben keresnek. (gyorsak)
• listák O(n) időben keresnek.

"-".join(["Ez","egy","módszer","stringek","összefűzésére"])

import random
random.choice(["egy","két","há"])  # egy lista véletlenszerű eleme

letters = "abcdef"
word_len = [1, 2, 3, 4, 5]
N = 10000
samples = []

for i in range(N):
    word = []
    for j in range(random.choice(word_len)):
        word.append(random.choice(letters))
    samples.append("".join(word))
    
samples = list(samples)

word = []
for j in range(random.choice(word_len)):
    word.append(random.choice(letters))
word = "".join(word)
print(word)
word in samples

list lookup

%%timeit

word = []
for j in range(random.choice(word_len)):
    word.append(random.choice(letters))
word = "".join(word)
word in samples

set lookup

samples_set = set(samples)
len(samples_set), len(samples)

%%timeit

word = []
for j in range(random.choice(word_len)):
    word.append(random.choice(letters))
word = "".join(word)
word in samples_set

Stringek

• A stringek immutable sorozatok, melyek Unicode karaterekből állnak

pelda="ez egy string"
single = 'ab\'c'
double = "ab\"c"
multiline = """
sdfajfklasj;
sdfsdfs
sdfsdf
"""
single == double

• mivel immutable, nem lehet megváltoztatni!!

s = "abcdefg"
s[3:7]
# s[1] = "c"  # TypeError

• minden string operáció új függvényt hoz létre

print(id(s))
s = s + "def"
id(s), s

• a stringekre is elérhető a legtöbb függvény, amit a listák tudnak.
  • pl: indexelés

s = "abcdefghijkl"
s[::2], "x" in s,

s = "ábc"
print(type(s))

with open("file.txt", "w") as f:
    f.write(s)
    f.write("\n")

with open("file.txt") as f:
    text = f.read().strip()
    
print(text)
type(text)

String operációk

• rengeteg függvény elérhető

"abC".upper(), "ABC".lower(), "abc".title()

s = "\tabc  \n"
print("<START>" + s + "<STOP>")

s.strip()

s.rstrip()

s.lstrip()

"abca".strip("a")

Mivel minden függvény visszatér egy új stringgel, egymás után fűzhetőek.

" abcd abc".strip().rstrip("c").lstrip("ab")

Eldöntendő kérédsek

"abc".startswith("ab"), "abc".endswith("cd")

"abc".istitle(), "Abc".istitle()

"  \t\n".isspace()

"989".isdigit(), "1.5".isdigit()

split és join

s = "the quick brown fox jumps over the lazy dog"
words = s.split()
words

s = "R.E.M."
s.split(".")

"-".join(words)

Példa: Egy wikipedia oldal szó frekvenciája

 # Ez csak akkor működik, ha a wikipedia csomag már telepítve van. Később részletesebben lesz szó arról,
 # hogy hogyan lehet telepíteni. Alapvetően a pip install wikipedia parancsot
 # kell kiadni windowson az anaconda promptban, linuxon pedig a terminálban.  
    
 import wikipedia
 article = wikipedia.page("Hungary")

text=article.content

text

words = text.split()
len(words), len(set(words))

word_freq = {}
for word in words:
    if word not in word_freq:
        word_freq[word] = 1
    else:
        word_freq[word] += 1

for word, freq in sorted(word_freq.items(), key=lambda x: -x[1])[:40]:
    print(word, freq)

List comprehension

• Rövidités a foor loop leggyakoribb használatára, hogy gyorsan tudjunk listákat létrehozni

l = []
for i in range(10):
    l.append(2*i+1)
l

Egy soros megfelelő:

l = [2*i+1 for i in range(10)]
l

Az általános formula

[<expression> for <element> in <sequence>]

even = [n*n for n in range(20) if n % 2 == 0]
even

Ami azzal ekvivalens, hogy

even = []
for n in range(20):
    if n % 2 == 0:
        even.append(n)
even

egy feltételt is megadhatunk, hogy szűrjük az elemeket:

[<expression> for <element> in <sequence> if <condition>]

• mivel itt szűrésre használjuk az if részt, nincs else ág

• viszont a kezdeti kifejezésben használhatunk esetszétválasztást:

l = [1, 0, -2, 3, -1, -5, 0]

signum_l = [int(n / abs(n)) if n != 0 else 0 for n in l]
signum_l

Ez persze nem a list comprehension extrája, hanem csak annyi, hogy ez is egy értelmes kifejezés:

n = -3.2
int(n / abs(n)) if n != 0 else 0

Több listán is végigfuthatunk:

l1 = [1, 2, 3]
l2 = [4, 5, 6]

[(i, j) for i in l1 for j in l2]

[(i, j) for j in l2 for i in l1]

Egymásba is ágyazhatjuk őket:

matrix = [
    [1, 2, 3],
    [5, 6, 7]
]

[[e*e for e in row] for row in matrix]

Set és dictionary comprehension

Minden analóg módon működik:

fruit_list = ["apple", "plum", "apple", "pear"]

fruits = {fruit.title() for fruit in fruit_list}

type(fruits), len(fruits), fruits

word_list = ["apple", "plum", "pear", "apple", "apple"]
word_length = {word: len(word) for word in word_list}
type(word_length), len(word_length), word_length

word_list = ["apple", "plum", "pear", "avocado"]
first_letters = {word[0]: word for word in word_list}
first_letters

for i in word_length.keys():
    if len(i)%2==0:
        print(i)
        #del word_length[i]
    

{a:word_length[a] for a in word_length.keys() if len(a)%2==1}

Mutable alapértelmezett argumentumok

• csak óvatosan!!

def insert_value(value, l=[]):
    l.append(value)
    print(l)
    
l1 = []
insert_value(12, l1)
l2 = []
insert_value(14, l2)

insert_value(-1)

insert_value(-3)

• legjobb ha messzire elkerüljük

Egy lehetséges megoldás:

def insert_value(value, l=None):
    if l is None:
        l = []
    l.append(value)
    return l

l = insert_value(2)
l

insert_value(12)

Lambda kifejezések

• névtelen függvények
• lehet paramétere
• egy kifejezést számít ki

l = [-1, 0, -10, 2, 3]

Rendezzünk például abszolút érték szerint. A beépített sorted függvény nem elég.

De megadhatjuk, hogy milyen key kulcsot használjon:

for e in sorted(l, key=lambda x: abs(x)):
    print(e)

Bármilyen függvényt használhatunk

for e in sorted(l, key=abs):
    print(e)

(lambda x,y: 1/(x**3+y+1))(1,2)