follow

Ямар цуглуулга ашиглахаа хэрхэн сонгох вэ?

Өгөгдлийн цуглуулгыг үр дүнтэй ашиглана гэдэг програм хангамж хөгжүүлэгчдийн үндсэн чадвар байдаг. Бараг бүх компьютерийн ухааны салбарын оюутнууд нэг буюу хэд хэдэн хичээлээр өгөгдлийн бүтцийн талаар дагнан судалдаг.

.NET фреймворкын нэлээд олон цуглуулгын төрлүүд нийтлэг өгөгдлийн бүтцүүдийг өөртөө тусгасан байдаг. MSDN (Microsoft Developer Network) дээр дараах нийтлэг цуглуулгын төрлүүдийг жагсаажээ:

•    Array
•    ArrayList and List
•    HashTable and Dictionary
•    SortedList and SortedDictionary
•    Queue
•    Stack

Мэдээж үүнээс гадна олон цуглуулгууд байдаг хэдий ч хүссэн үр дүндээ хүрэхэд эдгээр цуглуулгууд хангалттай. Гол нь өөрийн зорилгодоо тохируулж эдгээрээс алийг нь сонгох вэ гэдэг юм.

Арга зам:

Таны сонголт уг цуглуулгыг чухам юунд ашиглах дээр тулгуурлах ёстой. Мөн хандалтын хурд болон санах ойн зохицуулалтыг харгалзан үзнэ. Цуглуулгаа сонгохоос өмнө та өөртөө дараах асуултуудыг тавьж болно:

-    Цуглуулгын дурын элемент рүү хандах уу, дарааллаар нь хандах уу?
-    Хэрвээ дурын элемент рүү хандах бол дугаараар /index/ нь хандах уу, түлхүүрээр /key/ хандах уу?
-    Цуглуулгын урт /хэмжээ/ нэмэгддэг байх уу, тогтмол байх уу?
-    Элементүүдийг эрэмблэх боломжтой байх уу?

Array

Цуглуулгын төрлүүдээс хамгийн энгийн нь Array бөгөөд бусдаасаа доод түвшний боловч хүчирхэг байдаг. Энэ нь санах ойд байрлах утгууд болон заалтуудын дараалал юм. Array нь таны хувьд гүйцэтгэл чухал, хэдэн элемент хадгалах нь тодорхой үед ашиглахад тохиромжтой.
Харин нийтийн хандалттай /public/ property-нүүдийн буцаах утгыг энэ төрлөөр зарлах нь тохиромжгүй. Урьд нь доод түвшний програмчлалд аливаа функцууд руу утга дамжуулахад array ашиглагддаг байсан. Жишээ нь: урсгалтай /stream/ ажиллах үед:

byte[] data = new byte[] {0x0f, 0x0e, 0x13};
data[0] = 0xff; // дурын хандалт
MemoryStream stream = new MemoryStream(data);

Дээрх жишээнд үзүүлснээр түүнийг зарлах синтакс нь харахад ойлгомжтой байдаг нь array-г ашиглах нэг давуу тал болдог.

ArrayList ба List<T>

Хэрвээ та цуглуулганд хадгалах элементүүдийн тоог мэдэхгүй бол Array ашиглах боломжгүй болно. ArrayList нь элементүүдийнхээ уртыг динамикаар өсгөж болдогоороо Array-ээс ялгаатай. ArrayList нь Array-тэй ижилхэн нэг интерфейсийг хэрэгжүүлдэг боловч элемент нэмэх нэмэлт функцуудтай.

ArrayList items = new ArrayList(new byte[] { 0x0f, 0x0e, 0x13 });
items[0] = 0x00; // Дурын хандалт
items.Add(0xff); // ArrayList-ийг динамикаар өргөтгөж байна

Зарлагааны синтакс нь Array шиг ойлгомжтой биш байгааг харж байгаа байх. Учир нь ArrayList-ийн байгуулагч функц нь ICollection төрлийг авдаг бол Array нь ICollection интерфейсийг хэрэгжүүлдэг.

ArrayList өөрийн элементдээ Object төрлийг авах боломжтой. Тиймээс элемент хадгалах болон уншиж авахад boxing, unboxing хийгддэг учир Array-г бодвол удаан ажиллана. Энэ үед List<T> классыг ашиглах нь үр дүнтэй. List<T> нь маш олон сайжруулалт хийгдсэн ба Microsoft Framework-ийн багийнхан ArrayList-ээс бүх талаараа илүү гэж зөвлөдөг.

Boxing ба Unboxing
Энэ нь C# хэлэн дэх өгөгдлийн төрлийн хувиргалтыг зохицуулах механизм бөгөөд энгийн өгөгдлийн төрөл /int, double гэх мэт/ болон заалт төрлүүдийн /класс болон өгөгдлийн бүтцүүд/ хооронд хувиргалт хийдэг. Энгийн өгөгдлийн төрлийг заалт төрөл рүү хувиргахыг boxing, эсрэг тохиолдолд unboxing гэдэг. Эдгээр үйлдлүүдийг их хэмжээгээр хийх нь таны програмын ажиллагаанд удаашралыг бий болгодог.

 

Түрүүчийн кодын хэсгийг List<T> ашиглан бичье:

List<byte> items = new List<byte>(new byte[] { 0x0f, 0x0e, 0x13 });
items[0] = 0x00;
items.Add(0xff);

Энэ код нь өмнө бичсэнтэй бараг төстэй харагдаж буй боловч boxing болон unboxing-оос зайлсхийж байгаагаараа давуу талтай юм. 

Hashtable ба Dictionary

Цуглуулгын элементүүдэд дугаараар нь хандахын гол дутагдалтай тал нь эдгээр дугаарууд байнга өөрчлөгдөж байдагт оршино. Дараах кодыг харна уу:

List<int> scores = new List<int>(new int[] {962, 175, 238});
Console.WriteLine("At index 0 we have: " + scores[0]);
scores.Insert(0, 23);
Console.WriteLine(scores[1] + " is now t index 1.");

Дээрх код нь гурван ширхэг бүхэл тоог List<T> цуглуулга руу нэмж байна /бидний жишээнд тоглоомын оноо/. 962 тоог 0 дугаар дээр хадгалаад 0 дугаар дээрх элементийг хэвлэхэд 962 гарна. Харин 0 дугаар дээр шинээр элемент нэмэхэд 0 дугаар дээр байсан 962 тоо 1 дугаартай болж өөрчлөгдөнө. Таны програм элемент анх нэмэгдсэн дугаараараа хандагдах боломжтой байх тохиолдолд дээрх асуудал тулгарна.

List<T>-ийн оронд Hashtable-ийг хэрэглэх нь бидэнд элемент бүр рүү түлхүүр хандах боломжийг өгнө. Дээрх жишээг өргөтгөж, түлхүүрээр нь тоглогчийн нэрийг сонгоё:

Hashtable scores = new Hashtable();
scores.Add("Phil", 196); // boxing
scores.Add("Jon", 250);
scores.Add("Scott", 750);
scores.Add("Jeff", 901);

Console.WriteLine("Phil's Score is: " + scores["Phil"]);

Дээрх жишээний сул тал нь санах ой эзэлнэ.

Dictionary класс нь Hashtable-тэй ерөнхийдөө төстэй. Hashtable нь түлхүүр болон утгын төрлийг Object-оор сонгодог байхад, Dictionary нь тэр хоёрын утгыг тодорхойлж өгөх боломжийг олгодог. Ингэснээр тогтмол төрөлтэй /strongly typed/ Hashtable-ийг үүсгэнэ гэсэн үг. Dictionary-гаас өгөгдөл авах нь boxing-unboxing үүсгэдэггүй учраас үйлдэл маш хурдан хийгдэнэ. Одоо жишээ харцгаая:

Dictionary<string, int> scores = new Dictionary<string, int>();
scores.Add("Phil", 196); // boxing үүсэхгүй
scores.Add("Jon", 250);
scores.Add("Scott", 750);
scores.Add("Jeff", 901);
Console.WriteLine("Phil's Score is: " + scores["Phil"]);

SortedList ба SortedDictionary

Дээр дурьдсан тоглоомын жишээг үргэлжлүүлэн, бидний програм тоглогчдын оноо руу дугаар болон түлхүүрийн аль хүссэнээрээ хандах хэрэгтэй гэж бодъё.  Жишээлбэл, тоглогчдын нэрсийн эхний үсгийн эрэмбийн дагуу оноог авдаг гэе. Энэ тохиолдолд Hashtable ашиглавал эрэмбэлсэний дараа элементүүд хуучин байрандаа үлдэхгүй.

Энэ тохиолдолд SortedList болон SortedDictionary классууд нэн тохиромжтой. Эдгээр классуудын интерфейс ижилхэн ч гэсэн энэ удаад SortedList-ийг түлхүү авч үзье. Дараах кодыг харцгаая:

SortedList<string, int> scores = new SortedList<string, int>();
scores.Add("Phil", 196);
scores.Add("Jon", 250);
scores.Add("Scott", 750);
scores.Add("Jeff", 901);
Console.WriteLine("Scores in alphabetical order");
foreach(string key in scores.Keys){
Console.WriteLine("{0}: {1}", key, scores[key]);
}
// Элементүүд рүү түлхүүрээр нь хандах боломжтой.
Console.WriteLine("Phil's Score is: " + scores["Phil"]);

Хэдий тоглогчдын нэрс, оноог санамсаргүй байдлаар нэмсэн ч, тэдгээрийг дараалан уншиж авах үед оноонууд тоглогчдын нэрсийн дагуу эрэмбэлэгдсэн байна.

Jeff: 901
Jon: 250
Phil: 196
Scott: 750

Бид элементүүдээ дурын байдлаар эрэмбэлэхийн тулд IComparer-ийн тохиолдлыг ашиглах хэрэгтэй. Жишээ нь оноонуудыг тоглогчдын нэрсийн цагаан толгойн дарааллаар бус нэрсийн уртаар эрэмблэе гэвэл IComparer интерфейсийг хэрэгжүүлсэн жижиг хэмжээний класс бичих хэрэгтэй:

public class KeyLengthComparer : IComparer<string>
{
   public int Compare(string x, string y)
   {
      return x.Length.CompareTo(y.Length);
   }
}

Дараа нь уг классаа SortedList-ийн байгуулагч функц рүү дамжуулна:

SortedList<string, int> scores = new SortedList<string, int>(new KeyLengthComparer());

SortedList болон SortedDictionary-ийн алинг нь сонгох вэ? SortedList нь SortedDictionary-гаасаа санах ой бага эзэлдэг ба элементүүд рүү нь дугаараар хандах боломжтой. Хэрвээ таны программ их хэмжээний өгөгдөл хадгалах бол SortedList-ийг, бага хэмжээний өгөгдөл хадгалах болон элементүүд рүү дугаараар нь хандах шаардлагагүй бол SortedDictionary-г хэрэглээрэй.

By Boldkhuu Batbaatar with 6 сэтгэгдэл

6 сэтгэгдэл:

  • Byambaa says:

    Sainuu boldhvv, KTMS-d datastructure geheer yamar neg concrete helnii ogogdliin bvtetsiig vzdeg uu? Jishee ni C# iin ogogdliin butets, ArrayList gej yu we, yaj ashiglah wee geh metchilen? Eswel abstract mayagaar, programmchlaliin ali neg helnees hamaarahgui uhagdahuunaar ni sudalj bna u?

  • Сайн уу? КтМС-д Java хэлний Өгөгдлийн бүтцийг сонгон авч үздэг. Өгөгдлийн бүтцийн сан дээр нэмэлт функцууд нэмж сайжруулах, функцуудыг нь өөрчлөх, өгөгдлийн бүтцийг ашиглаж элдэв асуудал шийдэх гэх мэт.

  • Byambaa says:

    Yamar neg programming language -aas hamaarahgui, onol talaasaa. Surahad yamar ch computer shaardlagagui, tsaas harandaa l hereg boloh nom :D
    mongol heleer medeej. Delhiin tvwshind neegdchiheed baigaa effective data structure uud, google-iin search engine iin structure, dictionary dotor constant hurdaar hailt hiih, yamar neg range dotorh todorhoi neg shinj chanartai toog constant toon utgaar ilerhiilegdeh hurdaar oloh geh metchilen. textiig shugaman hurdaar comress hiih (linuxt ashiglagddag, windows ch bas ashigladag baih, closed system bolohoor yag ch medehgui l dee), bioinformatik dotorh geniin temdegtiin tsuwaag herhen shugaman hurdaad haritsuulah, hamgiin urt adil hesgiig oloh geh metchilen