Комментарии 25
Написано сумбурно, но обзор добротный — ссылок много и даже не все они фиолетовые. Спасибо.
старался структурировать в том порядке как эти структуры обычно перечисляются в классическах учебниках по алгоритмам. Также пытался обратить внимание только на самое важное, полная картина — в исходниках и жавадоках.
Графовые структуры и алгоритмы нужно в библиотеках реализовывать. Зачем их тащить в JDK?
Наверное, было бы неплохо добавить всё это отдельным пакетом.
Тогда какой критерий затаскивания в jdk? Почему например gzip включили?
По моему графы даже уже в энторпрайзе можно встретить
По моему графы даже уже в энторпрайзе можно встретить
Граф — не структура данных, а достаточно высокоуровневая модель с множеством вариаций, которые редко даже совпадают в прикладных задачах, которая реализуется поверх структур (из JDK или библиотек).
большинство графовых задач решается с испольованием простой модели на смежных списках (adj lists), вот она к примеру: Digraph.java +алгоритм кратчайшего пути — вроде не сильно высокий уровень, вот чего то подобного в jdk не хватает для универсальности.
В чистом виде это нужно только для олимпиадных задач. В практических задачах у вершин и/или ребер есть какие-то метаданные, поэтому они превращаются в объекты. Дополнительные ограничения, эвристики возникают. И т. д.
На практике добавляем generic (Т) value для ноды и ребра +компаратор, все — эвристикам вроде больше ничего не нужно. Графовые алгоритмы — довольно просты, вкратце: сравнение и подсчет весов ребер, перебор исходящих и т.д.
Как идентифицировать ребра? Если только началом и концом, то возникают проблемы с кратными ребрами.
Как идентифицировать вершины? Добавление и удаление вершин будет сбивать их нумерацию.
Вес ребра хранится в value или во внутренних структурах графа? Он целочисленный или действительный? Как обрабатывать погрешности при работе с действительными числами (вдруг у вас есть цикл веса -1e-100, нужно ли выдавать ошибку при поиске кратчайшего пути?)? Разрешены ли отрицательные веса? С отрицательными весами нужно применять другие алгоритмы.
Как передавать вершины между функциями? Как граф + число, граф + объект вершины или объект вершины? В последних случаях, что делать если кто-то сохранит вершину, которую в последствии удалят из графа?
Как удалять ребро за O(1), а не за O(степень вершины)?
Как проверить, есть ли ребро между вершинами за O(1) или может хотя бы за O(log N)?
Как только вы начнете отвечать на подобные вопросы, очень быстро окажется, что нужны десятки различных классов графов. После чего, нужно реализовать дополнительно десятки алгоритмов конвертации между любыми из них.
Как идентифицировать вершины? Добавление и удаление вершин будет сбивать их нумерацию.
Вес ребра хранится в value или во внутренних структурах графа? Он целочисленный или действительный? Как обрабатывать погрешности при работе с действительными числами (вдруг у вас есть цикл веса -1e-100, нужно ли выдавать ошибку при поиске кратчайшего пути?)? Разрешены ли отрицательные веса? С отрицательными весами нужно применять другие алгоритмы.
Как передавать вершины между функциями? Как граф + число, граф + объект вершины или объект вершины? В последних случаях, что делать если кто-то сохранит вершину, которую в последствии удалят из графа?
Как удалять ребро за O(1), а не за O(степень вершины)?
Как проверить, есть ли ребро между вершинами за O(1) или может хотя бы за O(log N)?
Как только вы начнете отвечать на подобные вопросы, очень быстро окажется, что нужны десятки различных классов графов. После чего, нужно реализовать дополнительно десятки алгоритмов конвертации между любыми из них.
Смежная тема, но тоже интересно — stackoverflow.com/questions/1673841/examples-of-gof-design-patterns
Автор лукавит, говоря, что отсутствует hash таблица с открытой адресацией — вы забыли о ThreadLocalMap — хранилище для ThreadLocal. Другое дело, что как-то использовать его кроме ThreadLocal нельзя.
Queue — интерфейс (api) LIFO очереди, добавление в начало, удаление с конца за O(1)
Я не java-ист (хотя в данном случае это роли не играет), но стало интересно почему это называется Queue? Queue это разве не FIFO?
Недавно наткнулся на интересный ответ на stackoverflow — примеры реализации шаблонов проектирования в JDK stackoverflow.com/questions/1673841/examples-of-gof-design-patterns/2707195#2707195
НЛО прилетело и опубликовало эту надпись здесь
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Алгоритмы и структуры данных JDK