Hlavní navigace

Squeak: návrat do budoucnosti (12)

27. 4. 2004
Doba čtení: 6 minut

Sdílet

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.

root_podpora

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.

Byl pro vás článek přínosný?