Dynamické pole

Dynamické pole (Vector, ArrayList) je datový kontejner (struktura určená k uchovávání dat) postavený nad polem. Dynamické pole umožňuje přidávat libovolný počet prvků, čímž eliminuje hlavní nevýhodu klasického pole – fixní velikost.

Princip

Dynamické pole ukládá své prvky do vnitřního pole fixní délky, v okamžiku, kdy je kapacita pole vyčerpána, dojde k alokaci nového většího pole (obvykle 2x většího z důvodu amortizace), všechny prvky původního pole se překopírují a staré pole se dealokuje. Obdobným způsobem se kontejner zachová, je-li příliš prázdný (poměr neobsazenosti překročí určitou mez) - zaalokoje se přiměřeně menší pole a opět se do něj hodnoty překopírují.

Složitost operací

Vkládání

Na první pohled je postup při vkládání prvku neefektivní, protože v okamžiku, kdy dojde místo, musí ArrayList veškerá data překopírovat. Asymptotická složitost vkládání prvku je proto O(n) .

Amortizovaná složitost vkládání

Pokud program běží dostatečně dlouho, tak se tato složitost vkládání amortizuje. To znamená, že se náklady na provedení této operace určitým způsobem v čase rozloží.

Představme si, že každému prvku dáme 2k+1 mincí (kde k je nějaká konstanta), kterými může platit za operace, které s ním nakládají. První minci prvek utratí při vložení do pole, si jich může ponechat v banku na později.

V okamžiku, kdy je pole velikosti n plné, tak je v banku přesně $k \\cdot n$ mincí (pole bylo po minulé realokaci pouze z poloviny prázdné – natahujeme jej vždy dvojnásobně). Nyní kontejner vytvoří nové pole a kopíruje veškeré prvky. Za každé přenesení prvku z banku vezme k mincí (přenesení stojí k operací). Po překopírování všech prvků je bank prázdný a celou tuto proceduru ukládání a přenášení prvků můžeme opakovat.

Protože je 2k+1 konstanta (k je konstanta), tak je amortizovaná složitost vkládání O(1) , jelikož jak amortizovaná, tak asymptotická složitost, ignorují multiplikativní konstanty.

Díky amorizované složitosti je struktura dynamického pole velmi rychlá, ač by tomu asymptotická složitost jejích operací nenapovídala. Na druhou stranu není její použití vhodné v real-time systémech, které musí garantovat určitou odezvu, protože vždy může dojít k onomu jednotlivému nepříznivému případu.

Mazání

Složitost operace mazání prvku závisí na konkrétní implementaci. Pokud mazaný prvek pouze prohodíme s posledním prvkem a místo na konci kontajneru uvolníme (prohlásíme za neobsazené), tak asymptotická složitost bude O(1) , ale dojde ke zpřeházení prvků. Pokud odstranění provedeme tak, že všechny další prvky posuneme o jedno místo, bude asymptotická složitost O(n) , ale pořadí prvků zůstane zachováno.

Čtení

Čtení prvku na indexu i proběhne v O(1) , protože pole umožňuje náhodný přístup.

Kód:

Java

 public class ArrayList {
     private final int defaultSize;
     private int size;
     private int[] array;
     
     /**
      * Konstruktor - vychozi kapacita listu je 4
      */
     public ArrayList(){
         this(4);  
     }
 
     /**
      * Konstruktor, lze nastavit vychozi delku listu, pod tuto nebude nikdy zkracen
      * @param size
      */
     public ArrayList(int size){
         this.size = 0;
         this.defaultSize = size;
         array = new int[size];
     }
 
     /**
      * Prida prvek do arraylistu
      * @param i prvek k pridani
      */
     public void add(int i){
         if(getSize() == array.length){
             this.enlarge();
         }
         array[size] = i;
         size++;
     }
 
     /**
      * Odstrani prvek na zadanem indexu
      * @param index index prvku k odstraneni
      */
     public void remove(int index){
         array[index] = array[getSize() - 1];
         size--;
         trim();
     }
 
     /**
      * Vrati prvek na zadanem indexu
      * @param index index prvku
      * @return pozadovany prvek
      */
     public int get(int index){
         if(index >= getSize()) throw new IndexOutOfBoundsException("mimo meze");
         return array[index];
     }
 
     /**
      * Prodlouzi pole o polovinu, pokud je plne
      */
     private void enlarge(){
         int[] newArray = new int[getSize() * 2];
         for (int i = 0; i < getSize(); i++) {
             newArray[i] = array[i];
         }
         array = newArray;
     }
 
    /**
     * Pokud je pole plne mene nez z ctvrtiny, tak ho zkratime na polovinu 
     * (pokud by to nebylo mene, nez je vychozi delka)
     */
     private void trim(){
         if((array.length/4) > getSize() && array.length/2 >= getDefaultSize()){
             int[] newArray = new int[array.length/2];
             for (int i = 0; i < getSize(); i++) {
                 newArray[i] = array[i];
             }
             array = newArray;
         }
     }
 
     @Override
     public String toString() {
         StringBuilder builder = new StringBuilder();
         for (int i = 0; i < size; i++) {
             builder.append(array[i]);
             builder.append(" ");
         }
         builder.append("\\narray.length: ");
         builder.append(array.length);
         builder.append(", size: ");
         builder.append(size);
         builder.append(", default size: ");
         builder.append(defaultSize);
         return builder.toString();
     }
 
     /**
      * Getter na vychozi delku pole
      * @return vychozi delka pole
      */
     public int getDefaultSize() {
         return defaultSize;
     }
 
     /**
      * Vrati pocet prvku ulozenych v poli 
      * @return pocet ulozenych prvku
      */
     public int getSize() {
         return size;
     } 
 }