자바의 행렬에서 "matches"를 찾는 효율적인 방법

Question

주문 주문서를 모델링하는 기존 (java) 응용 프로그램이 있습니다. 이제 주문 ACL 당 (효과적으로 무엇이) ACL을 제자리에 두어야한다는 요구 사항이 있습니다.

설명하기 위해 예, 나는 액세스 그룹 [VZ]와이 있다고 할 수 있습니다 주문 [AF] 새로운 순서가 온다

 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 

는 빠르고 방법이 될 것입니다 무엇 & Y. W 가시성을 지정합니다 수신 오더에서 볼 수있는 값 집합을 반환 하시겠습니까?

제안 된 한 가지 구현은 각 행을 BitSet으로 표현하고 W | 매트릭스의 크기가 커질수록 성능에 어떤 영향이 있을지 궁금합니다. "로 |"X 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-1 "

알고리즘 방향 및/또는 적절한 데이터 구조에 대한 힌트를 주시면 감사하겠습니다.

Answer 1

간단한 해결책 :

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 단어를 사용합니다. 주로 객체 헤더.

이 코드는 영리하지 못하지만, 당신은 꽤 반복적으로 < 200주기의 O (n)을 이길 것이라고 생각합니다.

특히 개념적 매트릭스가 희박한 경우 (즉, 각각 몇 개의 주문이있는 많은 액세스 그룹이있는 경우), 이것은 비트 세트 방식에서 벗어나 바지를 뜯어 낼 것입니다. 공간은 0으로, 시간은 함께 OR 제로.