|
Java форум JavaTalks
форум программистов
|
|
|
|
| Предыдущая тема :: Следующая тема |
| Автор |
Сообщение |
sergioblog : 2
Новичок
|
 Дек 29, 2011 20:26 |
 |
|
Вопрос нубский, но беглый поиск в гугле вскрыл пару холиваров, а однозначного ответа на вопрос не дал.
Итак, есть программа, работающая с массивом классов. Классов в массиве может быть очень много, но сразу скажу, что память меня не сильно волнует. Волнует скорость.
В реалтайме происходят следующие операции:
1. Перебор всех элементов массива
2. Доступ к i-му элементу массива
3. Добавление элемента в массив (при этом индекс не важен)
Как происходит операция 3. Изначально задана константа N (максимальное число элементов), и при старте приложения создается массив размера N, в котором создается N элементов (т.е. память выделяется только один раз в самом начале). Переменная n (текущее число элементов) равна нулю. Далее если мы хотим добавить в массив элемент, мы либо инициализируем n-й элемент нужными значениями (и делаем n++), либо ищем среди n первых элементов неинициализированный и используем его. Если нам нужно удалить i-й элемент, мы не очищаем память, а помечаем его как неинициализированный.
Надеюсь, понятно написал Это сделано, чтобы не выделять память в реалтайме и минимизировать частоту запуска сборщика мусора.
Пример реализации:
| Код: |
public class Element {
public final static int N = 100000;
public static Element[] array;
public static int n;
public int info;
public boolean initialized;
public static void allocate() {
array = new Element[N];
for (int i = 0; i < N; i++) {
array[i] = new Element();
}
}
public static void addElement(int _info) {
for (int i = 0; i < n; i++) {
if (!array[i].initialized) {
array[i].init(_info);
return;
}
}
array[n].init(_info);
n++;
}
public static void iterate() {
Element e;
for (int i = 0; i < n; i++) {
e = array[i];
if (e.initialized) {
//do something
}
}
}
public Element() {
initialized = false;
}
public void init(int _info) {
info = _info;
initialized = true;
}
public void delete() {
initialized = false;
}
}
|
Массив для данной задачи хорошо подходит, поскольку:
1. операции перебора и доступа к элементу массива быстры
2. не требуется выделять и очищать память в реалтайме
Однако, необходимо определить константу N, что оставляет место для потенциальной ошибки, когда заранее невозможно предсказать сколько будет данных. Так что массив не подходит.
Отсюда вопрос, что использовать вместо массива?
Учитывая описанные условия, конечно (не требуются такие вещи, как вставка в середину, удаление и т.п.).
И аргументируйте, пожалуйста.
Заранее спасибо. |
|
|
|
 |
pjotar : 453
Бывалый
Откуда: Санкт-Петербург
|
| Дек 29, 2011 21:42 |
| |
|
| sergioblog писал(а): |
В реалтайме происходят следующие операции:
1. Перебор всех элементов массива
2. Доступ к i-му элементу массива
3. Добавление элемента в массив (при этом индекс не важен)
|
Это требования к структуре данных. Им удовлетворяет List. Поскольку изменяете Вы только добавлением в конец - подходит ArrayList.
Почему тема называется "Быстрый ассоциативный массив"? |
|
|
|
|
sergioblog : 2
Новичок
|
| Дек 29, 2011 21:59 |
| |
|
| pjotar писал(а): |
| подходит ArrayList |
Ок, попробуем. Спасибо.
| pjotar писал(а): |
| Почему тема называется "Быстрый ассоциативный массив"? |
Не придумал как назвать по-другому |
|
|
|
|
sgdread : 2184
JT Библиотекарь
Откуда: USA
|
| Дек 30, 2011 11:36 |
| |
|
Обычно ассоциативными массивами называют структуры данных, хранящих пары ключ-значение.
_________________
 |
|
|
|
|
|
|
|
