Javaの反復中にセットを変更する

StackOverflow https://stackoverflow.com/questions/497025

  •  20-08-2019
  •  | 
  •  

質問

再帰的メソッドを反復的にしようとしています。

反復処理して、そのサブオブジェクトを確認したいオブジェクトのリストがあります。

再帰的:

doFunction(Object)
while(iterator.hasNext())
{
   //doStuff
   doFunction(Object.subObjects);
}

こんな感じに変更したいです

doFunction(Object)
iIterator = hashSet.iterator();
while(Iterator.hasNext()
{
   //doStuff
   hashSet.addAll(Object.subObjects);
}

貧弱な疑似コードで申し訳ありませんが、基本的には、チェックする新しいオブジェクトをリストの最後に追加しながら、サブオブジェクトを反復処理したいと考えています。

リストを使用してこれを行うことができ、次のようなことを行うことができます

while(list.size() > 0)
{
   //doStuff
   list.addAll(Object.subObjects);
}

ただし、重複したサブオブジェクトを追加したくないのです。もちろん、追加する前に list.contains( each subObject) かどうかを確認することもできます。

しかし、私は Set を使用してそのクリーンな機能を実現したいと考えています。

それで、基本的に、反復中にセットに追加する方法はありますか、または手動で.contains()をチェックするのではなく、リストをセットのように動作させる簡単な方法はありますか?

コメントは大歓迎です。

ありがとう

役に立ちましたか？

解決

私は 2 つのデータ構造を使用します --- 列 （例えば。 ArrayDeque) サブオブジェクトが参照されるオブジェクトを格納するためのもの。 セット （例えば。 HashSet) 訪問したすべてのオブジェクトを重複せずに保存します。

Set visited = new HashSet();   // all visited objects
Queue next = new ArrayDeque(); // objects whose subobjects are to be visited

// NOTE: At all times, the objects in "next" are contained in "visited"

// add the first object
visited.add(obj);

Object nextObject = obj;

while (nextObject != null)
{
    // do stuff to nextObject

    for (Object o : nextObject.subobjects)
    {
        boolean fresh = visited.add(o);

        if (fresh)
        {
            next.add(o);
        }
    }

    nextObject = next.poll(); // removes the next object to visit, null if empty
}

// Now, "visited" contains all the visited objects

ノート：

  • ArrayDeque スペース効率の高いキューです。循環配列として実装されているため、使用するスペースが List 要素を追加すると成長し続けます。
  • "boolean fresh = visited.add(o)「組み合わせる」boolean fresh = !visited.contains(o)" そして "if (fresh) visited.add(o)".

他のヒント

私はあなたの問題は本質的にリストを経由して解決すべき問題だと思います。あなたはそれについて考える場合は、ソリューションのあなたのセットのバージョンは、ちょうどその上で動作リストにアイテムを変換されます。

もちろん、List.containsは（））（Set.containsと比較して遅い動作であるので、速度が懸念される場合にはハイブリッドを考え出す価値があります：

while(list.size() > 0)
{
   //doStuff

   for each subObject
   {
      if (!set.contains(subObject))
      {
         list.add(subObject);
         set.add(subObject)
      }
   }
}

このソリューションは、高速でも概念的に健全である - リスト上で動作する項目のキューであるのに対し、セット、見たすべての項目のリストと考えることができます。これは、しかし、単独のリストを使用してより多くのメモリを取るん。

あなたがリストを使用しない場合は、

、反復子はできるだけ早くあなたがセットを変更した後、そこから読むと例外がスローされます。私はリストを使用して、挿入制限を強制する、それを反復しながら、それはあなたがリストを変更することができますよう反復子を使用することをお勧めします。

    HashSet nextObjects = new HashSet();
    HashSet currentObjects = new HashSet(firstObject.subObjects);

    while(currentObjects.size() > 0)
    {
        Iterator iter = currentObjects.iterator();
        while(iter.hasNext())
        {
            //doStuff
            nextObjects.add(subobjects);
        }
        currentObjects = nextObjects;
        nextObjects = new HashSet();
    }

私は、第1のセットはサブオブジェクトが同じオブジェクトを指すことだけで、重複が含まれていることを心配していないよ、このようなものは私がやりたいだろうと思います。

複数のセットを使用し、「ラウンド」でそれを行う：

/* very pseudo-code */
doFunction(Object o) {
    Set processed = new HashSet();
    Set toProcess = new HashSet();
    Set processNext = new HashSet();

    toProcess.add(o);

    while (toProcess.size() > 0) {
        for(it = toProcess.iterator(); it.hasNext();) {
            Object o = it.next();
            doStuff(o);
            processNext.addAll(o.subObjects);
        }
        processed.addAll(toProcess);
        toProcess = processNext;
        toProcess.removeAll(processed);
        processNext = new HashSet();
    }
}

なぜオブジェクトのセット全体が含まれている追加のセットを作成していませんか？あなたは、ルックアップのためにそれを使用することができます。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top