重构嵌套for循环

我有这种情况，我有两组数据之间的父子关系。我有一个父文档集合和一个子文档集合。要求是父母及其相应的孩子需要出口到一个pdf文档。一个简单的实现上述情况可以像（Java上下的伪代码如下所示）如下：重构嵌套for循环

for(Document parentDocument:Documents){ 
    ExportToPdf(parentDocument); 
    for(Document childDocument:parentDocument.children()){ 
     AppendToParentPdf(childDocument); 
    } 
}

东西如上面可能会解决这个问题，但一下子要求的变化和现在的每一种父母和他们对应的孩子需要在单独的PDF文件，所以上面给出的片段是通过改变AppendToParentPdf()到ExportToPdf()如下修改：

for(Document parentDocument:Documents){ 
    ExportToPdf(parentDocument); 
    for(Document childDocument:parentDocument.children()){ 
     ExportToPdf(childDocument); 
    } 
}

沿着这条道路前进，将需要很长时间这个看似微不足道的段之前会遭受一些严重的代码异味。

我的问题，SO是：

是否存在父子关系的更好的表示，如上述的地方，而不是暴力破解我的方式，通过在O(n^2)时尚的所有文件和他们的孩子，我可以使用不同的数据结构或技术以更优化的方式遍历整个结构。
在上面描述的场景中，业务规则对于导出pdf的方式非常流畅，是否有更智能的方法来编写导出函数的性质？导出格式也是暂时的。 PDF可以让位给* .docs/csvs/xmls等。

这将是很好的一些观点。

感谢

来源

2011-11-29 sc_ray

关于你提到的第一个问题，它并不像你是暴力破解，因为你只检索parentDocument.Children规定每位家长和这包含所有的孩子文件特定父的名单。所以你的时间复杂度不是o（n^2），而是o（n + m），其中n和m分别是父文件和子文件的计数。 – Santhosh

@sc_ray你应该说明'childDocument'是否可以有多个'parentDocument'。 – Alderath

@Santosh - 我不知道这是怎么了O（N + M）的问题，因为循环需要通过每米儿童n次的迭代，给它O（N * M）或O（n的时间复杂度^ 2）。 –

您可以封装你想在一个处理一个文档做什么。这也将允许您定义将来可以传递给现有代码的新处理程序。

interface DocumentHandler { 
    void process(Document d); 
} 

class ExportToPdf implements DocumentHandler { ... } 
class AppendToParentPdf implements DocumentHandler { ... } 

// Now you're just passing the interface whose implementation does something with the document 
void handleDocument(DocumentHandler parentHandler, DocumentHandler childHandler) { 
    for(Document parent : documents) { 
     parentHandler.process(parent); 

     for(Document child : parent.children()) { 
      childHandler.process(child); 
     } 
    } 
} 

DocumentHandler appendToParent = new AppendToParentPdf(); 
DocumentHandler exportToPdf = new ExportToPdf(); 

// pass the child/parent handlers as needed 
handleDocument(exportToPdf, appendToParent); 
handleDocument(exportToPdf, exportToPdf);

至于效率，我会说不要优化，除非遇到性能问题。在任何情况下，问题都不是嵌套循环，而是处理文档的逻辑本身。

来源

2011-11-29 07:26:41 armandino

谢谢。这是一个非常优雅的片段。 –

谢谢！很高兴有帮助:) – armandino

我试图融入评论这一点，但有太多可说的......

我没有看到你在谈论的变化是怎样一个代码味道。如果这个简单功能的需求发生变化，那么它们就会改变。如果你只需要在一个地方做出改变，那听起来你做得很好。如果您的客户需要两种方法（或更多），那么您可能会考虑某种策略模式，因此您不必重写周围的代码即可执行任何功能。

如果你每星期做出几十次这些变化，那么它可能会变得混乱，你可能应该制定一个计划，以更有效地处理一个非常繁忙的变化轴。否则，纪律和重构可以帮助你保持清洁。

至于n2是否是一个问题，这取决于。 n有多大？如果你必须经常这样做（即每小时几十次），并且n在1000以上，那么你可能会遇到问题。否则，只要满足或超出需求并且CPU /磁盘利用率超出危险区域，我就不会冒汗。

来源

2011-11-29 04:40:27 Bill

感谢您的回答。问题是，在任何给定的时间点，300多个用户可能会出口100万以上的文件（父母+孩子），尽管没有人希望任何种类的亚秒级出口商魔法发生，但该系统有可能成为这种预计负载征税。 –

即使有一百万份文档，用户在给定请求中要请求多少个文档？一次将有多少用户在系统中，其中有多少用户同时生成文档？除非你有一些不寻常的要求，否则我会希望这些数字能够合理地解决。尽管如此，如果您担心需要完成大量工作，那么您可能需要考虑工作队列来限制将发生的并发工作量。我不担心，直到一些负载测试证明我需要它们。 – Bill

第二个问题的问题可以通过简单地创建一个inteface Exporter与方法 export(Document doc);，然后对每种不同的格式实现。 class DocExporterImpl implements Exporter。

第一个取决于您的要求，没有任何设计模式可以解决这些问题。无法帮助你。

来源

2011-11-29 04:45:59

为了您的第二个问题，你可以使用provider pattern或它的一个扩展。

提供商模式：这个模式有它的根在战略模式，它可以让你设计出一个抽象的数据和行为，这样就可以随时换出实施

来源

2011-11-29 07:09:25 Santhosh

是否有更好地表达亲子关系，比如上述，而不是勉强以O（n^2）方式通过所有文件和他们的孩子。

这不是O(N^2)。它是O(N)其中N是父文件和子文件的总数。假设没有孩子有多个父母文档，那么你不能显着提高性能。而且，与生成PDF的调用的代价相比，遍历的代价可能微不足道。

，你可能要考虑优化的唯一情况是，如果子文档可以是多个父母的子女。在这种情况下，您可能需要跟踪已生成PDF的文档，并在遍历中重新访问时跳过它们。可以使用HashSet执行“我之前看过这个文档”的测试。

来源

2011-11-29 07:18:47

感谢您的回答。我不明白两个嵌套for循环如何使时间复杂度O（n + m）或O（n）代替n^2。外循环的执行将暂停，直到内循环完成执行，除非java执行了一些非常激进的循环展开，将n^2变成n。 –

使用了一套跟踪哪些元素已出口可能不是最漂亮的解决方案，但它会阻止出口的两倍的文件。

Set<Document> alreadyExported = new HashSet<Document>(); 

for(Document parentDocument:Documents){ 
    ExportToPdf(parentDocument); 
    for(Document childDocument:parentDocument.children()){ 
     if(!aldreadyExported.contains(childDocument)){ 
     ExportToPdf(childDocument); 
     alreadyExported.add(childDocument); 
     } 
    } 
}

来源

2011-11-29 14:09:53 Alderath

重构嵌套for循环

回答

相关问题