[Tutor PyCZ] razeni polozek ve slovniku

[Petr Prikryl]

> > [...] Pokud mám ve slovníku N položek, pak se
> > konkrétní položka vyhledá na výrazně méně, než N
> > kroků. U seznamu potřebuji v nejhorším případě
> > právě N kroků a průměrně (statisticky) N/2 kroků.
>
> mohu tomu rozumet tak, ze pri vyzadani si
> padesate polozky ze seznamu jsou projety vsechny
> polozky od 0 do 50 a ta padesata je vracena

Pokud nevím, kde ta položka v seznamu leží, musím
ji vyhledávat. Pokud je úplně na konci (nebo pokud
tam vůbec není) a vyhledávám od začátku, pak musím
prohledat všech 50 položek. Pak je odpověď ano.
Pythonovský seznam se ale také chová jako pole.
Pokud znám index položky, můžu na ni skočit přímo.
Memusím nic vyhledávat.

> kdezto vyzadam li si polozku s klicem 'pepa' a
> hodnotou 'zdepa' (jez je take padesata) je pouzit
> nejaky efektivnejsi algoritmus nez je proste
> projeti celeho slovniku od prvni do padesate
> polozky a tento algoritmus vyzaduje nejake
> informace (neco jako index u mysql) ktere
> vznikaji pri plneni slovniku pricemz pri jeho ev
> sortovani by se musely znova
> vytvaret...preindexovat?

Přibližně ano. U slovníku musím vyhledávat i v
případě, když vím, že tam ta položka je. Nedá se
na ni skočit přímo, jako v poli (seznamu). Ale
vyhledávání je výrazně výkonnější. Používají se
techniky, které nás velmi rychle dostrkají k
samotné položce a případné dohledávání synonym je
velmi rychlé. Podrobnější vysvětlení lze nalézt v
http://www.skil.cz/python/cztuttrn.html#Pdata_hash

> > Můžu ale vytvořit (nebo si u speciálních variant
> > slovníků vnitřně udržovat) pomocné datové
> > struktury, které budou zachycovat pořadí položek
> > podle mých představ.
> 
> jak by mohla vypadatat takova pomocna datova
> struktura?

Různě. Podle požadavků. Může to být například
seznam klíčů v určitém pořadí nebo to může být
přímo seznam odkazů na hodnotové objekty, které
jsou zařazené do slovníku. Když už potřebuji
takovou specialitu, je lepší to ušít na míru a
nesnažit se to řešit příliš obecně. Nebo je lepší
použít něco hotového. Nebo přehodnotit svůj
postoj, zda to vůbec potřebuji. Optimalizovat by
se mělo až v případě, kdy je neoptimalizovaná
varianta moc pomalá.

Za pomocnou strukturu vždy nějak zaplatím.
Například při udržování nějakého pořadí položek ve
slovníku bude operace vkládání vždy složitější,
než když žádné dodatečné pořadí nepotřebuji.

> > Průchod slovníkem seřazený podle hodnot prakticky
> > spočívá v tom, že vytvoříme seznam položek a ten
> > seřadíme podle hodnotové části. (V příkladu neuvedeno.)
> 
> cili pri predpokladu ze bych se slovnikem
> pracoval pouze timto zpusobem je lepsi pouzit
> rovnou pole?

To nelze takhle říct. Záleží to na řešeném
problému.

> s assoc. polema rad pracuji v php ale shledavam
> ze se od slovniku v pythonu dost lisi. assoc.
> pole jsem pouzival predevsim proto, ze bylo mozne
> aby jeden zaznam nesl dve uzitecne informace
> (typu string), zatimco v pripade bezneho pole je
> nutne pouzit kvuli dvoum informacim vnorene pole.

Pole nepatří mezi zabudované struktury Pythonu.
Vícerozměrné už vůbec ne. 

Slovník je něco podobného, jako asociativní pole.
V Pythonu mi nic nebrání, aby na místě hodnotové
části byl jakýkoliv objekt. Můžu tam tedy vložit
dvojici, seznam, jiný slovník, funkci, libovolný
objekt, atd. Příklad:

soubor b.py
=================================================
# -*- coding: cp1250 -*-

def funkce(x):
    print x
    
class C(object):
    def __init__(self, identifikace):
        self.identifikace = identifikace
    def metoda(self, argument):
        print self.identifikace, argument
        
# telo skriptu
c1 = C('objekt1')
c2 = C(888)
d = { 'klic1': c1, 
      'k2':    c2,
      333:     c1.metoda,
      'dvojice': (c1, 15),
      'seznam': [1, 2, 3, 'xxx', ('aaa', 'bbb')],
    }  
      
lst = [1, 'abc', (5, 6), d]
d['lst'] = lst

print '-' * 70
print u'slovník'
print type(d)
print d

print '-' * 70
print u'seznam'
print type(lst)
print lst

print '-' * 70
print u'klíče slovníku'
for k in d:
    print k 

print '-' * 70
print u'hodnoty slovníku'
for k in d:
    print d[k]
 
print '-' * 70
print u'Ze slovníku získáme uložený seznam a z něj dvojici uloženou na konci.'
L = d['seznam']
print L
dvojice = L[-1]
print dvojice
print dvojice[0], dvojice[1]
print L[-1][0], L[-1][1]
print d['seznam'][-1][0], d['seznam'][-1][1]

print '-' * 70
print u'Ze slovníku si zpřístupníme uložený objekt a zavoláme jeho metodu.'
cx = d['klic1']
cx.metoda(u'můj argument')
d['klic1'].metoda(u'můj argument 2')
d['k2'].metoda(u'můj argument 3')

print '-' * 70
print u'Pod klíčem 333 máme dokonce uložen odkaz na metodu konkrétního objektu.'
d[333](u'můj argument 333')
=================================================

Když spustíme python b.py >b.out, najdeme v
souboru b.out následující. Ponechávám bez
komentáře. Ptejte se na nejasnosti.

----------------------------------------------------------------------
slovník
<type 'dict'>
{'seznam': [1, 2, 3, 'xxx', ('aaa', 'bbb')], 333: <bound method C.metoda of <__main__.C object at 0x00922D90>>, 'klic1': <__main__.C object at 0x00922D90>, 'k2': <__main__.C object at 0x00922E50>, 'lst': [1, 'abc', (5, 6), {...}], 'dvojice': (<__main__.C object at 0x00922D90>, 15)}
----------------------------------------------------------------------
seznam
<type 'list'>
[1, 'abc', (5, 6), {'seznam': [1, 2, 3, 'xxx', ('aaa', 'bbb')], 333: <bound method C.metoda of <__main__.C object at 0x00922D90>>, 'klic1': <__main__.C object at 0x00922D90>, 'k2': <__main__.C object at 0x00922E50>, 'lst': [...], 'dvojice': (<__main__.C object at 0x00922D90>, 15)}]
----------------------------------------------------------------------
klíče slovníku
seznam
333
klic1
k2
lst
dvojice
----------------------------------------------------------------------
hodnoty slovníku
[1, 2, 3, 'xxx', ('aaa', 'bbb')]
<bound method C.metoda of <__main__.C object at 0x00922D90>>
<__main__.C object at 0x00922D90>
<__main__.C object at 0x00922E50>
[1, 'abc', (5, 6), {'seznam': [1, 2, 3, 'xxx', ('aaa', 'bbb')], 333: <bound method C.metoda of <__main__.C object at 0x00922D90>>, 'klic1': <__main__.C object at 0x00922D90>, 'k2': <__main__.C object at 0x00922E50>, 'lst': [...], 'dvojice': (<__main__.C object at 0x00922D90>, 15)}]
(<__main__.C object at 0x00922D90>, 15)
----------------------------------------------------------------------
Ze slovníku získáme uložený seznam a z něj dvojici uloženou na konci.
[1, 2, 3, 'xxx', ('aaa', 'bbb')]
('aaa', 'bbb')
aaa bbb
aaa bbb
aaa bbb
----------------------------------------------------------------------
Ze slovníku si zpřístupníme uložený objekt a zavoláme jeho metodu.
objekt1 můj argument
objekt1 můj argument 2
888 můj argument 3
----------------------------------------------------------------------
Pod klíčem 333 máme dokonce uložen odkaz na metodu konkrétního objektu.
objekt1 můj argument 333


pepr