需要更有效的循环嵌套解决方案

Question

我正在比较两个文件。我将列出两个文件内容：

 File 1                           File 2

"d.complex.1"                     "d.complex.1"

  1                                 4
  5                                 5
  48                                47
  65                                21

d.complex.10                    d.complex.10

  46                                5
  21                                46
 109                               121
 192                               192

每个文件中总共有2000个d.complex。我试图比较这两个文件，但问题是在d.complex下面列出的值。第一个文件中的1必须与第二个文件中的所有2000个d.complex条目进行检查，如果条目不匹配，它们将被打印出来。例如，在上述文件中，在file1d.complex.1中，数字48在file2d.complex.1中不存在，所以这个数字必须存储在一个列表中（以后打印出来）。同样的d.complex.1必须与file2的d.complex.10进行比较，因为1、48和65不存在，所以必须将它们附加到一个列表中。在

我选择的方法是使用集合，然后进行交集。我写的代码是：

^{pr2}$

上面的代码给出了如下输出（只是一个示例）：

1
48
65
d.complex.1.dssp
d.complex.1.dssp

46
21

109 d、 复杂1.dssp d、 复杂1.dssp d、 复杂10.dssp

虽然上面的答案是正确的，但是我想要一个更有效的方法来做这件事，有人能帮我吗？此外，还打印了两个d.complex.1.dssp，而不是一个也不好的。在

我想要的是：

d.complex.1
d.complex.1 (name from file2)
   1
   48
   65

d.complex.1
d.complex.10 (name from file2)
   1
   48
   65

我对python太陌生了，所以我上面的概念可能有缺陷。我也从来没有使用过集：（。有人能帮我一下吗？在

Answer 1

指针：

• 使用列表理解或生成器表达式来简化数据处理。更具可读性
• 只生成一次集合。在
• 使用函数不要重复你自己，尤其是做同一个任务两次。在

我对你的输入数据做了一些假设，你可能想试试这样的方法。在

def parsefile(filename):
  ret = {}
  cur = None
  for line in ( x.strip() for x in open(filename,'r')):
    if line.startswith('d.complex'):
      cur = set()
      ret[line] = cur
    if not cur or not line.isdigit():
      continue
    cur.add(int(line))
  return ret

def compareStructures(first,second):
  # Iterate through key,value pairs in first
  for firstcmplx, firstmembers in first.iteritems():
    # Iterate through key,value pairs in second
    for secondcmplx, secondmembers in second.iteritems():
      notinsecond = firstmembers- secondmembers
      if notinsecond:
        # There are items in first that aren't in second
        print firstcmplx
        print secondcmplx
        print "\n".join([ str(x) for x in notinsecond])

first = parsefile("myFirstFile.txt")
second = parsefile("mySecondFile.txt")

compareStructures(first,second)

已编辑修复。。显示了我有多依赖于运行代码来测试它：）谢谢Alex

Answer 2

@MattH已经有了一个很好的答案，它集中在Python问题的细节上，虽然它可以在几个细节上得到改进，但是这些改进只会使效率提高一些百分点，值得一提，但效果并不理想。在

提高效率的唯一希望（相对于“kai-zen”的渐进式改进），是对算法进行彻底的改变，这取决于你没有透露的数据的特征，以及关于你的精确要求的一些细节。在

关键的部分是：大致上，文件中会出现多少个数字，以及每个“d.complex.N”节有多少个数字？你已经告诉过我们每个文件大约有2000节（这当然也很关键），印象是，在每个文件中，它们将通过连续递增n1、2、3等来排序（是这样吗？）。在

您的算法构建了两个maps-stanza->；numbers（不是效率最高的，但这正是@MattH的答案着重于增强的内容），因此不可避免地需要N squared节到节的检查，因为N是2000，它需要400万个这样的检查。在

考虑构建反向的映射，节如果数字的范围和一节中的数字的典型大小都受到合理的限制，那么这些将更加紧凑。例如，如果数字在1到200之间，并且每节大约有4个数字，这意味着一个数字通常在(2000 * 4) / 200->；40节中，因此这样的映射将有200个条目，每个条目大约40个小节。它只需要200平方（40000）的检查，而不是400万，以获得每个数字的联合信息（然后，根据输出格式的确切需要，格式化这些信息可能需要非常大的努力，如果你绝对需要作为最终结果的400万“节对”部分，那么当然没有办法避免400万“输出操作，这将不可避免地非常昂贵）。在

但所有这些都取决于那些你没有告诉我们的平均节数，文件中的数字范围，以及你必须绝对遵守输出格式的限制的细节（如果这些数字是合理的，输出格式约束将成为big-O性能的关键约束，您可以从任何程序中获得。在

记住，引用Fred Brooks：

Show me your flowcharts and conceal your tables, and I shall continue to be mystified. Show me your tables, and I won’t usually need your flowcharts; they’ll be obvious.

布鲁克斯在60年代写作（尽管他的散文集《神秘的人月》后来在70年代出版），“流程图”（我们称之为代码或算法）和“表”（我们称之为数据或数据结构）的奇特用法，但总体概念仍然是完全有效的：在各种侧重于数据处理的程序中（如您的程序），数据的组织和性质，可能比代码的组织更重要，尤其是因为它约束了后者；-）。在