2

私は再帰的な方法を反復的にしようとしています。

繰り返し処理したいオブジェクトのリストがあり、それらのサブオブジェクトをチェックします。

再帰的:

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() をチェックするのではなく、リストをセットのように動作させる簡単な方法はありますか?

コメントをお待ちしております。

ありがとう

4

6 に答える 6

5

サブオブジェクトが訪問されるオブジェクトを格納するためのキュー(例: ) と、訪問されたすべてのオブジェクトを重複なく格納するためのセット(例: ) の2 つのデータ構造を使用します。ArrayDequeHashSet

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)
于 2009-01-31T01:51:14.693 に答える
1

あなたの問題は本質的にリストを介して解決する必要がある問題だと思います。考えてみれば、Set バージョンのソリューションは、アイテムを List に変換してから操作するだけです。

もちろん、List.contains() は Set.contains() に比べて遅い操作なので、速度が問題になる場合はハイブリッドを考える価値があるかもしれません:

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

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

このソリューションは高速であり、概念的にも健全です。セットは表示されるすべてのアイテムのリストと考えることができますが、リストは作業するアイテムのキューです。ただし、リストを単独で使用するよりも多くのメモリを消費します。

于 2009-01-30T20:16:13.217 に答える
0 
    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();
    }

このようなものは私が望むことをすると思います。最初のセットに重複が含まれていることは気にしません。サブオブジェクトが同じオブジェクトを指している可能性があることだけです。

于 2009-01-30T20:35:49.103 に答える
0

複数のセットを使用し、「ラウンド」で実行します。

/* 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();
    }
}
于 2009-01-30T20:36:31.130 に答える
0

オブジェクトのセット全体を含む追加のセットを作成してみませんか? それをルックアップに使用できます。

于 2009-01-30T20:37:37.463 に答える
0

List を使用しない場合、セットを変更した後にリストから読み取るとすぐに、反復子は例外をスローします。List を使用して挿入制限を適用することをお勧めします。次に ListIterator を使用すると、反復処理中にリストを変更できるようになります。

于 2009-01-30T20:17:10.110 に答える