2

我正在解决一个问题，我必须找出一个数字是否在某个范围内。但是，由于我正在处理的文件有数十万行，所以问题很复杂。

下面我尝试用尽可能简单的语言来解释这个问题。

这是我的输入文件的简要说明：

文件Ranges.txt有一些范围，其最小值和最大值是制表符分隔的。

10 20
30 40
60 70

这可以有大约 10,000,000 条带范围的此类行。

注意：范围从不重叠。

文件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 范围内，因此对于 30-40 范围，我必须计算 34 和 37 的关联值的平均值. （即 0.79 和 0.87 的平均值），即 0.82

我的最终输出文件应该是Ranges.txt，但所有数字的相关值的平均值都落在每个范围内。就像是 ：

输出.txt

10 20 <mean>
30 40 0.82
60 70 <mean>

等等。

对于如何在 Python 中有效编写它的任何帮助和想法，将不胜感激。

4

3 回答 3

4

显然，您需要针对 Ranges.txt 中的每一行运行 Numbers.txt 中的每一行。

您可以只遍历 Numbers.txt，并且对于每一行，遍历 Ranges.txt。但这将永远花费数百万次读取整个 Ranges.txt 文件。

您可以将它们都读入内存，但这会占用大量存储空间，这意味着在您完成读取和预处理这两个文件之前，您将无法进行任何处理。

因此，您要做的是将 Ranges.txt 读入内存一次，然后将其存储为例如整数对的列表，但懒惰地读取 Numbers.txt，遍历每个数字的列表。

这种事情时时出现。通常，您希望将较大的集合放入外部循环，并使其尽可能惰性，而较小的集合进入内部循环，并对其进行预处理以使其尽可能快。但是，如果可以更有效地预处理更大的集合（并且您有足够的内存来存储它！），请反过来。

说到预处理，你可以做的比仅仅读入一个整数对列表要好得多。如果您对 Ranges.txt 进行排序，您可以通过二等分找到最接近的范围，然后只需检查（18 步），而不是详尽地检查每个范围（100000 步）。

这对 stdlib 来说有点麻烦，因为在使用 时很容易出错bisect，但是有很多 ActiveState 配方可以使它更容易（包括从官方文档链接的一个），更不用说第三个了-party 模块之类的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，找到排序后的数字中的所有匹配项，然后写出该范围的结果。

这有点复杂，因为您必须 bisect_left 和 bisect_right 并迭代其间的所有内容。但这是唯一更难的方法。（在这里，第三方类将提供更多帮助。例如，使用 abintrees.FastRBTree作为您的排序集合，它只是sorted_number_tree[low:high].）

如果范围可以重叠，你需要更聪明一点——你必须找到最接近的范围而不超过起点，以及最接近的范围而不超过终点，并检查两者之间的所有内容。但其中的主要技巧与上一版本使用的技巧完全相同。唯一的另一个技巧是保留两个范围的副本，一个按起始值排序，一个按结束排序，您需要将其中一个映射到另一个索引，而不仅仅是一个普通列表。

于 2013-09-25T00:05:11.843 回答
1

看起来您在两个文件中的数据已经排序。如果没有，首先通过外部工具或使用 Python 对它们进行排序。

然后，您可以并行浏览这两个文件。您从文件中读取一个数字Numbers.txt，并查看它是否在文件的范围内，Ranges.txt并根据需要从该文件中读取尽可能多的行来回答该问题。然后从 中读取下一个数字Numbers.txt，然后重复。这个想法类似于合并两个排序的数组，并且应该及时运行O(n+m)，n并且m是文件的大小。如果您需要对文件进行排序，则运行时间为O(n lg(n) + m lg(m)). 这是我编写的一个快速程序来实现这一点：

import sys
from collections import Counter

class Gen(object):
    __slots__ = ('rfp', 'nfp', 'mn', 'mx', 'num', 'd', 'n')
    def __init__(self, ranges_filename, numbers_filename):
        self.d = Counter() # sum of elements keyed by range
        self.n = Counter() # number of elements keyed by range 

        self.rfp = open(ranges_filename)
        self.nfp = open(numbers_filename)
        # Read the first number and the first range values
        self.num = float(self.nfp.next()) # Current number
        self.mn, self.mx = [int(x) for x in self.rfp.next().split()] # Current range

    def go(self):
        while True:
            if self.mx < self.num:
                try:
                    self.mn, self.mx = [int(x) for x in self.rfp.next().split()]
                except StopIteration:
                    break
            else:   
                if self.mn <= self.num <= self.mx:
                    self.d[(self.mn, self.mx)] += self.num
                    self.n[(self.mn, self.mx)] += 1
                try:
                    self.num = float(self.nfp.next())
                except StopIteration:
                    break
        self.nfp.close()
        self.rfp.close()
        return self.d, self.n

def run(ranges_filename, numbers_filename):
    r = Gen(ranges_filename, numbers_filename)
    d, n = r.go()
    for mn, mx in sorted(d):
        s, N = d[(mn, mx)], n[(mn, mx)]
        if s:
            av = s/N
        else:
            av = 0
        sys.stdout.write('%d %d %.3f\n' % (mn, mx, av))

对于每个文件中包含 10,000,000 个数字的文件，以上在我的计算机上运行大约 1.5 分钟，没有输出部分。

于 2013-09-25T17:30:16.083 回答
1

天真的方法是按数字顺序将 Numbers.txt 读入某个结构，然后读取 Ranges 的每一行，我们进行二分查找以找到该范围内的最小数字，然后读取高于该数字的数字以找到所有这些范围内，这样就可以产生对应的输出行。

我认为问题是你不能在内存中拥有所有的数字。

因此，您可以分阶段解决问题，其中每个阶段读取数字的一部分，然后执行上述过程，但使用带注释的 Ranges 版本，其中每一行包含迄今为止产生的值的 COUNT意思是，并将编写一个类似注释的版本。

显然，最初的 pass 不会有 Ranges 的注释版本，最终的 pass 也不会产生一个。

于 2013-09-25T00:01:19.620 回答