Ändern einer Reihe während der Iteration java

Question

Ich suche eine rekursive Methode iterativ zu machen.

Ich habe eine Liste von Objekten I iterieren möchten, und dann deren Subobjekte überprüfen.

Rekursiv:

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

Ich mag es so etwas ändern

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

Sorry für den schlechten Pseudo-Code, aber im Grunde will ich über Subobjekte wiederholen, während neue Objekte in das Ende der Liste angehängt zu überprüfen.

ich tun könnte dies eine Liste verwenden, und tun so etwas wie

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

Aber ich möchte wirklich nicht zu doppelten Subobjekte hinzufügen. Natürlich konnte ich nur, ob list.contains überprüfen (jedes Subobjekt), bevor ich es hinzugefügt.

Aber ich würde gerne ein Set verwenden, die Reiniger zu erreichen.

So ist Grundsätzlich gibt trotzdem einen Satz, während Iterieren über sie anhängen, oder gibt es einen einfacheren Weg, um eine Liste handeln wie ein Set zu machen, anstatt manuell überprüft .contains ()?

Jede Kommentare sind willkommen.

Danke

Answer 1

Ich würde zwei Datenstrukturen verwenden --- a Warteschlange (zB ArrayDeque ) für Objekte, deren Subobjekte Speicherung besucht werden, und ein gesetzt (zB HashSet ) für alle besuchten Objekte ohne Duplizierung zu speichern.

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

NOTES:

• ArrayDeque ist ein platzspar Warteschlange. Es wird als ein zyklisches Array implementiert, das bedeutet, dass Sie weniger Platz als ein traditionellen List , die weiter wachsen, wenn Sie Elemente hinzufügen.
• "boolean fresh = visited.add(o)" verbindet "boolean fresh = !visited.contains(o)" und "if (fresh) visited.add(o)".

Answer 2

Ich denke, Ihr Problem ist von Natur aus ein Problem, das über eine Liste gelöst werden muss. Wenn man darüber nachdenkt, ist Ihre Set-Version der Lösung nur die Elemente in eine Liste konvertiert dann auf dem Betrieb.

Natürlich List.contains () ist ein langsamer Vorgang im Vergleich zu Set.contains (), so kann es sich lohnen, mit einem Hybrid kommen, wenn die Geschwindigkeit ist ein Anliegen:

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

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

Diese Lösung ist schnell und konzeptionell solide auch - das Set als Liste aller Elemente gedacht zu sehen ist, während die Liste eine Warteschlange von Elementen ist zu arbeiten. Es dauert bis mehr Speicher als eine Liste allein verwenden, though.

Answer 3

Wenn Sie nicht über eine Liste verwenden, wird der Iterator eine Ausnahme auslösen, sobald Sie von ihm lesen, nachdem die Menge ändern. Ich würde empfehlen, eine Liste und Durchsetzung der Einführungslimiten, dann ListIterator Verwendung als das Ihnen erlaubt, um die Liste zu ändern, während über sie iterieren.

Answer 4

    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();
    }

Ich denke, so etwas wie dies tun, was ich will, ich bin nicht besorgt darüber, dass der erste Satz Duplikate enthält, nur dass die Teilobjekte auf die gleichen Objekte verweisen können.

Answer 5

Verwenden Sie mehr als einen Satz und tut es in „Runden“:

/* 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();
    }
}

Answer 6

Warum einen zusätzlichen Satz nicht schaffen, die die gesamte Menge von Objekten enthält? Sie können, dass für Lookups verwenden.