0

假设我有一个 xml 文档，我可以在其中找到指向相同类型的其他文档的链接，这些文档也可以具有指向另一个文档的链接。在起点，我有要阅读和分析的文件列表。我编写了以下算法来阅读和分析这些文档：

    private static List<String> documentNames = new ArrayList<String>();

    main(...) {
       //add names to documentNames arrayList above.
       for(String documentName : documentNames) {
           readDocument(documentName);
        }
    }

函数 readDocument 如下所示：

       private static CopyOnWriteArrayList<String> visitURL(String documentName) {
       CopyOnWriteArrayList<String> visitedDocs = new CopyOnWriteArrayList<String>(); //visited Ref urls
         if (!visitedDocs .contains(documentName)) {
            analyseAndWriteOnDisk(documentName)    //it saves analised document on disk
            CopyOnWriteArrayList<String> tmp = visitURL(documentName);
            visitedDocs.addAll(tmp);
         } else {
            System.out.println(documentName " - I have seen it !");
         }
         return visitedDocs;
       }

它可以工作，但是在执行程序后，我可以找到重复的文件（具有相同内容的文件）。我不应该拥有它们 - 我通过函数 visitURL 中的 if 条件来阻止它。我的问题是：什么在这里不起作用？我想用数组visitedDocs 操作有问题。如何使用已访问的文件进行每个递归调用实际版本的数组？

尽我所能，我有一个递归函数，它在一些集合 X 上运行：

   recursion(CollectionType X) {
      someoperations(X)
      recursion(X)
   }

并且X必须始终是实际的。

4

2 回答 2

0

您不应该为此使用递归算法。使用包含所有要分析的文档的队列和包含已分析的所有文档的集合更容易。只要队列不为空，您就可以从中提取一个文档，对其进行分析，然后将提取的链接添加到队列中（如果它们尚未访问）。

private Collection<String> visit(Collection<String> intialDocs) {
    Queue<String> documents = new LinkedBlockingQueue(initialDocs);
    Set<String> visited = new HashSet<>();
    while (!documents.isEmpty()) {
        String doc = documents.poll();
        visited.add(doc);

        Collection<String> links = analyzeDocument(doc);
        for(String link : links) {
            if (!visited.contains(link) documents.add(link);
        }
    }
    return visited;
}

private Collection<String> analyzeDocument(String document) {
    // TODO: analyze document and return a list of all links in that document
}

用法：

Set<String> allVisitedDocuments = visit(documentNames);

这种迭代方法相对于递归解决方案的优势：

  • 更容易看到它是如何工作的。
  • 更容易争论它将终止。
  • 更容易调试。
  • 如果需要，它可以很容易地并行化。
  • 只需更改用于对文档进行排队的集合类型，就可以很容易地影响文档处理的顺序。（现在它执行广度优先搜索，如果您使用类似 LIFO 的方法Stack，您将获得深度优先，并且某些优先级队列可能让您根据文档类型左右做出决定）。
  • 如果您有很长的一系列链接文档，递归可能会变得非常深，并且可能会发生堆栈溢出。

注意：如果您不使用多个线程，则不应使用它，因为它会在每次写入访问CopyOnWriteArrayList时对其内部内容进行完整复制！

于 2014-08-13T17:40:20.677 回答
0

每次调用 时visitURL，您都在创建 的新实例visitedDocs。因此，每次调用开始时它都是空的，最后只包含tmp.

根据JavaDocs，您需要像这样调用新的：

CopyOnWriteArrayList<String> visitedDocs = new CopyOnWriteArrayList<String>(documentNames) //here you need to add the parameter of the ArrayList you want to copy, otherwise you're instantiating a blank ArrayList.

然后，您需要将documentNamesequal 设置为返回的visitedDocs.

于 2014-08-13T15:23:22.383 回答