Докладний аналіз структур даних. Частина 1. Введення в структури даних, Алгоритми на. NET, ASP, статті




Ця стаття – перша стаття в серії з шести частин, присвяченої важливим структурам даних та їх використання при розробці додатків. Ми розглянемо структури даних, які присутні в . 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>

*

*