Доброго времени суток, дорогие друзья.

В этом посте я расскажу об одной из негативных сторон языка Java на соревнованиях по программированию (да и вообще), а точнее, как я попытался ее решить. Как известно, язык Java страдает недостатком при работе с коллекциями: ограничения этого языка заставляют программиста использовать объектные типы данных даже там, где этого как бы и не требуется. Сравните ArrayList<Integer> и vector<int>: в Java-варианте лист хранит объекты типа Integer, которые создаются при каждом добавлении элемента в список и распаковываются при каждом обращении, тогда как C++-ный вектор хранит обычные честные int-ы. Это замедляет работу программ на Java и много кому не нравится.

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

Так родился маленький проект под названием EZ Collections (ссылка на репозиторий на Github). Я, разумеется, не писал все возможные коллекции для всех возможных типов данных. Достаточно было написать каждую коллекцию один раз, оставив в исходнике некоторые подсказки для Maven-плагина, который потом сгенерирует все как надо.

Замечу, что библиотека предполагается для использования именно на олимпиадах, ну или просто для личного пользования. Она абсолютно вся thread-unsafe, там нет некоторых валидаций, во время итерирования нельзя менять коллекцию, нет сериализации и, наверное, чего-то еще нет. Но задачки сдаются.

Чтобы начать использовать эту библиотеку, вам необходимо:

1. Установить Git и выкачать себе репозиторий с помощью команды git clone (на главной странице проекта написан URL). Либо просто скачать его, нажав кнопку Download ZIP.

2. Скачать Maven (ссылка на страницу загрузок), установить и настроить его (кто не умеет — Google в помощь, но вроде бы достаточно прописать путь к Maven в системных переменных).

3. Зайти в корневую директорию библиотеки и выполнить команду mvn clean install. После этого в вашем локальном Maven-репозитории, а также в папке target появятся два jar-файла: один с class-файлами, другой с исходниками. Теперь вы можете подключать эти jar-ники к своему проекту.

По прежнему, правда, непонятно, как применять это на олимпиадах. Придется вспомнить про плагин Egor-а CHelper для IntelliJ IDEA. После его переезда на Github наконец-то был замержен пулл-реквест, исправляющий некоторые проблемы. Собранную последнюю версию (коммит 29dc20b), включающую в себя этот пулл-реквест, можно скачать отсюда и подключить самостоятельно.

После обновления плагина достаточно добавить библиотеку в ваш олимпиадный проект, указав путь к jar-файлу с исходниками. И можно пользоваться!

Пример использования: решаем задачу 118E - Дороги в Бертауне

• используем List<Integer>[] для хранения графа: 8293080 — 1060 мс, 39100 КБ
• используем EzIntList[] для хранения графа: 8293086 — 654 мс, 12148 КБ

(в этой задаче достаточно большие входные данные, чем они больше — тем более заметен будет выигрыш в производительности)

Еще один пример: решаем задачу Timus 1521

С помощью TreeList все пишется буквально в несколько строчек:

int n = in.readInt();
int k = in.readInt();
EzIntList a = new EzIntTreeList(n);
for (int i = 0; i < n; i++) {
    a.add(i);
}
int idx = 0;
for (int i = 0; i < n; i++) {
    idx = (idx + k - 1) % a.size();
    out.print(a.removeAt(idx) + 1);
    out.print(' ');
}

Что же сейчас есть в EZ Collections? На данный момент присутствуют:

• ArrayList
• ArrayDeque (с возможностью обращения по индексу)
• Heap
• Sort (гарантированная за NlogN)
• HashSet
• HashMap (я использовал открытую адресацию. Не уверен, ломается ли моя реализация, но кажется, что не должна)
• TreeSet
• TreeMap
• TreeList (массив, умеющий делать add, set, insert и removeAt за логарифмическое время)
• классы Pair

Также хочется отметить, что существует известная библиотека Trove (ее репозиторий располагается тут), и, возможно, многие используют ее на работе, но проблема в том, что они сделали лишь ArrayList, HashSet и HashMap. А для олимпиад этого явно не хватает.

Некоторые замечания и планы:

• Не поддерживаются NaN, POSITIVE_INFITITY и подобная ерунда. И никогда не будут поддерживаться. Вы сам себе знаете кто, если используете такое.

• В связи с невозможностью возвращения null (ведь в коллекциях хранятся примитивные типы) везде, где это необходимо, добавлен метод returnedNull(), который следует вызвать сразу же. Следующие два использования идентичны:

    TreeSet<Integer> set = new TreeSet<Integer>();
    Integer lower = set.lower(42);
    if (lower == null) {
        ...
    }

    EzIntTreeSet set = new EzIntTreeSet();
    int lower = set.lower(42);
    if (set.returnedNull()) {
        // не используйте значение lower, никто не гарантирует, что будет возвращено
    }

• Текущий механизм генерации исходников не очень хорош и накладывает некоторые ограничения, да и вообще ужасно выглядит. Поэтому я буду его переписывать. Но все коллекции, которые я хотел написать в первой версии, уже работают.

• boolean считается несравнимым типом, поэтому Pair с boolean-ами не реализует Comparable. После переписывания генерации это должно пофикситься.

• В будущем планируется добавить LinkedList (на массивах). Но это только после того, как перепишу генерацию исходников.

• А потом планируется добавить мапы, у которых ключ — примитивный тип, а значение — объект, или наоборот. Тоже должно дать прирост в скорости.

Пишите ваши замечания и фидбеки мне в личку на Codeforces.

История версий:

• 21.02.2015 — выпущена версия 0.1.0. По содержанию она идентична стандартным коллекциям Java.
• 15.03.2015 — выпущена версия 0.1.1. Добавлен TreeList, а также добавлена возможность задавать собственные хеш-функции для HashSet/HashMap.