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

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

Java collections

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

JDK

• java.util.ArrayList
• java.util.LinkedList

Open Source

• Commons Collections
• Commons Primitives
• GS Collections
• Guava
• HPPC
• PCJ
• Trove

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

Для создании универсальной коллекции подходит использование принципов 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:

    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()));

Результаты тестирования коллекций

Вывод

Ещё раз хочу заметить, что за уменьшение времени выполнения мы расплачиваемся объемом расходуемой памяти. При выполнении вышеуказанных тестов в процессе дефрагментации размер коллекции FastArray увеличился в 3 раза от номинального. Для уменьшения размера коллекции используется метод trimToSize().
Данная версия реализации не является финальной. Здесь реализован минимально требуемый функционал, который в последствии можно более тщательно оптимизировать.

Исходный текст полностью представлен на github

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

Автор: Alex_java

Источник