Hlavní navigace

Squeak: návrat do budoucnosti (12)

Pavel Křivánek 27. 4. 2004

Dnes máme na mušce pouze jedno téma, ovšem o to důležitější - kolekce. Prostředek, který dodává Smalltalku eleganci funkcionálních jazyků při zachování jeho imperativního objektového charakteru.

Kolekce jsou jedním z nejpodstatnějších prvků Smalltalku. Jedná se o objekty určené k uchovávání jiných objektů. Implementovány jsou za pomocí celé řady tříd, z nichž všechny mají jako společného předka třídu Collection.

Collection
  Bag
    IdentityBag
  CharacterSet
  SequenceableCollection
    ArrayedCollection
      Array
      ByteArray, WordArray, IntegerArray, FloatArray
      RunArray
      String, Symbol, Text
    Heap
    Interval
    LinkedList
    MappedCollection
    OrderedCollection
      SortedCollection
  Set
     IdentitySet
     Dictionary
      IdentityDictionary
        SystemDictionary

Tento seznam není úplný a obsahuje pouze nedůležitější z nich. Kolekce dělíme podle toho, zda jsou indexované, či nikoliv, zda se používá celočíselné (implicitní) indexování, či klíče, zda mají omezenou množinu hodnot, zda mají proměnnou velikost a jestli umožňují řazení. Některé třídy (např. Collection, SequenceableCo­llection) jsou pouze abstraktní a neumožňují vytváření svých instancí.

Set, Bag, CharacterSet

Množiny (Set), multimnožiny (Bag) a množiny znaků (CharacterSet) jsou neindexované neklíčované kolekce s proměnnou velikostí. Multimnožiny mohou na rozdíl od množin obsahovat stejné prvky několikrát.

#(1 2 3 3 3 4 5) asSet   -> a Set(1 2 3 4 5)
#(1 2 3 3 3 4 5) as: Bag -> a Bag(1 2 3 3 3 4 5)

CharacterSet je množina optimalizovaná pro udržování znaků

'abbccd' asCharacterSet -> a CharacterSet($a $b $c $d) 

Nejdůležitější metody těchto tříd jsou add:, remove:,includes: a union:

Slovníky (Dictionary)

Slovníky jsou velmi užitečné kolekce, které tvoří množina asociací klíč/hodnota. Jako klíče mohou sloužit obecně libovolné objekty, velmi často se používají symboly.

| dict preklad |
dict := Dictionary new.
dict at: 'set' put: 'mnozina'.
dict at: 'bag' put: 'multimnozina'.
dict at: 'dictionary' put: 'slovnik'.
preklad := dict at: 'bag'.

Při nenalezení klíče je vyvolána výjimka. Tomu lze předejít tím, že slovníku dodáme náhradní blok (at:ifAbsent:).

preklad := dict at: 'array' ifAbsent: [ 'nezname slovo' ]. 

Při vkládání hodnoty na již existující klíč je stará hodnota nahrazena novou.

Identity kolekce

Kolekce mohou pro porovnávání svých prvků používat binární zprávu = (rovnost porovnávající obsah objektů) nebo zprávu == (identita porovnávající pouze totožnost objektů). Porovnávání pomocí identity objektů je obecně podstatně rychlejší.

Jedná se o třídy IdentityDicti­oanary, IdentitySet,I­dentityBag apod. Standardní implementace rovnosti dvou objektů je řešena pomocí identity.

Systémový slovník

Systémový slovník je speciální verze IdentityDictionary hrající ve Smalltalku stěžejní úlohu. Má jednu globální instanci jménem Smalltalk, jejímž hlavním úkolem je uchovávat reference na globální objekty.

Objekt Smalltalk je jedním z mála objektů, o němž ví virtuální stroj. V okamžiku, kdy daný identifikátor není nalezen na lokální úrovni (ve třídě, ve sdílených slovnících), je vyhledán právě v tomto slovníku. To je případ identifikátorů tříd, několika globálních objektů (Display, Processor…) a samozřejmě i samotného objektu Smalltalk.

Vytvoření globální proměnné pak vypadá tak, že standardním způsobem do slovníku Smalltalk přidáte asociaci. Jako klíče se používají zásadně symboly. Vložený symbol je pak použitelný jako libovolný jiný identifikátor (není třeba k němu přistupovat přes příkaz Smalltalk at:)

Smalltalk at: #MujGlobalniObjekt put: 'Ja jsem globalne pristupny objekt'. 

Slovník Smalltalk má standardní chování slovníku. Krom toho ale také implementuje celou řadu metod sloužících pro provoz systému. Naleznete zde například metody pro správu paměti, ukládání image, správu tříd, ořezávání image, zpřístupňuje informace o hostitelském systému apod.

Pole

Pole jsou celočíselně indexované kolekce s konstantní velikostí. Není proto možné do nich přidávat prvky prostřednictvím metody add:. Jejich použití je optimalizováno pomocí primitivních metod, proto jsou velmi efektivní.

Jedná se například o třídy ByteArray, WordArray, IntegerArray, FloatArray. Samotná třída Array pak slouží k ukládání obecných objektů.

Zajímavá je třída RunArray, která je optimalizovaná pro ukládání sekvence objektů, kde za sebou často následují stejné prvky.

RunArray newFrom: #(1 2 2 3 4 5 5 5 5 5 6 7)
  -> a RunArray runs: #(1 2 1 1 5 1 1)
                values: #(1 2 3 4 5 6 7)

Řetězce, symboly

O řetězcích a symbolech již byla řeč. Množina metod pro práci s řetězci je skutečně velmi bohatá. Od všemožných vyhledávání a porovnávání přes různé obousměrné konverze (čísla, HTML atd.) až po celou řadu úprav a změn formátování.

Je na místě upozornit na některé výkonnostní aspekty používání symbolů a řetězců. Symboly se porovnávají výrazně rychleji. Nicméně se v žádném případě nesnažte zrychlit porovnávání řetězců jejich převodem na symboly. Následující řádky vám jistě jasně ukáží důvod. Časy jsou v milisekundách a platí pro 1000000 opakování.

[ #symbol1 == #symbol2 ] timeToRun -> 114
[ 'string1' = 'string2' ] timeToRun -> 665
[ 'string1' == 'string2' asSymbol ] timeToRun -> 2736
[ 'string1' asSymbol == 'string2' asSymbol ] timeToRun  -> 5213 

OrderedCollectin, SortedCollection

OrderedCollections jsou indexované kolekce s proměnnou velikostí. Řadí se k těm nejpoužívanějším. Prvky se do nich přidávají především pomocí metody add: či addAll:, vkládající celou kolekci prvků.

V OrderedCollection jsou prvky uloženy podle pořadí, v jakém byly do kolekce vloženy. Naproti tomu SortedCollection svůj obsah dokáže řadit.

#( 5 9 4 3 8 7 2 ) asSortedCollection
  -> a SortedCollection(2 3 4 5 7 8 9)

| collection |
collection := SortedCollection sortBlock: [:x :y | x odd ].
collection addAll: #( 5 9 4 3 8 7 2 ); reSort
  -> a SortedCollection(5 9 7 3 4 8 2) 

LinkedList

LinkedList od svých prvků vyžaduje, aby rozuměly zprávám nextLink a nextLink:, tedy podporovaly rozhraní třídy Link. Tyto metody ve skutečnosti nejsou nic jiného než obyčejné přistupující metody instanční proměnné nextLink.

V takovém případě poskytuje poměrně efektivní implementaci spojitého seznamu s metodami addFirst:, addLast:, first, last, isEmpty, removeFirst apod.

[ | list |
list := LinkedList new.
1000000 timesRepeat: [ list add: Link new ].
] timeToRun -> 1292

[ | list |
list := OrderedCollection new.
1000000 timesRepeat: [ list add: Link new ].
] timeToRun -> 5153

Další kolekce

Krom těchto základních obsahuje Smalltalk ještě celou řadu dalších nějakým způsobem specializovaných kolekcí. Mimo haldy (Heap, řazená struktura, která je při dodržení několika pravidel efektivnější než SortedCollection) stojí za pozornost ještě kolekce MappedCollection

MappedCollection collection: #(7 8 9) map: #(3 2 1)
  -> a MappedCollection(9 8 7) 

a Interval.

OrderedCollection new addAll: (1 to: 20 by: 2); yourself
  -> an OrderedCollection(1 3 5 7 9 11 13 15 17 19) 

Vytváření kolekcí

Prázdné kolekce se vytvářejí běžně konstruktorem new nebo konstruktory new: či ofSize:, které jako parametr přijímají počáteční velikost.

Set new.
OrderedCollection ofSize: 100.

Často využívané jsou konstruktory s definicí prvků (with:, with:with:… withAll:)

Set with: 'red' with: 'green' with: 'blue'.
SortedCollection withAll: #(6 8 4 9 2 7 6 1 3 8).

Některé kolekce mají samozřejmě konstruktory šité přímo na míru.

Častá je vzájemná konverze kolekcí.

#( 3 2 1 ) asSortedCollection.
#( 3 2 1 ) as: SortedCollection.

Počet prvků kolekce zjistí metoda size.

Iterace nad kolekcemi

Iterování nad kolekcemi je velmi časté a Smalltalk podporuje celou řadu různých variant této operace.

do:, reverseDo:

Nejjednodušší průchod všemi prvky kolekce. U uspořádaných kolekcí metoda reverseDo: zpracuje prvky v opačném pořadí.

#( 1 2 3 8 9 )
   do: [:item | Transcript show: item ]

with:do:

Zpracování dvou sekvenčních kolekcí současně. Kolekce musí mít stejnou velikost.

| sum |
sum := 0.
#(1 2 3 4 5) with: #(6 5 8 7 5) do:
[:n1 :n2 | sum := sum + n1 + n2 ].

collect:, with:collect:

Přepis kolekce do nové kolekce stejné třídy. Metoda with:collect: zpracovává dvě kolekce současně.

#( 1 2 3 8 9 )
   collect: [: item | item + 42 ]
  ->  #(43 44 45 50 51)

detect:, atRandom

Nalezne první prvek, pro nějž vstupní blok vrací true. Zpráva atRandom vrátí náhodný prvek kolekce).

#( 1 3 4 )
   detect: [:item | item > 2 ]
  -> 3

select:, reject:, count:

Zpráva select: vytvoří novou kolekci obsahující prvky, pro něž vstupní blok vrací true. Metoda reject: je opakem select:. Zpráva count: zjistí počet vybíraných prvků

#( 1 3 4 )
   select: [:item | item > 2 ]
  -> #(3 4)

average, max, min, median, sum, range…

Celá řada matematických operací prováděných nad kolekcemi.

{1@1. 2@1. 1@5} sum
  -> 4@7

inject:into:

Vrací hodnotu vycházející z počáteční hodnoty a obsahu kolekce zpracované vstupním blokem. Jedná se o funkci typu „scan“.

#(1 2 3 4 5)  inject: 0 into: [:suma :cislo | suma + cislo].
  -> 15

#(1 2 3 4 5) inject: '' into: [:str :num | str, num asString].
  -> '12345'

"Fibonacciho posloupnost"
(3 to: 15)
  inject: (OrderedCollection with: 1 with: 1)
  into: [ :inj :n |
    inj addLast: ((inj at: n-2)+(inj at: n-1)); yourself ]. 

Poznámky

Při použití kolekcí se poměrně často lze setkat se zprávou yourself, která nevrací nic jiného než volaný objekt. Metody na přidávání prvků do kolekce totiž z dobrých důvodů vracejí vkládaný prvek, na což v zájmu zachování duševního zdraví není radno zapomínat.

mnozina := Set new add: 1; add: 2.
  -> 2
mnozina := Set new add: 1; add: 2; yourself.
  -> a Set(1 2)

V každém případě se snažte vyhnout konstrukcím, ve kterých budete měnit kolekci, přes niž právě iterujete.

Kolekce jsou mocným nástrojem a celá řada metod je v nich již implementována. Je nanejvýš doporučeníhodné se s nimi podrobněji seznámit, protože si tak programátor může ušetřit velmi mnoho zbytečné práce.

Našli jste v článku chybu?

20. 12. 2006 4:59

Teda... a o 2 roky později odkaz nefunguje, no je to možný? :'-)

30. 4. 2004 16:29

vj (neregistrovaný)

Ten clanek rozhodne neni mimo misu. LISP je jednim ze zakladnich korenu Smalltalku. Oba jazyky jsou si v mnoha ohledech velmi blizke a zmineny clanek lze bez problemu vztahnout i na Smalltalk.

Mirne desive jsou ovsem v ceskem prekladu brutalni chyby v i/y.



Měšec.cz: Zdravotní a sociální pojištění 2017: Připlatíte

Zdravotní a sociální pojištění 2017: Připlatíte

Podnikatel.cz: Babiše přesvědčila 89letá podnikatelka?!

Babiše přesvědčila 89letá podnikatelka?!

Vitalia.cz: Chtějí si léčit kvasinky. Lék je jen v Německu

Chtějí si léčit kvasinky. Lék je jen v Německu

Podnikatel.cz: Přehledná titulka, průvodci, responzivita

Přehledná titulka, průvodci, responzivita

DigiZone.cz: Recenze Prostřeno: cirkus postižených

Recenze Prostřeno: cirkus postižených

Lupa.cz: Teletext je „internetem hipsterů“

Teletext je „internetem hipsterů“

Lupa.cz: Insolvenční řízení kvůli cookies? Vítejte v ČR

Insolvenční řízení kvůli cookies? Vítejte v ČR

Podnikatel.cz: Podnikatelům dorazí varování od BSA

Podnikatelům dorazí varování od BSA

Podnikatel.cz: Chtějte údaje k dani z nemovitostí do mailu

Chtějte údaje k dani z nemovitostí do mailu

Vitalia.cz: Drahé i levné. Tyhle potraviny nosili na charitu

Drahé i levné. Tyhle potraviny nosili na charitu

120na80.cz: Na ucho teplý, nebo studený obklad?

Na ucho teplý, nebo studený obklad?

120na80.cz: Jak oddálit Alzheimera?

Jak oddálit Alzheimera?

Měšec.cz: Přejete si číslo účtu na přání?

Přejete si číslo účtu na přání?

Lupa.cz: Co se dá měřit přes Internet věcí

Co se dá měřit přes Internet věcí

Vitalia.cz: To není kašel! Správná diagnóza zachrání život

To není kašel! Správná diagnóza zachrání život

Vitalia.cz: Mondelez stahuje rizikovou čokoládu Milka

Mondelez stahuje rizikovou čokoládu Milka

Měšec.cz: Za palivo zaplatíte mobilem (TEST)

Za palivo zaplatíte mobilem (TEST)

Vitalia.cz: Láska na vozíku: Přitažliví jsme pro tzv. pečovatelky

Láska na vozíku: Přitažliví jsme pro tzv. pečovatelky

Lupa.cz: UX přestává pro firmy být magie

UX přestává pro firmy být magie

Podnikatel.cz: Víme první výsledky doby odezvy #EET

Víme první výsledky doby odezvy #EET