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

У рачунарству, имплицитне структуре података су структуре података које користе веома мало меморије поред стварних елемената података, односно веома мало информација осим главних података се чувају у овим структурама. То су шеме за складиштење које не садрже показиваче и представља датотеку од н к-торки које су сачуване као једноставна матрица димензије н са к, из које се подаци читају брже. Код имплицитних структура података, једина структурна информација која се чува је информација која омогућава да низ расте и да се н смањује. Ни једна друга информација није обавезна. Овакве структуре података се зову "имплицитне" јер је већина структуре елемената имплицитно изражена по њиховом реду. Још један термин који се користи као синоним је просторна ефикасност. Дефиниције "веома малог" нису прецизне и могу значити од О(1) до О(н) додатног простора. Свему се приступа у-месту, читајући битове на различитим позицијама у подацима. Да би се постигло оптимално кодирање, користимо битове уместо бајтова. Имплицитне структуре података су често, такодје, и сажете структуре података (структуре података које заузимају мало простора за податке).

Иако би се већина сложила да простор на диску данас није проблем и да не треба да се оптерећујемо бринући о побољшању искоришћености простора, проблем за који су имплицитне структуре података дизајниране да побољшају је проблем коришћења главне меморије. Хард дискови, или било који други уредјаји за чување велике количине података, као и У/I уредјаји су много спорији од главне меморије. Дакле, што већи проценат задатака може да стане у бафере у главној меморији то је мања зависност на спорим У/I уредјајима. Дакле, ако већи комад имплицитне структуре може да стане у главну меморију, операције извршене у њој могу бити брже чак и ако асимптотско време извршавања није толико добро колико његова просторна сложеност. Осим тога, пошто је кеш меморија централно процесорске јединице обично много мања од главне меморије, имплицитне структуре података могу побољшати ефикасност кеш меморије, његову брзину рада, поготово ако се користи метод побољшавања на просторној сложености.

Имплицитне дата структуре за тежинске елементе

За презентацију елемената различитих тежина постоји неколико структура података. Структуре користе јос једну локацију поред обавезних за вредности елемената. Прва структура подржава најгори случај временске претраге у смислу рангирања тежина елемената. Ако елементи нису сортирани, онда варијација ове структуре користи просечно време.

Примери

Примери имплицитних структура података укључују и

• Бинарни хип
• Двородитељски хип

Спољашње везе

• Погледати чланке од Ј. Иан Мунро, Грег Фредерицксон.