LJV

Чему нас может научить визуализация структур данных в Java

Иван Пономарев

ivan

Иван Пономарев

  • Техлид в компании КУРС

  • Преподаю Java в МФТИ

Что значит «сделать лекционный курс»?

  • 14 недель подряд каждую неделю готовить доклад на 1,5 часа

  • На доске рисовать неохота (а теперь ещё и нельзя)

  • Хочется делать слайды как код

  • Можно ли, чтобы слайды рисовали себя сами?

https://habr.com/ru/post/456032/

presentationascode

GraphViz (Graph Visualization Software)

  • Initial release: before 1991

  • Latest release: 2.46.1, February 2021

  • DOT language & visualization software

GraphViz (Graph Visualization Software)

        digraph G{
          A->B->C;
          B->D->A;
          C->A;
        }
dot -Tpng myfile.dot > myfile.png
diag e76cb0718790c18785ef409880a4f1ea

Lightweight Java Visualizer

Lightweight Java Visualizer: второе рождение

  • Нурас Ногаев, Илья Селиванов (МФТИ)

  • Улучшен API

  • Обновлён GraphViz

  • GitHub, Maven, CI, тесты

https://github.com/atp-mipt/ljv

githubljv

Шаг 1: создаём и конфигурируем LJV

LJV ljv = new LJV()
    .setQualifyNestedClassNames(true)
    .setIgnoreNullValuedFields(true)
    .addFieldAttribute("sourceSpliterator", "constraint=false");

Шаг 2: создаём изучаемый объект

Stream<Integer> o =
    List.of(1, 2, 3)
    .stream()
    .map(x -> x * x)
    .filter(x -> x % 2 == 0);

Шаг 3: визуализируем

//DOT script
String dot = ljv.drawGraph(o);

//use GraphViz online
String encoded = URLEncoder.encode(dot, "UTF8")
                .replaceAll("\\+", "%20");
Desktop.getDesktop().browse(
    new URI("https://dreampuf.github.io/GraphvizOnline/#"
                        + encoded));

Шаг 4: смотрим, что же у нас получилось

diag a9ec5d888cff8dc2e78244d5e4e9877a

Наш план

  • Строки и обёртки примитивов

  • Очереди

  • Map и ConcurrentMap

  • NavigableMap и ConcurrentNavigableMap

Строка

 new LJV().drawGraph("Hello");

Эволюция String

Java 6–

Java 7+

Java 9+

Java 13+

diag 8a47e5061084a40f0aed95f784fcc479
diag f655369e584705b2dc6b1c1e888e6329
diag 177e2ddf6f640f5b20f31f26eda54d7a
diag 218c0aabc28eef42772097d6105de7e9

evolution

Java 6

"The quick brown fox jumps over the lazy dog".split(" ")
diag f4ce26d56320065441c201e9f1e52dd8

Java 6: memory leak

"The quick brown fox jumps over the lazy dog".substring(0, 3)
diag c9d2092ccd7fc79df0c61d4f8562aa55

Java 8: no offset/count

"The quick brown fox jumps over the lazy dog".split(" ")
diag 91f5d0290cc6ad789b666f6eff9739c0

Java 8: no offset/count

"The quick brown fox jumps over the lazy dog".substring(0, 3)
diag ffdd7df126b4aae8a3904f18ab054825

Java 8-: backed by char[]

new String[]{"Hello!", "Привет!"}
diag 4e2ede1b97506aad704e0b1a5985df93

Java 9+: backed by byte[]

new String[]{"Hello!", "Привет!"}
diag 49bed2720bb284a9e72429840e7068ef

Zero hashcode: Java 12-

String[] s = new String[]{"f5a5a608", "abc"};
System.out.println(s[0].hashCode()); //0
System.out.println(s[1].hashCode()); //96354
diag 41907651d1a9e88e16c8e3f783e525f2

Zero hashcode: Java 13+

String[] s = new String[]{"f5a5a608", "abc"};
System.out.println(s[0].hashCode()); //0
System.out.println(s[1].hashCode()); //96354
diag 4e6a98961bb5130ac3fd003667843945

Создание строк

LJV ljv = new LJV().addIgnoreField("hash")
    .addIgnoreField("coder").addIgnoreField("hashIsZero");
String x = "Hello";
new String[]{x,
             new String(x),
             new String(x.toCharArray()),
             x + "",
             "" + x,
             x.concat(""),
             "".concat(x)}

Создание строк (Java 15-)

diag f6f3f6d6397ac28be62896ae9a5b4c9d
    /*0*/   x,
    /*1*/   new String(x),  //переиспользуется буфер
    /*2*/   new String(x.toCharArray()),
    /*3*/   x + "",
    /*4*/   "" + x,
    /*5*/   x.concat(""),   //переиспользуется весь x
    /*6*/   "".concat(x)

Создание строк (Java 16+)

diag 3514e093a498909bfd797bc3fecbc7b3
    /*0*/   x,
    /*1*/   new String(x),
    /*2*/   new String(x.toCharArray()),
    /*3*/   x + "",
    /*4*/   "" + x,
    /*5*/   x.concat(""),   //переиспользуется весь x
    /*6*/   "".concat(x)

Интернирование строк

x,
new String(x).intern(),
new String(x.toCharArray()).intern(),
(x + "").intern(),
("" + x).intern(),
x.concat("").intern(),
"".concat(x).intern()
diag 654b4ee0702f701eb2733bf70d274b01

Промежуточные выводы

  • Переходите на новые версии Java, строки всё лучше и лучше!

  • При наличии показаний со стороны перформанс-анализа делайте дедупликацию строк (но не через intern()).

Что посмотреть по теме

Дедупликация (кэширование) boxed primitives

new Integer[]{
    42,
    42,
    Integer.valueOf(42),
    new Integer(42),
    -4242,
    -4242
}

Дедупликация (кэширование) boxed primitives

diag c4f4d6523f13cabdbc397e94cf9644b4
/*0*/ 42,
/*1*/ 42, // дедуплицируется диапазон -128 .. 127
          // или -128 .. -XX:AutoBoxCacheMax
/*2*/ Integer.valueOf(42), //дедуплицируется
/*3*/ new Integer(42),   //НЕ дедуплицируется, deprecated since Java9
/*4*/ -4242,
/*5*/ -4242              //не дедуплицируется (вне диапазона)

Промежуточные выводы

  • Помните о дедупликации boxed primitives

  • При наличии показаний со стороны перформанс-анализа используйте библиотеки:

Наш план

  • Строки и обёртки примитивов

  • Очереди

  • Map и ConcurrentMap

  • NavigableMap и ConcurrentNavigableMap

LinkedList (implements List, Deque)

LJV ljv = new LJV().setDirection(Direction.LR)
    .addFieldAttribute("last", "constraint=false")
    .addFieldAttribute("prev", "constraint=false")
    .setTreatAsPrimitive(Integer.class);

List<Integer> list = new LinkedList<>();
list.add(1); list.add(2); list.add(3); list.add(4);
visualize(ljv, list);
diag 5a782d85c3c701329e2140525f1d055e

Нужен ли LinkedList в Java?

whouselinkedlist

ArrayDeque

LJV ljv = new LJV()
    .setTreatAsPrimitive(Integer.class)
    .highlightChangingArrayElements();

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);
diag 14846a10de07a9c8c4616b4ec8daab6e

ArrayDeque

        arrayDeque.poll(); //returns 1
        arrayDeque.poll(); //returns 2
        visualize(ljv, arrayDeque);
diag ea195445f87ed9c0adb97d358c3822e4

ArrayDeque

    arrayDeque.add(4); arrayDeque.add(5); arrayDeque.add(6);
    visualize(ljv, arrayDeque);
diag d9a2952c39a9de9144771e2a7e69e07d

PriorityQueue

List<Integer> list = IntStream.range(0, 16)
                     .boxed()
                     .collect(Collectors.toList());
Collections.shuffle(list);
visualize(new LJV().setTreatAsPrimitive(Integer.class),
          list.toArray());
diag 65dd67a6a108558b2bd481dc7a1f90ad

PriorityQueue

LJV ljv = new LJV().setTreatAsPrimitive(Integer.class)
                .setIgnoreNullValuedFields(true)
                .highlightChangingArrayElements();
PriorityQueue<Integer> q = new PriorityQueue<>(16);
q.addAll(list);
visualize(ljv, q);
diag 52946411dfaa694712346695bb798779

PriorityQueue: в чём фокус?

  • Binary min-heap, инварианты:

    • \(q[n] \leq q[2n + 1]\)

    • \(q[n] \leq q[2n+2]\)

  • Следствие:

    • \(q[0] = \min(q)\)

diag 2e2d8fa8d1de0102cf07cdf64c1e5460

Удаление элемента

q.poll();
diag f99a78d8ee39e9a54a171203ee7c625e

Удаление элемента

q.poll();
diag f6c574d2589a5df22a4429490b44571b

Удаление элемента

q.poll();
diag 1af4ba217bd329dca800ff572c8f945f

Добавление элемента

q.add(1);
diag 62a83e374c3434e81ec4828e7cf22650

Concurrent Lock-free Queue/Deque?

diag 09fb9124fc09b82ec74573b35f329970
diag ef15a0c7414cabb764209168a459e707

Промежуточные выводы

  • java.util.LinkedList не нужен, используем ArrayList / ArrayDeque / PriorityQueue.

  • Массив — очень мощная основа для построения эффективных структур данных!

  • Если нужна потокобезопасность и неблокирующее поведение, идея связного списка снова начинает работать в ConcurrentLinkedQueue / ConcurrentLinkedDeque.

Наш план

  • Строки и обёртки примитивов

  • Очереди

  • Map и ConcurrentMap

  • NavigableMap и ConcurrentNavigableMap

Его Величество 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);

Его Величество HashMap

diag b7c1cad1e9ec048c9054a056b4306b83

Готовим визуализацию

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);

6 коллизий

diag 41e7067318c90131cc22b93de227082a

11 коллизий, Java 8+: одеревенение

diag 5c2b1a4c5a4c3ca34fc904c99c40a37f

TreeNode

static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
    TreeNode<K,V> parent;  // red-black tree links
    TreeNode<K,V> left;
    TreeNode<K,V> right;
    TreeNode<K,V> prev;    // needed to unlink next upon deletion
    boolean red;

LinkedHashMap.Entry?!

LinkedHashMap: почти готовый LRU кэш

diag 849fc10c0315b57571ea59b06820f1d0

LinkedHashMap: режим access order

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);
diag f27f80080c2ef6721f18db71ab7ad86b

LinkedHashMap: режим access order

map.get("two");
diag c3ee6273e13d1c1872a008d8cfb4e73a

MapN: иммутабельная хэшмапа

ljv = new LJV().setIgnoreNullValuedFields(true);

Map.of(1, 'A', 2, 'B', 3, 'C', 4, 'D'));
diag 5c4367eb3fa0906c02f05021a5b875ab

Коллизии в MapN: linear probing

 Map.of("aaa", 1, "abB", 2, "bBa", 3)
diag 4baa969b9ebc137e243ca0ffc27f5095

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);

ConcurrentHashMap: Java 7-

diag 75b946bfeba2674ef90d0eda76495543

ConcurrentHashMap: Java 8+

diag de8c5a19b8c187f0c487097730a7ea44

Промежуточные выводы

  • Существенный апгрейд HashMap и ConcurrentHashMap — в Java 8.

  • В Java 9 — иммутабельные хэшмапы с открытой адресацией.

  • Не забываем про LinkedHashMap:

    • два режима работы

    • protected boolean removeEldestEntry(…​)

Наш план

  • Строки и обёртки примитивов

  • Очереди

  • Map и ConcurrentMap

  • NavigableMap и ConcurrentNavigableMap

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);

TreeMap: красно-чёрное дерево

diag fc41f44f18be6cd23ef916963502ab46

Красно-чёрное дерево: в чём фокус?

  • Инварианты КЧД:

    • Корень — чёрный.

    • null—«листья» в конце ветвей считаются чёрными.

    • Оба потомка каждого красного узла — чёрные.

    • Любой простой путь от узла-предка до листового узла-потомка содержит одинаковое число чёрных узлов.

  • Следствие:

    • Путь от корня до самого дальнего листа (ЧКЧКЧ…​) не более чем вдвое длиннее, чем до самого ближнего (ЧЧЧ…​)

TreeMap

diag 0f56dcb9ab3a6567851ebe91a8c17ffb

TreeMap

diag 52e8b326a5d2ab65dcf726afe0385f0d

TreeMap

diag 5f50b3a399b36a9c012c65340e4d4e25

TreeMap

diag 34179ad63ee5a054ad0e766a6035e9c5

TreeMap

diag 69bad9544b2d6335bd3a346d7d4fadb4

TreeMap

diag 7119237aaa6dfd368f568e40af2962f0

TreeMap

diag fd77a5a1b639ce9cd06ff6cca2d8867a

TreeMap

diag 5c3cf32c844f425e45c36dec6df05bd9

ConcurrentNavigableMap: то же самое, но thread-safe?

  • ConcurrentSkipListMap

  • В комментариях к исходному коду CSLM обнаруживаются:

    • две научные статьи

    • книга

    • три докторских диссертации

ConcurrentSkipListMap: идея

diag 2cc9358d9bc8084479bef4ca4b30492e

ConcurrentSkipListMap

diag b606e8be52eb288b608f929e19e6cf0d

ConcurrentSkipListMap

diag 680c74d5072e8e2c578e85e01057c382

ConcurrentSkipListMap

diag ae7dc25ab9f27a11bcda0d982bd8da44

ConcurrentSkipListMap

diag eccbf6ed36aa23fa571317cab7437339

ConcurrentSkipListMap

diag 3bedfe9b3655832d804a930fc0b7e7cc

ConcurrentSkipListMap

diag 48b14a62d6be88fd521f42d2150da41f

ConcurrentSkipListMap

diag 52de3fc564297968055f1815120e6258

ConcurrentSkipListMap

diag e527c2f59f60c54f5551afa4e3de4088

Промежуточные выводы

  • Продвинутые алгоритмы творят чудеса.

  • Мы вступили на почву, где простой визуализации недостаточно.

На этом всё!