Создание лучшего ArrayList

Когда вы вставляете в ArrayList в начале или середине списка, который вы всегда будете иметь O(n) производительность, но вставка в конце может поддерживать O(1) потому что вы просто привязываете его к концу списка.

У меня есть идея высокого уровня о том, как сделать вставку в начале O(1) и сделать O(n) вставки в среднем O(n/2) но я не уверен, что это возможно с базовой структурой массива.

Моя идея

Так как ArrayList на самом деле это просто больший массив, который "изменяет размеры" себя, когда достигает порогового значения, почему он не может изменить размеры как в начале, так и в конце списка, а не только в конце? Это позволило бы вставки в начале O(1) в то же время позволяя вам переписать вставку в середине, чтобы выбрать самый короткий путь для вставки. (Например, если вы вставляете в индекс 1было бы легче двигаться 0 над чем двигаться 2 в n).

Я думаю, что ответ Sun почему-то не сделал это из-за того, как Arrays.copyOf и, соответственно, System.arrayCopy написаны. Оба начинаются с начала списка и копируются в больший массив. Я взглянул на исходный код Sun для этих двух методов, но он немного продвинулся до уровня моих навыков Java.

Вопросы

На мой взгляд, есть два основных вопроса относительно того, будет ли это работать или нет:

1) Во-первых, может Arrays.copyOf или же System.arrayCopy быть переписан / перегружен, чтобы вставить подмассив в середину большего массива?

2) Каковы будут большие последствия этого?

Так что это хорошая идея или я упускаю что-то очевидное, что сделало бы это неосуществимым?

Заранее спасибо!

Источник

3 ответа

Решение

Ваша идея полностью работоспособна, и она будет иметь большой смысл для реализации deque, где распространенным случаем является добавление и удаление элементов на обоих концах. Это не имеет большого смысла для ArrayList потому что 99% его случаев использования только когда-либо добавляют к концу.

Что касается ваших вопросов о природе System.arraycopyЯ не уверен, что полностью вас понимаю

а) да, вы можете использовать arraycopy перезаписать середину одного массива содержимым другого, и

б) arraycopy не вставляется в массив, потому что эта операция не имеет никакого значения для массивов фиксированного размера Java.

Наиболее близким к идее "вставки в массив" является создание совершенно нового, большего массива и arraycopyсоответствующие диапазоны из двух входных массивов. Результат - лучшее, что вы можете получить.

Источник

То, что вы описываете, не соответствует идее ArrayList,

Порядок элементов ArrayList определяются порядком, в котором они вставляются (в этом случае вы всегда будете добавлять их в конец, если вы, конечно, не указали индекс).

Если порядок определяется значением членов объектов, а не порядком вставки, то вы хотите LinkedList,

Источник

Да, вы можете сделать вставку в начале такой же эффективной, как вставку в конце. Вам просто нужно начинать заполнять вспомогательный массив посередине, а не с индекса 0. Для этого вам не нужна другая System.arraycopy, см. Пример кода ниже.

Вместо того, чтобы просто хранить резервный массив (data) и текущий sizeВы также сохраняете текущий start смещение, и принять это во внимание соответственно.

BetterArrayList<T> extends AbstractList<T> {
  private int size;   // Used elements in data.
  private int start;  // Position of element 0 in data.
  private T[] data;   // data.length is the current total capacity.

  public BetterArrayList<T>(int initialCapacity) {
    data = new Object[initialCapacity];
    start = initialCapacity / 2;
    size = 0;
  }

  public void add(int index, T value) {
    if (index < size / 2) {  // Insert at the front or end?
      if (start == 0) {
        realloc(data.length * 2);
      }
      System.arraycopy(data, start, data, start - 1, index);
      start--;
    } else {
      if (size + start == data.length) {
        realloc(data.length * 2);
      }
      System.arraycopy(data, start + index, 
                       data, start + index + 1, size - index);
    }
    data[start + index] = value;
    size++;
  }    

  public T get(int index) {
    if (index < 0 || index >= size) {
      throw new IndexOutOfBoundsException();
    }
    return data[start + index];
  }

  private void realloc(int newCapacity) {
    T[] newData = new Object[newCapacity];
    int newStart = newCapacity - size / 2;
    System.arraycopy(data, start, newData, newStart, size);
    start = newStart;
    data = newData;
  }

  public T set(int index, T value) {
    Value old = get(index);
    data[size + index] = value;
    return old;
  }

  public int size() {
    return size;
  }
}

Я бы предположил, что Sun не пошла по этому пути, потому что она тратит больше памяти в типичном случае использования для списков массивов (который добавляется в конце). И вы получаете только более эффективные вставки спереди, вставка в любом другом месте все равно будет O(n), потому что содержимое все еще необходимо сместить.

Кстати: в зависимости от вашего варианта использования, но вас может заинтересовать структура данных Rope: http://en.wikipedia.org/wiki/Rope_%28data_structure%29

Источник
Другие вопросы по тегам