Докладний аналіз структур даних. Частина 1. Введення в структури даних




Ця стаття – перша стаття в серії
з шести частин, присвяченої важливим структурам даних та їх використання при
розробці додатків. Ми розглянемо структури даних, які присутні в
. NET Framework, а також інші важливі структури даних, які нам доведеться
створювати самим. Ця стаття – перша в серії – присвячена визначенню
поняття структур даних, до того як проводити аналіз їх ефективності і чому
такий аналіз важливий. Також, в цій статті ми розглянемо класи Array і
ArrayList.


Введення
Аналіз ефективності структур даних
Улюблена лінійна, однорідна структура даних з прямим доступом

ArrayList – неоднорідний масив змінного розміру
Висновок


Введення


Ласкаво просимо! Ви дивитеся першу із шести статей у серії, присвяченій
структурам даних в. NET. У цій серії статей ми будемо розглядати різні
структури даних. Деякі з них включені в базову бібліотеку класів. NET
Framework Base Class Library, інші ми створимо самі. Структури даних
це абстрактні структури або класи, які використовуються для організації
даних і надають різні операції над цими даними. Найбільш
поширеною і загальновідомою структурою даних є масив
(array)
, Який містить безперервну сукупність елементів даних, до
яким можна отримати доступ за допомогою порядкового індексу.


Перед тим як заглибитися в матеріал цієї статті, давайте поглянемо на те, що
чекає нас попереду. Якщо ви вважаєте, що якісь важливі теми відсутні в цьому
списку, автор буде радий, якщо ви повідомите йому про свої думки за адресою mitchell@4guysfromrolla.com. Автор
із задоволенням додасть ваші доповнення до відповідного розділу або, якщо це
буде необхідно, напише сьому статтю до даної серії.


У першій статті ми розглянемо питання про важливість структур даних і про те, як
вони впливають на ефективність алгоритмів. Для визначення того, як структури
даних впливають на продуктивність програм, нам знадобиться розглянути, як
ми можемо суворо проаналізувати різні операції, що виконуються структурами
даних. В кінці ми звернемося до двох структурам даними, присутніх в. NET
Framework — Array (масив) І ArrayList (масив змінного
розміру
). Напевно, ви вже використовували раніше обидві ці структури даних у
своїх проектах. У першій статті ми розглянемо операції, які надають
ці структури даних і проаналізуємо ефективність цих операцій.


У другій частині ми більш детально досліджуємо клас ArrayList
разом з його близнятами: класами Queue (чергу) І
Stack (стек). Як і ArrayList, Класи
Queue і Stack зберігають безперервну колекцію
даних і присутні в базовій бібліотеці класів. NET Framework. Однак, в
відміну від ArrayList, З якого ми можемо отримати
довільний елемент даних, черги і стеки дозволяють отримувати доступ
до даних лише в певному послідовному порядку. Ми розглянемо деякі
застосування черг і стеків, і побачимо, як реалізувати обидва ці класу, розширюючи
клас ArrayList. Після "метушні" з чергами і стеками ми
розглянемо хеш-таблиці, які, як і ArrayList, Надають
прямий доступ до своїх елементах, проте зберігають дані індексованими по
строковому ключу.


У той час, як ArrayList ідеально підходить для зберігання
вмісту та надання прямого доступу до нього, він не є кращим
вибором, коли нам необхідно здійснювати пошук серед даних. У Частині 3 ми
вивчимо двійкове дерево пошуку (binary search tree data structure), В
якому пошук можна здійснювати набагато еффектівнеe, ніж у
ArrayList. До складу. NET Framework не входять вбудовані класи,
реалізують двійкові дерева, так що нам доведеться написати свої
власні.


Ефективність пошуку за допомогою бінарного дерева залежить від порядку, в якому дані
були вставлені в дерево. Якщо дані вставляються в відсортованому або майже
відсортованому порядку, то виграш від використання двійкового дерева замість
ArrayList значно падає. Для обходження цього недоліку в
Частини 4 ми розглянемо цікаву рандомізованих структуру даних –
листковий список або skip-список (SkipList). Скіп-списки
володіють ефективністю пошуку двійкового дерева, проте нечутливі до
впорядкованості, що вводяться.


У Частині 5 ми звернемо нашу увагу на структури даних, що використовуються для
подання графів. Граф – це сукупність вузлів (nodes) і
ребер (edges), Що з'єднують різні вузли. Наприклад, ми можемо
уявити собі карту автошляхів, як граф з містами як вузли і шосе
між містами в якості ребер. Дуже багато реальних практичних завдань можна
абстрактно описати в термінах графів, що робить їх часто використовуваної
структурою даних.


І нарешті, в частині 6 ми поглянемо на структури даних, представляють
безлічі (sets)
і непересічні безлічі (disjoint sets).
Безліч – це невпорядкована сукупність елементів. Непересічні
множини – це сукупність множин, які не мають спільних елементів. Як безлічі
так і неперескающіеся безлічі знаходять безліч застосувань в програмах,
які ми детально і розберемо в останній частині.


Аналіз ефективності структур даних


У процесі міркування над конкретним додатком або програмістської завданням
багато програмістів (включаючи мене) знаходять більш цікавим процес написання
алгоритму для вирішення певної проблеми або додавання нової "навороченої"
функціональності в додаток з тим, щоб зробити його більш зручним для
користувачів. При цьому рідко, якщо взагалі коли-небудь, ви почуєте захоплені
вигуки про те, яка структура даних використовується в додатку. Хоча,
правильний вибір структур даних для конкретного алгоритму може дуже
значно вплинути на його продуктивність. Типовий приклад – це пошук
елемента в структурі даних. У випадку використання звичайного масиву, цей
процес займає час пропорційне числу елементів масиву. Двійкові
дерева пошуку або скип-списки, вимагають сублінейного часу. При здійсненні
великої кількості пошуків вибір структури даних має вирішальне значення для
швидкості роботи програми, яка може бути виміряна секундами, а іноді й
хвилинами.


А раз структура даних, яка використовується в алгоритмі може значно вплинути
на швидкість його роботи, важливо мати строгу процедуру порівняння ефективності
різних структур даних. Нас, як розробників, які використовують структури
даних, головним чином цікавить те, як змінюється ефективність структури
даних із зростанням об'єму інформації. А саме, як впливає додавання
кожного нового елемента, на швидкість виконання операцій над даними.


Розглянемо приклад, в якому наша програма використовує метод
System.IO.Directory.GetFiles(path) для отримання списку всіх
файлів в заданнном каталозі в вигляді строкового масиву. Тепер, уявіть, що
вам захотілося дізнатися, чи є серед отриманих файлів XML-файл (тобто файл із
розширенням .xml). Можливе рішення – це переглянути
послідовно весь масив і при знаходженні xml-файлу змінити значення
деякого прапора. Код буде виглядати, наприклад, так:

using System;
using System.Collections;
using System.IO;

public class MyClass
{
public static void Main()
{
string [] fs = Directory.GetFiles (@ "C: Inetpubwwwroot");
bool foundXML = false;
int i = 0;
for (i = 0; i < fs.Length; i++)
if (String.Compare (Path.GetExtension (fs [i]), ". xml", true) == 0)
{
foundXML = true;
break;
}

if (foundXML)
Console.WriteLine ("XML file found -" + fs [i]);
else
Console.WriteLine("No XML files found.");

}
}


Неважко помітити, що в найгіршому випадку, коли XML-файл є останнім
елементом або коли він взагалі відсутній, нам доведеться рівно 1 раз переглянути
кожен елемент масиву. Для аналізу ефективності масиву при сортуванні ми
повинні задати собі таке запитання: "Припустимо, у нас є масив з n
елементів. Якщо ми додамо один елемент в масив, так що їх кількість стане
рівним n + 1, Яке буде при цьому новий час виконання
алгоритму? ". (Термін час виконання, Всупереч своїй назві, не
означає абсолютний час виконання програми в секундах, а скоріше, він означає
число кроків, яке повинна вчинити програма для виконання даної конкретної
завдання. При роботі з масивами кількістю таких кроків буде кількість разів,
яке програма зчитує елементи масиву). Для знаходження конкретного
значення елемента масиву нам потенційно доведеться відвідати всі його елементи.
Таким чином, якщо у нас є n + 1 елемент, нам
буде потрібно виконати n + 1 перевірок. Це означає, що
час пошуку в масиві лінійно залежить від числа його елементів.


Тип оцінок, розглянутих нами називається асимптотичними оцінками,
оскільки ми аналізуємо, як ефективність структури даних змінюється при
обсягами збережених даних, що прагне до нескінченності. У асимптотичному аналізі
зазвичай використовують позначення "О-велике". За допомогою даного позначення
складність пошуку у масиві можна записати, як O(n). Тут
n – Розмір масиву, а фраза "складність пошуку у масиві залежить від числа
його елементів як O(n) Означає, що число кроків, які потрібні
для перебування елемента масиву лінійно залежить від його розміру. Тобто із зростанням
числа елементів масиву кількість кроків, необхідних для здійснення пошуку
буде пропорційно розміру масиву. Більш систематичним методом обчислення
асимптотичного часу виконання блоку коду буде наступна нескладна
процедура:



  1. Визначте дії, що становлять час виконання алгоритму. Як вже було
    згадано, у разі масиву, розглянутими діями будуть читання і запис
    елементів масиву. Ці дії можуть бути іншими для інших структур даних.
    Зазвичай нам хочеться розглядати дії, які несуть сенс на рівні
    структури даних, а не найпростіші атомарні операції, виконувані комп'ютером.
    Наприклад, у фрагменті коду, наведеному вище, я обчислював час виконання,
    підраховуючи лише те, скільки разів необхідно отримувати доступ до елементів масиву,
    не беручи до уваги час, необхідний для створення та ініціалізації
    змінних або перевірки на рівність двох рядків.
  2. Знайдіть у коді рядки, в яких виконуються дії, які ви
    підраховуєте. Напишіть 1 навпроти кожної такої рядки.
  3. Для кожного рядка, поряд з якою ви написали 1, перевірте, чи не входить
    вона в цикл. Якщо так, то помножте цю одиничку на максимальну кількість ітерацій,
    яке може бути виконано в циклі. Якщо у вас є кілька вкладених
    циклів, множте послідовно на максимальну кількість ітерацій для кожного
    циклу.
  4. Серед чисел, записаних вами відшукайте максимальне. Це і буде час
    виконання.

Давайте спробуємо застосувати цей метод до фрагмента коду, наведеного вище.
Ми вже з'ясували, що дії, які нас цікавлять і які ми будемо
підраховувати – це доступ до елементів масиву. Переходячи до пункту 2, помічаємо що
у нас присутні 2 рядки в яких ми отримуємо доступ до елементів масиву
fs – Як параметр методу String.Compare() і в методі
Console.WriteLine(). Отже, ставимо позначку 1 навпроти кожної з цих
рядків. Після цього переходимо до пункту 3 і помічаємо, що доступ до fs
в методі String.Compare()відбувається всередині циклу, которsq
виповнюється максимум n разів (де n – Розмір масиву). Отже,
перекреслюємо одиничку в циклі і замінюємо її на n. В кінці ми бачимо, що
максимальне значення – це n, а значить час виконання блоку коду можна
записати як O(n).


O(n) Або лінійний час – це лише один з нескінченного числа
можливих варіантів асимптотичного часу виконання програми. Серед інших
варіантів, наприклад, O(log2 n), O(n
log2 n), O(n2),
O(2n) І так далі. Навіть не заглиблюючись у математичні нетрі
асимптотичного аналізу, зрозуміло, що чим менше порядок члена в дужках
O(*), Тим більше ефективність даної структури даних.
Наприклад, програма, що виконується за логарифмічне час O(log
n) Більш ефективна, ніж програма, що виконується за лінійний час
O(n), Оскільки при великих n справедливо нерівність log n
< n.


Примітка. У разі якщо вам необхідно коротке нагадування з
області математики, рівність loga b = y еквівалентно
ay = B. Таким чином, log2 4 = 2, тому що 22 = 4.
Аналогічно, log2 8 = 3, тому що 23 = 8. Очевидно, що
log2 n зростає набагато повільніше, ніж саме n.
Наприклад, коли n = 8, log2 n = 3. У Частині 3 ми
розглянемо двійкові дерева, пошук в яких здійснюється за час
O(log2 n).


Протягом всієї серії статей, ми будемо підраховувати час виконання різних
операцій для різних структур даних і порівнювати їх один з одним.


Улюблена лінійна однорідна структура
даних з прямим доступом – масив


Масив – одна з найпростіших і найбільш широко застосовуються в комп'ютерних
програмах структур даних. У будь-якій мові програмування масиви мають
кілька загальних властивостей:



Типові операції для масивів включають:



Коли в C # оголошується масив, його значення дорівнює null.
Наприклад, наступний рядок коду просто створює змінну з ім'ям
booleanArray , Яка дорівнює null:

bool [] booleanArray;

Перш, ніж почати роботу з масивом, ми повинні виділити певне
кількість елементів. Синтаксично це виглядає так:

booleanArray = new bool[10];

Або більш узагальнено:

arrayName = new arrayType[allocationSize];

Цією рядком ми виділяємо безперервний блок пам'яті у керованій купі
міжмовної середовища виконання (CLR-managed heap), розмір якого дорівнює
allocationSize, Помноженому на розмір елемента типу
arrayType. Якщо arrayType – Розмірний тип (value
type), то створюються allocationSize розпакованих (unboxed)
екземплярів типу arrayType. Якщо arrayType – Контрольний
тип (reference type), то створюються allocationSize посилань на об'єкти
типу arrayType. (Якщо ви не знайомі з відмінностями між розмірними і
посилальними типами CLR і тим, коли змінні розміщуються у керованій купі чи
стеку – ознайомтеся зі статтею Understanding
.NET”s Common Type System)


Щоб остаточно розібратися з тим, як в. NET Framework зберігається
внутрішній вміст масиву, розглянемо наступний приклад:

bool [] booleanArray;
FileInfo [] files;

booleanArray = new bool[10];
files = new FileInfo[10];


Тут, booleanArray – Масив елементів розмірного типу
System.Boolean, А files – Це масив елементів
посилального типу System.IO.FileInfo. На рисунку 1 показано стан
керованої купи CLR після виконання цих чотирьох рядків коду.


Малюнок 1. Вміст масиву виділяється у вигляді безперервного блоку пам'яті
у керованій купі CLR


Важливо пам'ятати, що 10 елементів масиву files є посиланнями
на примірники типу FileInfo. На Малюнку 2 ця ситуація видно
особливо чітко. На ньому показано вміст пам'яті, якщо ми призначимо деяким
елементам масиву files екземпляри типу
FileInfo.


Малюнок 2. Вміст масиву розташовується непрервивно у керованій
купі.


Всі масиви в. NET дозволяють як зчитувати вміст їх елементів, так і
записувати в них. Синтаксис для доступу до елемента масиву виглядає таким
чином:

 / / Читання елемента масиву
bool b = booleanArray[7];

/ / Запис в елемент масиву
booleanArray[0] = false;


Час доступу до елементу масиву записується як O(1), тому що воно
одно константі. Тобто незалежно від кількості елементів у масиві час
читання / запису одного елемента завжди одне і те ж. Цей час доступу постійно
лише завдяки тому, що елементи масиву зберігаються в пам'яті послідовно і
безперервно, отже, для доступу до елемента масиву необхідно знати лише
адреса в пам'яті першого елемента масиву, розмір кожного елемента масиву і номер
елемента, до якого необхідний доступ.


Важливо розуміти, що в керованому коді (managed code) знаходження елемента
масиву (array lookups) відбувається трохи більш складним чином через те, що
при кожному доступі до елементу масиву CLR перевіряє, що запитуваний індекс
знаходиться в межах кордонів масиву. Якщо зазначений індекс потрапляє за кордону
масиву, то відбувається виключення IndexOutOfRangeException. Така
перевірка гарантує, що при проходженні масиву ми випадково не вийдемо за
межі останнього індексу масиву і не зіпсуємо дані, записані в цій
області пам'яті. Варто відзначити, що ці перевірки не впливають на ефективність
масиву, оскільки час витрачається на них не збільшується з збільшенням
розміру масиву.


Примітка. Такі перевірки кордонів масиву лише трохи зменшують
продуктивність додатків, які багато разів здійснюють доступ до елементів
масиву. Проте, за допомогою оголошення коду некерованим (unmanaged code), можна
обійти перевірку меж масиву. Про це докладно написано в Главі 14 книги Дж.
Ріхтера "Програмування на платформі Microsoft. NET Framework“.


При роботі з масивом вам може знадобитися змінити число елементів,
яке цей масив повинен утримувати. Для цього вам доведеться створити новий
примірник масиву необхідного розміру, а потім скопіювати вміст старого
масиву в новий масив нового розміру. Цей процес називають зміною розміру
масиву (redimensioning) і його можна здійснити за допомогою наступного коду:

using System;
using System.Collections;

public class MyClass
{
public static void Main()
{
/ / Створення масиву цілих чисел з 3 елементів
int [] fib = new int[3];
fib[0] = 1;
fib[1] = 1;
fib[2] = 2;

/ / Зміна розміру до 10 елементів
int [] temp = new int[10];

/ / Копіювання масиву fib в temp
fib.CopyTo(temp, 0);

/ / Привласнимо масиву temp значення fib
fib = temp;
}
}


Після виконання останнього рядка коду, fib посилається на масив
з 10 елементів типу Int32. Елементи з 3-го по 9-й в масиві fib
будуть мати значення за замовчуванням для типу Int32 – 0.


Масиви є чудовою структурою даних, якщо ми хочемо зберігати
колекцію однорідних типів, до яких ми хочемо мати прямий доступ. Пошук в
відсортованого масиву займає лінійне від розміру масиву час. Це
прийнятно, якщо ми працюємо з малими масивами, або коли нам потрібно лише
зрідка проводити пошук всередині масиву. Якщо ж ваш додаток зберігає великі
масиви, в яких часто проводиться пошук, то існують структури даних
набагато краще пристосовані до таких ситуацій. Ми розглянемо деякі з них
в наступних статтях цієї серії. (Пам'ятаєте, що якщо ви здійснюєте пошук в
масиві по деякому ключу, а масив відсортований з цього ключа, ви
завжди можете використовувати алгоритм двійкового пошуку, складність якого
O(log n), Що еквівалентно часу пошуку в двійкових деревах. На
Насправді, клас Array містить статичний метод BinarySearch().
Більш докладно це метод описаний у більш ранній статті автора Efficiently
Searching a Sorted Array.


Примітка . NET Framework підтримує також і багатовимірні масиви.
Багатовимірні масиви, Як і одномірні вимагають постійного часу для
доступу до своїх елементах. Згадайте, що час пошуку в n-елементному масиві
одно O(n). Для двовимірного масиву розміром nxn
час пошуку дорівнюватиме O (n2), Тому що процедура пошуку повинна
буде переглянути n2 елементів. У більш загальному випадку, час пошуку в
k-Мірному масиві є O (nk).


ArrayList – неоднорідний масив
змінного розміру


Незважаючи на те, що звичайні масиви, безумовно, знаходять широке застосування,
вони накладають певні обмеження на програміста, оскільки кожен
масив може зберігати дані тільки одного типу (однорідність) до того ж перед
використанням масиву ви повинні виділити (allocate) певну кількість
елементів. Однак, часто розробникам хочеться чогось більш гнучкого – просту
колекцію об'єктів потенційно різного типу, з якими можна було б просто
працювати, не турбуючись про питання, пов'язані з виділенням
елементів (allocation). Базова бібліотека класів. NET Framework містить таку
структуру даних. Вона називається System.Collections.ArrayList.


У шматочку коду, наведеному нижче, демонструється ArrayList в дії.
Зауважте, що якщо ми використовуємо ArrayList, то ми можемо додати в нього будь-який
тип, причому ніяких дій щодо виділення пам'яті виконувати не потрібно. На ділі
виходить, що в ArrayList можуть бути додані елементи будь-якого типу. Більше
того, нам більше не потрібно піклуватися про зміну розміру ArrayList. Всі ці
дії проводяться для нас за кулісами.

ArrayList countDown = new ArrayList();
countDown.Add(5);
countDown.Add(4);
countDown.Add(3);
countDown.Add(2);
countDown.Add(1);
countDown.Add("blast off!");
countDown.Add(new ArrayList());

А за лаштунками ArrayList використовує System.Array типу
object. Оскільки всі типи є прямими або непрямими
спадкоємцями object, Масив екземплярів типу object
може містити елементи довільного типу. За замовчуванням ArrayList створює
масив з 16 елементів типу object, Хоча точний розмір може бути
зазначений через параметр конструктора у властивості Capacity. При додаванні
елемента за допомогою методу Add() число елементів у внутрішньому масиві
звіряється з розміром масиву. Якщо операція додавання елемента викликає
перевищення числа елементів масиву над його розміром, то розмір автоматично
подвоюється (redimensioned).


ArrayList, як і звичайний масив, використовує індекс для доступу до своїх
елементів за допомогою аналогічного синтаксису:

 / / Читання елемента
int x = (int) countDown[0];
string y = (string) countDown[5];

/ / Запис даних
countDown[1] = 5;

/ / ** Буде згенерований ВИКЛЮЧЕННЯ ArgumentOutOfRange **
countDown[7] = 5;


Оскільки ArrayList зберігає масив об'єктів, ви повинні явним чином привести
(Explicitly cast) лічене з ArrayList значення до того типу даних, який
зберігався в даному елементі ArrayList-а. Також зауважте, що якщо ви спробуєте
послатися на елемент ArrayList-а номер, якого більше, ніж розмір ArrayList-а,
буде згенеровано виняток System.ArgumentOutOfRange.


Хоча ArrayList забезпечує додаткову гнучкість в порівнянні із звичайним
масивом, досягається ця гнучкість за рахунок швидкості роботи, особливо якщо ви
зберігайте в ArrayList-е розмірні типи (value types). Згадайте, що масив
розмірних типів – таких як System.Int32,
System.Double, System.Boolean, І т.д. – Зберігається в
безперервній області пам'яті керованої купи в розпакованої формі (unboxed
form). Внутрішній масив ArrayList-а при цьому є масивом посилань на
екземпляри типу object. Тому, навіть якщо ваш ArrayList не зберігає нічого, крім
розмірних типів, кожен елемент ArrayList-а є посиланням на упакований
розмірний тип (boxed value type), як показано на Малюнку 3.


Малюнок 3. ArrayList містить безперервну область посилань на примірники
типу object


Процеси пакування та розпакування, поряд з наявністю додаткових накладних
витрат при зберіганні розмірних типів у ArrayList-е, можуть негативно позначитися
на продуктивності вашого додатка при використанні великих ArrayList-ів з
великою кількістю операцій читання / запису. Як показує Рисунок 3,
використання пам'яті для посилальних типів виглядає однаково як у випадку
використання звичайних масивів, так і ArrayLists-ів.


Автоматична зміна розміру ArrayList-а не повинно викликати погіршення
продуктивності в порівнянні з масивом. Якщо вам відомо точно число
елементів, яка повинна зберігатися в ArrayList-е, ви просто можете відключити
автоматичне зміна розміру, вказавши початковий розмір в конструкторі
ArrayList-а. Якщо точний розмір вам неізестен, навіть у разі використання
масиву, вам знадобитися збільшувати його розмір, якщо число вставляються
елементів перевищує розмір масиву.


Класичною завданням computer science є визначення того, скільки
місця необхідно виділяти при закінченні пам'яті в деякому буфері (області
пам'яті). Одне рішення соcтоіт в тому, щоб додатково виділити тільки один
елемент з пам'яті буфера. Тобто при додаванні елемента в заповнений масив з 5
елементів, розмір масиву стане рівним шести. Очевидно, що даний підхід
є найбільш економним, однак він може бути занадто дорогим, тому
що за кожною вставкою нового елемента після заповнення масиву слід
зміна його розміру.


Діаметрально протилежний підхід полягає у збільшенні розміру масиву в
100 разів при закінченні наявності вільного місця в ньому для вставки нових
елементів. Тобто після заповнення масиву з 5 елементів при спробі додавання
6-го елемента розмір масиву буде змінений до 500 елементів. Ясно, що такий
підхід грандіозно зменшує число змін розміру масиву, проте якщо лише
небагато елементів будуть додані в масив, величезна кількість вільної пам'яті
буде витрачено даремно.


Перевіреним на практиці компромісом рішення даної проблеми є просте
подвоєння поточного розміру масиву, коли закінчується вільне місце для нових
елементів. Тобто для масиву, в якому було спочатку виділено 5 елементів,
додавання шостого елемента викличе збільшення розміру масиву до 10 пунктів.
Це як раз і робить клас ArrayList і, що найприємніше, він робить усе
це за вас.


Асимптотичне час виконання операції ArrayList-а така ж, як і у
звичайного масиву. Незважаючи на те, що при роботі з ArrayList-му дійсно
виникають додаткові накладні витрати, особливо при зберіганні розмірних
типів, співвідношення між числом елементів ArrayList-а і вартістю виконання
операцій не відрізняється від стандартного масиву.


Висновок


Дана стаття відкрила обговорення структур даних, фокусуючись на тому, чому
вивчення струтуре даних важливо. Були описані способи аналізу ефективності
використання структур даних. Цей матеріал важливий для підрахунку часу
виконання різних операцій структур даних і є корисним інструментом
при виборі тієї або іншої структури даних для конкретної програмістської
завдання.


Після вивчення того, як слід аналізувати структури даних, ми
звернулися до дослідження двох найбільш поширених структур даних у
базової бібліотеці класів. NET Framework – класам System.Array і
System.Collections.ArrayList. Масиви дозволяють зберігати безперервний блок
однорідних типів. Основна їх перевага полягає у виключно малому часі
доступу до своїх елементах для читання і запису. Слабке місце масивів –
дорожнеча пошуку в них, тому що при пошуку в відсортованого масиву ми
потенційно повинні відвідати кожен елемент масиву.


ArrayList є більш гнучкою массівоподобной структурою даних. Він може
містити дані різних типів, використовуючи масив object-Ів. Більше
того, ArrayList не вимагає явного виділення елементів і може самостійно
розширюватися у міру додавання елементів.


У наступній статті нашої серії ми звернемо увагу на класи Stack і
Queue. Ми також розглянемо асоціативні масиви (associative arrays),
які являють собою масиви, елементи яких індексується не
цілочисловим, а строковим значенням. Асоціативні масиви присутні в
базової бібліотеці класів. NET Framework у вигляді класу Hashtable.



Переклад – Станіслав Воног, Московський фізико-технічний інститут

Схожі статті:


Сподобалася стаття? Ви можете залишити відгук або підписатися на RSS , щоб автоматично отримувати інформацію про нові статтях.

Коментарів поки що немає.

Ваш отзыв

Поділ на параграфи відбувається автоматично, адреса електронної пошти ніколи не буде опублікований, допустимий HTML: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

*

*