Алгоритмы и структуры данных 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, но отсутствие графовых структур и алгоритмов совсем в век социальных сетей в языке претендующим на самый универсальный — вызывает удивление баги и велосипеды.
Язык программирования Java SE 8. Подробное описание.
Эта книга написана разработчиками языка Java и является полным техническим справочником по этому языку программирования. В ней полностью описаны новые возможности, добавленные в Java SE 8, включая лямбда-выражения, ссылки на методы, методы по умолчанию, аннотации типов и повторяющиеся аннотации. В книгу также включено множество поясняющих примечаний. В ней четко обозначены отличия формальных правил языка от практического поведения компиляторов.
Java является языком программирования общего назначения, ориентированным на параллельное выполнение и основанным на классах объектно-ориентированным языком. Он специально разрабатывался так, чтобы быть достаточно простым, так что многие программисты могут легко достичь высокой скорости работы.
Язык программирования Java является строго и статически типизированным. В дан ной спецификации четко различаются ошибки времени компиляции, которые могут и должны быть обнаружены во время компиляции, и ошибки, которые происходят во время выполнения.
Язык программирования Java — язык относительно высокого уровня, что проявляется, в частности, в том, что детали представления машинного кода в языке недоступны.
Сюда входят автоматическое управление памятью, обычно с использованием сборщика мусора (чтобы избежать проблем, связанных с явным освобождением памяти. Высокопроизводительные реализации сборки мусора могут ограничиваться работой в паузах выполнения программы, чтобы обеспечить возможность создания системных программ и приложений реального времени.
Язык не включает ни одной небезопасной конструкции, такой как доступ к массиву без проверки диапазонов индексирования, поскольку такие небезопасные конструкции могут приводить к неопределенному поведению программы.
Программа на языке Java обычно компилируется в набор команд байт-кода и бинарный формат, определенный в спецификации виртуальной машины Java The Java Virtual Machine Specification, Java SE 8 Edition.