- PVSM.RU - https://www.pvsm.ru -
Всем привет. Идея создать коллекцию, позволяющую управлять массивом информации, в основе которой лежит матрица, зародилась достаточно давно. Воплотить идею в жизнь я решил после изучения языка программирования Java. В статье речь пойдет о коллекциях, которые реализуют интерфейс списка.
На данный момент в распоряжении мы имеет больше чем достаточно, как родных JDK, так и сторонних библиотек для работы с коллекциями:
Для создании универсальной коллекции подходит использование принципов generics [10]. Основу коллекции создает класс java.util.AbstractList [11]. Обязательными к переопределению являются методы get и size.
public class FastArray<E> extends AbstractList<E> {
@Override
public E get(int index) {
return null;
}
@Override
public int size() {
return 0;
}
}
К тому же, тело некоторых методов абстрактного класса AbstractList определено как throw new UnsupportedOperationException()
, что заставляет нас их так же переопределить на нужное нам поведение:
public E set(int index, E element) {
throw new UnsupportedOperationException();
}
public void add(int index, E element) {
throw new UnsupportedOperationException();
}
public E remove(int index) {
throw new UnsupportedOperationException();
}
Структура хранения данных в коллекции представлена в виде одной матрицы и одного массива c типом IndexData:
private Object[][] elementData;
private IndexData[] data;
Для хранения элементов списка используется двухмерный массив elementData. Двухмерный массив в ущерб объему памяти позволяет обеспечивать более быстрый доступ к элементам списка в процессе чтения, записи и удаления.
В отличии от стандартного поведения ArrayList (при добавлении элементов содержимое массива копируется в новый увеличенный массив), в FastArray первая размерность массива имеет переменную длину и меняется при необходимости, вторая размерность массива имеет постоянную длину равную 32 элементам.
private static final int CAPACITY = Integer.SIZE;
То есть, все сводится к тому, что при нехватке размера хранилища elementData, будет выполнено:
Массив IndexData требуется для хранения занятых мест и их общего количества во второй размерности elementData:
private static class IndexData {
private int data;
private int size;
private boolean isFull() {
return size == CAPACITY;
}
private void take(final int index) {
if (isFree(index)) {
data = data | 1 << index;
size++;
}
}
private void free(final int index) {
if (isTaked(index)) {
data = data ^ 1 << index;
size--;
}
}
private boolean isTaked(final int index) {
return !isFree(index);
}
private boolean isFree(final int index) {
return (data & 1 << index) == 0;
}
private int getSize() {
return size;
}
private int getIndexLeadingFreeBit() {
return CAPACITY - Integer.numberOfLeadingZeros(data);
}
private int getIndexTrailingFreeBit() {
return Integer.numberOfTrailingZeros(data) - 1;
}
}
32 места хранятся в битах одного 32-битого числа. Данный прием позволяет сократить некоторые циклы при обходе массивов. Например, поиск свободного места слева или справа во второй размерности.
private int getTakedIndexAt(int data, int number) {
int count = 0;
int index = -1;
number++;
do {
count += data & 1;
index++;
} while ((data >>>= 1) != 0 && count != number);
return index;
}
Данный алгоритм должен найти, например, пятое занятое место с начала. Если есть идеи, как убрать цикл из данного алгоритма, то просьба указать их в комментариях.
Коллекция FastArray начинает показывать положительные результаты после того, как превысит свой размер в 1000 элементов. В противном случае, время на выполнение операций существенно увеличено по сравнению с результатами других коллекций.
int count = 100000;
for(int i = 0; i < count; i++)
list.add(1);
for(int i = 0; i < count; i++)
list.add(rand.nextInt(count), 10);
for(int i = 0; i < count * 2; i++)
list.get(rand.nextInt(count));
for(int i = 0; i < count; i++)
list.remove(rand.nextInt(list.size()));
# | Name | Time (ms) |
---|---|---|
1 | FastArray | 804 |
2 | HPPC | 2857 |
3 | Guava | 2887 |
4 | Commons Collections | 2909 |
5 | ArrayList | 2949 |
6 | PCJ | 6370 |
7 | Trove | 6503 |
8 | LinkedList | 83002 |
Ещё раз хочу заметить, что за уменьшение времени выполнения мы расплачиваемся объемом расходуемой памяти. При выполнении вышеуказанных тестов в процессе дефрагментации размер коллекции FastArray увеличился в 3 раза от номинального. Для уменьшения размера коллекции используется метод trimToSize()
.
Данная версия реализации не является финальной. Здесь реализован минимально требуемый функционал, который в последствии можно более тщательно оптимизировать.
Исходный текст полностью представлен на github [12]
Благодарю за внимание
Автор: Alex_java
Источник [13]
Сайт-источник PVSM.RU: https://www.pvsm.ru
Путь до страницы источника: https://www.pvsm.ru/java/190093
Ссылки в тексте:
[1] java.util.ArrayList: https://docs.oracle.com/javase/8/docs/api/java/util/ArrayList.html
[2] java.util.LinkedList: https://docs.oracle.com/javase/8/docs/api/java/util/LinkedList.html
[3] Commons Collections: http://commons.apache.org/proper/commons-collections/
[4] Commons Primitives: http://commons.apache.org/dormant/commons-primitives/
[5] GS Collections: https://github.com/goldmansachs/gs-collections
[6] Guava: https://github.com/google/guava
[7] HPPC: https://github.com/carrotsearch/hppc
[8] PCJ: http://pcj.sourceforge.net/
[9] Trove: http://trove.starlight-systems.com/
[10] generics: https://docs.oracle.com/javase/tutorial/java/generics/types.html
[11] java.util.AbstractList: https://docs.oracle.com/javase/8/docs/api/java/util/AbstractList.html
[12] github: https://github.com/alex-java/fastarray/blob/master/FastArray.java
[13] Источник: https://habrahabr.ru/post/310500/?utm_source=habrahabr&utm_medium=rss&utm_campaign=sandbox
Нажмите здесь для печати.