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

我将使用两种数据结构——一个队列（例如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添加元素时不断增长的 a 少。
  • " 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)
      }
   }
}

这个解决方案速度很快，而且在概念上也是合理的——Set 可以被认为是所有可见项目的列表，而 List 是要处理的项目的队列。不过，它确实比单独使用 List 占用更多的内存。

于 2009-01-30T20:16:13.217 回答
0

如果您不使用 List，则在修改集合后，一旦您从中读取，迭代器就会抛出异常。我建议使用 List 并强制执行插入限制，然后使用 ListIterator 因为这将允许您在迭代列表时修改列表。

于 2009-01-30T20:17:10.110 回答
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();
    }

我认为这样的事情会做我想要的，我不担心第一个 Set 包含重复项，只是 subObjects 可能指向相同的对象。

于 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 回答