Разработка коллекции на основе матрицы

в 11:15, , рубрики: collections, java

Всем привет. Идея создать коллекцию, позволяющую управлять массивом информации, в основе которой лежит матрица, зародилась достаточно давно. Воплотить идею в жизнь я решил после изучения языка программирования Java. В статье речь пойдет о коллекциях, которые реализуют интерфейс списка.

Java collections

На данный момент в распоряжении мы имеет больше чем достаточно, как родных JDK, так и сторонних библиотек для работы с коллекциями:

JDK

Open Source

Выбор основания

Для создании универсальной коллекции подходит использование принципов generics. Основу коллекции создает класс java.util.AbstractList. Обязательными к переопределению являются методы 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, будет выполнено:

  1. динамическое выделение памяти на новый размер первой размерности массива
  2. скопированы ссылки на все массивы второй размерности
  3. динамически создан новый массив второй размерности

Массив IndexData требуется для хранения занятых мест и их общего количества во второй размерности elementData:

class IndexData

    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

Благодарю за внимание

Автор: Alex_java

Источник

Поделиться новостью

* - обязательные к заполнению поля