Проређени низ
| Овај чланак је започет или проширен кроз пројекат семинарских радова. Потребно је проверити превод, правопис и вики-синтаксу. Када завршите са провером, допишете да након |проверено=. |
У рачунарству, проређени низ је низ у коме већи број елемената има исту вредност (подразумевана вредност је углавном 0 или нулл). Појава нула елемената у великом низу је веома неефикасна како за рачунање тако и за смештање истих. Низ у коме је велики број нула елемената претендује да буде проређен.
У случају проређених низова, може се затражити вредност са "празног" места у низу. У том случају, за низ бројева враћа се вредност 0, а за низ неких других података враћа се вредност НУЛЛ.
Проста имплементација низа може алоцирати простор за цео низ, али у случају када је неколико неподразумевајућих вредности, таква имплементација није ефикасна. Обично је алгоритам који се користи уместо обичног низа окарактерисан другим познатим особинама низа. На пример, ако је проређеност унапред позната или су елементи сложени према некој функцији.
Хип, меморијски алокатор, у програму може да изабере да сачува делове празног простора у повезаној листи пре него што би сачувао све алоциране делове у такозвани битовски низ.
Приказ
уредиПроређен низ може бити приказан као:
Спарсе_Арраy[{пос1 -> вал1, пос2 -> вал2,...}] или
Спарсе_Арраy[{пос1, пос2,...} -> {вал1, вал2,...}]
где су вредности проређеног низа смештене на одговарајућим позицијама .
Проређени низ као повезана листа
уредиОчигледно је питање зашто нам је потребна повезана листа за представљање проређеног низа, ако га можемо једноставно представити користећи обичан низ. Одговор на ово питање лежи у чињеници да приликом приказивања проређеног низа као обичног низа, велика количина меморије је алоцирана за 0 или НУЛЛ елементе. На пример, узмимо у обзир следћу декларацију:
- доубле арр[1000][1000];
Када декларишемо овај низ, алоцирали смо неопходан простор за 1000000 вредности типа доубле. Како сваки доубле захтева 8 бајтова у меморији, овај цео низ затева 8 милиона бајтова у истој. Зато што је ово проређени низ, многи његови елементи имају вредност 0 (или НУЛЛ). Отуда ће декларисање овог низа упити сав простор што ће резултовати расипање меморије (у поређењу са низом чија је меморија алоцирана само за не-нула елементе). Ефикасан начин да се превазиђе овај проблем је да се низ представи као повезана листа која захтева мање меморије, јер су смештени само не-нула елементи. Такође, када се користи повезана листа, приступ елементима низа се врши кроз мањи број итерација него у обичном низу.
Проређени низ као повезана листа садржи чворове међусобно повезане. У једнодимензионалном низу, сваки чвор се састоји од "индекса" (позиције) не-нула елемента и "вредности" на тој позицији, и показивача на "следећи" чвор(због повезивања са следећим чвором), а чворови су повезани у истом реду као и индекси. У случају дводимензијоналних проређених низова, сваки чвор се састоји од индекса за врсту, индекса за колону, вредности на тој позицији и показивача на следећи елемент.