1. Вступление

В заметке будут рассмотрены некоторые теоретические и практические вопросы операций над множествами при помощи бесплатной библиотеки Google Guava. Прежде всего, основное внимание будет уделено её применению в системах анализа поведенческих факторов, которые применяются для повышения качества (конверсии) крупных интернет-ресурсов.

2. Комбинаторика

Предположим, что мы выполняем обработку персонализированной статистики. Нам известны темы документов интернет-ресурса и количество просмотров (без отказов). Более того, мы знаем сколько каждый конкретный пользователь посмотрел документов (в разрезе по темам). Пусть каждый документ является элементом одного из пяти множеств (множество — это тема документа). Мы наблюдаем, что все пользователи сайта (в примере их 6 для экономии места) очень активно смотрят только документы из множества T1:



Для более удобного визуального восприятия можно отобразить матрицу:





Рассмотрим на этом примере несколько задач комбинаторики. Во-первых, попробуем выявить сколько существует комбинаций порядка просмотра документов. Данная величина напрямую зависит от мощности этого множества (количества элементов). Если мы его знаем, то и знаем и количество комбинаций. Например, факториал числа 9 равен 362880 (в R это factorial(9)).

Во-вторых, возникает потребность узнать, сколькими способами я могу выбрать заданное количество элементов из множества (биномиальный коэффициент из n по k). Нам нужно знать количество выбираемых элементов и мощность множества. Как вы помните, порядок расположения элементов не учитывается. Если бы я использовал R, то написал бы:

> choose(19,3)
[1] 969

Получается, что если я буду читать по 3 документа из 19 возможных, то я смогу это сделать при помощи 969 комбинаций. Вернёмся к Java, а точнее к Google Guava, где также необходимо передавать упомянутую информацию. Попробуем:

logger.trace(LongMath.factorial(9)); // 362880
logger.trace(LongMath.binomial(19, 3)); // 969

3. Формирование множеств

При наполнении коллекции (обычно это импорт данных из других систем по API или через RabbitMQ, Redis, Tarantool) можно использовать весьма простую схему: добавлять в коллекцию имя множества в виде ключа, а имя элемента в виде значения. В результате получим:

Multimap<String, String> sets = ArrayListMultimap.create();
		
sets.put("main", "a");
sets.put("new", "b");
sets.put("new", "c");

logger.trace(sets.get("main")); // [a]
logger.trace(sets.get("new")); // [b, c]
logger.trace(sets.asMap()); // {new=[b, c], main=[a]}

// Попробуем простой схематический пример в стиле «Привет Мир!»
Gson gson = new Gson();
Jedis jedis = new Jedis("localhost");

jedis.set("habr", gson.toJson(sets.asMap()));
logger.trace(jedis.get("habr")); // {"new":["b","c"],"main":["a"]}

Теперь я попробую получить данные на стороне проекта, написанного на PHP. Обычно для этого используется готовая библиотека, однако, в данном примере (на «продакшене» лучше так не делать) я попробую вручную посчитать количество аргументов и их длину, чтобы сделать прямой запрос на родном для Redis протоколе:

$fp = fsockopen('127.0.0.1', 6379);

fwrite($fp,  "*2\r\n\$3\r\nGET\r\n\$4\r\nhabr\r\n");
echo fgets($fp);
echo fgets($fp);

Вижу смысл упомянуть о других простых способах получения элементов множества из локальных файлов или сетевых ресурсов. Прежде всего, это метод readLines, который есть у класса Files (работа с локальной файловой системой) и у класса Resources (работа с распределённой системой, но доступной по HTTP протоколу в свободном режиме). Иногда приходится получать список элементов из обычной строки, где разделение происходит запятой или пробелом. Для этого тоже есть полезные методы. Вот примеры некоторых из них:

List<String> eventNames = Resources.readLines(new URL(url), Charsets.UTF_8);
logger.trace(eventNames);

List<String> set = Splitter.on(',').trimResults().omitEmptyStrings().splitToList("a,b,b,b,c");
logger.trace(set); // [a, b, b, b, c]

String test = Joiner.on(" - ").join(set);
logger.trace(test); // a - b - b - b - c

4. Основные операции над множествами

Рассмотрим пример и дадим описание выполненным операциям:

Set<String> a = ImmutableSet.of("a", "b", "c", "d");
Set<String> b = ImmutableSet.of("c", "d", "e", "f");

logger.trace(Sets.union(a, b)); // [a, b, c, d, e, f]
logger.trace(Sets.intersection(a, b)); // [c, d]
logger.trace(Sets.difference(a, b)); // [a, b]
logger.trace(Sets.symmetricDifference(a, b)); // [a, b, e, f]

В данном примере были выполнены следующие операции:

• Объединение (union) создаёт новый объект (множество), который поглотил в себя все элементы обоих множеств. Разумеется, без дублей элементов. Мы можем быть уверены, что теперь любой уникальный элемент, который был в одном из этих множеств, стал элементом нового множества.
• Пересечение (intersection) порождает новое множество, которое может содержать только совпадающие (есть у первого и у второго) элементы. Что у них есть общего, то и будет в новом множестве.
• С понятием разности (difference) тоже всё просто — новое множество содержит только те элементы, которые входят в первое множество, но не входят во второе.
• Есть ещё и такое понятие, как симметрическая разность (symmetricDifference). В этом случае мы получаем новое множество, которое состоит из всех элементов обоих множеств, кроме пересечённых. Например, если мы заходим увидеть симметрическую разницу множества с самим собой, то получим пустое множество.

5. Множества, в которых могут быть не уникальные элементы

Хочу обратить ваше внимание на коллекцию HashMultiset, которая позволяет максимально просто выполнять подсчёт количества повторяющихся элементов. Вполне логичное желание получить отсортированный список по количеству повторений:

HashMultiset<String> habr = HashMultiset.create();
habr.add("habr_7");
habr.add("habr_5");
habr.add("habr_5");
habr.add("habr_5");
habr.add("habr_5");
habr.add("habr_9");
habr.add("habr_9");
habr.add("habr_1");
habr.add("habr_1");
habr.add("habr_1");

logger.trace(habr); // [habr_1 x 3, habr_9 x 2, habr_5 x 4, habr_7]

logger.trace(habr.count("habr_1")); // 3
logger.trace(habr.count("habr_5")); // 4
logger.trace(habr.count("habr_0")); // 0

ImmutableMultiset<String> highestRank = Multisets.copyHighestCountFirst(habr);
logger.trace(highestRank); // [habr_5 x 4, habr_1 x 3, habr_9 x 2, habr_7]

6. Заключение

Очень надеюсь, что данная скромная заметка поможет некоторым читателям лучше понять и быстрее разобраться в ряде теоретических и практических вопросов работы с множествами при помощи Google Guava.