LJV: Чему нас может научить визуализация структур данных в Java |
||
МЕНЮ Главная страница Поиск Регистрация на сайте Помощь проекту Архив новостей ТЕМЫ Новости ИИ Голосовой помощник Разработка ИИГородские сумасшедшие ИИ в медицине ИИ проекты Искусственные нейросети Искусственный интеллект Слежка за людьми Угроза ИИ ИИ теория Внедрение ИИКомпьютерные науки Машинное обуч. (Ошибки) Машинное обучение Машинный перевод Нейронные сети начинающим Психология ИИ Реализация ИИ Реализация нейросетей Создание беспилотных авто Трезво про ИИ Философия ИИ Big data Работа разума и сознаниеМодель мозгаРобототехника, БПЛАТрансгуманизмОбработка текстаТеория эволюцииДополненная реальностьЖелезоКиберугрозыНаучный мирИТ индустрияРазработка ПОТеория информацииМатематикаЦифровая экономика
Генетические алгоритмы Капсульные нейросети Основы нейронных сетей Распознавание лиц Распознавание образов Распознавание речи Творчество ИИ Техническое зрение Чат-боты Авторизация |
2022-01-06 16:23 Эта статья является пересказом моего доклада на Java-конференции SnowOne 2021 года. LJV — проект, созданный в 2004 году как инструмент для преподавания языка Java студентам. Он позволяет визуализировать внутреннее устройство структур данных. В этом докладе я запускаю LJV на разных структурах (от Откуда взялся LJV и зачем он нужен Моя основная работа – инженер на коммерческих проектах, но также я работаю в МФТИ, где раз в неделю читаю лекции по Java. Обычно на конференциях я рассказываю про опыт, связанный с коммерческими проектами, но этот доклад сделан исключительно на основе опыта, полученного в процессе преподавания. Моя основная работа – инженерная, преподаю я как совместитель. Пару лет назад мне пришла идея сделать лекционный курс по Java. Что такое сделать лекционный курс? Это значит, что 14 недель подряд нужно готовить качественный полуторачасовой доклад. Неохота рисовать на доске, хочется переиспользовать из года в год одни и те же слайды. В процессе создания и редактирования слайдов хочется не выходить из своей IDE, то есть создавать слайды как код. Кроме того, мне, как ленивому программисту (а каждый программист ленив) хочется, чтобы некоторые слайды себя сами нарисовали – например, слайд с внутренним устройством какой-нибудь Насчёт того, как делать слайды как код, у меня есть пост на Habr, где рассказано, какие технологии для этого можно применить. Но отдельно следует упомянуть такую вещь, как Graphviz – Graph Visualization Software. Я уверен, что очень многие знают его, но кто-то, возможно, слышит о нём впервые. Если зайти на Википедию, то можно узнать, что это программа очень старая, первый релиз был до 1991 года. Но если зайти в GitLab, то мы увидим, что последний релиз был совсем недавно, и бурная деятельность в проекте продолжается. Это очень продвинутая и активно развивающаяся десятилетиями штука. Она состоит из двух частей. Первая – это язык DOT. Вторая – это софт для визуализации текстов на языке DOT. Вот пример простого DOT-скрипта: digraph G{ A->B->C; B->D->A; C->A; } Мы определили digraph, то есть directed graph, направленный граф, определили ноды, связи между ними, сохранили этот скрипт как текстовый файл. Теперь, если выполнить в консоли команду dot -Tpng myfile.dot > myfile.png то мы получим вот такую красивую png-картинку: Смысл Graphviz в том, что вы задаете ноды и связи в графе, а он сам красиво их располагает на плоскости и отрисовывает. Конечно, как всегда, дьявол кроется в деталях. DOT – система достаточно продвинутая, на ней можно рисовать интересные вещи, но для того, чтобы достичь желаемых результатов, потребуется некоторое изучение этой технологии. Однако именно на языке DOT я люблю рисовать диаграммы, когда мне надо делать слайды как код. И вот, начиная создавать курс лекций по Java, я стал гуглить в поисках какого-нибудь механизма, который внутреннее устройство стандартных объектов Java автоматически отрисовывал бы в языке DOT. И я нашел. Я нашел очень старую страницу Computer Science Department Оклендского университета. Человек по имени John Hamer в 2004 году сделал утилиту, которую назвал LJV. Хотя сейчас это трудно себе представить, но в 2004 году ещё не было ни GitHub, ни Maven. Поэтому все, что сделал Джон – по GPL лицензии выложил файл LJV.java на университетской странице. Я взял этот файл, и, к моему удивлению, эта штука оказалась рабочей. Она работает на любых версиях Java, потому что она очень проста по идее: она использует Reflection API для того, чтобы посмотреть, из чего объект состоит, и довольно прямолинейную трансляцию в DOT для того, чтобы это визуализировать. Я построил какие-то иллюстрации для своих слайдов. Затем осенью 2020 года я предложил своим студентам, Нурасу Ногаеву и Илье Селиванову, в качестве семестрового задания превратить этот проект в современный, то есть выложить на GitHub, обложить тестами, отрефакторить. Вот какой проект получился: https://github.com/atp-mipt/ljv (кстати, приходите, поставьте туда звезду). О том, как им пользоваться, можно прочитать в документации и README. Цель моего доклада – применить этот инструмент к стандартным классам и стандартной библиотеке Java и посмотреть, какие штуки интересные мы можем там увидеть. Простой пример использования LJV Пользоваться LJV довольно просто. Сначала мы создаем объект с типом LJV и при необходимости конфигурируем его дополнительными опциями: LJV ljv = new LJV() .setQualifyNestedClassNames(true) .setIgnoreNullValuedFields(true) .addFieldAttribute("sourceSpliterator", "constraint=false"); На втором шаге мы создаем тот объект, который хотим визуализировать. Например, мы хотим посмотреть, как устроен объект Stream<Integer> o = List.of(1, 2, 3) .stream() .map(x -> x * x) .filter(x -> x % 2 == 0); Построив этот объект, мы просто передаем его в метод String dot = ljv.drawGraph(o); И дальше мы можем с этим делать что угодно. Если программа dot стоит на локальной машине, можно локально сгенерировать и получить png или svg. Но есть замечательный сайт, называемый Graphviz Online, который тот же самый dot-скрипт выполняет у вас в браузере, и может прямо в браузере открыть визуализацию скрипта, если его в формате URLEncoded передать в URL страницы. //use GraphViz online String encoded = URLEncoder.encode(dot, "UTF8") .replaceAll("+", "%20"); Desktop.getDesktop().browse( new URI("https://dreampuf.github.io/GraphvizOnline/#" + encoded)); При запуске этой программы откроется браузер, и мы увидим такую картинку: Что это за нотация? Прямоугольники – это объекты. Три выложенных в ряд квадратика в правом нижнем углу – это массив. Т. к. источником данных у нас является иммутабельный список, его объект отображён как экземпляр класса Примитивные поля каждого объекта перечисляются в правой части прямоугольника. Примитивные поля – это либо поля примитивных типов (таких как Поля, являющиеся ссылками на другие объекты (например, Так получается граф объектов: есть иммутабельная коллекция Визуализация строк и боксированных примитивов Теперь мы попробуем применить этот инструмент к самым разным классам и объектам из стандартной библиотеки. Сначала начнем с простого. Какой самый распространенный класс в Java? Конечно, В общем, вся эволюция string немножко напоминает одну известную картинку: Давайте быстро разберёмся, почему так происходило. Если в Java 6 мы возьмем длинную строчку и выполним Исходная строка превратилась в массив строк, но при этом каждая строка из этого массива переиспользует один большой длинный буфер, а поля Однако более часто встречается иная ситуация. Если мы хотим просто выделить из длинной строки первое слово, допустим, «The» при помощи То есть, обратите внимание: эта строчка, если её распечатать в консоли, выведет просто «The». Но в памяти она держит ссылку на длинный буфер. Если весь буфер нам больше не нужен, а нужен только этот сегмент «The», то, если мы специально не постараемся, от остальных символов мы не избавимся никак. Это утечка памяти, и поэтому, начиная с определенного апдейта Java 7, ситуация поменялась: от Теперь строка, содержащая три символа, занимает в памяти всего лишь три История двигалась дальше, и в Java 9, как мы знаем, появились compacted-строки. До этого момента буфер Потом оказалось, что это не так, и Поэтому, начиная с Java 9, появились compacted строки. Теперь буфер строки – не Но это еще не все. Последнее на сегодня усовершенствование класса Так получилось, что алгоритм вычисления хэшей для Java строки допускает нулевой хэш для непустой строки. Значение переменной hash призвано запоминать уже вычисленный hash, но если оно равно нулю, то система считает, что мы hash еще не посчитали, и будет его пересчитывать всякий раз. Из-за этого непустые строчки, в которых нулевой hash (к примеру, String[] s = new String[]{"f5a5a608", "abc"}; System.out.println(s[0].hashCode()); //0 System.out.println(s[1].hashCode()); //96354 Поэтому, начиная с Java 13, появилось специальное поле Тут можно поспорить, нужно это было делать или нет: ведь строки с нулевым хэшем должны встречаться очень редко, статистически – одна на 4 миллиарда. Но, по крайней мере, ушла возможность с помощью злонамеренных действий заполнить хэш-таблицу специально строками с нулевым хэшем с целью устроить DoS атаку. Ведь хэш-функция для Java-строк не является криптографической и можно очень легко сгенерировать много строк с заранее заданным хэшем! Есть еще интересный момент. Хотя начиная с Java 7, система больше не занимается попытками частично переиспользовать длинные буферы, в целом не запрещено и даже имеет смысл переиспользовать буфер строки целиком между двумя равными по String x = "Hello"; new String[]{x, new String(x), new String(x.toCharArray()), x + "", "" + x, x.concat(""), "".concat(x)} Как это будет выглядеть с точки зрения размещения объектов в памяти? На Java до версии 15 мы увидим такую картину: Нулевой элемент массива – сама исходная строчка Понятно, что оператор Во втором элементе мы сначала перевели строку в А вот дальше происходит что-то интересное. Случай конкатенации с пустой строкой – тривиальный, но тем не менее, нам спецификация языка говорит, что конкатенация должна порождать новый объект. Однако заметим, что до 15-й Java при этом зачем-то и буфер пересоздается заново! У класса Выглядит это не очень здорово, но, благодаря усилиям Тагира Валеева, начиная с Java 16 картина сильно исправилась. Как мы видим, теперь во всех этих случаях происходит переиспользование буфера для одинаковой строки, в том числе при конкатенации с пустой строкой. Для элемента с индексом 5 микрооптимизация для concat сохраняется, ну и в случае №2, когда мы теряем всякую связь с исходным буфером – ничего не поделаешь, тут, конечно, будет новый объект и новый его буфер: Коротко скажу про интернирование. Наверное, лучше, чтобы много людей не знали про метод Но если вы не пишете стандартную библиотеку Java, то метод Давайте сделаем промежуточные выводы:
Почему так? Про внутреннее устройство строк и их эволюцию довольно много было докладов. Это и доклады Алексея Шипилева (Катехизис java.lang.String (JPoint 2015, 20.04.2015), The Lord of the Strings: Two Scours (JBreak 2016, 19.03.2016)), доклады Тагира Валеева (Ещё немного маленьких оптимизаций (JPoint 2020, 29.06.2020)), и был доклад Сергея Цыпанова на прошлом JPoint (Ах, эти строки (JPoint 2020, 29.06.2020)), тоже посвященный внутренностям строк и каким-то перформанс-тонкостями, с этим связанными. Там вы можете услышать всю теоретическую часть и все объяснения, почему сделано так, а не иначе. Коротко хотелось бы посмотреть на родственников строк – boxed primitives. Они тоже иммутабельные, и для них также существует проблема дедупликации. Вопрос “сколько разных объектов создастся при выполнении такого кода?” можно задавать студентам для проверки того, насколько хорошо они уяснили материал, но я думаю, что у опытного Java-разработчика здесь вопросов быть не должно: new Integer[]{ 42, 42, Integer.valueOf(42), new Integer(42), -4242, -4242 } Оператор Глядя на эту картинку, мы можем сделать следующие выводы:
Списки и очереди Давайте теперь посмотрим что-то более интересное и сложное – на одномерные, линейные структуры данных, к которым относятся списки и очереди. LinkedList На любом курсе по алгоритмам и структурам данных изучается связный список. В Java он реализован в виде класса Подготовим LJV для того, чтобы он красиво нарисовал LJV ljv = new LJV().setDirection(Direction.LR) .addFieldAttribute("last", "constraint=false") .addFieldAttribute("prev", "constraint=false") .setTreatAsPrimitive(Integer.class); Затем возьмём LinkedList, положим туда элементы и получим вот такую картинку: List<Integer> list = new LinkedList<>(); list.add(1); list.add(2); list.add(3); list.add(4); visualize(ljv, list); Действительно, это связный список, который теоретически обладает рядом полезных свойств. Например, в ситуации, когда мы не знаем заранее размера списка, мы его легко, со скоростью O(1) можем увеличить, а также мы можем быстро, со скоростью O(1) в середину вставлять и из середины вынимать элементы. Теоретических преимуществ у этой структуры данных много, но на практике в Java всё обстоит не так. Я люблю показывать своим студентам этот твит Джошуа Блоха: В жизни Java-разработчиков ArrayDeque Для начала рассмотрим очередь. Кажется, что Мы можем столкнуться с фрагментацией памяти: как ноды, так и связанные с ними объекты могут быть “разбросаны” по памяти, и при проходе по А вот как может быть устроена очередь, основанная на массиве? Чтобы понять, как она работает, мы используем метод LJV ljv = new LJV() .setTreatAsPrimitive(Integer.class) .highlightChangingArrayElements(); Deque<Integer> arrayDeque = new ArrayDeque<>(4); arrayDeque.add(1); arrayDeque.add(2); arrayDeque.add(3); visualize(ljv, arrayDeque); ArrayDeque по своему внутреннему устройству похож на //note that this sets initial capacity to 5! Deque<Integer> arrayDeque = new ArrayDeque<>(4); arrayDeque.add(1); arrayDeque.add(2); arrayDeque.add(3); visualize(ljv, arrayDeque); Вот мы вычитали первые два, и мы видим, что они заменились null-ами с начала, а тройка никуда не переместилась. arrayDeque.poll(); //returns 1 arrayDeque.poll(); //returns 2 Потом мы добавили еще три элемента, дошли до конца буфера. Но в начале буфера у нас есть свободное пространство, поэтому закольцевались и пишем с начала. arrayDeque.add(4); arrayDeque.add(5); arrayDeque.add(6); visualize(ljv, arrayDeque); И так далее. То есть получается у нас закольцованный буфер, и если мы примерно с одинаковой скоростью пишем и читаем, и буфер нам не надо изменять в размерах, то ясно, что это будет работать очень эффективно и гораздо эффективней, чем PriorityQueue Другой очень интересный класс – это Если бы мы спросили себя: “как бы мы реализовали очередь с приоритетами?”, ничего об этом заранее не зная, то кажется, первое, что пришло бы на ум, это связный список. Мы его отсортируем. Потом, когда нам надо будет вынимать, мы будем вынимать всегда из головы за время O(1), а когда надо будет вставлять, мы будем вставлять куда-то в серединку, так, чтобы новое значение всегда ставилось на место сортировки, т. е. вставка имела бы сложность O(n). Но на самом деле есть решение иное, без применения связного списка. Давайте возьмём и случайным образом перетасуем массив значений от 0 до 15: List<Integer> list = IntStream.range(0, 16) .boxed() .collect(Collectors.toList()); Collections.shuffle(list); visualize(new LJV().setTreatAsPrimitive(Integer.class), list.toArray()); Потом положим их в PriorityQueue и визуализируем. Получается картинка, очень похожая на ArrayList или ArrayDeque: LJV ljv = new LJV().setTreatAsPrimitive(Integer.class) .setIgnoreNullValuedFields(true) .highlightChangingArrayElements(); PriorityQueue<Integer> q = new PriorityQueue<>(16); q.addAll(list); visualize(ljv, q); Массив значений выглядит так, словно он не до конца отсортирован. Есть маленькие значения в левой части: 0, 1, 6. Но и в правой части тоже есть маленькие – например, 3, 4. Как же это работает? Фокус здесь в том, что применяется так называемая структура binary min-heap, в которой предполагается, что каждый элемент удовлетворяет вот такому инварианту: Нулевой элемент массива меньше следующих за ним двух, то есть 0 меньше 6 и 1. В свою очередь, 6 меньше 7 и 10, 1 меньше 5 и 2 и так далее. Следствие – в голове у нас всегда минимальный элемент. Другое следствие – что мы можем вынимать и вставлять в такую структуру данные за время O(log (n)). q.poll(); Если мы вынули первый элемент из Понятно, что при этом “дырка”, т. е. блок не подлежащих перемещению элементов, каждый раз удваивается, и мы за логарифмическое время передвинем все элементы, потому что мы логарифмически малую долю элементов двигаем. Вот мы можем вынуть пару элементов и посмотреть, как это происходит: Можем вставить какой-то элемент. И мы видим, что всякий раз перемещается только очень маленькое подмножество элементов, и за счет этого PriorityQueue работает быстро. q.add(1); ConcurrentLinkedQueue и ConcurrentLinkedDeque Все вещи, которые я показывал до сих пор, не потокобезопасны. Если мы хотим использовать их в многопоточной программе, мы должны либо их синхронизировать полностью, либо, если мы хотим что-то более эффективное, если мы не хотим устраивать lock contention, нам нужно использовать lock-free структуры. И такие структуры в Java есть. Первая называется То есть в данном случае идея cвязного списка как структуры данных никуда не делась, она здесь работает, позволяя реализовывать lock-free алгоритмы. Конечно, сложность этих двух классов не в их внутренней структуре, а в алгоритмике, которая, увы, никак не визуализируется при помощи LJV. Но, во всяком случае, мы можем видеть, что идея связного списка никуда не девается. Итак, промежуточные выводы по этой части.
Реализации интерфейса Map HashMap Следующая часть посвящена мапам. В первую очередь рассмотрим LJV ljv = new LJV() .setIgnoreNullValuedFields(true) .setTreatAsPrimitive(Integer.class) .setTreatAsPrimitive(String.class); Map<String, Integer> map = new HashMap<>(); map.put("one", 1); map.put("two", 2); map.put("three", 3); map.put("four", 4); visualize(ljv, map); Именно ради этой самой картинки, чтобы показать ее студентам, я в свое время LJV и отыскал. Конкретно для Давайте подготовим более серьезно наш LJV и попробуем устроить более длинные коллизии. Как мы знаем, хэш строки не является криптографическим, строки довольно легко подделать под задуманный хэш, поэтому достаточно просто написать класс, генерирующий очень много строчек с одинаковым хэшем. LJV ljv = new LJV() .setIgnoreNullValuedFields(true) .setTreatAsPrimitive(Integer.class) .setTreatAsPrimitive(String.class) .addIgnoreField("value") .addFieldAttribute("prev", "constraint=false,color=green") .addFieldAttribute("next", "constraint=false,color=green") .addObjectAttributesProvider(Main::redBlackForHM); /*redBlackForHM: red ? "color=red" : "color=black";*/ List<String> collisions = new HashCodeCollision().genCollisionString(7); Map<String, Integer> map = new HashMap<>(); for (int i = 0; i < len; i++) { map.put(collisions.get(i), i); } visualize(ljv, map); Начнём вставлять коллизии в Этим свойством Обратите внимание, что здесь количество bucket-ов вообще никак не спасает ситуацию. Проблема такой коллизии не в том, что ключи попадают в один и тот же бакет случайно: у них у всех хэш одинаковый, поэтому, сколько бакетов не добавляй, они непременно попадут в один и тот же бакет, и map превращается в связный список. Такая беда могла произойти вплоть до Java 7, но в Java 8 ситуацию исправили. Поэтому, если мы возьмем свежую версию Java и накидаем туда много коллизий в одну и ту же hash-таблицу, мы увидим вот такую картинку: В исходниках hashmap это по-английски называется treeification, на русский я бы это перевёл как “одеревенение”. Как только длина связного списка переходит через определенный порог, у нас происходит превращение связного списка в дерево. Заметим, что некоторые ноды покрашены красным, из чего мы делаем вывод, что это красно-черное дерево, но LJV об этом не просто так догадался: обратите внимание на то, что мы передали ему Заметим ещё, что ноды этого дерева “прошиты” зелёными ссылками вперед и назад, с помощью полей Что же произошло? Если коллизий становится слишком много, чтобы все-таки не делать линейный поиск по связному списку, список превращается в красно-черное дерево поиска. Вообще говоря, для дерева поиска нужно, чтобы ключи были сравнимы не только по “равно”, но и по “больше/меньше”. Таким образом, если для ключей реализован интерфейс Мы видим, что здесь очень большой overhead по памяти. Например, много места занимает “лапша” из зелёных ссылок. Она нужна для двух вещей: во-первых, для совместимости с LinkedHashMap Давайте посмотрим визуализацию только что упомянутого Помимо случаев, когда нам надо сохранить правильный порядок перебора элементов внутри мапы, HashMap может работать как LRU-кэш (т. е. least recently used cache). Если создать Map<String, Integer> map = new LinkedHashMap<>(5, 0.8f, /*accessOrder:*/ true); map.put("one", 1); map.put("two", 2); map.put("three", 3); map.put("four", 4); map.get("two"); Такое поведение даёт возможность, например, удалять из кэша те элементы, которые мы дольше всего не читали. Те элементы, которые были прочитаны недавно, всегда будут в голове списка, их удалять не надо. Получается, что Мы сейчас рассмотрели старые классы, о которых более-менее все знают. Я думаю, что большинству Java-разработчиков устройство HashMap знакомо, и вообще, “как устроены HashMap и что изменилось после Java 8?” – это один из довольно расхожих вопросов на собеседованиях. MapN Недавно в Java появилась еще одна вещь, которую, возможно, ещё знают не все. Пользователи Java 11 заметили удобные конструкции ljv = new LJV().setIgnoreNullValuedFields(true); Map.of(1, 'A', 2, 'B', 3, 'C', 4, 'D')); Мы видим, что это ещё одна имплементация интерфейса Самое главное, что для разрешения коллизий у такой мапы используется не chaining-подход, а метод открытой адресации, также известный как linear probing. Если мы положим в наш Map.of("aaa", 1, "abB", 2, "bBa", 3) Мы нашли нужное место в массиве, вставили строчку У linear probing имеется ряд проблем. Во-первых, размер массива бакетов должен быть достаточно большим, чтобы занятые бакеты не “слепились” в большой блок и поиск не превратился в последовательный перебор. Во-вторых, имеется проблема с удалением. Нельзя просто взять и удалить элемент, потому что мы можем создать “дырку” из пустого элемента в массиве и нарушить поиск в linear probing, поэтому приходится что-то с этим делать. Однако особенность иммутабельной мапы как раз в том, что удалять ничего и не надо! Изменять размер её массива в случае переполнения тоже не надо. С момента выбора достаточного размера массива в самом начале больше меняться ничего не будет. Конечно же, такая мапа с точки зрения производительности работает гораздо лучше, и у нее гораздо меньше overhead по памяти. У нее нет проблемы с фрагментацией памяти, потому что все её данные лежат рядом, не то что у ConcurrentHashMap Теперь давайте посмотрим на Map<String, Integer> map = new ConcurrentHashMap<String, Integer>( /*initialCapacity:*/16 , /*loadFactor:*/0.75f, /*concurrencyLevel:*/8); map.put("one", 1); map.put("two", 2); map.put("three", 3); map.put("four", 4); map.put("five", 5); visualize(map); Сначала по хэш-коду ключа определяется то, с каким сегментом мы работаем. Далее этот сегмент мы блокируем, синхронизируемся по нему и работаем с ним, независимо от остальных. Эта история поменялась в Java 8, поэтому глава книги «Java Concurrency in practice», посвящённая Для заполнения элемента массива бакетов используются CAS-операции, а дальше, в случае коллизии, синхронизация уже происходит по всей цепочке нод, привязанной к конкретному бакету. Легко видеть, что здесь гораздо меньше overhead по памяти, структурно все проще, lock contention встречается реже, стало работать лучше. Промежуточные выводы.
Реализации интерфейса NavigableMap TreeMap
Для таких задач имеется интерфейс LJV ljv = new LJV() .setTreatAsPrimitive(Integer.class) .setTreatAsPrimitive(String.class) .setIgnoreNullValuedFields(true) .addIgnoreField("color") .addObjectAttributesProvider(Main::redBlack); //color ? black : red Map<String, Integer> map = new TreeMap<>(); map.put("one", 1); map.put("two", 2); map.put("three", 3); map.put("four", 4); map.put("five", 3); map.put("six", 4); visualize(ljv, map); Действительно, это дерево, и действительно какие-то ноды красные, какие-то – черные. В чём проблема у дерева поиска? Если не предпринимать специальных действий, то вставка элементов в эту структуру может привести к ситуации, когда большинство элементов будут лежать в очень длинных ветвях. Например, если вставлять уже отсортированные данные, то будет всегда выбираться одно и то же плечо дерева, и в итоге вместо дерева у нас получится связный список с линейным O(n) временем поиска. (Опять связный список! Сколько раз он уже был упомянут, и это ещё не последний раз!) Значит, вставка и удаление в дереве поиска должны сопровождаться его перестроением, балансировкой. Идея балансировки красно-чёрного дерева, как в случае с очередью с приоритетами, основана на сохранении инвариантов. Имеются определенные условия, инварианты, которые мы обязаны сохранять на каждом шаге изменения дерева. Вот они:
Из этих условий (посмотрите внимательно на последние два) следует, что путь от корня до конца потенциально самой длинной ветки – он будет состоять из чередующихся ЧКЧК-узлов – будет не более чем вдвое длиннее пути от корня до конца потенциально самой короткой ветки, состоящей только из чёрных узлов. Таким образом, красно-чёрное дерево будет всегда – пусть не идеально, но достаточно хорошо – сбалансировано. Цена сохранения инварианта – всегда логарифмическое время. За неимением времени я не буду рассказывать про алгоритмы, выполняющие данные инварианты, просто давайте посмотрим на визуализацию, как это происходит: ConcurrentSkipListMap Вопрос: если мы хотим то же самое, тот же интерфейс В случае с Для начала вспомним, что такое skip list map в принципе. Это, как ни удивительно, все тот же связный список, в котором мы решили облегчить себе поиск нужного элемента путём “наслоения” дополнительных связных списков. Все значения в этой структуре данных отсортированы. Допустим, нам нужен элемент H. Сначала мы перебираем самый верхний, короткий список и понимаем, что нам нужен диапазон от D до I. Спускаемся на уровень ниже по ссылке Понятно, что с точки зрения затрат памяти это гораздо менее эффективная структура, чем бинарное дерево. Но для того, чтобы создать lock-free структуру, это как раз то, что нужно. Именно на ней lock-free алгоритмы работают. Еще одно замечательное ухищрение, которое здесь используется, заключается в следующем. Когда мы добавляем элементы, нам надо в какой-то момент принимать решение о том, что соответствующий сегмент списка сделался слишком длинным и пора вставлять индексы, т. е. элементы в списках верхнего уровня. Фокус в том, что мы можем принимать такое решение на основании датчиков случайных чисел. Не пытаясь подсчитать количество элементов, независимо от других потоков, которые что-то параллельно делают, просто на основании датчика случайных чисел мы можем автономно принимать решение, когда вставлять индекс. Тогда законы статистики будет работать на нас и в целом наша структура получится примерно сбалансированной: хотя “перекосы” и возможны, но просто вероятность их возникновения будет мала. Поэтому, когда мы визуализируем Какие выводы по этой части можно сделать?
На этом у меня всё. Заходите на проект https://github.com/atp-mipt/ljv, ставьте звёздочки. Спасибо Джону Хеймеру, который в свое время этот проект придумал. Я с ним связался, он сейчас не в Новой Зеландии, он профессор в Шотландии, до сих пор преподает Computer Science, и очень был рад, что эта штука до сих пор актуальна и кому-то пригождается. Спасибо Тагиру Валееву, который ревьюил этот доклад и предложил для него несколько идей. Экспериментируйте с LJV, присылайте свои идеи насчёт того, что ещё было бы интересно визуализировать. Весь этот доклад находится на GitHub, презентация как код. И весь код, который здесь показан, присутствует в этом же проекте. Источник: m.vk.com Комментарии: |
|