Веб-два-нольные ярлыки для Java

Когда мне понадобилось реализовать ярлыки для Java «как в веб-два-ноль», гугление не помогло найти ни одной библиотеки, содержащей в себе подобный тип коллекции.

Решил сделать сам.

Итак, нам надо хранить объекты в коллекции данного типа (назовем его, скажем, LabelsMultiMap). Как объекты, так и ярлыки могут быть произвольного типа. Количество ярлыков сверху не ограничено, равно как и количество объектов. Одним и тем же набором ярлыков могут быть описаны более 1 объекта. У одного объекта один ярлык может встретиться только 1 раз.

Пример валидных ярлыков:
Ярлыки Объекты
green, wooden, alive tree
green, wooden, lifeless bench
green, alive, croak frog

Коллекция должна позволять:

  1. put() — помещать в неё объекты со списком прикрепленных меток
  2. getValues() — возвращать объекты, содержащиеся в коллекции
  3. findValues() — осуществлять поиск объектов, ярлыки которых содержат запрашиваемый набор ярлыков
  4. findValuesOnlyIn() — осуществлять поиск только тех объектов, все ярлыки которых входят в запрашиваемый набор ярлыков


Поясню последние 2 пункта на следующей таблице по тем объектам, которые были рассмотрены в предыдущем примере:
Ярлыки, передаваемые в качестве аргумента findValues() findValuesOnlyIn()
green, wooden tree, bench
green, wooden, alive, lifeless tree, bench
tree, bench, frog

Поиск должен быть быстрым, поэтому для индексации будем использовать битовые маски. Т.е. сам объект храним в массиве, а его порядковый номер в этом массиве — это порядковый номер бита в битовой маске.

Опять же вернемся к нашему примеру:

Нумерация объектов в массиве: 0 — tree, 1 — bench, 2 — frog.
Тогда битовая маска для ярлыка green будет {1, 1, 1}, для wooden — {1, 1, 0}, для alive — {1, 0, 1}, lifeless — {0, 1, 0}, croak — {0, 0, 1}.

Битовые маски позволяют упростить поиск объектов по ярлыку, просто выполняя двоичные операции: AND, OR, NOT и т.п… В результате, если на определенной позиции останется единичный бит, то по её номеру легко извлечём из массива искомый объект.

Начинаем реализацию:

Здесь V — тип объектов, L — тип ярлыков, labelsBitSets — хранилище битовых масок ярлыков, values — хранилище объектов:

public class LabelsMultiMap<L, V> {
  private final Map<L, BitSet> labelsBitSets = new HashMap<>();
  private final List<V> values = new ArrayList<>();
}

Метод, помещающий новый объект с его описывающими ярлыками в нашу коллекцию:

Здесь мы помещаем наш объект в values в методе addValue(), который вернет индекс новой ячейки массива. Далее по каждому ярлыку проверяем, есть ли битовая маска для данного ярлыка, если нет, то создаем пустую маску, добавляем в labelsBitSets, если уже есть, то возвращаем старую маску, и выставляем единичный бит в ней по позиции объекта в массиве, которая хранится в i:

public void put(Set<L> labels, V value) {
  int i = addValue(value);
  for(L label : labels) {
    BitSet bitSet = getOrCreateLabel(label);
    bitSet.set(i);
  }
}

Метод, возвращающий все объекты из коллекции:

public List<V> getValues() {
  return Collections.unmodifiableList(values);
}

Метод, осуществляющий поиск объектов, ярлыки которых содержат запрашиваемый набор ярлыков:

public Collection<V> findValues(Set<L> labels) {
  Iterator<L> it = labels.iterator();

Если список ярлыков в аргументе пуст, то возвращаем весь список:

  if (!it.hasNext()) {
    return getValues();
  }

Если по первому попавшемуся ярлыку не нашли ни одной битовой маски, то возвращаем пустой результат:

  BitSet firstBitSet = labelsBitSets.get(it.next());
  if (firstBitSet == null) {
    return Collections.emptySet();
  }

Инициализируем аккумулятор, куда будем накапливать найденные битовые маски с помощью операции AND. Использовал clone(), т.к. у BitSet отсутствует конструктор копирования:

  BitSet accumulator = (BitSet) firstBitSet.clone();

Накапливаем в accumulator все маски, если не нашли хоть одну битовую маску по одному из последующих ярлыков, то возвращаем пустую коллекцию:

  while (it.hasNext()) {
    BitSet nextBitSet = labelsBitSets.get(it.next());
    if (nextBitSet == null) {
      return Collections.emptySet();
    }
    accumulator.and(nextBitSet);
  }

Возвращаем результат в виде новой коллекции по накопленной маске в accumulator:

  return new ValuesByBitSetCollection<>(accumulator, values);
}

Ну и последний метод, осуществляющий поиск только тех объектов, все ярлыки которых входят в запрашиваемый набор ярлыков:

В inAccumulator накапливаем те битовые маски, которые есть в нашем запросе, а в outAccumulator — которых нет в нашем запросе, если исходный запрос пуст, возвращаем пустое множество:

public Collection<V> findValuesOnlyIn(Set<L> labels) {
  if (labels.isEmpty()) {
    return Collections.emptySet();
  }
  BitSet inAccumulator = new BitSet(values.size());
  BitSet outAccumulator = new BitSet(values.size());

Пробегаем по всем сохраненным ярлыкам в нашей коллекции, откладывая их битовые маски в in-/outAccumulator в зависимости от наличия их в labels, в конце просто вычтем одно множество из другого и вернем результат в виде коллекции по результирующей маске.

  for(Map.Entry<L, BitSet> bitSetEntry : labelsBitSets.entrySet()) {
    BitSet accumulator = labels.contains(bitSetEntry.getKey()) ? inAccumulator : outAccumulator;
    accumulator.or(bitSetEntry.getValue());
  }
  
  inAccumulator.andNot(outAccumulator);

  return new ValuesByBitSetCollection<>(inAccumulator, values);
}

Вспомогательные классы и методы
Вспомогательная функция по добавлению элемента в массив (добавляем элемент в конец массива, возвращаем его позицию):
private int addValue(V value) {
  values.add(value);
  return values.size() - 1;
}

Вспомогательная функция по возврату битовой маски для данного ярлыка:

private BitSet createOrGetLabel(L label) {
  BitSet ret = labelsBitSets.get(label);
  if (ret == null) {
    ret = new BitSet(values.size());
    labelsBitSets.put(label, ret);
  }
  return ret;
}

Вспомогательный класс, позволяющий накладывать на массив битовую маску, в size кэшируем количество единичных бит в маске (BitSet.cardinality()):

private static class ValuesByBitSetCollection<V> extends AbstractCollection<V> {
  private final BitSet bitSet;
  private final List<V> values;
  private int size = -1;
  
  private ValuesByBitSetCollection(BitSet bitSet, List<V> values) {
    this.bitSet = bitSet;
    this.values = values;
  }

  @Override
  public boolean isEmpty() {
    return bitSet.isEmpty();
  }

  @Override
  public Iterator<V> iterator() {
    return new ValuesByBitSetIterator<>(bitSet, values);
  }

  @Override
  public int size() {
    if (size < 0) {
      size = bitSet.cardinality();
    }
    return size;
  }
}

Вспомогательный класс для итерирования по этой коллекции, в index храним позицию следующего установленного бита (или -1, если такого бита больше нет):

private static class ValuesByBitSetIterator<V> implements Iterator<V> {
  private final BitSet bitSet;
  private final List<V> values;
  private int index;

  private ValuesByBitSetIterator(BitSet bitSet, List<V> values) {
    this.bitSet = bitSet;
    this.values = values;
    index = bitSet.nextSetBit(0);
  }

  @Override
  public boolean hasNext() {
    return index >= 0;
  }

  @Override
  public V next() {
    if (index < 0) {
      throw new NoSuchElementException();
    }
    V ret = values.get(index);
    index = bitSet.nextSetBit(index + 1);
    return ret;
  }

  @Override
  public void remove() {
    throw new UnsupportedOperationException();
  }
}

Share post

Comments 7

    +1
    Чем вас не устроил com.google.common.collect.BiMultimap?
      0
      Он отнаследован от SetMultimap, метод get() которого возвращает множество значений. Вот если бы был метод, который накладывал constraint на весь BiMultimap и возвращал view, типа BiMultimap, значения которого имеют данный ярлык, то да, эта функциональность меня бы устроила.
        0
        я тоже первым делом подумал про BiMultimap, а ответа не понял — какого именно метода не хватает?
        put и getValues тривиально
        findValues(List labels) — Multimaps.filterValues(objectToLabel, Predicates.in(labels)).getKeys()
        и т.п.
          0
          Поизучал, как работают предикаты и Multimaps.filterValues(): получается, что последовательно (с помощью Predicates.AndPredicate.apply()) накладывает условие на ярлыки по всем элементам коллекции для каждого ярлыка из запроса.

          Т.е. если у нас в среднем m ярлыков в запросе, в среднем n ярлыков для каждого объекта в коллекции, и k объектов в коллекции, то временная сложность алгоритма итерирования по Multimaps.filterValues().values() будет O(k*m) (если принимаем, что Set.contains() имеет сложность O(1))

          В моем же случае уже есть предрасчитанный bitmap index, который сводит временную сложность к O(m + k).
            0
            Согласен! Вопрос, как обычно, в том важно ли это =)

            Вы не писали, зачем вы это делаете — для прод системы? Логичнее было бы БД использовать. В любом случае распределенная система по-хорошему нужна.
              0
              Для прод системы: есть много устройств в сети, которым надо обращаться, у каждого есть набор уникальных свойств/фич, этим свойствам присвоены лейблы.

              Есть диспетчер, который перед стартом работы из базы вычитывает инфу по устройствам и начинает асинхронно принимать запросы от сторонних систем (у каждого из запросов набор лейблов, которыми должно обладать то или иное устройство, чтобы выполнить запрос). Диспетчер должен быстро перенаправить запрос на то или иное свободное устройство согласно информации о лейблах, дождаться ответа от устройства, и перенаправить ответ обратно.

              Есть динамическое удаление устройства (например, выходит из строя, или проблемы с сетью). Но пока это редкое событие, поэтому удаление не реализовывал (потребуется перестроение bitmap-индексов), а удаленные устройства отфильтровываю по флажку недоступности.

              Если бы использовал БД, то это лишние лаги и введение лишних точек отказа (линк до бд, да и сама бд).
        0
        Кстати, BiMultimap не входит в релизную ветку гуавы, соответственно та версия, которая, например, через мавен к моему проекту подтягивается, не имеет этой функциональности.

      Only users with full accounts can post comments. Log in, please.