Изборът на правилната структура на данните може да направи вашата програма по-ефективна. Ето ръководство, което ще ви помогне да направите правилния избор.

Изборът на най-добрата структура от данни за вашите цели може да бъде предизвикателство с множество налични опции. Когато избирате структура от данни, вземете предвид данните, с които ще работите, операциите, които трябва да се извършат върху данните, и средата, в която ще се изпълнява вашето приложение.

Разберете вашите данни

Разбирането на данните, с които ще работите, преди да изберете структура от данни, е жизненоважно. Общи структури от данни които работят с различни типове данни, включват масиви, свързани списъци, дървета, графики и хеш таблици.

Например, когато трябва да получите произволен достъп до елементи от вашите данни, масивите може да са най-добрият избор. В случай, че постоянно трябва да добавяте или изтривате елементи от списък и размерът на списъка също може да се промени, тогава свързаните списъци могат да бъдат особено полезни.

instagram viewer

Когато трябва ефективно да съхранявате множество нива на данни, като структури на записи, и да извършвате операции като търсене и сортиране, тогава дърветата са полезни.

Когато трябва да опишете взаимодействията между обекти, като тези в социалните мрежи, и да извършите операции като най-кратък път и свързаност, тогава се предпочитат Графиките. Хеш таблиците са полезни за бързо търсене на ключове.

Помислете за операциите, които трябва да се извършат върху данните

Докато избирате структура от данни, трябва да вземете предвид и операциите, които ще се извършват върху данните. Различните структури от данни оптимизират множество действия, като сортиране, търсене, вмъкване и изтриване.

Например свързаните списъци са по-добри за действия като вмъкване и изтриване, но двоичните дървета са най-добри за търсене и сортиране. Хеш таблицата може да бъде най-добрият избор, ако вашето приложение изисква едновременно вмъкване и търсене.

Оценете околната среда

Когато разглеждате структура от данни, трябва да оцените средата, в която ще работи приложението. Средата влияе върху това колко добре и колко бързо са достъпни структурите от данни.

Обърнете внимание на следните фактори, когато оценявате текущото си състояние:

  1. Мощност на обработка: Изберете структури от данни за вашите приложения, които работят добре на персонални компютри с малка процесорна мощност, докато работят на платформата. Например по-прости структури от данни като масиви могат да бъдат по-подходящи от дървета или графики.
  2. Паралелност: Трябва да изберете безопасна за нишки структура на данни, която може да обработва едновременен достъп без повреда на данните; ако вашето приложение работи в едновременна среда, където множество нишки или процеси имат достъп до структурата на данните едновременно. В този случай структури от данни без заключване като ConcurrentLinkedQueue и ConcurrentHashMap може да са по-подходящи от традиционните като ArrayListand HashMap.
  3. Латентност на мрежата: Ако вашето приложение изисква прехвърляне на данни през мрежа, трябва да имате предвид латентността на мрежата, докато избирате най-добрата структура на данните. В такива ситуации използването на структура от данни, която ограничава мрежовите повиквания или намалява обема на трансфер на данни, може да помогне за подобряване на изпълнението.

Общи структури от данни и техните случаи на използване

Ето обобщение на няколко популярни структури от данни и тяхната употреба.

  1. Масиви: Това е проста и ефективна структура от данни, която може да съдържа поредица от елементи с фиксиран размер от един и същи тип данни. За да работят правилно, те се нуждаят от бърз, директен достъп до конкретни обекти чрез индекс.
  2. Свързани списъци: Свързаните списъци са съставени от възли, които съдържат елемент и препратка към следващия възел и/или предишен възел. Поради ефективните си операции, свързаните списъци са най-подходящи в ситуации, изискващи често вмъкване или изтриване на елементи. Достъпът до отделни елементи по индекс в свързаните списъци обаче е по-бавен в сравнение с масивите.
  3. Опашки и стекове: Купчините се придържат към правилото Last-In-First-Out (LIFO), където последният вмъкнат елемент е първият премахнат елемент. Опашките се управляват от принципа „първи влязъл, първи излязъл“ (FIFO). където първият добавен елемент е и първият изтрит.
  4. Хеш таблици: Хеш таблиците са форма на структура от данни, която съдържа двойки ключ-стойност. Най-доброто решение е да използвате хеш-таблици, когато броят на компонентите е непредвидим и имате нужда от бърз достъп до стойностите по ключ.
  5. дървета: Дърветата са йерархични структури от данни, които могат да съхраняват група от елементи в йерархия. Най-добрите приложения за двоични дървета за търсене са в йерархични структури от данни, където връзките между елементите от данни могат да представляват дървовидна структура.

Избор на правилната структура на данните

Преди да изберете структура от данни, помислете за данните, задълженията и средата на вашето приложение. Докато правите своя избор, помислете за следните елементи:

  1. Времева сложност: Ефективността на вашето приложение може да бъде значително повлияна от времевата сложност на вашата структура от данни. Ако вашето приложение изисква чести операции за търсене или извличане, използвайте структура от данни с намалена времева сложност, като хеш таблица.
  2. Космическа сложност: Пространствената сложност на структурата от данни е друго важно съображение. Ако приложението ви изисква много памет, изберете структура от данни с по-малко пространствена сложност, като например масив. Ако пространството не е проблем, можете да използвате структура от данни с по-голяма пространствена сложност, като например дърво.
  3. Прочетете срещу Операции за писане: Ако вашето приложение използва много операции за запис, изберете структура от данни с по-бързо вмъкване, като хеш таблица. Ако вашето приложение изисква много операции за четене, изберете структура от данни с по-бърза скорост на търсене, като например двоично дърво за търсене.
  4. Тип данни: Данните, с които работите, може също да повлияят на избраната от вас структура на данните. Например, можете да използвате дървовидна структура от данни, ако вашите данни са йерархични. Ако имате прости данни, които трябва да бъдат достъпни на случаен принцип, изборът на структура от данни, базирана на масив, може да бъде най-добрият вариант.
  5. Налични библиотеки: Помислете за библиотеките, които са лесно достъпни за структурата на данните, която обмисляте. Може да бъде по-лесно за изпълнение и поддръжка, ако вашият език за програмиране има налични вградени библиотеки за определена структура от данни.

Следващият пример на Python демонстрира как да изберете най-добрата структура на данни за конкретен случай на употреба.

Помислете за случая, в който разработвате приложение за файлова система, което трябва да съхранява и извлича файлове в йерархия. Трябва да изберете структура от данни, която може ефективно да представи тази йерархична структура и бързо да изпълнява операции като търсене, вмъкване и изтриване.

Може да е добра идея да използвате дървовидна структура от данни като двоично търсене или B-дърво. Ако броят на записите във всяка директория е относително малък и дървото не е много дълбоко, бинарното дърво за търсене ще работи добре. B-дърво би било по-подходящо за по-голям брой файлове и по-дълбоки структури на директории.

По-долу е даден пример за двоично дърво за търсене в Python.

класВъзел:
деф__в него__(аз, стойност):
 self.value = стойност
 self.left_child = Нито един
 self.right_child = Нито един


класДвоично дърво за търсене:


деф__в него__(себе си):
 self.root = Нито един
дефвмъкнете(аз, стойност):


ако self.root еНито един:
 self.root = Възел (стойност)


друго:
 self._insert (стойност, self.root) 
деф_вмъкнете(самостоятелно, стойност, текущ_възел):


ако стойност < current_node.value:
ако текущ_възел.ляво_дете еНито един:
 current_node.left_child = Възел (стойност)


друго:
 self._insert (стойност, current_node.left_child)
елиф стойност > current_node.value:
ако текущ_възел.дясно_дете еНито един:
 current_node.right_child = Възел (стойност)
друго:
 self._insert (стойност, current_node.right_child)


друго:
 печат („Стойността вече съществува в дървото.“)
дефТърсене(аз, стойност):
ако self.root енеНито един:
връщане self._search (стойност, self.root)


друго:
връщанеНевярно
деф_Търсене(самостоятелно, стойност, текущ_възел):


ако стойност == current_node.value:
връщанеВярно


елиф стойност < current_node.value и текущ_възел.ляво_дете енеНито един:
връщане self._search (стойност, current_node.left_child)


елиф стойност > текущ_възел.стойност и текущ_възел.дясно_дете енеНито един:
връщане self._search (стойност, current_node.right_child)
друго:
връщанеНевярно

В тази реализация вие конструирате два класа: a Двоично дърво за търсене клас, който управлява операциите за вмъкване и търсене и a Възел клас, който символизира възел в двоичното дърво за търсене.

Докато методът за вмъкване вмъква нов възел в подходящото място в дървото в зависимост от неговата стойност, методът за търсене търси възел с определена стойност. Времевата сложност на двете операции в балансирано дърво е O(log n).

Изберете оптималната структура на данните

Скоростта и адаптивността на вашето приложение могат значително да се подобрят чрез структурата на данните, която сте избрали. Вземането под внимание на вашите данни, вашите операции и вашата среда може да ви помогне да изберете най-добрата структура на данните.

Важни са съображения като времева сложност, пространствена сложност, операции за четене срещу запис, паралелност, тип данни и достъпност на библиотеката.

Като оценявате теглото на всеки компонент, трябва да изберете структурата на данните, която отговаря на нуждите на вашето приложение.