Главная
Блог разработчиков phpBB
 
+ 17 предустановленных модов
+ SEO-оптимизация форума
+ авторизация через соц. сети
+ защита от спама

Trove 4.0? Примитивы в стандартном каркасе коллекций из Java 8

Anna | 4.06.2014 | нет комментариев
Около месяца назад на Прогре была статья про Trove — самую Зачастую упоминаемую библиотеку, когда спрашивают про конструкции данных с примитивами на Java. Приблизительно за пару дней до этого я сел эту библиотеку переписывать :) Время бесстрашно кончилось, следственно делюсь поиском с вами, правда не дюже-то верю, что кто-то продолжит это дело :)

На данный момент сделаны хеш-таблицы 6 типов: множества примитивов, объектов и все 4 варианта мапов: примитив — примитив, примитив — объект, объект — примитив и объект — объект, над которыми нависает туча обобщающих интерфейсов.

Меня неизменно поражало, отчего все сходственные библиотеки создают еще одну иерархию типов, а не встраиваются в давным-давно теснее зарекомендовавший себя типовой каркас коллекций Явы. Никаких принципиальных задач с этим я не видел и не вижу. Следственно над моей тучей интерфейсов, как на пантеоне, возвышаются java.lang.Iterablejava.util.Collection и java.util.Map. Я не напрасно дал ссылки на документацию по Java 8. Реализованы примерно все способы из грядущих интерфейсов, помимоspliterator(). Дозволено начинать привыкать :)

Добавочные элементы нового фреймворка Trove

mapIterator() — гибрид spliterator() из Java 8 и entrySet().iterator().

interface TMapIterator<K, V> {
    boolean tryAdvance();
    K key();
    V value();
    ...
}
// идиома применения
for (IntKeyMapIterator<String> it = map.mapIterator(); it.tryAdvance(); ) {
    doSomething(it.intKey(), it.value());
}

Едва ли это больше массивно, чем entrySet().iterator(), но значительно результативнее.

Во всех хешах объектов есть способы для управления разбиением объектов на множества равнозначных:

class DHashSet<E> {
    ...
    protected boolean elementsEquals(@NotNull E a, @Nullable E b) {
        return a.equals(b);
    }
    protected int elementHashCode(@NotNull E element) {
        return element.hashCode();
    }
}

«Реверсивные» способы над целыми коллекциями: addAllTo()allContainingIn()removeAllFrom() — для убыстрения поточных операций. В стандартном каркасе способ неизменно вызывается на коллекции, которая будет изменяться, правда итерироваться придется по 2-й. Правда именно последняя «знает», как стремительней каждого пройтись по каждому элементам.

В некоторых случаях реверсивный проход может выполняться в 2 раза стремительней, чем внешний, с поддержкой обыкновенного итератора. Скажем, при дампе множества в список.

Так как контракты соответствующих способов из стандартного каркаса имеют достаточно тонкие нюансы, реверсивные способы не рекомендуется вызывать вручную, Дабы не сделать что-нибудь не то :) Они теснее вызываются изнутри обыкновенных способов в реализациях.

Реализация

Сердце Trove — хеш-таблицы с открытой адресацией и двойным хешированием для разрешения коллизий. При удалении элемента в них невозможно легко пометить ячейку, как свободную. Следственно, если из таблицы регулярно удаляются и добавляются элементы, она всецело забивается занятыми и «удаленными» ячейками, скорость операций падает. В предыдущей версии Trove, Дабы не допустить этого, был счетчик удалений, эвристически завязанный на задаваемый показатель заполненности таблицы.

При показателе k (от 0 до 1) получается, что при непрерывных удалениях перед перестроением таблицы остается k — k^2 заполненных ячеек, и k^2 удаленных, при попеременных удалениях и вставках различных случайных элементов — k заполненных и (1 — k) ^2 — свободных (все величины — в долях от 1).

Подставим цифры. При показателе по умолчанию — 0,5 — в обоих случаях получается максимум по четверти удаленных элементов в таблице. Дюже прекрасно. Но вот при моем любимом показателе 0,8 — при абсолютно типичном образце применения таблицы может остаться каждого 4% свободных ячеек — это криминал.

Источник: programmingmaster.ru

Оставить комментарий
Форум phpBB, русская поддержка форума phpBB
Рейтинг@Mail.ru 2008 - 2017 © BB3x.ru - русская поддержка форума phpBB