Jak możemy zoptymalizować wstawianie w ArrayList?

Question

W rzeczywistości jest to pytanie zadane kilka dni temu.

Ankieter chce mi wyrazić różnicę pomiędzy ArrayList i LinkedList, i poprosił, aby zoptymalizować operację wstawiania na ArrayList, innymi słowy, aby ponownie wdrożyć add(int index, E element) i oczywiście złożoność get(int index) pracy może zostać zaprzepaszczone.

Moja odpowiedź polegała na odseparowaniu tablicy na pod-tablice k i zaktualizowaniu tablicy liczącej reprezentującej liczbę elementów już w odpowiedniej tablicy podrzędnej. A pamięć każdej pod-tablicy jest przydzielana dynamicznie z oczekiwanym początkowym rozmiarem. Kiedy muszę wstawić dane do ArrayList, mogę najpierw zlokalizować pod-tablicę i wykonać operację w małej tablicy. A jeśli wstawienia nie są zbyt częste lub indeksy są rozłożone równomiernie, złożoność czasu wstawiania może wynosić średnio O(log(k) + n/k + k), gdzie log(k) oznacza, że ​​powinniśmy najpierw zlokalizować tablicę podrzędną z wyszukiwaniem binarnym na tablicy sum liczników tablic, n/k jest dla przenoszenie danych lub nawet ponowne przydzielanie pamięci, a k oznacza aktualizację tablicy sum.

Jestem pewien, że istnieją lepsze rozwiązania. Potrzebuję sugestii, dzięki!

Answer 1

LinkedList jest połączoną listą z dostępem \ insert \ remove wymaga O (n), listy połączone obsługują dostęp sekwencyjny O (n).

ArrayList jest tablicą z insert \ remove wymaga O (2n), ale dostęp wymaga O (1), tablice obsługują dostęp losowy O (1).

znaleźć bardziej optymalnej struktury hybrydowe, można zacząć z tym:

template <T> 
public class LinkedArrayList 
{ 
    LinkedList<ArrayList<T>> list; 

    public LinkedArrayList() 
    { 
     list = new LinkedList<ArrayList<T>>(); 
    } 

    // .. 
} 

Będziesz musiał zrównoważyć segmenty (tablic) na liście pomiędzy dostępem złożoności i włóż \ usunąć złożoność

Answer 2

Można go zaimplementować w zbalansowanym drzewie binarnym, tak aby oba opcje dodawania() i get() kosztowały O (logn)

Przykładowa implementacja będzie wyglądać (ręcznie spreparowana tutaj, nie będzie się kompilować, przypadki narożników nie są pokryte):

class Node { 
    int subTreeSize; 
    Node left,right; 
    Element e; 
    // all i 0-indexed 
    Node get(int i) { 
    if (i >= subTreeSize) { 
     return null; 
    } 
    if (left != null) { 
     if(left.subTreeSize > i) { 
     return left.get(i); 
     } else { 
     i -= left.subTreeSize; 
     } 
    } 
    if (i == 0) { 
     return this; 
    } 
    return right.get(i-1); 
    } 

    // add e to the last of the subtree 
    void append(Element e) { 
    if(right == null){ 
     right = new Node(e); 
    } else { 
     right.append(e); 
     right = right.balance(); 
    } 
    subTreeSize += 1; 
    } 

    // add e to i-th position 
    void add(int i, Element e) { 
    if (left != null) { 
     if(left.subTreeSize > i) { 
     add(i,left); 
     left=left.balance(); 
     } else { 
     i -= left.subTreeSize; 
     } 
    } 
    if (i == 0) { 
     if (left == null){ 
     left = new Node(e); 
     } else { 
     left.append(e); 
     left = left.balance(); 
     } 
    } else { 
     if (right == null) { 
     // also in this case i == 1 
     right = new Node(e); 
     } else { 
     right.add(i-1, e); 
     right = right.balance(); 
     } 
    } 
    subTreeSize += 1; 
    } 
    // the common balance operation used in balance tree like AVL or RB 
    // usually just left or right rotation 
    Node balance() { 
    ... 
    } 
} 

public class Tree { 
    Node root; 
    public Element get(int i) { 
    return root.get(i).e; 
    } 
    public void add(int i, Element e) { 
    if (root == null) { 
     root = new Node(e); 
    } else { 
     root.add(i,e); 
     root = root.balance(); 
    } 
    } 
} 

Answer 3

Jednym z rozwiązań mogłoby być:

• add(int index, E element) zawsze dodać element do końca tablicy (trzeba również przechowywać indeks gdzie ten element powinien być dodana) - złożoność O (1)
• get(int index) jest przywrócenie prawidłowej kolejności matrycy (jeżeli niektóre elementy zostały dodane po ostatnim wezwaniem) - znając pozycję, w której każdy element powinien być może przywrócić prawidłową kolejność o (n)

Answer 4

Wariant z order statistic tree pozwoliłby na dodanie i pobranie według indeksu w O (log n).

Podstawowa idea jest następująca:

• mieć każdy sklep węzła wielkości poddrzewa zakorzenione w tym węźle.

• Indeks węzła będzie odpowiadał jego pozycji w drzewie in-order traversal.

  Oznacza to, że porządkowanie węzłów jest określane na podstawie miejsca w drzewie, w którym się pojawiają - nie jest tak, jak zwykle działa binary search tree, gdzie elementy węzłów mają pewne uporządkowanie, które nie jest zależne od miejsca w drzewie. pojawia się (np f jest większa niż a w regularnych BST nakazał leksykograficznie, ale w naszym przypadku f może być mniejsza lub większa niż a, ponieważ zamówione na podstawie indeksu od f i a).

• Aby dodać lub uzyskać, zaczynamy u nasady i rekursywnie przejść przez drzewa, ustalenie, czy nasza pozycja wkładka lub wyszukiwanie jest oparte na indeksie docelowej i wielkości poddrzewa w lewo lub w prawo.

  Dokładniej, mamy następujące definicje rekurencyjne:
  (z niektórymi dodaje złożoności dla zerowych węzłów i faktycznie wstawienie węzła)

  node.add(index, element): 
      if index <= left.subtreeSize 
       left.add(index, element) 
      else 
       // anything to the right is after left subtree and current node, so those must be excluded 
       right.add(index - left.subtreeSize - 1, element) 
  
  node.get(index, element): 
      if index == left.subtreeSize 
       return node 
      if index < left.subtreeSize 
       return left.get(index) 
      else 
       return right.get(index - left.subtreeSize - 1) 
  

Aby to lepiej zrozumieć, następujący przykład drzewo może Bądź pomocny:

Values:     Indices (in-order pos): Subtree sizes: 
    a       5       8 
/\      /\      /\ 
    b g      1 6      5 2 
/\ \     /\ \     /\ \ 
f c h     0 3 7     1 3 1 
/\      /\      /\ 
    e d      2 4      1 1 

Jeśli chcemy wstawić nowy węzeł w pozycji 5, na przykład zostanie wstawiony na prawo od d.

Poniżej znajduje się mały program testowy do zademonstrowania tego (tworzenie drzewa pokazanego powyżej).

Należy pamiętać, że nadal trzeba będzie wykonać balancing, aby uzyskać czas działania O (log n) na operację.

class Test 
{ 
    static class Node<T> 
    { 
     Node<T> left, right; 
     T data; 
     int subtreeCount; 
     Node(T data) { this.data = data; subtreeCount = 1; } 

     public String toString(int spaces, char leftRight) 
     { 
     return String.format("%" + spaces + "s%c: %s\n", "", leftRight, data.toString()) 
       + (left != null ? left.toString(spaces+3, 'L') : "") 
       + (right != null ? right.toString(spaces+3, 'R') : ""); 
     } 

     int subtreeSize(Node<T> node) 
     { 
     if (node == null) 
      return 0; 
     return node.subtreeCount; 
     } 

     // combined add and get into 1 function for simplicity 
     // if data is null, it is an get, otherwise it's an add 
     private T addGet(int index, T data) 
     { 
     if (data != null) 
      subtreeCount++; 
     if (index == subtreeSize(left) && data == null) 
      return this.data; 
     if (index <= subtreeSize(left)) 
     { 
      if (left == null && data != null) 
       return (left = new Node<>(data)).data; 
      else 
       return left.addGet(index, data); 
     } 
     else if (right == null && data != null) 
      return (right = new Node<>(data)).data; 
     else 
      return right.addGet(index-subtreeSize(left)-1, data); 
     } 
    } 

    static class TreeArray<T> 
    { 
     private Node<T> root; 
     public int size() { return (root == null ? 0 : root.subtreeCount); } 

     void add(int index, T data) 
     { 
     if (index < 0 || index > size()) 
      throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size()); 
     if (root == null) 
      root = new Node<>(data); 
     else 
      root.addGet(index, data); 
     } 

     T get(int index) 
     { 
     if (index < 0 || index >= size()) 
      throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size()); 
     return root.addGet(index, null); 
     } 

     @Override 
     public String toString() { return root == null ? "Empty" : root.toString(1, 'X'); } 
    } 

    public static void main(String[] args) 
    { 
     TreeArray<String> tree = new TreeArray<>(); 
     tree.add(0, "a"); 
     tree.add(0, "b"); 
     tree.add(1, "c"); 
     tree.add(2, "d"); 
     tree.add(1, "e"); 
     tree.add(0, "f"); 
     tree.add(6, "g"); 
     tree.add(7, "h"); 
     System.out.println("Tree view:"); 
     System.out.print(tree); 
     System.out.println("Elements in order:"); 
     for (int i = 0; i < tree.size(); i++) 
     System.out.println(i + ": " + tree.get(i)); 
    } 
} 

ten wyjścia:

Tree view: 
X: a 
    L: b 
     L: f 
     R: c 
      L: e 
      R: d 
    R: g 
     R: h 
Elements in order: 
0: f 
1: b 
2: e 
3: c 
4: d 
5: a 
6: g 
7: h 

Live demo.