Эффективность различных способов хранения изменяемый массив

Question

Для класса программирования некоторое время назад мы получили сравнительно простую задачу, суть которой можно свести к:

хранить массив (не a) n Строки, где n всегда < = m, позволяющий добавлять новые строки и старые, которые необходимо удалить. (В данном случае, м было 50)

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

Друг A пошел на реализацию того, что было по существу ArrayList; создавая новый массив с другим размером и помещая все элементы из исходного массива в новый с циклом for (плюс или минус тот, который он добавлял/удалял).

Друг В просто создан массив длины м, удаляя элементы, установив их значение нулевое значение (например, array[13] = null), и добавление элементов путем не мокрой очистки вперед от индекса 0 до тех пор, пустое место было найдено (это было for петля).

Друг С [Me] также создал массив длиной м, но сдвинуты каждое следующее значение вперед (т.е. уменьшается их индекс на 1 с for цикла), когда строка была удалена, так что п - 1 всегда был индексом последнего значения (когда n> 0), а n также был индексом для добавления новых значений в (исключая цикл for для добавления строк).

Это довольно простой класс, и им все равно , как мы сделали это до тех пор, пока мы это сделали, но нам любопытно.

Редактировать: Я только что понял, что я забыл что-то важное. Проблема указала удаление строк на значение (например, removeString("someString")), а не индекс, что также потребовало определения значения (и его индекса).

Answer 1

Возможно, не правильный ответ, потому что создаваемые вами массивы в конце концов реализуются для системы. Так что это зависит от системных требований. Но, как правило, с учетом эффективности:

• Решение друга А представляется мне неприятным. Создание нового массива для Добавление/удаление элемента - это потеря памяти и циклов процессора. И также я считаю, что это не так, как ArrayList реализован на Java.

• Решение друга B, имеет такую ​​же худшую временную сложность, как и у . Друг C, однако, он может работать намного лучше.Поскольку порядок строк не имеет значения, это выглядит лучше.

• Решение друга C , на самом деле довольно эффективно. Что касается добавления elemnt, у вас уже есть индекс i.e. n. Следовательно, он также должен хорошо выполнять .

Однако, как я уже говорил, это зависит от системы, которую реализует. Но только, чтобы обернуть его, я должен сказать, A < B = C.

Digvijay

Answer 2

Для меня ваша версия efficeint всех. Просто если вы устраните цикл с System.arraycopy. Причина состоит в том, что A имеет цикл для каждого добавляемого массива. B имеет два для петель, и у вас есть только один.

Я создал образец программы вашей версии с System.arraycopy, и я думаю, что это самый эффективный способ сделать это.

import java.util.Arrays; 

public class Sample { 

private int currentIndex = 0; 
private String[] strings = null; 

public Sample(int length) { 
    strings = new String[length]; 
} 

public Sample(String[] strs) { 
    if(strs == null) 
     throw new NullPointerException(); 
    strings = strs; 
} 

public boolean add(String str) { 
    if (currentIndex == strings.length) 
     return false; 
    strings[currentIndex++] = str; 
    return true; 

} 

public boolean remove(int index) { 
    if (index >= strings.length) 
     return false; 
    System.arraycopy(strings, index + 1, strings, index, (strings.length 
      - index - 1)); 
    strings[--currentIndex] = null; 
    return true; 
} 

public boolean remove(String value) { 
    if (value == null || value.isEmpty()) { 
     return false;// we are saved since value is null or empty;) 
    } 
    for (int count = 0; count < strings.length; count++) { 
     if (value.equals(strings[count])) { 
      remove(count); 
      break; 
     } 
    } 
    return true; 
} 

/** 
* @param args 
*/ 
public static void main(String[] args) { 
    Sample sample = new Sample(5); 
    sample.add("a"); 
    sample.add("b"); 
    sample.add("c"); 
    sample.add("d"); 
    sample.add("e"); 
    sample.remove("a"); 

    System.out.println(Arrays.toString(sample.strings)); 

} 

}