我正在研究一个问题,我必须找出一个数字是否在一定范围内。然而,问题很复杂,因为我处理的文件有数十万行。
下面我试着用尽可能简单的语言来解释这个问题。
以下是对输入文件的简要说明:
文件Ranges.txt有一些最小值和最大值以制表符分隔的范围。
10 20
30 40
60 70
这可以有大约10000000个这样的行,其范围为。
注意:范围永远不会重叠。
文件Numbers.txt有一个数字列表和与每个数字相关联的一些值。
12 0.34
22 0.14
34 0.79
37 0.87
等等。同样,有成千上万这样的行,其中包含数字及其相关值。
我想做的是从Numbers.txt中获取每个数字,并检查它是否在ranges.txt中的任何范围内。
对于所有这些在一个范围内的数字,我必须得到它们相关值的平均值(即每个范围的平均值)。
例如,在上面的Numbers.txt示例中,有两个数字34和37在Ranges.txt的30-40范围内,因此对于Ranges 30-40,我必须计算34和37的相关值的平均值。(即0.79和0.87的平均值),即0.82
我的最终输出文件应该是Ranges.txt,但是所有数值的平均值都在每个范围内。类似于:
输出.txt
10 20 <mean>
30 40 0.82
60 70 <mean>
等等。
如果您对如何用Python高效地编写这篇文章有任何帮助和想法,我们将不胜感激。
最佳答案
显然,您需要对Ranges.txt中的每一行运行Numbers.txt中的每一行。
您可以遍历Numbers.txt,对于每一行,遍历Ranges.txt。但这需要花费很长时间,读取整个Ranges.txt文件数百万次。
你可以把这两个文件都读入内存,但这会占用大量的存储空间,这意味着在读完这两个文件并对其进行预处理之前,你将无法进行任何处理。
因此,您要做的是将Ranges.txt读入内存一次,并将其存储为一个int对列表,而不是惰性地读取Numbers.txt,遍历每个数字的列表。
这种事经常发生。一般来说,您希望使较大的集合进入外部循环,并使其尽可能懒,而较小的集合进入内部循环,并进行预处理以使其尽可能快。但是如果更大的集合可以更有效地预处理(并且您有足够的内存来存储它!),倒过来。
说到预处理,您可以做得比仅仅读入一个int对列表要好得多。如果您对Ranges.txt进行了排序,您可以找到最接近的范围,而不必进行等分,然后只需检查(18个步骤),而不是彻底检查每个范围(100000个步骤)。
这对于stdlib来说有点麻烦,因为使用bisect
时一个错误就很容易搞定,但是有很多ActiveState方法可以让它变得更容易(包括一个linked from the official docs),更不用说像blist
或bintrees
这样的第三方模块可以在一个简单的OO界面中为您提供排序的集合。
所以,像这样的伪代码:
with open('ranges.txt') as f:
ranges = sorted([map(int, line.split()) for line in f])
range_values = {}
with open('numbers.txt') as f:
rows = (map(int, line.split()) for line in f)
for number, value in rows:
use the sorted ranges to find the appropriate range (if any)
range_values.setdefault(range, []).append(value)
with open('output.txt') as f:
for r, values in range_values.items():
mean = sum(values) / len(values)
f.write('{} {} {}\n'.format(r[0], r[1], mean))
顺便说一句,如果解析结果比在每一行上调用
split
更复杂,我建议使用csv
模块……但看起来这不会是个问题。如果不能将Ranges.txt放入内存,但可以将Numbers.txt放入内存,该怎么办?好吧,您可以对其进行排序,然后遍历Ranges.txt,在排序后的数字中找到所有匹配项,并写出该范围的结果。
这有点复杂,因为你必须将左、右二等分,并在两者之间迭代。但这是唯一一个更难的方法。(在这里,第三方课程将提供更多帮助。例如,有一个
bintrees.FastRBTree
作为您的排序集合,它只是sorted_number_tree[low:high]
)如果范围可以重叠,你需要更聪明一点,你必须找到最接近的范围而不超过开始,最接近的范围而不超过结束,并检查两者之间的一切。但是主要的技巧和上一个版本完全一样。唯一的另一个技巧是保留两个范围副本,一个按开始值排序,一个按结束值排序,您需要将其中一个副本映射到另一个范围中的索引,而不仅仅是一个简单的列表。
关于python - 处理两个巨大文件的有效Python方法?,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/18993956/