令人困惑的循环问题(python)

Question

这类似于python中的合并排序中的问题 我正在重述,因为我不认为我在那里很好地解释了这个问题.

基本上我有一系列约1000个文件都包含域名.总共数据> 1gig所以我试图避免将所有数据加载到ram中.每个单独的文件都使用.sort(get_tld)进行排序,它根据TLD对数据进行排序(不是根据其域名排序.将所有.com排在一起,.orgs排在一起等)

典型的文件可能看起来像

something.ca
somethingelse.ca
somethingnew.com
another.net
whatever.org
etc.org

但是显然更长.

我现在想要将所有文件合并为一个,保持排序,以便最终一个大文件仍然可以将所有.com放在一起,.orgs在一起等等.

我基本上想做的是

open all the files
loop:
    read 1 line from each open file
    put them all in a list and sort with .sort(get_tld)
    write each item from the list to a new file

我遇到的问题是我无法弄清楚如何循环使用open()不能使用的文件,因为我没有1个文件打开循环,我有很多.而且它们都是可变长度的,所以我必须确保通过最长的一个.

任何建议都非常感谢.

Answer 1

您是否能够同时保留1000个文件是一个单独的问题,取决于您的操作系统及其配置; 如果没有,你将不得不分两步 - 将N个文件组合并为临时文件,然后将临时文件合并到最终结果文件中(两个步骤应该足够了,因为它们可以合并N个平方文件;只要N至少为32,就可以合并1000个文件).在任何情况下,这都是"将N个输入文件合并到一个输出文件"任务中的一个单独的问题(这只是你是否一次或多次调用该函数的问题).

该函数的一般思想是保留一个优先级队列(模块heapq擅长于;-),其中包含"排序键"的小列表(在您的情况下是当前的TLD),后面是从文件中读取的最后一行,以及最后打开文件准备好读取下一行(以及两者之间的不同之处,以确保正常的词典顺序不会意外地最终尝试比较两个打开的文件,这将失败).我认为一些代码可能是解释一般概念的最佳方式,所以接下来我将编辑这个答案以提供代码(但是我没有时间来测试它,所以把它当作伪代码来传达这个想法;-) .

import heapq

def merge(inputfiles, outputfile, key):
  """inputfiles: list of input, sorted files open for reading.
     outputfile: output file open for writing.
     key: callable supplying the "key" to use for each line.
  """
  # prepare the heap: items are lists with [thekey, k, theline, thefile]
  # where k is an arbitrary int guaranteed to be different for all items,
  # theline is the last line read from thefile and not yet written out,
  # (guaranteed to be a non-empty string), thekey is key(theline), and
  # thefile is the open file
  h = [(k, i.readline(), i) for k, i in enumerate(inputfiles)]
  h = [[key(s), k, s, i] for k, s, i in h if s]
  heapq.heapify(h)

  while h:
    # get and output the lowest available item (==available item w/lowest key)
    item = heapq.heappop(h)
    outputfile.write(item[2])

    # replenish the item with the _next_ line from its file (if any)
    item[2] = item[3].readline()
    if not item[2]: continue  # don't reinsert finished files

    # compute the key, and re-insert the item appropriately
    item[0] = key(item[2])
    heapq.heappush(h, item)

当然,在您的情况下,作为key函数,您需要一个提取顶级域的函数给定一个域名的行(带有尾随换行符) - 在上一个问题中,您已经指向urlparse模块作为首选为此目的进行字符串操作.如果你坚持字符串操作,

def tld(domain):
  return domain.rsplit('.', 1)[-1].strip()

或者这些方面的东西可能是这种约束下的合理方法.

如果您使用Python 2.6或更高版本,heapq.merge是显而易见的替代方案,但在这种情况下,您需要自己准备迭代器(包括确保"打开文件对象"永远不会被意外地比较...)与类似"装饰/不装饰"的方法,我在上面的更可移植的代码中使用.