我们怎样才能在ArrayList的优化插入？ [英] How can we optimize insertion on ArrayList?

问题描述

其实，这是一个面试问题前几天问。

In fact this is a interview question asked a few days ago.

面试官要我EX preSS 的ArrayList 和的LinkedList 之间的区别，并要求优化在 ArrayList中的插入操作，换句话说，重新实现添加（INT指数，E元素）和当然了获取的复杂性（INT指数）皆可抛操作。

The interviewer wants me to express the difference between ArrayList and LinkedList, and asked to optimize the insertion operation on ArrayList, in other words, to re-implement add(int index, E element) and of course the complexity of get(int index) operation can be sacrificed.

我的回答是分开阵列分成k子阵列和更新计数阵列重新$ P $相应子阵列中psenting元素的数量已经。与每个子阵列的存储器是动态一个具有预期的初始大小分配。当我需要插入数据到的ArrayList ，我可以先找到一个子阵列，并做一小阵内的操作。  如果插入不是太频繁或索引是均匀分布的，插入的时间复杂度为 O（日志（K）+ N / K + K）的平均水平，其中，日志（K）表示，我们应该首先找到子阵列与计数阵列的总和阵列， N / K 为数据移动或甚至内存的重新分配，和k代表总和阵列的更新

My answer was to separate the array into k sub-arrays and update a counting array representing the number of elements already in the corresponding sub-array. And the memory of every sub-array is allocated dynamically with an expected initial size. When I need to insert a data into the ArrayList, I can locate a sub-array first, and do the operation within a small array. And if insertions are not too frequent or the indexes are uniform distributed, the time complexity of inserting can be O(log(k) + n/k + k) in average, where log(k) means we should locate the sub-array first with binary searching on the counting array's sum array, n/k is for data movement or even memory re-allocation, and k stands for the updating of the sum array.

我敢肯定有更好的解决方案。我确实需要一些建议，谢谢！

I'm sure there are better solutions. I do need some suggestions, thanks!

推荐答案

您可以在一个平衡二叉树实现它，这样既增加（）和get（）成本O（LOGN）

You can implement it in a balanced binary tree, so that both add() and get() cost O(logn)

这是示例实现的样子（这里是手工制作的，将无法编译，不是盖的拐角例）：

An example implementation will look like (hand-crafted here, will not compile, corner cases not covered):

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();
    }
  }
}

这篇关于我们怎样才能在ArrayList的优化插入？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！