funktory.pdf

Wydajno±¢u»yciafunktorówzbibliotek¡STLj¦zyka

C++

IrekSzcze±niak ,MaciekSobczak y

1pa¹dziernika2005roku

Streszczenie

Artykuª dotyczy wydajno±ci u»ycia funktorów z bibliotek¡ STL (Standard Template

Library)j¦zykaC++.BibliotekaSTLoferujestrukturydanychtakiejakwektory,zbiory

czy kolejki priorytetowe i wiele funkcji do operowania na strukturach, np. funkcj¦ sor-

tuj¡c¡.Strukturomdanych,takimjak std::priority_queue,orazfunkcjom,takimjak

std::sort czy std::transform,opróczdanychmo»naprzekaza¢te»funktor,któryde-

niujesposóboperowanianadanych.DlatrzechimplementacjibibliotekiSTLdostarcza-

nychzkompilatoramiGNU,SGIiSUNprzedstawiamywyniki±wiadcz¡ceotym,»epewne

elementybibliotekiwykonuj¡wielekopiifunktora(np.±rednio1330kopiiprzysortowaniu

wektoraodªugo±ci1000elementów).Cowa»niejsze,poka»emyte»naprzykªadzie,»e¹le

zaprojektowanyfunktorwu»yciuzbibliotek¡STLmo»ebardzospowolni¢dziaªaniepro-

gramu.Nakoniecartykuªupoka»emy,jakwydajnieu»ywa¢funktorówzbibliotek¡STL.

Wagaprzedstawionegoproblemuwynikazfaktu,»ebibliotekaSTLjestcz¦±ci¡standar-

dowej biblioteki j¦zyka C++ i sprzyja tworzeniu przeno±nych programów { programi±ci

korzystaj¡cy z j¦zyka C++ mog¡ znale¹¢ w tym artykule wskazówki przydatne w ich

wªasnejpracy.

1 Wprowadzenie

J¦zyk C++ wyrósª z j¦zyka C poprzez dodanie nowych mo»liwo±ci, takich jak przeci¡»anie

funkcji, programowanie obiektowe, czy szablony. J¦zyk C++ i jego biblioteka standardowa

ci¡glesi¦rozwij¡.Cz¦±ci¡bibliotekistandardowejC++jestStandardTemplateLibrary(STL)

[1],którejdotyczytenartykuª.

BibliotekaSTLjestprzykªademprogramowaniagenerycznego(ang.genericprogramming),

które polega na implementacji rozwi¡zania postawionego problemu w taki sposób, »e to roz-

wi¡zanie zale»y jak najmniej od szczegóªów technicznych postawionego problemu, takich jak

zastosowanychalgorytmów,oraztypówistrukturydanych.

BibliotekaSTLjestgenerycznapodtrzemawzgl¦dami.Popierwsze,algorytmys¡niezale»-

ne od struktur danych, na których maj¡ operowa¢, czyli temu samemu algorytmowi (funkcji

bibliotekiSTL)mo»emyprzekaza¢zarównowektor(std::vector),jakinp.list¦(std::list).

Rozdzielenie algorytmów od struktur danych uzyskano dzi¦ki zastosowaniu iteratorów, które

zawszestanowi¡elementpo±rednipomi¦dzystruktur¡danychaalgorytmem.Podrugie,struk-

tury danych mo»emy budowa¢ z dowolnych typów danych, takich jak liczba caªkowita albo

zdeniowanaprzeznasklasa,czylimo»emyzadeklarowa¢obiekttypustd::vector<int>albo

typustd::vector<moj_typ>.Potrzecie,algorytmyistukturydanychbibliotekiSTLmo»emy

InstytutInformatykiTeoretycznejiStosowanejPolskiejAkademiiNauk

y niezale»nykonsultant

rozszerza¢ przez dostarczenie wªasnych funktorów, które okre±laj¡ sposób operowania na da-

nych.Przezfunktormo»emynp.okre±li¢sposóbporównywaniaelementówpodczassortowania,

porz¡dek w jakim ma by¢ utrzymana kolejka priorytetowa (std::priority_queue), dziaªa-

nie jakie ma by¢ wykonane podczas transformacji sekwencji (std::transform), itp. Wa»n¡

zasad¡ obowi¡zuj¡c¡ w bibliotece STL jest to, »e w du»ej cz¦±ci jest ona zbiorem konwencji

skªadniowychanieinterfejsówwtradycyjnymsensieklasbazowych,dziedziczeniaifunkcjiwir-

tualnych.Ró»neelementySTLwspóªpracuj¡zesob¡(orazzelementamidostarczonymiprzez

programist¦) dzi¦ki przestrzeganiu tych konwencji, chocia» nie musz¡ by¢ ze sob¡ formalnie

powi¡zane.

Niniejszy artykuª skupia si¦ na funktorach zastosowanych do rozszerzania biblioteki STL

oraznaaspektachzwi¡zanychzwydajno±ci¡funktorów.

2 Cotojestfunktor?

Funktorjesttoobiektzezdeniowanymoperatoremwywoªaniafukncji.Funktornazywanyjest

tak»e obiektem funkcyjnym. Na przykªad, poni»ej u»yty obiekt rd jest funktorem, poniewa»

mo»emywykona¢rd(20).

#include <iostream >

struct razy_dwa

{

int operator ()(int i) { return 2 * i; }

};

int main()

{

razy_dwa rd;

std::cout << rd(102) << '\n';

}

Oczywi±cietensamefektuzyskamyprzezu»yciezwykªejfunkcjitypuint rd(int i).Jed-

nakprzewag¡funktorównadfunkcj¡jestto,»eka»dyfunktormo»emie¢\wªasne"dane,czyli

stan,przechowywanypomi¦dzywywoªaniami,cojestichzalet¡wstosunkudofunkcjikorzy-

staj¡cychzezmiennychglobalnychalbostatycznych.Wprzykªadzieni»ejfunktorrnzawiera

wsobieinformacj¦(mno»nik),któr¡przechowujeizktórejkorzysta,gdyjestwywoªany.

#include <iostream >

class razy_n

{

int n;

public:

razy_n(int arg) : n(arg) {}

int operator ()(int i) { return n * i; }

};

int main()

{

razy_n rn(3);

std::cout << rn(102) << '\n';

}

Aleit¦cech¦funktoramo»emyzrealizowa¢przezwywoªywaniedowolnejinnejfunkcjiskªa-

dowej(np.nazwanejwynik),niekoniecznieoperatorawywoªaniafunkcji,takjaktojestprzed-

stawioneni»ej.

#include <iostream >

class razy_dwa

{

public:

int wynik(int i) { return 2 * i; }

};

int main()

{

razy_dwa rd;

std::cout << rd.wynik(102) << '\n';

}

Prawdziwezastosowaniefunktorawida¢dopierowpoª¡czeniuzszablonami,gdziemo»emy

zamiennieu»ywa¢funktorówifunkcji,poniewa»u»yciefunktorajestskªadniowozgodnezwy-

woªaniemfunkcji.Zdeniujemyfunkcj¦suma,którab¦dziezwra¢sum¦liczbzwracanychprzez

funktor. Funktorowi przeka»emy wszystkie liczby caªkowite od 1 do 99. Naszej funkcji suma

mo»emyterazprzekaza¢nietylkofunktor,aletak»ezwykª¡funkcj¦,jakpokazanejestni»ej.

#include <iostream >

// zwykla funkcja

int funkcja(int i) { return 2 * i; }

// klasa funktora

class razy_n

{

int n;

public:

razy_n(int arg) : n(arg) {}

int operator ()(int i) { return n * i; }

};

// szablon funkcji sumujacej

template <typename T>

int suma(T funk)

{

int suma = 0;

for(int i = 100; --i;)

suma += funk(i);

return suma;

}

int main()

{

razy_n funktor (2);

std::cout << suma(funktor) << '\n';

std::cout << suma(funkcja) << '\n';

}

Poni»szy przykªad pokazuje, »e funktory mog¡ równie» modykowa¢ swój stan w trakcie

pracy, niezale»nie od innych funktorów. Program ten wykorzystuje jedn¡ denicj¦ funktora

doobliczenia±rednichwarto±cidwóchró»nychtablic.redniajestobliczanadladwóchtablic

równocze±nie, ale ka»dy z funktorów operuje na swoich wªasnych danych, nie wpªywaj¡c na

siebienawzajem.

#include <iostream >

class srednia

{

public:

srednia () : suma(0), liczba (0) {}

void operator ()(int i)

{

suma += i;

++liczba;

}

double wynik () { return (double)suma / liczba; }

private:

int suma;

int liczba;

};

int main()

{

int tab1[] = {1, 4, 2, 3, 6};

int tab2[] = {7, 4, 6, 9, 3};

srednia sr1;

srednia sr2;

for (int i = 0; i != 5; ++i)

{

sr1(tab1[i]);

sr2(tab2[i]);

}

std::cout << "srednia z tab1: " << sr1.wynik() << '\n';

std::cout << "srednia z tab2: " << sr2.wynik() << '\n';

}

2.1 Konwencja

Jak zostaªo ju» wspomniane na pocz¡tku artykuªu, wiele elementów biblioteki STL mo»e ze

sob¡wspóªpracowa¢dzi¦kiprzestrzeganiupewnychkonwencji.Jedn¡zkonwencjiwprowadzo-

nych przez standard C++ [2] jest zalecenie, aby funktor zawieraª publiczne denicje typów

argumentówizwracanejwarto±ci.Dlafunktoraunarnego(akceptuj¡cegojedenargument)tymi

denicjamis¡:

typedef ... argument_type;

typedef ... result_type;

Natomiastdlafunktorabinarnegostandardwymaganast¦puj¡cychdenicji:

typedef ... first_argument_type;

typedef ... second_argument_type;

typedef ... result_type;

Dzi¦kiprzestrzeganiutejkonwencji,mo»naimplementowa¢generycznefunktoryialgorytmy,

któreskªadaj¡zesob¡kilkafunktorów,alboadaptuj¡jedoinnychpotrzeb.Wdalszejcz¦±ci

artykuªub¦dziemyprzestrzega¢tejkonwencji.

3 Przykªadipuªapka

Naszym zadaniem jest odpowiednie uporz¡dkowanie liczb caªkowitych zapisanych w wekto-

rze o nazwie produkty (typu std::vector<int>). Ka»da liczba tego wektora jest numerem

oferowanego towaru. Do dyspozycji mamy tablic¦ asocjacyjn¡ o nazwie sprzedanych (typu

std::map<int, int>), w której kluczem jest numer towaru, a warto±ci¡ jest liczba sprzeda-

nychsztuk.Brakwtablicyjakiego±numerutowaruoznacza,»eniesprzedanotegotowaru.

Odpowiednieuporz¡dkowaniewektoraproduktypoleganaprzemieszczeniunumerówcz¦-

±ciej kupowanych towarów w kierunku ko«ca wektora. Zatem je»eli i , j , i < j s¡ indeksami

uporz¡dkowanegowektora,to:

sprzedanych[produkty[i]] ¬ sprzedanych[produkty[j]] :

Dosortowaniau»yjemyfunkcjistd::sort,którejprzeka»emyzdeniowanyprzeznasfunk-

tor.Uporz¡dkowanywektorzawieraliczbywtejkolejo±ci: 10,20,5,13,botowarunumer10

niesprzedanowcale,atowarunumer13sprzedanonajwi¦ksz¡liczb¦sztuk.

#include <algorithm >

#include <iostream >

#include <iterator >

#include <map >

#include <vector >

// klasa funktora

class komparator

{

std::map <int , int > sprzedanych;

public:

typedef int first_argument_type;

typedef int second_argument_type;

typedef bool result_type;

komparator(const std::map <int , int > &arg):

sprzedanych(arg) {}

bool operator ()(const int a, const int b)

{

return sprzedanych[a] < sprzedanych[b];

}

};

int main()

{

std::vector <int > wektor;

wektor.push_back (13);

wektor.push_back (20);

wektor.push_back (5);

wektor.push_back (10);

std::map <int , int > sprzedanych;

sprzedanych [5] = 651;

sprzedanych [20] = 99;

sprzedanych [13] = 2148;

komparator porzadek(sprzedanych);

std::sort(wektor.begin(), wektor.end(), porzadek);

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: