Алгоритмдер мен ассоциативтік жиымдар

 

С++ is a general purpose prograrnming language designed to make jprograrmrang more enjoyable for the serious programmer. Except for minor details, С++ is a superset of the С programming language. In addition to the facilities provided by C, С++ provides flexible and efficient facilities for defining new types.

 

Программаның жұмыс істеу нәтижесі:

 

С: 1

С++: 3

С# t 1

Excepts 1

Xn: 1

a: 2

addition: 1

and: 1

by: 1

defining: 1

designed: 1

details,: 1

efficient: 1

enjoyable: 1

facilities: 2

flexible: 1

for: 3

general: 1

is: 2

language: 1

language.: 1

make: 1

minor: 1

more: 1

new: 1

of: 1

programmer.: 1

programming: 3

provided: 1

provides: 1

purpose: 1

serious: 1

superset: 1 t

he: 3

to: 2

types.: 1

 

 

21.6.3 Ассоциативтік жиымның тағы бір мысалы

 

map контейнерінің пайдалылығын бағалау үшін, 21.5.3 бөліміндегі Доу-Джонс индексті мысалға оралайық. Ол жерде жазылған код дұрыс жұмыс істейді, егер vector классының объектісінде жазылған салмақтар мен аттардың позициялары сәйкес болса ғана. Бұл талап айқын емес және түсініксіз қателерді тудыруы мүмкін. Бұл проблеманы шешудің көптеген мысалдары бар, бірақ солардың ішіндегі ең қызықтыратыны салмақтарды оладың тикерлерімен бірге сақтау, мысалы ("АА",2.4808). Тикер – бұл компания атауының аббревиатурасы. Аналогты түрде компания тикерін оның акция бағасымен бірге сақтауға болады, мысалы ("АА",34.69). Қорытындылай келе, АҚШ-тың нарықтық фондымен сирек кездесетін адамдар тикерді компания атымен бірге жаза алады, мысалы ("АА","Alcoa Inc."); басқаша айтқанда сәйкес мәнді үш ассоциативтік жиым сақтай аламыз.

Басында (символ, баға) жұбынан тұратын  ассоциативтік контейнер құрамыз.

 

map<string,double> dow_price;

// Доу-Джонса индексі (символ, баға)

// ағымдағы баға белгілеуді (котировка) www.djindexes.com веб-сайтынан көріңіз

dow_price["MMM"]  = 81.86;

dow_price ["АА"]  = 34.69;

dow_price ["МО"] = 54.45;

// . . .

 

(символ, салмақ) жұптарынан тұратын  ассоциативтік жиым былай жарияланады:

 

map<string,double> dow_weight; // Доу-Джонса индексі (символ, салмақ) dow_weight.insert(make_pair("МММ", 5.8549)) ;

dow_weight.insert (make_pair ("АА", 2.4808));

dow_weight.insert(make_pair("MО", 3.8940));

// . . .

 

Біз insert() және make_pair() функцияларын қолданған себебіміз, map контейнерінің элементтері pair классының объектісі екендігін көрсету үшін. Сонымен қатар бұл мысал белгілеулердің мәнін көрсетеді; біздің ойымызша индекстеу түсінікті әрі оңай жазылады.

(символ, атау) жұбынан тұратын ассоциативтік  контейнер.

 

 

 

map<stringf string> dow_name; // Доу-Джонс (символ, атау)

dow_name["МММ"]   = "3M Co.";

dow_name["АА"]  = "Alcoa Inc.";

dow_name["МО"]  = "Altria Group Inc.";

// . . .

 

Осы ассоциативтік контейнерлердің  көмегімен кез-келген мәліметті  шығарып алуға болады, мысал қарастырайық.

 

double alcoa_price = dow_j>rice ["AAAn];        // ассоциативтік жиымнан

// мәндерді оқимыз

double boeing_jprice = dow_price ["ВА"] ;

 

if  (dow_price. f ind("INTC")   != dow_price.end())   // ассоциативтік жиым

// элементін табады

cout << "Intel is in the Dow\n";

 

Ассоциатвтік жиым бойынша жылжу  оңай. Біз тек кілт – first екендігін, ал – second мән екендігін есте сақтауымыз керек.

 

typedef map<string,double>::const_iterator Dow_iterator;

 

// Доу-Джонс индексіне кіретін әрбір компания үшін акция бағасын жазады

 

for (Dow_iterator р = dow_price.begin() ; р != dow_price.end(); ++p) {

const string& symbol = p->first; // тикер

cout << symbol << '\t'

<< p->second << '\t'

<< dow__name [symbol]  << '\n';

}

 

Біз тіптен ассоциативтік жиымдарды  қолдана отырып, кейбір есептеулер жүргізе аламыз.

21.5.3 бөліміндегі сияқты индексті  есептей аламыз. Біз акциялар  бағасын және сәйкес ассоциативтік  жиымнан салмақтарды шығарып  алып оларды көбейтуіміз керек.  Біз кез-келген екі map<string, double> ассоциативтік жиымдарымен осы амалды орындайтын функция жаза аламыз.

 

double weightedvalue(

const pair<string,double>& a, const pair<string,double>& b

)      // мәндерді шығарып оларды көбейтеді

 

return a.second * b.second;

 

Енді осы функцияны inner_product() алгоритмінің жалпыланған версиясына қойып, индекс мәнін аламыз.

 

double dji_index =

inner_product (dow_price.begin(), dow_price.end() ,

// все компании

dow_weight.begin(),  //олардың салмақтары 
0.0,    // бастапқы мәні

plus<double>() ,  // қосу (кәдімгі)

weighted_value) ;        // салмақтар мен мәндерді алып,

// көбейтеді

 

 Неге мұндай мәліметтерді  векторларда емес ассоциативтік  жиымдарда сақтаған дұрыс? Біз  әр-түрлі мәндер арасындағы байланыс  айқын болуы үшін map классын қолдандық. Бұл себептердің бірі. Бұдан басқа map контейнері элементтерді олардың кілттері тағайындаған тәртіпке байланысты сақтайды. Мысалы, біз dow контейнерін аралап шыққанда символдарды алфавиттік тәртіпте шығардық; егер біз vector классын қолданғанда оны сорттау керек болар еді. Көпшіліктің map классын қолданатын себебі, мәндерді олардың кілттері бойынша іздегісі келгендіктен. Үлкен реттіліктерде элементтерді find() алгоритмі бойынша іздеу map сияқты реттелген құрылымға қарағанда баяу болады.

_____________________________________________________________________________

 Байқап көріңіз

Берілген мысалды жұмыс істейтін қалпына келтіріңіз. Содан кейін  өзіңіздің қалауыңыз бойынша  бірнеше компания қосып, олардың  салмақтарын тағайындаңыз.

_____________________________________________________________________________

 

21.6.4 Unordered_map() алгоритмі

 

 Vector контейнерінде элементті табу үшін find() алгоритмі бірінші элеметтен бастап, ізделініп жатқан немесе соңғы элементке дейін барлығын тексеріп шығуы тиіс. Бұл іздеудің орташа қиындығы (N) векторының ұзындығына пропорционал; бұндай жағдайда алгоритм қиындығы O(N) дейді.

 Мap контейнерінде элементті табу үшін индекстеу операторы тал түбірінен бастап, ізделінентін мән немесе тал жапырағына дейін барлық элементтерді тексеріп шығады. Бұл іздеудің орташа қиындығы тал тереңдігіне байланысты. N элементтен тұратын баланстандырылған бинарлық талдың максимал тереңдігі log₂N – ге тең, ал іздеу қиындығы O(log₂N) – ге тең. Басқаша айтқанда log₂N шамасына пропорционал. Бұл O(N) – ға қарағанда жақсырақ.

 

N  15        128       1023     16383

log₂N      4     7      10           14

 

Іздеудің шын қиындығы біздің мәндерді қалай тез тапқандығымызға және салыстыру мен итерация операцияларына қанша уақыт кеткендігіне байланысты. Нұсқауыштардың ізінен жүру, нұсқауышты инкрементациялауғ қарағанда қиынырақ.

 Кейбір типтер үшін, әсіресе бүтін сандар мен символдық тіркестерге map контейнеріндегі тал бойынша іздеуге қарағанда үлкенірек нәтижеге жетуге болады. Егжей-тегжейіне кірмей-ақ негізгі идеяны айтатын болсақ, кілт бойынша біз vector контейнерінде индексті есептей аламыз. Бұл индекс хеш-функцияның мәні деп аталады (hash value), ал бұл әдіс қолданылатын контейнер хеш-таблица (hash table) деп аталады. Хеш-таблицадағы мүмкін кілттер саны, ұяшықтар санына қарағанда көбірек. Мысалы, хеш-функция миллиардтаған мүмкін тіркестерді мыңдаған элементтен тұратын вектор индексына көрсету үшін қолданылады. Мұндай есеп қиын болып көрінуі мүмкін, бірақ оны шешуге болады. Бұл үлкен map контейнерлерін жасағанда әсіресе ыңғайлы. Хеш-таблицаның негізгі артықшылығы оның орташа қиындығы тұрақты және ондағы элементтер санына байланысты емес, яғни О(1) – ге тең. Бұл үлкен ассоциативтік жиымдарға зор артықшылық, мысалы, 500-мың веб-адрес сақтайтындарға. Хеш-таблица бойынша бұдан да нақты мәліметтерді оқырмандар unordered_map() контейнерінің документациясында немесе мәліметтер құрылымына байланысты кітаптардан таба алады. Іздеудің графикалық көрсетілімін (реттелмеген) векторда, баланстандырылған бинарлық талда және хеш-таблицада қарастырайық.

• Реттелмеген vector контейнеріндегі іздеу.

• map контейнерінде іздеу (баланстандырылған бинарлық тал).

• Unordered_map (хеш-таблица) контейнерінде іздеу.

 

 

STL кітапханасындағы Unorderedmap контейнері хеш-таблица көмегімен іске асырылған, тар контейнері – балансталған бинарлы ағаш (сбалансированного бинарного дерева) негізінде, ал vector контейнері болса – массив күйінде жүзеге асырылған. STL кітапханасының тиімділігі, бір жағынан ол мәліметтерді сақтау мен оған қолжетімділіктің (доступ), екінші жағынан, алгоритмдерді сақтау мен оған қолжетімділіктің түрлі әдістерін біртұтас жүйеге біріктіруімен түсіндіріледі.

 

Эмпирикалық ережеде былай айтылған:

• егер сізде былай істемеудің айтарлықтай негіздері болмаса vector контейнерін қолданыңыз
• егер сізге мәні бойынша іздеу(поиск по значению) жүргізу керек болса, тар контейнерін қолданыңыз ( және кілттің түрі «азырақ» («меньше») операциясын тиімді қолдануға мүмкіндік берсе)
• егер сізге үлкен ассоциацияланған массивте іздеу жүргізуді жиі іске асыру қажет болғанда және сізге тәртіпке келтірілген айналым (упорядоченный обход) керек емес болған жағдайда unordered_map контейнерін қолданынңыз (егер сіздің кілтіңіздің түрі хеш-функцияларын тиімді қолдануға мүмкіндік берсе).

Біз unordered_map контейнерін нақты сипаттамаймыз. Оны string немесе int типті кілттерімен тура тар контейнері сияқты, элементтердің айналымы (обход) кезінде олар реттелмеген жағдайды есептемегенде, қолдануға болады. Мәселен, біз 21.6.3 тарауынан Доу-Джонс индексін есептеп шығару үшін кодтың үзіндісін жазып алсақ болар еді. Ол келесідей жүзеге асырылар еді:

 

unordered_map<string,double> dow_price;

 

typedef unordered_map<string, double>:: const_iterator Dow_iterator;

 

for (Dow_iterator p = dow_price.begin() ; pi =dow_price.end() ; ++p) {

const stringfc symbol = p->first; // the "ticker" symbol

cout << symbol <<  '\t' << p->second << 1 \t' << dow name[symbol]  << ' \n';

}

 

Енді dow контейнеріндегі іздеуді жылдамырақ жүзеге асырса болар еді. Алайда, мұндай үдеу (ускорение) бұл индекске тек қана 30 компания кірістірілгеннен кейін (включены) байқаусыз (незаметным) болып қалуы мүмкін. егер біз нью-йорктік биржалық қорымен танылатын (котирующихся) барлық компаниялардың акцияларының бағаларын есепке  алсақ, онда программа өнімділігінің (производительность) арақатынасын түсінер едік. Әзірше тек қана логикалық өзгешелікті айтып өткен жөн: әрбір итерациядағы мәліметтер алфавиттік тәртіппен шығарылмайды.

С++ тілінің стандартындағы тәртіпке келтірілмеген (неупорядоченный) ассоциацивті массивтері жаңалық болып табылады және оның толыққанды элементі болып есептелмейді, себебі олар стандарт текстінің өзінде емес, С++ тілін стандартизациялау Комиссиясының (Technical Report) техникалық есебінде сипатталған. дегенмен, олар кең таралған, олар жоқ жерлерде олардың баламаларын (аналог), мәселен, hash_maP классы тәріздес бір нәрселерді кездестіруге болады.

 

21.6. АССОЦИАТИВТІ КОНТЕЙНЕРЛЕР (АССОЦИАТИВНЫЕ КОНТЕЙНЕРЫ)

 

• Байқап көріңіз

#include<unordered_map> директивасын қолдана отырып кіші көлемді бағдарлама жазып көріңіз. Егер ол жұмыс істемесе, unordered_map классы сіздің С++ тілін реализациялауына кірістірілмеген (не включен в вашу реализацию языка С++). Егер сізге шын мәнінде unordered_map контейнері керек болса, оның қолжетімді реализациясынның біреуін веб жүйесінен жүктеп алсаңыз болады ( мәселен, сайт www.boost.org).

__________________________________________________________________________

 

 

21.6.5. Көп мүшеліктер(Множества)

 

set контейнерін мәндері (значения) маңызды емес ассоциативті массив ретінде немесе  мәнсіз ассоциативті массив ретінде түсіндіруге болады. set контейнерін келесідей сипаттауға болады:

 

First кілті

Node* left Node* right

 
set контейнерінің торабы (узел)

 

 

Мәселен, жеміс жидектер (21.6.2 тарауын қараңыз) көрсетілген set контейнерін келесідей көрсетсе болады:   

 

set контейнері несімен пайдалы? Шын мәнінде, мәселелерді шешу  кезінде қандай да бір мәнді көрген-көрмегенімізді есте сақтауды қажет ететін көптеген мәселелер бар екен. Мысалдардың бірі ол – қолда бар жемістерді санап өту (перечисление); екінші мысал – сөздіктерді құрастыру. Осы контейнерді қолданудың өзгешелеу әдісі – кілттің рөлін оның мүшелерінің бірі ойнайтын, потенциалды көп ақпараты бар, элементтері объектілері болып табылатын «жазбалардың» («записи») көптігі.  

Мысалын қарастырайық.

 

struct Fruit {

string name;

int count;

double unit_price;

Date last_sale_date;

//  .   . .

};

 

struct Fruit_order {

bool operator()(const Fruitfc a, const Fruitfc Ь) const

{

return a.name<b.name;

}

};

set<Fruit, Fruit_order> inventory;

 

Бұл жерде біз объект-функция STL кітапханасының компоненттері арқылы шешуге ыңғайлы есептер спектрін кеңейтіп жатқанын қайтадан көріп жатырмыз.

 Set контейнерінің мәндері жоқ болғандықтан ол индекстеу операциясын (operator[]()) қолдамайды. Сондықтан біз оның орнына insert() және erase() сияқты “тізімдерге арналған операцияларды” қолдануымыз керек. Map және set контейнерлері push_back() функциясын айқын себеп бойынша қолдамайды: жаңа элементті кірістіру орнын программист емес, set контейнері анықтайды.

Бұның орнына insert() функциясын қолдану керек.

 

inventory.insert(Fruit("quince",5)) ;

inventory.insert(Fruit("apple", 200, 0.37));

 

Set контейнерінің Map контейнеріне қарағандағы артықшылығы біз итератордан алынған мәнді қолдана аламыз. Map контейнеріне қарағандағы Set контейнерінің (кілт, мән) деген жұбы болмағандықтан, атын ауыстыру (разыменование) оепраторы элемент мәнін қайтарады.

 

typedef set<Fruit>::const_iterator SI;

for (SI p = inventory.begin() , p! =inventory.end() ;  ++p)  cout << *p

<< ‘\n’;

 

Бұл фрагмент сіз << операторын Fruit классы үшін анықтасаңыз ғана жұмыс істейді.

 

21.7 Көшіру (копирование)

 

21.2 бөлімінде біз find()  функциясын «ең оңай әрі тиімді алгоритм» деп атадық.  Бұл көзқарасты да дәйектеуге болады. Көптеген қарапайым алгоритмдер тиімді тіпті тривиалды болып табылады. Жаңа программаны жазу не үшін керек? егер біреу жазып дұрыстаған код болса. Қарапайымдығы және тиімділігі жағынан copy() алгоритмі find() алгоритміне қарағанда жақсырақ. STL кітапханасында copy() алгоритмінің үш түрі бар.