10 июня 2013 в 16:03

Алгоритмы и структуры данных JDK из песочницы

[ english version ]
Периодически проверяя нет ли реализации того или иного стандартного алгоритма в jdk, пришла мысль составить подобный обзор. Также интересны были причины наличия/отсутствия многих известных структур данных.
Формат обзора — только ключевые свойства и особенности структур и алгоритмов в составе jdk, подробности и детали — расписаны в javadoc или легко найти в исходниках.
Надеюсь на конструктивную критику и коллективный разум если что упустил.
Хватит вступлений, итак, давайте рассмотрим что включает в себя текущий jdk 7 и почему.

Структуры


Стек

В jdk имеется старый стек (Stack), который существует с момента выхода java и использовать уже не рекомендуется, он сложный и странный: наследуется от Vector, а значит построен на динамически расширяемом массиве и синхронизированный.
Зачем это все обычному стеку и почему это не интерфейс — не совсем ясно (обсуждалось не раз: 1, 2), но похоже на ошибку проектирования, такую же как и сам Vector.
К тому же в самом javadoc советуют вместо него использовать Deque.

Deque — это интерфейс (api) двухсторонней очереди(LIFO + FIFO за O(1)), который включает в себя и стековые операции (push, pop, isEmpty, size). Доступен в jdk не так давно (1.6+).
Конечно проще если бы эти стековые операции находились в интерфейсе Stack, а Deque его например наследовал бы, но поскольку Stack уже присутствовал, а обратная совместимость — это для java “наше все”, пришлось пожертвовать нормальным дизайном.
Реализации Deque — это ArrayDeque и LinkedList, которые по совместительству также имплементируют обычную очередь, поэтому рассмотрим позже.

Очереди

Далее по порядку смотрим очереди. Здесь все хорошо, дизайн достойный.
Queue — интерфейс (api) FIFO очереди, добавление в начало, удаление с конца за O(1).

Основные реализации — это ArrayDeque, циклический буффер на основе динамически расширяемого массива (увеличивается вдвое при заполнении) и LinkedList, классический двусвязный список, размер не ограничен. Странным образом, первая не поддерживает случайный доступ (add/remove/get с индексом), вторая — поддерживает но за время O(n) итерации по связному списку.
Эти же имплементации реализуют и упомянутую двустороннюю очередь, а значит удаление с конца и добавление в начало — тоже O(1).

Далее c jdk 1.5+ была добавлена PriorityQueue которая по факту нарушает контракт очереди т.к. элементы достаются не с конца (кладутся тоже не в начало) а согласно их приоритетам.
Построена на основе расширяемой бинарной кучи, на вершине — минимальный элемент (согласно его компаратору), при заполнении увеличивается в размере в полтора раза. Соотв-но добавление/удаление — это O(log N), ссылка на минимальный (голову) — O(1).

Остальные типы очередей предназначены для многопоточного использования, это BlockingQueue, TransferQueue, ConcurrentLinkedQueue и ConcurrentLinkedDeque.

Реализации BlockingQueue ( ArrayBlockingQueue, LinkedBlockingQueue, PriorityBlockingQueue) — это своего рода синхронизированные версии их оригиналов, т.е. почти каждая операция выполняется синхронно (блокируется). Сюда же можно отнести и DelayQueue — также синхронизированная, внутри использует PriorityQueue.

В то время как SynchronousQueue, TransferQueue (LinkedTransferQueue), ConcurrentLinkedQueue, ConcurrentLinkedDeque — основаны на другом подходе: там применяются алгоритмы неблокирующей очереди на связных списках с применением CAS инструкций, которые хорошо распараллеливаются в многопроцессорном окружении. Подробное описание — в исходниках.
Алгоритмы такого класса довольно обширный и новый материал, еще не совсем стандартизированный и структурированный, поэтому выходит за рамки данного обзора и скорее тема для отдельной статьи.

Очереди с приоритетом (кучи)

Как уже было сказано начиная с 1.5 присутствует универсальная PriorityQueue, кроме того есть еще одна реализации кучи в jdk. Это старый добрый Timer, внутренний классик TaskQueue (на вершине — задача с минимальным временем ожидания). Естественно это закрытая реализация и кроме как внутри таймера она использоваться не может.

Списки

Как известно бывают последовательного и/или случайного доступа.
В java список — это List и 2 основные реализации, первая — это ArrayList, поддерживает случайный доступ, в основе динамически расширяемого массива (увеличивается в полтора раза при заполнении), но при удалении элементов сам не сужается, для этого нужно вызывать предусмотренный метод (trimToSize).

И вторая — уже упомянутвый LinkedList, двусвязный список последовательного доступа, размер ограничен только свободной памятью jvm. Хотя методы случайного доступа (по индексу) тоже присутствуют — как уже было сказано, они здесь выполняются за O(n)

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

Для использования списков в многопоточном окружении существует CopyOnWriteArrayList (операции изменения — O(n)), обертки (synchonizedList) а также устаревший Vector.

Символьные таблицы

Представлены бинарным деревом и хеш-таблицей.

Дерево — это TreeMap (TreeSet), реализация SortedMap (SortedSet соотв-но), в основе лежит классическое красно-черное дерево, т.е. сбалансированное и основные операции гарантировано за O(log N), в размерах не ограничен.
Других типов деревьев — в jdk нет.

Хеш-таблица — HashMap (HashSet) наверное самая используемая структура в java, построена на динамически расширяемой хеш-таблице с цепочками, со всеми вытекающими: производительность зависит от хеш функции, в худшем случае O(N). Когда размер достигает заданного loadFactor — увеличивается вдвое. Стоит еще отметить что для защиты от плохих хеш-функций, используется двойное хеширование, при котором к результату вызова hashCode() применяется хитрая битовая арифметика.

Есть в jdk реализации хеш-таблиц и с открытой адресацией (linear probing). Одна из них это IdentityHashMap, в которой к тому же используется оптимизация классического linear probing когда и ключи и значения хранятся в одном массиве рядом с друг другом, для лучшего кеширования данных (javadoc: «better locality for large tables than does using separate arrays»)
Вторая реализация — очень специфическая: служит только для хранения ThreadLocal элементов (внутренний скрытый классик ThreadLocalMap) и для использования конечно недоступна.

Многопоточные версии: ConcurrentHashMap, обертка synchronizedMap, Hashtable и ConcurrentSkipListMap. Обертка — естественно просто блокирующая версия обычной HashMap, Hashtable — тоже самое, ConcurrentHashMap — lock-striping версия, позволяющая сократить критические секции (читать об этом лучше в JCiP, вот отрывок).
ConcurrentSkipListMap — неблокирущая версия одноименного алгоритма адаптированного для хеш-таблицы (подробнее — в исходниках).

Через хеш-таблицы реализованы и множества Set (не допускающие дубликатов), поэтому все что сказано к хеш-таблицам — справедливо для Set.

Графы

Графовые структуры и алгоритмы в jdk не представлены. Поэтому в этом случае остается использовать только сторонние библиотеки

Строки

Реализация стандартная — на основе массива unicode символов. Стоит напомнить что начиная с версии 1.7_17 производительность substring теперь O(n), поскольку подстрока копируется.

Интересно что для поиска подстроки используется алгоритм простого перебора дающий O (N*M) в худшем случае, а не какой нибудь эффективный алгоритм построенный на конечном автомате (Knuth-Morris-Pratt и др.).
Причин несколько: во-первых опять же большой размер алфавита UTF символов (~65K), а значит большие накладные расходы на хранение конечного автомата, в то время как алгоритм перебора — in-place (не используется доп память).
И во-вторых, производительность на среднестатистических строках — в этом видимо перебор не сильно проигрывает другим алгоритмам.

Тоже самое с сортировкой. Существуют эффективные сортировки строк подсчетом (LSD, MSD и др), но в jdk используется стандартная для объектов, дающая O(M * N * log N), если большинство строк не сильно отличаются (M — средняя длина строк).
Причина та же: сортировки подсчетом используют вспомогательные массивы размером алфавита UTF, что делает их неэффективными на среднестатических входных данных.

Алгоритмы


Сортировка

В jdk7 произошло много изменений касательно вариантов сортировок, тема обсуждалась неоднократно, информации и статей на эту тему полно, подробней могу посоветовать вот этот обзор.
В кратце, актуальный список реализаций сортировок доступных на данный момент в jdk: TimSort — сортировка объектов по умолчанию, слиянием — тоже для объектов, старый вариант (включаемый через системное свойство), для примитивов используется Dual-Pivot Quick sort, для байтовых/символьных массивов используется сортировка подсчетом, для небольших массивов во всех случаях используется сортировка вставками.

Cортировка коллекций Collections.sort(List ...) по прежнему делается через копирование в массив, сортировку и затем перезаписывает коллекцию. Поэтому без накладных расходов сделать это стандартными средствами нельзя, хотя наверное не помешало бы иметь in-place сортировку связных списков.

Для сортировки строк тоже используется объектная версия, причины упомянуты выше.

Поиск

Традиционный бинарный поиск присутствует для всех массивов примитивов и объектов а также списков поддерживающих случайный доступ.

Более того в Collections присутствует версия для связных списков. Получается сортировку для связных списков делать смысла не было, но двоичный поиск понадобился, хотя смысла еще меньше поскольку производительности O (log N) там и близко нет.

Регулярные выражения

Используется традиционная реализация на основе недетерминированного конечного автомата (NFA) и поиска с возвратом (backtracking). Т.е. экспоненциальная сложность O(m^N) в худшем случае на вырожденных значениях, пример:

"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa".matches("(a|aa)*b")


Также имеет место т.н. “ordered alternation” (порядковая альтернатива?) — это когда поиск прекращается сразу после нахождения первого соответствия из нескольких а не самого специфического (длинного), пример.

Хеш-функции, контрольные суммы

Алгоритмов вычисления hashCode в jdk целых шесть, по-умолчанию используется Park-Miller_random_number_generator, подробней — недавняя статья на хабре.

Имеются также стандартные промышленные алгоритмы хеширования (SHA-*, MD5 и вариации) — MessageDigest

Для вычисления контрольных сумм присутствуют еще реализации алгоритмов Adler-32 (javadoc) и CRC32 (javadoc)

Сжатие

В jdk имеется реализация стандартного алгоритма сжатия deflate (Deflater) и также на его основе zip/gzip. Все это в пакете java.util.zip

Вывод


Как видно классические структуры данных в java представлены далеко не полностью, но в тоже время почти для каждой имеется несколько вариантов потокобезопасных версий.
Чего не хватает — вопрос открытый. Например можно спорить нужен ли в jdk какой-нибудь Union-Find, но отсутствие графовых структур и алгоритмов совсем в век социальных сетей в языке претендующим на самый универсальный — вызывает удивление баги и велосипеды.
Миша @yetanothercoder
карма
19,0
рейтинг 0,0
java кодер

Комментарии (25)

  • +3
    Написано сумбурно, но обзор добротный — ссылок много и даже не все они фиолетовые. Спасибо.
  • 0
    старался структурировать в том порядке как эти структуры обычно перечисляются в классическах учебниках по алгоритмам. Также пытался обратить внимание только на самое важное, полная картина — в исходниках и жавадоках.
  • +2
    Графовые структуры и алгоритмы нужно в библиотеках реализовывать. Зачем их тащить в JDK?
    • 0
      Наверное, было бы неплохо добавить всё это отдельным пакетом.
      • +2
        конечно, по аналогии того же java.util.zip
        графовые алгоритмы то давно устоявшиеся и изведаны +это добавило бы еще универсальности платформе
    • 0
      Тогда какой критерий затаскивания в jdk? Почему например gzip включили?
      По моему графы даже уже в энторпрайзе можно встретить
      • +3
        Граф — не структура данных, а достаточно высокоуровневая модель с множеством вариаций, которые редко даже совпадают в прикладных задачах, которая реализуется поверх структур (из JDK или библиотек).
        • 0
          большинство графовых задач решается с испольованием простой модели на смежных списках (adj lists), вот она к примеру: Digraph.java +алгоритм кратчайшего пути — вроде не сильно высокий уровень, вот чего то подобного в jdk не хватает для универсальности.
          • +1
            В чистом виде это нужно только для олимпиадных задач. В практических задачах у вершин и/или ребер есть какие-то метаданные, поэтому они превращаются в объекты. Дополнительные ограничения, эвристики возникают. И т. д.
            • 0
              На практике добавляем generic (Т) value для ноды и ребра +компаратор, все — эвристикам вроде больше ничего не нужно. Графовые алгоритмы — довольно просты, вкратце: сравнение и подсчет весов ребер, перебор исходящих и т.д.
              • +2
                Как идентифицировать ребра? Если только началом и концом, то возникают проблемы с кратными ребрами.
                Как идентифицировать вершины? Добавление и удаление вершин будет сбивать их нумерацию.
                Вес ребра хранится в value или во внутренних структурах графа? Он целочисленный или действительный? Как обрабатывать погрешности при работе с действительными числами (вдруг у вас есть цикл веса -1e-100, нужно ли выдавать ошибку при поиске кратчайшего пути?)? Разрешены ли отрицательные веса? С отрицательными весами нужно применять другие алгоритмы.
                Как передавать вершины между функциями? Как граф + число, граф + объект вершины или объект вершины? В последних случаях, что делать если кто-то сохранит вершину, которую в последствии удалят из графа?
                Как удалять ребро за O(1), а не за O(степень вершины)?
                Как проверить, есть ли ребро между вершинами за O(1) или может хотя бы за O(log N)?

                Как только вы начнете отвечать на подобные вопросы, очень быстро окажется, что нужны десятки различных классов графов. После чего, нужно реализовать дополнительно десятки алгоритмов конвертации между любыми из них.
                • 0
                  вы совершенно правы в сложности формализации графовых моделей, но, повторюсь, существует мнение что в 90% графовых задач нет паралельных ребер, нет отрицательных весов и других сложностей, а нужно всего лишь делать какой нибудь topological sort или кратчайший путь.
  • 0
    Смежная тема, но тоже интересно — stackoverflow.com/questions/1673841/examples-of-gof-design-patterns
  • +1
    Автор лукавит, говоря, что отсутствует hash таблица с открытой адресацией — вы забыли о ThreadLocalMap — хранилище для ThreadLocal. Другое дело, что как-то использовать его кроме ThreadLocal нельзя.
    • 0
      спасибо, добавил про нее.
    • +3
      IdentityHashMap, кстати, тоже с открытой адресацией.
      • 0
        вот про это совсем упустил, добавил, спасибо!
  • 0
    Queue — интерфейс (api) LIFO очереди, добавление в начало, удаление с конца за O(1)

    Я не java-ист (хотя в данном случае это роли не играет), но стало интересно почему это называется Queue? Queue это разве не FIFO?
    • 0
      Вы правы, это опечатка в статье.

      П. С. Пожалуйста, не насилуйте так больше русский язык. «Я не пишу на Яве (Java)»
      • 0
        опечатка, поправил
  • +2
    Недавно наткнулся на интересный ответ на stackoverflow — примеры реализации шаблонов проектирования в JDK stackoverflow.com/questions/1673841/examples-of-gof-design-patterns/2707195#2707195
    • 0
      да, вот выше в камментах тоже указывали на этот топик, только шаблоны проектирования и структуры данных — это все же разные вещи, конечно смежные темы, но граница между ними думаю довольна ясна.
      • 0
        о что то я не заметил — да темы разные но я тут провел параллель с примерами из JDK ))
  • 0
    А где делась LinkedHashMap? Неужели в Java 7 её нет?
    • 0
      Упустил, но и смысла мало:

      LinkedHashMap<K,V> extends HashMap<K,V>

      — это ж не новая структура а тот же HashMap с дополнительными ссылками.

Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.