Java：コレクションを等価クラスに分割する方法は？

Question

私が項目のリストを持っている（！）：

• B
• C
• D
• E
• ...

は、私がしたいですそれらをグループ化する：

• [A、C、D]
• [B、E]
• ...

グループはによって定義される：グループ内のすべての項目が記載等しい

• >ブール
• F（A、B）= F（B、A）

- カスタム関数 F（A、B）に

質問：は準備ができていますか？

<T> List<List<T>> group(Collection<T> collection, BiFunction<T, T, Boolean> eqF); 

UPDATE。この質問は、あなたがグループ化するためにいくつかの品質を定義することができるシナリオでは全くありません！この場合、Java 8 Collectors.groupingByが最も簡単な答えです。私は、多次元ベクトルと平等の機能で働いています

は、次のようになります。

• メトリックハッシュを定義することは、最初のタスクを解決するに等しい。このケースでは（a、b）は<しきい値

： ）

Answer 1

ハッシュを使用して線形時間でこれを行うことができます。

これを行うには、最初にhashCode()関数をオブジェクトに実装する必要があります。したがって、等しい要素に対して等しいハッシュ値を返します（たとえば、インスタンスプロパティのハッシュコードをXORするなど）。次に、セットのハッシュテーブルを使用して要素をグループ化することができます。

同じ要素が同じハッシュを生成するので、それらは同じ同値クラスに挿入されます。

さて、あなたは私もハッシュメカニズムを実装することをお勧めしますhashMap.values();

Answer 2

を使用して（セットなど）は、すべての等価クラスのコレクションを取得することができます。

FluentIterable.from(collection) 
    .index(new Function<T, K>() { 
     K apply(T input) { 
      //transform T to K hash 
     } 
    })//that would return ImmutableListMultimap<K, T> 
    .asMap()//that would return Map<K, Collection<T>> 
    .values();//Collection<Collection<T>> 

Answer 3

私は何も、このための標準APIでありませんかなり確信して：あなたは、グアバFluentIterableと似た何かを行うことができます。 TroveのTCustomHashSetのようなサードパーティのコレクションクラスをお試しください。 （this related threadのコメントによれば、グアバグループは（今のところ）類似のクラスを拒否していることに興味があります。

代わりに、独自のソリューションをロールバックすることです。あなたがあまりにも多くのアイテムを持っていない場合は、ブルートフォースアプローチを提案します：アイテムリストのリストを保持し、新しいアイテムごとにリストのリストを調べ、それが最初の要素と等しいかどうかを確認します。リスト。そうであれば、一致するリストに新しい項目を追加し、そうでない場合は、その項目を唯一のメンバーとして持つリストのリストに新しいリストを追加します。計算の複雑さはそれほど良くありません。なぜなら、アイテムの数が少ないか、実行時間のパフォーマンスがまったく問題にならない場合にのみこれをお勧めします。

第2の方法は、カスタム等価機能を実装するようにアイテムクラスを変更することです。しかし、ハッシュベースのコレクションクラスでそれを使用するには、hashcode()もオーバーライドする必要があります。ハッシュベースのコレクションを使用していない場合は、ブルートフォースアプローチを使用することもできます。アイテムクラスを変更したくない（またはできない）場合（たとえば、平等テスト）、私は等価（とハッシュコード）戦略を使用するパラメータ化することができますラッパークラスを作成することをお勧めします。 （これは、アイテムクラスの変更とTroveクラスの使用の中間の一種です。）

Answer 4

ここでは、簡単な例の文字列のグループ化について説明します。グループ化するオブジェクトが複雑な場合は、identity()以外の別の機能を指定する必要があります。

public class StreamGroupingBy 
{ 

    public static void main(String[] args) 
    { 
     List<String> items = Arrays.asList( 
       "a", "b", "c", "d", 
       "a", "b", "c", 
       "a", "b", 
       "a", "x"); 

     Map<String,List<String>> result = items.stream().collect(
       Collectors.groupingBy(Function.identity())); 
     System.out.println(result); 
    } 
} 

出力：

{a=[a, a, a, a], b=[b, b, b], c=[c, c], d=[d], x=[x]} 

Answer 5

あなたのシナリオはgroupingByコレクターのために良いユースケースのように聞こえます。通常、等価関数を提供する代わりに、修飾子を抽出する関数を指定します。要素はリスト内のこれらの修飾子にマップされます。場合

すなわち

Map<Qualifier, List<T>> map = list.stream() 
    .collect(Collectors.groupingBy(T::getQualifier)); 

Collection<List<T>> result = map.values(); 

Tのアイデンティティは、あなたが引数としてFunction.identity()使用することができ、あなたの修飾子です。

これは、修飾子がTの1つ以上のフィールドである場合に問題になります。タプル型を使用して、Tの代替IDを作成することもできますが、フィールドの数ごとに別々のタプルクラスが必要になるため、これまでのところしかありません。

---

あなたがgroupingByあなたを使用したい場合は、本当にTための温帯別のIDを作成する必要があるので、あなたはTのequalsとhashCode方法を変更する必要はありません。

適切なIDを作成するには、equalsとhashCodeを実装する必要があります（または、パフォーマンスが低下するハッシュコードの場合は常に0を返します）。そこ私の知っている、このためのAPIクラスは、ありませんが、私は単純な実装作られています

interface AlternateIdentity<T> {  
    public static <T> Function<T, AlternateIdentity<T>> mapper(
      BiPredicate<? super T, Object> equality, ToIntFunction<? super T> hasher) { 
     return t -> new AlternateIdentity<T>() { 
      @Override 
      public boolean equals(Object other) { 
       return equality.test(t, other); 
      } 

      @Override 
      public int hashCode() { 
       return hasher.applyAsInt(t); 
      } 
     }; 
    } 
} 

あなたのような使用できます。

Collection<List<T>> result 
    = list.stream() 
     .collect(Collectors.groupingBy(
      AlternateIdentity.mapper(eqF, hashF) 
     )) 
     .values(); 

eqFは、あなたの関数をある

、そしてhashFがあるがeqFと同じフィールドをハッシュするハッシュコード関数。また0をhashFに返すこともできますが、適切な実装をすると処理が速くなります）