Эффективный способ найти "совпадения" в матрице в Java - PullRequest
Новая
       24

Эффективный способ найти "совпадения" в матрице в Java

1 голос
/ 13 июня 2009

У меня есть существующее (java) приложение, которое моделирует книгу заказов, так как она стоит, каждый заказ виден всем остальным. В настоящее время существует требование разместить (что эффективно) ACL для каждого заказа на месте.

Пример для иллюстрации, скажем, у меня есть группы доступа [V-Z] и заказы [A-F] 

      A B C D E F
   V  1 0 0 1 1 0
   W  0 1 1 0 0 1
   X  0 0 0 0 1 1
   Y  1 1 0 0 0 1
   Z  0 1 0 1 0 0

Появляется новый ордер, который определяет видимость как W & Y. Какой быстрый способ вернуть набор значений, которые можно увидеть во входящем ордере?

Одна из предложенных реализаций состоит в том, чтобы представлять каждую строку как BitSet и выполнять W | Хотя интересно, что будет с производительностью при увеличении размера матрицы.

Приятно иметь, но не существенную особенность, это разрешить отношения родитель-потомок в одном измерении, например 

        A B C D E F
   V    1 0 0 1 1 0
   W    0 1 1 0 0 1
   X-1  0 0 0 0 1 1
   X-2  1 0 0 0 1 1
   X-3  0 1 0 0 1 1
   Y    1 1 0 0 0 1
   Z    0 1 0 1 0 0

Было бы идеально, если бы было так же эффективно извлечь "W | X" как "W | X-1"

Любые подсказки в направлении алгоритма и / или соответствующей структуры данных приветствуются.

1 Ответ

1 голос
/ 13 июня 2009

Простое решение: 

class AccessGroupName { ... }
class Order { ... }

Map<AccessGroupName, Collection<Order>> visibility = new HashMap<AccessGroupName, Collection<Order>>();

addVisibility(AccessGroupName group, Order order) {
    Collection<Order> orders = visibilities.get(group);
    if (orders == null) {
        orders = new ArrayList<Order>();
        visibility.put(group, orders);
    }
    if (!orders.contains(order)) orders.add(order);
}

public Set<Order> getVisibility(Collection<AccessGroupName> names) {
    Set<Order> visible = new HashSet<Order>();
    for (AccessGroupName name: names) {
        visible.addAll(visibilities.get(name));
    }
    return visible;
}

HashMap ищет O (1). Итерирование ArrayList - это O (n). Добавление элементов в HashSet - O (n). В целом, это будет O (n), где n - это общее количество элементов в добавленных списках (которое может быть больше, чем количество элементов в результирующем наборе, если есть наложение). Константа - это, примерно, время, необходимое для получения элемента из итератора ArrayList, плюс время, необходимое для добавления чего-либо в HashSet - первое порядка 10 циклов, второе ближе к 100.

Использование памяти сверх самих экземпляров AccessGroupName и Order составляет около 14-15 слов на группу плюс 1-2 слова на заказ. Главным образом заголовки объекта.

Этот код не делает ничего умного, но я думаю, что вам будет довольно трудно победить O (n) с константой <200 циклов. </p>

В частности, если условная матрица является разреженной (то есть, если есть много групп доступа с несколькими заказами в каждой), это отбросит штаны от подхода с битами, что приведет к потере чертовски много места по нулям, а время по нулям ИЛИ вместе.

...