Տվյալների կառուցվածքները, Հիշողության Կառավարումը և Ալգորիթմները C#–ում
Ցանկացած ծրագրի աշխատանք ենթադրում է հիշողության մեջ պահվող տվյալների հետ կատարվող փոփոխություն, այսինքն՝ կոնկրետ մուտքային տվյալների դեպքում կոնկրետ ելքային տվյալների ստացում։ Բնականաբար հիշողության պարունակությունը միշտ պիտի ձևափոխվի այնպես, ինչպես ակնկալվում և կանխատեսվում էր։ Չնայած, որ հիշողության հետ տեղի ունեցող փոփոխությունների արդյունքում ելքային արժեքը միշտ պետք է նույնը լինի, դեռ կա ակադեմիական բանավեճ հիշողության տարբեր հատվածների հետ արվող գործողությունների և հերթականության վերավերյալ։ Սա այլ կերպ կոչվում է ծրագրի դետերմիստական աշխատանք։ Ստացվում է, որ հիշողությունը, տվյալները և դրանց հետ արվող գործողությունները ֆունդամենտալ կարևորություն ունեն։ Մաթեմատիկան և ծրագրավորման լեզուները սահմանում են համապատասխան գործիքակազմ այս ամենի համար։ Արդյունքում ինֆորմացիայի հետ աշխատելու համար մենք նախ պայմանականորեն առանձնացնում ենք 2 խումբ, որոնք իրար հաջորդում են։ Դրանք են՝
1․ Ինտերֆեյսը կամ տեսական սահմանումները, որոնք ցուց են տալիս պահվող տվյալների տեսակները, դրանց հետ արվող հնարավոր գործողությունները և խնդիրները։
2․ Տվյալների կառուցվածքը կամ ինտերֆեյսի գործնական դրսևորումը, որը սահմանում է տհյալների պահպանման ձևը, ներկայացումը և խնդիների լուծման ալգորիթմները։
Ինտերֆեյսներն իրենց հերթին ունեն 2 հիմնական խումբ (էջ 86)։ Դրանք են՝
1․ «Set», բազմություն կամ շարք, որի տարրերը պիտի լինեն եզակի և իրարից տարբեր, օրինակ՝ {a, b, a}, որում կան միայն 2 տեսակի տարրեր, ուստի կրկնություններ ունենալ պետք չէ։ {a, b, c} և {a, c, b} շարքերը նույնն են, այսինքն՝ տարրերի դասավորությունը կապ չունի և շարքերը ոչ կարգավոր են, unordered։ C#–ում բազմությունները հիմնականում նաև սորտավորված են, այսինքն՝ դասավորված են աճման կարգով։ Համակարգչային գիտությունն այս խմբի համար սահմանում էր Hash tree–ն։ Ավելի կատարելագործված տարբերակն է Hash table կամ Hash map կառուցվածքը։
2․ «Sequence» կամ ցուցակ, հաջորդականություն, որում տարրերը կարող են կրկնվել, բայց միևնույն ժամանակ կունենանք տարբերվող հավաքածուներ, օրինակ՝ (a, b, c) և (a, c, b) հաջորդականությունները տարբեր են և ունեն 3 տարր, այսինքն՝ կարգավոր են, ordered։
«Static Sequence»–ում տարրերի քանակը հաստատուն է, բայց կոնկրետ տարրի արժեքը կարող է փոխվել։ Տիպիկ օրինակ է զանգվածը՝ Array–ը, որի կամայական անդամի արժեք կարելի է կարդալ կամ փոփոխել ցանկացած պահի և պատահականորեն։ Օպերատիվ հիշողությունը՝ «RAM»–ը, հենց այս սկզբունքով է աշխատում։ Ինդեքս օգտագործող հավաքածուների դեպքում տարրերը հիշողության մեջ գրանցվում են անմիջապես իրար կողք կողքի։
«Dynamic Sequence»–ում կարելի է ոչ միայն ստանալ տարրերի արժեքը, այլ նաև ցանկացած հատվածում ավելացնել նոր տարր, այսինքն՝ փոխել եկարությունը։ Տիպիկ օրինակ է «Linked List»–ը։ Հղումային հավաքածուների դեպքում տարրերը հարող են գրանցվել հիշողության տարբեր կտորներում։ Սա բացասական է ազդում արագագործության վրա։
Նոր ավելացվող տարրը ֆիզիկապես կարող է գրանցվել մյուսներից հետո, և միայն ցուցիցչներն են իրենց արժեքը փոխելու և այլ անդամի ցույց տալու: Տարր ջնջելով ցուցակը կարճացնելը տեղի է ունենում նույն սկզբունքով։ Դինամիկ հավաքածուի դեպքում կամայական տարրի դիմելը դժվար է, քանի որ մինչ այդ տարրին հասնելը պետք է դիմել առաջին տարրին և հերթով կարդալ հղումները։
Պետք է հասկանալ, որ սրանք նախ և առաջ կոնցեպտներ են, հետևաբար յուրաքանչյուր լեզու սահմանում է իր խաղի կանոնները: Այստեղից հետևություն՝ ցանկացած հավաքածու ունի իր առավելություններն ու թերությունները։ Զանգվածի երկարությունը հնարաովոր չէ փոխել, բայց կարելի է արագ՝ Θ(1) ժամանակում ստանալ դրա պարունակությունը։ Ցուցակի դեպքում հակառակն է՝ կարելի է փոփոխել երկարությունը, բայց պարունակությունը ստանալն է դժվար և պահանջում է Θ(n) ժամանակ։ Կա նաև «Dynamic Array» կոնցեպտը, իրականացված որպես ArrayList, որն այս երկուսի միջակայքում է, Θ(1) ժամանակում կարելի է կարդալ ցանկացած տարր, բայց ավելացնել կարելի է միայն վերջից։ Աղյուսակը ցույց է տալիս կառուցվածքների հետ արվող հնարավոր գործողությունների արագագործությունը։
Տվյալների կառուցվածքի գործնական իմպլեմենտացիայի ժամանակ պարզ է դառնում, որ ակնհայտ կամ ոչ ակնհակտ ձևով կարող է օգտագործվել ցուցիչ, հատկապես, երբ պետք է կարողանալ դրա երկարությունը փոփոխել։ Հետևյալ կոդում ակնհայտ կերպով օգտագործվել է ցուցիչ:
Ամեն անգամ հատկացվում են հիշողության տարբեր հատվածներ հետևաբար աշխատանքն ավարտելուց հետո պետք է Garbage Collector–ի միջոցով մաքրել հիշողությունը։ Սա ոչ դետերինիստական գործընթաց է, որը հատկապես դրսևորվում է «Weak reference» ունենալու դեպքում։ Այն ենթադրում է, որ օբյեկտը կարող է օգտագործվել, բայց կարող է և մաքրվել հիշողությունից, ինչը, պարզ ասած, ենթադրում է պատահականությունների առկայություն։ Որոշ լեզուներ, այդ թվում C#–ը և CLR–ը կատարում են դա ավտոմատ կերպով, չնայած կարելի է ակնհայտ կերպով օգտագործել: Նման օրինակի կծանոթանանք հաջոր մասում։ Արդյունքը հետյալն է՝
Թեև ֆիզիկական մակարդակում տվյալները կարող են գրանցվել հաջորդաբար, բայց ըստ գրաֆիկական պատկերման տվյալների կառուցվածքները լինում են Linear կամ գծային և Non–Linear կամ ոչ գծային։ Գծային են Array, Stack, Queue, List, Linked List կոնցեպտները և դրանց ձևափոխությունները։ List–ը ստեղծվում է Array–ի հիման վրա, իսկ Linked List–ը և իր տարատեսակ Doubly Linked List–ն աշխատում են ցուցիչով։ Ոչ գծային են Graph–ը և Tree–ն, որոնց գաղափարաբանությանը մոտ են Hash Table–ը, Dictionary–ն և այն կառուցվածքները, որոնց տարրերի հատկանիշն է զրոյից տարբերվելը և եզակի արժեք ունենալը, այսինքն՝ Set–երը։ Binary Tree–ն կազմզած է բջիջներից կամ «Node»–երից, որոնցից յուրաքանչյուրն ունի ամենաշատը 2 ենթաբջիջ, Binary Search Tree–ի դեպքում ձախ ենթատարրը պիտի փոքր լինի աջ կողմից, իսկ Binary AVL Search Tree–ն ունի նաև հավասարակշռության գործակից, որը ձախ և աջ բջիջների ենթատարրերի քանակության տարբերոթյունն է։ Հասկանալի է, որ ծառերի դեպքում տարրի կրկնություն չի խրախուվում, քանի որ ըստ սահմանման բջիջները կարող են դասավորված լինել աճման կարգով, ինչպես օրինակ Binary Search Tree–ի դեպքում։
Պետք է տարբերել «Զանգված» և «Տվյալների Կառուցվածք» հասկացությունները։ Լավ հասկանալու համար նայենք հետևյալ կոդի աշխատանքը։
«Person[]» և «int[]» հրահանգներով հայտարարում ենք Person և Int տիպերի զանգված, որոնց տարրերին հասանելիություն ենք ստանում ինդեքսի միջոցով, երբ գրում ենք «arrayOfPerson[0] = new Person() { };» և «arrayOfInt[1] = 10;»։
Այդ նույն տիպերով ունենում ենք նաև «LinkedList<Person>» և «LinkedList<int>» հավաքածու, որոնց «listOfPerson.AddFirst(new Person { });» և «listOfInt.AddFirst(9);» հրահանգներով նոր տարր ենք ավելացնում։
«LinkedList<Person>[]» կամ «LinkedList<int>[]» հրահանգով ստեղծում ենք հավաքածուների զանգված, որի տարրերը կապակցված ցուցակ հավաքածուներն են, որոնք սկզբում null reference են և ցուցակում տարր ավելացնելուց առաջ «arrayOfLinkedListOfPerson[0] = new LinkedList<Person>();» հրահանգով պետք է հիշողությունից տեղ հատկացնել։ Հետո «arrayOfLinkedListOfPerson[0].AddFirst(new Person() { });» հրահանգով զանգվածի առաջին տարրին՝ ցուցակին ավելացնում ենք արժեք։
«LinkedList<Person[]>» և LinkedList<int[]> հրահանգով հայտարարում ենք Person[] և int[] զանգվածներ պարունակող ցուցակ։ «linkedListOfArrayOfPerson.AddLast(new Person[]{new Person { }, new Person { } });» և «linkedListOfArrayOfInt.AddLast(new int[] { 1,1});» հրահանգով ցուցակում ավելացնում ենք զանգված: Զանգվածի յուրաքանչյուր տարր կարող է լինել կա՛մ Person[] տիպի և պարունակել անուն, ազգանուն և էլ․ փոստի հասցե, կա՛մ լինել int[] տիպի և պարունակել ամբողջ թվեր։
C#–ում System.Collections անունների տիրույթը տրամադրում է ArrayList, BitArray, Hashtable, Queue, SortedList և Stack տիպերը, System.Collections.Specialized տրիրույթը՝ HybridDictionary, ListDictionary, StringCollection և BitVector32 տիպերը, իսկ System.Collections.Generic տիրույթը՝ Dictionary<TKey,TValue>, LinkedList<T>, List<T>, Queue<T>, SortedDictionary<TKey,TValue>, SortedSet<T> և Stack<T> տիպերը (Pro C# 9 with .NET 5, Foundational Principles and Practices in Programming, էջ 371)։
ArrayList–ի բոլոր տարրերին կարելի է դիմել հավասարապես և կամայականորեն՝ Random Access–ով։ Այն միաժամանակ կարող է պարունակել տվյալների տարբեր տիպեր։ Քանի որ այն զանգած է, թույլ է տալիս իր պարունակությանը դիմել նաև ինդեքսով՝ Θ(1) ժամանակով։ Նոր տարր ավելանում է վերջից, իսկ ամբողջ պարունակությունը հիշողության մեջ գրանցվում է հաջորդաբար։ Հատկացված հիշողության ծավալը սպառելուց հետո զանգվածի բոլոր տարրերը պատճենվում են մեկ այլ՝ ավելի ընդարձակ հատված։ Այս գործընթացն առաջացնում է հիշողության ծանրաբեռնում։
Ցուցիչ օգտագործող տվյալների կառուցվածքի օրինակ է LinkedList–ը։ Յուրաքանչյուր բջիջ՝ Node, իր ֆիզիկական դիրքով կարող է գտնվել մյուցներից հեռու։ Բջիջը պարունակում է 2 կտոր, մեկն արժեքի, մյուսն էլ հաջորդ բջիջին հղվելու համար։ Արժեքը ստանալու համար հարկավոր է Θ(n) ժամանակ, այսինք 198–րդ բջիջը ստանալու համար կատարվում է 198 քայլ։ Առաջին և վերջին տարրը ջնջելու կամ ավելացնելու համար պահանջվում է Θ(1) ժամանակ, իսկ մնացած տարրերը ջնջելը և կարդալը՝ Θ(n) + Θ(1) ժամանակ։ Doubly linked list–ի բջիջը պարունակում է 3 կտոր՝ բուն արժեքի, հաջորդ և նախորդ բջիջին հղվելու համար, ուստի այն ավելի շատ հիշողություն է պահանջում։ Առաջին և վերջին տարրը հասանելի են անմիջապես, O(1) ժամանակում։ Քանի որ պարտադիր չէ, որ բջիջները հիշողության մեջ գրանցվեն հաջորդաբար, դրանք պահվում են հիշողության կամայական, հնարովոր է նաև իրարից հեռու հատվածներում։ Այս պատճառով նոր բջիջ գրանցելն արագ է կատարվում, բայց կոնկրետ բջիջ ստանալը՝ համեմատաբար դանդաղ, քանի որ պետք է կարդալ մինչև դա եղած բոլոր բջիջներ։ Կրկնակի հղում ունենալը լուծում է անվտանգային խնդիրներ, քանի որ սովորական LinkedList–ի բջիջի վնասվելու դեպքում կորում է կապը հաջորդների հետ, իսկ կրկնակի հղումների դեպքում ունենք «Պլան Բ»։ Unrolled Linked List — ի դեպքում յուրաքանչյուր բջիջ կարող է ունենալ մեկից ավելիի բուն արժեք։ Գրենք հետևյալ կոդը`
intLinkedList–ային շղթայում գրանցվում է 40 թիվը, հոջորդ քայլով դրանից առաջ գրվում է 41–ը և այդպեց մինչև 50։ Շղթայի վերջ հանդիսացող 40–ից սկսած՝ ավելանում են 30–ը, 31–ը և այլն։ Այս կոդի աշխատանքի արդյունքում տպվում է հետևյալը՝
List–ն իր աշխատանքի սկզբունքով հիշեցնում է զանգված՝ Array, ուստի թույլ է տալիս իր կոնկրետ տարրերին դիմել նաև ինդեքսով։ Իմպլեմենտացվում է LinkedList–ի կամ Դինամիկ Զանգվածի հիման վրա։
Պատահական գեներացված թվերի ցուցակին Insert()–ով ավելացվում է նոր թիվ, RemoveAt()–ով՝ ջնջվում, իսկ Reverse() –ով՝ շրջվում։ Արդյունքը հետևյալն է՝
Stack–ը նման է քարակույտի, ուստի պարզ է, որ նախ հասանելի է վերևինը: Այն գործում է «LIFO» կամ «Last in, First Out» սկզբունքով, կոնկրետ պահին կատարվող գործողությունը վերաբերում է վերջինն ավելացված տարրին։
Ավելացնելու Push և հեռացնելու Pop հրահանգները վերաբերում են միայն գագաթին։ Stack–ն աշխատում է LinkedList–ի կամ զանգվածի հման վրա։ Ծրագրավորողն, ասես, գործ ունի ցուցակի կամ զանգվածի հետ, բայց սահմանափակված է իր գործողությունների մեջ ու միայն մի կողմից կարող է արժեք ավելացնել։ Stack–ը կարող է ունենալ սահմանափակ ծավալ, եթե իմպլեմենտացվել է զանգվածի հիման վրա։ Որպես աբստրակցիա Stack–ը վերաբերում է նաև տեխնիկական ապահովման մակորդակում հիշողության հատկացման սկզբունքներին։ Յուաքանչյուր թրեդի համար հիշողությունից հատկացվում է հատված։ Այս հիշողությունն օգտագործվում է ֆիքսված երկարությամբ փոփոխականների` «Value type»–երի պահման համար։ Կոդը հետևյալն է՝
Թվերն ավելացվել են փոքրից մեծ հերթականությամբ, բայց քանի որ Stack–ը գործում է «LIFO» կամ «Last in, First Out» սկզբունքով, կոնկրետ պահին կատարվող գործողությունը վերաբերում է վերջինն ավելացված տարրին։
Queue–ն հավաքածու է, որի դեպքում տվյալներն ավելանում են մի կողմից, իսկ գործողություններն արվում՝ հակառակ կողմից։ Նման է շարք կանգնած մարդկանց հերթին։ Աշխատում է «FIFO» կամ «First In, First Out» սկզբունքով։
Հիմքում գործում է Doubly linked list–ը, քանի որ դրա դեպքում ծայրակետերում արժեք ավելացնելը և հեռացնելը կատարվում է O(1) ժամանակում, որը շատ արդյունավետ է։ Double-ended queue–ն ավելի ընդհանուր աբստրակցիա է, որ դեպքում նույն գործողությունը կարող է կատարվել և՛ վերջից, և՛ սկզբից։ Այսինքն՝ Queue–ն և Stack–ը Double-ended queue–ի մասնավոր դեպքեր են։ Մեկ այլ դեպք է Priority queue–ն, որն իր կոնցեպտով նման է List–ին և կարող է իմպլեմանտացվել չկարգավորված զանգվածով։ Double-ended priority queue–ն թույլ է տալիս հեշտությամբ ջնջել մեծագույն և փոքրագույն տարրերը, քանի որ ունենում է որաշակի նախնական կարգավորումներ։ Իմպլեմենտացվում է ինքնքհավասարակշռվող երկուական որոնման ծառի հիմանա վրա։ Կոդը հետևյալն է՝
Կոդի աշխաատանքի արդյունքում ունենում ենք հետևյալ արդյունքը՝
Կան տվյալների կառուցվածքներ, որոնց տարրերը չեն կարող կրկնվել կամ լինել null։ Դրանք «Key — value» սկզբունքով գործող հավաքածուներն են։ Այս խմբի հիմնական աբստրակցիան Associative array–ն է, որն իրականացվում է Hash table–ով կամ երկուական ծառերով։ Hashing–ը նման կառուցվածք ստանալու պայմանական մեթոդն է, որն անկանխատեսելի չափով հիշողություն զբաղեցնեղ բանալիները հեշավորում՝ դարձնում է ֆիքսված չափով ինդեքսային տարրերի մի առանձին զանգված։ Այսինքն՝ մեթոդը բուն արժեքային դաշտին հղվող բանալին վերածում է «Hash code»–ի, որն էլ իր հերթին օգտագործվում է որպես ինդեքս: Բայց ի տարբերություն զանգվածների, հեշային կառույցների դեպքում նոր տարր ավելացնելիս արդեն եղած տարրերը չեն վերապատճենում հիշողության մի հատվածից մյուսը։ Hashing–ի և գաղտնագրման միջոցով կարելի է ստանալ բլոկչեյն։ Associative array–ի գործնական դրսևորումն են Dictionary–ն, SortedDictionary–ն և SortedList–ն։ SortedSet–ը ևս պաունակում է եզակի արժեքներ, բայց այն չունի բանալի։ Աշխատում է հետևյալ կերպ`
Հայտարարված Dictionary–ում Add()–ի միջոցով ավելացվում են int ամբողջ թվեր և Person տիպի ինֆորմացիա։ Remove(2) հրահանգով ջնջվում է տողը, որի բանալին 2 է։ Արդյունքում ունենում ենք հետևյալը։
«Key — value» սկզբունքով գործող տվյալներ կառուցվածքի մեկ այլ տեսակ է SortedDictionary–ն։ Բայց այս դեպքում տարրերը դասավորվում են բանալու աճման կարգով, չնայած, որ տարրեն ավելացվել են անկանոն։ SortedSet–ում տարրերը նույնպես դասվորվում են աճման կարգով,անկախ ներմուծված արժեքներից։
Արդյունքում ունենում ենք բանալու աճման կարգով դասավորված տողեր։
SortedList–ը և SortedDictionary–ն տարբերվում են միայն արագագոծությամբ։ Երկուսի դեպքում էլ տարր ստանալը տևում է O(log n) ժամանակ։ Արժեք հեռանցնելը և ավելացնելը SortedDictionary–ում O(log n) է, SortedList–ում՝ սովարաբարO(n)։ Կոդում համեմատվում են տարր ավելացնելը, հեռացնելը և գտնելը:
Կոդի աշխատանքից երևում է, որ նույն հաշվարկի կատարման տվողությունը, կախված համակարգչի ճարտարապետությունից և օպերացիոն համակարգից, տարբերվում է։ Այս պատճառով ալգորիթմի արագագործությունը ժամանակով կամ պրոցեսորային հրահանգների քանակով որոշելն արդյունավետ տարբերակ չէ։ Ուստի ալգորիթմների աշխատանքի արդյունավետությունը չափվում է կատարված քայլերի քանակով։ Հետյալ աղյուսակը ցույց է տալիս տվյալների կառուցվածքների հետ արվող կատարվող գործողությունների արագագործության գնահատականները։
Օրինակ՝ սորտավորված զանգվածում ամենամեծ կամ ամենափոքր տարրը գտնելը կատարվում է 1 քայլով, քանի որ արժեքներն արդեն դասավորված են աճման կամ նվազման կարգով և գտնելը հեշտ է։ Չսորտավորված զանգվածի դեպքում պետք է ստուգել բոլոր արժեքները, այսինքն n=500 տարր պարունակող հավաքածուում կատարվելու է 500 համեմատման գործողություն։ Դա նշանակվում է «O(n)»–ի միջոոցով։
Ոչ գծային տվյալների կառուցվածքների ամենակիրառվող ձևը երկուական որոնման ինքնահավասարակշռվող ծառն է` «Self-balancing binary search tree»–ն։ Փոքր տարրերը պահվում են ձախ կողմում, մեծերն՝ աջ։ Այս օրինակում սկզբնական կառույցին ավելացնում ենք 1 թիվը։ Համեմատում ենք արմատի՝ 25–ի հետ, հետո 20–ի և այդպես շարունակ։ 4 թիվն ավելացնելուց այն տեղափովում է 1–ի հետ։ 8–ը դարձյալ տեղավորվում է 9–ի և 4 –ի միջև։ 45–ն ու 42–ն էլ ավելանալիս տեղափոխվում են այլ բջիջների հետ, երբ անհրաժեշտ է։
Այս օրինակում ծառի բարձրությունը 4 միավոր է։ 7 բարձրությամբ երկուական ծառի առավելագույն տարրերի քանակը 72 կամ 128 է։ 1 թվի դիրքը գտննելու համար պահանջվում է 7 քայլ, որը համապատասխանում է «Log2(128) = 7» հավասարմանը։
Գրաֆնը նույնպես իրար միացված բջիջների՝ գաթների հավաքածու։ Այն շատ հարմար է համակարգչային ցաներ մոդելավորելու և լոգիստիկ հաշվարկներ կատարելու համար։
Գրաֆի օրինակ են ծրագրում օգտագործվող օբյետկները, որոնք կարող են հիշողության մեջ գրանցվել և իրար վրա հղվել անկանոն։ Երբ սկսվում է պրոցեսը, CLR–ն ամեն անգամ «new» բանալի բառին հանդիպելիս «Managed heap»–ում բոլոր օբյեկտների համար տեղ է հատկացնում, քանի դեռ պրեցեսի համար հատկացված վիրտուալ հիշողության բազմությունը սպառված չէ։ Բայց երբ արդեն վիրտուալ հիշողությունը սպառվում է, անհիաժեշ է լինում մաքրել հիշողությունը։ Այդ ընթացքում CLR–ը սառեցնում է պրոցեսում եղած բոլոր թրեդները և սկսում զննել օբյեկտները։
Garbage Collector–ի աշխատանքն ավելի արդյունավետ դարձնելու համար օգտագործվում են օբյեկտների սերունդները՝ «Object generations»։ Նոր ստեղծված օբյեկտը 0 սերնդի է և ավելի մեծ հավանականությամբ կարող է մաքրվել։ Չմաքրվելու դեպքում բոլքր օբյետկտները դերֆագմենտացվում և հիշողության մեջ պատճենվում են հաջորդաբար, արդյունքում դառնում են 1 սերնդի։ Garbage Collector–ի ևս մեկ անգամ վերապրելու դեպքում օբյեկտները դառնում են 2 սերնդի։ 85 000 բայթից ավել ծավալ ունեցող օբյեկտները կարող են լինել միայն 2 սրնդի, բայց երփեմն կոչվում են 3 սերնդի։
Պրոցեսի աշխատանքի ընթացքում օբյեկներն ունենում են 3 կարգավիճակ՝
1․ Root, Արմատներ, որոնք ծարագրի համար հասանելի են ուղակիորեն, հանդիսանում են «Managed heap»–ում պահվող օբյեկների հղման սկզբնակետը, օրինակներ են գլոբալ փոփոխականները, չնայած C#–ում չկա, լոկալ փոփոխականները, ստատիկ դաշտերը և Finalization queue–ն
2. Live object, ակտիվ օբյեկտներ, որոնք դեռ օգտագործվում են և հասանելի են արմատի կողմից,
3. Dead objects, ծրագրի կողմից չօգտագործվող և անհասանելի օբյեկտներ։
Հետևյալ օրինակում մենք ունենք իրար վրա հղումներ պարունակող օբյեկտներ, որոնցից յուրաքանչյուրի համար պահվում է մուտքային հղումների քանակը։
Օբյեկտներից մեկն ինչ–որ պահից սկսած այլևս չի օգտագործվում։ Արդյունքում հղումների քանակ ցույց տվող փոփոխականը դառնում է 0։
GarbageCollector–ը մաքրում է հիշողության այն հատվածները, որոնք զբաղեցված են չօգտագործվող օբյեկտների կողմից։
Բայց այս մոտեցումը չի աշխատում ցիկլային հղումներ պարունակող օբյեկտների դեպքում, քանի որ յուրաքանչյուր օբյետկ միշտ կանչվելու է մեկ ուրիշի կողմից։ Այս խնդիրը լուծող ալգորիթմներից մեկը կոչվում է «Mark and Sweep»։ Այս դեպքերում արմատից սկսած յուրաքանչյուր գագաթի համար կազմվում է Queue, որը ցույց է տալիս դրա հարևաններին, այսինքն այն տարրերին, որոնց վրա հղվել է։
R–ի հարևաններն են B–ն և C–ն։ B–ն ունի 1 հարևան՝ C–ն, որն արդեն գրանցված է։ C–ի հարևաններն են D–ն և E–ն։ D–ն չունի հարևան։ E–ի հարևանն է F–ը, F–ինն էլ՝ G–ն։ G–ն արդեն հարևաններ չունի, հետևաբար կարելի է ջնջել այն գագաթները, որոնք արմատի կորղմից հղումներ չեն պարունակում։ Այս ալգորիթմը ֆրագմենտացիա չի իրականացնում, և հիշողության տարբեր հատվածներում գրանցված օբյեկտները շարունակում են ցրված մնալ։ «Stop and Copy» ալգրիթմի դեպքում Queue–ի մեջ հենց օբյեկտներն են գրանցվում, այլ ոչ թե հղումները։ Այս ալգորիթմը կարող է անդաղ աշխատել, բայց ապահովում է հավաքածուի հետագա արագագ օգտագործումը։
Խոշոր հաշվով բոլոր տվյալներ կառուցվածքների դեպքում տարրերն ուղղակի կամ անուղղակի կերպով եզակի են։ Անգամ զանգվածների դեպքում կա չկրկնվող և եզակի արժեք՝ ինդեքսը։ Տարբերությունն այն է, որ ինդեքսը սահմանելը կախված է ծրագրավորման լեզվից և սահմանվում է ոչ ակնհայտ ձևով, իսկ ակնհայտ կերպով սահմանվող բանալիների դեպքում կրկնություն թույլ չտալը կախված է ծրագրավորողից։
Ամբողջ կոդը կարող եք գտնել գիտհաբում՝ AdvancedConcepts և DataStructures
Օգտագործված սկզբնաղբյուրները՝
Introduction to Algorithms
https://youtube.com/playlist?list=PLUl4u3cNGP63EdVPNLG3ToM6LaEUuStEY
Advanced Data Structures
2) https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-851-advanced-data-structures-spring-2012/
https://youtube.com/playlist?list=PLUl4u3cNGP61hsJNdULdudlRL493b-XZf
Performance Engineering of Software Systems
4) Pro C # 9 with .NET 5, Foundational Principles and Practices in Programming, Andrew Troelsen
5) CLR via C#, Developer Reference, Jeffrey Richter, 4th Ed., էջ 505
Ավելի մանրամասն ծանոթանալ ցանկացողների համար՝ https://docs.google.com/document/d/1qaFg7lVacBkBEAeicetvihny10VO-_HV/
