効率的な方法で、javaのマトリックスで "一致"を見つける

Question

私は、注文書をモデル化する既存の（Java）アプリケーションを持っています。オーダーごとのACLを適切に配置する必要があります。

説明する例は、& Y. Wとして可視性を指定し、私は新しい秩序が、その中に来る[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 

アクセスグループ[VZ]と注文を持っていると言うことができますへの迅速な方法だろう何着信オーダーで確認できる値のセットを返しますか？

提案されている実装の1つは、各行を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 "

アルゴリズムの方向性に関するヒントや適切なデータ構造については、非常に感謝しています。

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つのオーダーにつき1〜2ワードです。主にオブジェクトヘッダー。

このコードでは何も巧妙なことはしませんが、私はあなたがかなり正確にO（n）を打ち、< 200サイクルの定数で打ち負かすと思います。

特に、想定マトリックスが疎である（つまり、それぞれが少数のオーダーのアクセスグループがたくさんある場合）、これはビットセットアプローチからズボンを打ち負かし、多くの0のスペース、および0のORをとる時間。