0

HashSetから重複を削除するために使用しようとしましたArrayList<StringBuilder>。

たとえば、ここに がありArrayList、各行はStringBuilderオブジェクトです。

"u12e5 u13a1 u1423"
"u145d"
"u12e5 u13a1 u1423"
"u3ab4 u1489"

私は以下を取得したい:

"u12e5 u13a1 u1423"
"u145d"
"u3ab4 u1489"

私の現在の実装は次のとおりです。

static void removeDuplication(ArrayList<StringBuilder> directCallList) {
    HashSet<StringBuilder> set = new HashSet<StringBuilder>();
    for(int i=0; i<directCallList.size()-1; i++) {
        if(set.contains(directCallList.get(i)) == false)
            set.add(directCallList.get(i));
    }   
    StringBuilder lastString = directCallList.get(directCallList.size()-1);
    directCallList.clear();
    directCallList.addAll(set);
    directCallList.add(lastString);
}

ArrayListしかし、サイズが大きくなるにつれて、パフォーマンスはますます悪化します。この実装に問題はありますか? または、パフォーマンスの点でより良いものはありますか?

4

5 に答える 5

9

StringBuilder は equals() または hashcode() を実装していません。2 つの StringBuilders は、それらがまったく同じオブジェクトである場合にのみ等しいため、それらを HashSet に追加しても、同一の内容を持つ 2 つの異なる StringBuilder オブジェクトが除外されるわけではありません。

StringBuilders を String オブジェクトに変換する必要があります。

また、コンストラクターで「初期容量」を使用して HashSet を初期化する必要があります。これは、多数のオブジェクトを処理する場合の速度に役立ちます。

最後に、オブジェクトを追加する前にハッシュセットで contains() を呼び出す必要はありません。文字列をセットに追加するだけで、セットは重複を拒否します (そして false を返します)。

于 2012-10-15T17:05:15.197 に答える
2

メソッドを分析して、改善できる場所を見つけましょう。

static void removeDuplication(ArrayList<StringBuilder> directCallList) {
    HashSet<StringBuilder> set = new HashSet<StringBuilder>();
    for(int i=0; i<directCallList.size()-1; i++) {
        if(set.contains(directCallList.get(i)) == false)
            set.add(directCallList.get(i));
    }

このforループは、の各要素に対して1回繰り返されますArrayList。これは当面の作業では避けられないようです。ただし、HashSet各項目を1つしか含めることができないため、ifステートメントは冗長です。HashSet.add()まったく同じチェックを再度実行します。

    StringBuilder lastString = directCallList.get(directCallList.size()-1);

lastString私はあなたのリストからを取得してそれを追加する必要性を理解していません。ループが正しく機能する場合は、ループがすでに追加されているはずHashSetです。

    directCallList.clear();

リストの実装によっては、リストO(n)内のすべての要素にアクセスする必要がある場合があるため、これには時間がかかる場合があります。

    directCallList.addAll(set);

繰り返しますが、これにはO(n)時間がかかります。重複がない場合setは、元のアイテムが含まれています。

    directCallList.add(lastString);

この行は論理エラーのようです。にStringすでにあり、に追加されているsetを追加しdirectCallListます。}

したがって、全体として、このアルゴリズムにはO(n)時間がかかりますが、一定の係数があり3ます。この係数を減らすことができれば、パフォーマンスを向上させることができます。ArrayListこれを行う1つの方法は、既存のものをクリアするのではなく、単に新しいものを作成することです。

さらに、正しいコンストラクターを使用して重複なしremoveDuplication()で返す場合、この関数は1行で記述できます。ArrayList

static List<StringBuilder> removeDuplication(List<StringBuilder> inList) {
    return new ArrayList<StringBuilder>(new HashSet<StringBuilder>(inList));
}

もちろん、これはまだ他のStringBuilder人が指摘している問題に対処していません。

于 2012-10-15T17:09:00.140 に答える
1

他にもいくつかの選択肢がありましたが、私のソリューションは短く、シンプルで、要点がはっきりしているのが気に入っています。メソッドを変更して、パラメーターを操作するのではなく、新しいを返すようにしましたList。a を使用しSet<String>て、それぞれのコンテンツStringBuilderが既に含まれているかどうかを確認し、一意Stringの を返しました。また、インデックスによるアクセスの代わりに for each ループを使用しました。

static List<StringBuilder> removeDuplication(List<StringBuilder> directCallList) {
    HashSet<String> set = new HashSet<String>();
    List<StringBuilder> returnList = new ArrayList<StringBuilder>();
    for(StringBuilder builder : directCallList) {
        if(set.add(builder.toString())
            returnList.add(builder);
    }   
    return returnList;
}
于 2012-10-15T17:20:41.453 に答える
0

説明したように、StringBuildersはオーバーライドせず、オーバーライドObject#equalsしませんComparable。

StringBuildersを使用して文字列を連結するのが最善の方法ですが、連結が完了したら、StringBuildersの代わりに基になる文字列（ ）をリストに格納することをお勧めします。stringBuilder.toString()

重複を削除すると、1行になります。

Set<String> set = new HashSet<String>(list);

または、重複があることを知る必要がない場合は、文字列をセットに直接保存することをお勧めします。

于 2012-10-15T17:10:43.510 に答える
0

サムが述べているように、StringBuiderオーバーライドしないhashCodeためequals、Set適切に機能しません。

答えは、toString を 1 回だけ実行するオブジェクトで Builder をラップすることだと思います。

class Wrapper{
   final String string;
   final StringBuilder builder;

   Wrapper(StringBuilder builder){
      this.builder = builder;
      this.string = builder.toString();
   }

   public int hashCode(){return string.hashCode();}

   public boolean equals(Object o){return string.equals(o);}
}     


 public Set removeDups(List<StringBuilder> list){
    Set<Wrapper> set = ...;
    for (StringBuilder builder : list)
       set.add(new Wrapper(builder));

    return set;
 }

メソッドを更新して、removeDupsセットからビルダーを抽出し、List<StringBuilder>

于 2012-10-15T17:05:51.813 に答える