Изменение набора во время итерации java

Question

Я хочу сделать рекурсивный метод итеративным.

У меня есть список объектов, которые я хочу перебрать, а затем проверить их подобъекты.

Рекурсивный:

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 (каждый подобъект), прежде чем добавлять его.

Но я бы с удовольствием использовал Набор для создания такого очистителя.

Итак, в принципе, есть ли способ добавлять к набору во время итерации по нему, или есть более простой способ заставить список действовать как set, а не проверять вручную .contains()?

Любые комментарии приветствуются.

Спасибо

Answer 1

Я бы использовал две структуры данных --- a очередь (например, 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)".

Answer 2

Я думаю, что ваша проблема по своей сути - это проблема, которая должна быть решена с помощью Списка.Если вы подумаете об этом, ваша Установленная версия решения - это просто преобразование элементов в список, а затем работа с ним.

Конечно, List.contains() - медленная операция по сравнению с Set.contains(), поэтому, возможно, стоит придумать гибрид, если беспокоит скорость:

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

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

Это решение быстрое и к тому же концептуально обоснованное - набор можно рассматривать как список всех просмотренных элементов, в то время как Список представляет собой очередь элементов для работы.Однако это занимает больше памяти, чем использование только Списка.

Answer 3

Если вы не используете список, итератор выдаст исключение, как только вы прочитаете из него после изменения набора.Я бы рекомендовал использовать список и ввести ограничения на вставку, а затем использовать ListIterator, поскольку это позволит вам изменять список во время итерации по нему.

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

Я думаю, что что-то вроде этого будет делать то, что я хочу, меня не беспокоит, что первый набор содержит дубликаты, только то, что подобъекты могут указывать на одни и те же объекты.

Answer 5

Используйте более одного подхода и делайте это "раундами".:

/* 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

Почему бы не создать дополнительный набор, содержащий весь набор объектов?Вы можете использовать это для поиска.