En sparse array är en abstrakt representation av en vanlig array , där data inte presenteras kontinuerligt, utan fragmenterad; de flesta av dess element har samma värde (standardvärdet, vanligtvis 0 eller null). Att lagra ett stort antal nollor i en array är dessutom ineffektivt både för lagring och bearbetning av arrayen.
En gles array kan komma åt odefinierade element. I det här fallet kommer arrayen att returnera något standardvärde.
Den enklaste implementeringen av denna array allokerar utrymme för hela arrayen, men när det finns få icke-standardvärden är denna implementering ineffektiv. Funktioner för att arbeta med vanliga arrayer tillämpas inte på denna array i de fall där sparsiteten är känd i förväg (till exempel vid lagring av data i block).
En gles array representeras vanligtvis som en associativ array :
Sparse_Array[{pos1 -> val1, pos2 -> val2,…}]eller Sparse_Array[{pos1, pos2,…} -> {val1, val2,…}],där varje position pos i motsvarar värdet val i . Denna metod används för att spara minne (både nyckeln och värdet bär information).
En länkad lista används här istället för en vanlig array eftersom, för det första, en vanlig array kräver utrymme för att lagra odefinierade värden. Till exempel när du deklarerar:
double arr[1000][1000];8 MB minne kommer att tilldelas på en gång (8 byte per värde × 1 000 000 värden), vilket är ett omotiverat slöseri med minne. I fallet med en länkad lista lagras inte tomma värden, och utrymme för nya värden allokeras automatiskt när element läggs till eller tas bort (i det här fallet kan vi prata om dynamisk minnesallokering ).