Скуп (структура података)

Из Википедије, слободне енциклопедије

У рачунарству, скуп је апстрактна структура података која може да складишти одређене вредности. Ондоси се на имплементацију математичког концепта коначног скупа. Елементи скупа су организовани без експлицитног уређења и хијерархије и без понављања вредности. За разлику од већине других врста колекција, обично се испитује припадност елемента скупу а не тражи се његова вредност.

Неке скуповне структуре дизајниране су за статичку употребу и не мењају се након што су направљене. Статички скупови дозвољавају само операције упита над својим елементима - као што су провере да ли вредност припада скупу, или набрајања вредности у неком произвољном редоследу. Друге варијанте називају се динамички или променљиви скупови, и они дозвољавају уметање или брисање елемената из скупа.

Теорија типова[уреди]

У теорији типова, скупови су одређени својом индикатор функцијом (карактеристичном функцијом): према томе, скуп вредности типа А може се означити са 2^{A} или \mathcal{P}(A). Карактеристична функција F скупа A се дефинише као:

F(x) = \begin{cases}
  1, & \mbox{if } x \in A \\
  0,  & \mbox{if } x \not \in A
\end{cases}

У теорији, многе друге апстрактне структуре података могу се посматрати као скуповне структуре са додатно дефинисаним операцијама и/или правилима наметнутих стандардним операцијама. На пример, хип се може посматрати као скуповна структура са дефинисаном операцијом min(A) која враћа елемент најмање вредности.

Операције[уреди]

Конкретана реализација у неком програмском језику би могла да имплементира неки од наведених интерфејса.

Опште скуповне операције[уреди]

Могу се дефинисати следеће операције алгебре скупова:

  • unija(A,B): враћа унију скупова A и B.
  • presek(A,B): враћа пресек скупова A и B.
  • razlika(A,B): враћа разлику скупова A и B.
  • podskup(A,B): предикат који проверава да ли је скуп A подскуп скупа B.

Статички скупови[уреди]

Типичне операције за статички скуп су:

  • da_li_pripada(n, A): проверава да ли је вредност n у скупу A.
  • da_li_je_prazan(A): проверава да ли је скуп А празан.
  • veličina(A) или kardinalnost(A): враћа број елемената у A.
  • iterator(A): враћа функцију која враћа следћу вредност из А приликом сваког позива, у неком произвољном редоследу.
  • nabrajanje(A): враћа листу која садржи елементе из А у неком произвољном редоследу.
  • napravi(k1, k2, ... ,kn): ствара одређену структуру са вредностима к1, к2, ... , кn.
  • napravi_od(kolekcija): ствара нови скуп структуру која садржи све елементе дате колекције.

Динамички скупови[уреди]

Динамичке структуре обично имају::

  • stvori(): ствара нови, почетно празан скуп.
  • stvori_sa_kapacitetom_N(n): креира нови скуп, у почетку празан, али у стању да држи до n елемената.
  • dodaj(A,k): додаје елемент k на А, ако већ није присутан.
  • izbaci(A,k): уклања елемент k из А, ако је присутан.
  • kapacitet(A): враћа максималан број вредности које се могу сачувати у A.

Неке структуре могу дозволити само неке од ових операција. Ефикасност сваке операције ће зависити од реализације, а можда и од вредности које се налазе у скупу или редоследа којим су уметнуте.

Додатне операције:[уреди]

Постоје многе друге операције које могу бити дефинисане, као што су:

  • pop(A): враћа произвољан елемент из А и брише га.
  • map(F,A): враћа скуп различитих вредности које проистичу из примене функција F на сваки елемент из А.
  • ocisti(A): избрисати све елементе из A.
  • jednaki(A,B): проверава да ли је скуп A једнак B (тј. садржи све и само те исте елементе).

Друге операције могу да се дефинишу за скупове са елементима посебног типа:

  • zbir(A): враћа збир свих елемената A за неку дефиницију "збира".
  • najbliži(A,k): враћа елемент из A који је најближи вредности k (по неком критеријуму).
  • min(A), max(A): враћа минимални / максимални елемент из A.

Имплементација[уреди]

Скупови се могу имплементирати коришћењем различитих структура података, који пружају различите компромисе временске и просторне сложености за различите операције. Неке имплементације су дизајниране да побољшају ефикасност специјализованих операција, као што су najblizi или unija. Имплементације за "општу употребу" обично настоје да оптимизују операције element_od, dodati, izbrisati. Једноставан начин је да се користи листа, игноришући редослед елемената и водећи рачуна да се избегне понављање вредности. Ово је једноставна, али неефикасна имплементација, како су операције попут da_li_pripada или obrisi_element сложености O(n), јер захтевају пролазак кроз целу листу. Скупови су често имплементирани помоћу ефикаснијих структура података као што су разне врсте дрвећа или хеш табела.

Други популарни начини имплементације укључују низове. Посебно, скуп целих бројева 1 .. n се може ефикасно имплементирати као n-битни битски низ, који такође подржава веома ефикасне операције уније и пресека.

Подршка у прогамским језицима[уреди]

Један од најранијих језика са подршком за скупове је био Паскал. Данас, у многим језицима постоји подршка било у основном језику или у стандардној библиотеци.

  • Java нуди Set интерфејс за подршку за рад са скуповима.
  • Python има уграђне типове set и frozenset од верзије 2.4, а од 3.0 i 2.7, подржава непразан скуп коришћењем витичастих заграда, нпр: {x, y, z}.
  • .NET Framework пружа генеричке HashSet i SortedSet класе које имплементирају генерички ISet интерфејс.
  • Ruby стандардна библиотека укључује модул који садржи set и Set and SortedSet класе које имплементирају скупове помоћу хеш табеле, а други омогућава итерацију у сортираном редоследу.
  • C++, стандардна библиотека шаблона (STL) обезбеђује шаблон set, који имплементира сортиран скуп користећи бинарно претраживачко дрво.

Спољашње везе[уреди]