Модификация набора во время итерации Java - PullRequest
Новая
       33

Модификация набора во время итерации Java

2 голосов
/ 30 января 2009

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

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

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

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

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

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

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

Спасибо

Ответы [ 6 ]

5 голосов
/ 31 января 2009

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

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

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

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

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

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

0 голосов
/ 30 января 2009

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

0 голосов
/ 30 января 2009

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

/* 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();
    }
}
0 голосов
/ 30 января 2009 
    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();
    }

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

0 голосов
/ 30 января 2009

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

...