3

我有一个 4000 万行、3 GB 的大文本文件(可能无法放入内存),格式如下:

399.4540176 {Some other data}
404.498759292 {Some other data}
408.362737492 {Some other data}
412.832976111 {Some other data}
415.70665675 {Some other data}
419.586515381 {Some other data}
427.316825959 {Some other data}
.......

每行以一个数字开头,然后是一些其他数据。数字按排序顺序排列。我需要能够:

  1. 给定一个数字x和一个范围y,找出所有数字在y范围内的行x。例如 ifx=20y=5,我需要找到编号在15and之间的所有行25
  2. 将这些行存储到另一个单独的文件中。

什么是一种有效的方法来做到这一点而不必遍历整个文件?

4

4 回答 4

5

如果您不想提前为行长生成数据库,可以试试这个:

import os
import sys

# Configuration, change these to suit your needs
maxRowOffset = 100  #increase this if some lines are being missed
fileName = 'longFile.txt'
x = 2000
y = 25

#seek to first character c before the current position
def seekTo(f,c):
    while f.read(1) != c:
        f.seek(-2,1)

def parseRow(row):
    return (int(row.split(None,1)[0]),row)

minRow = x - y
maxRow = x + y
step = os.path.getsize(fileName)/2.
with open(fileName,'r') as f:
    while True:
        f.seek(int(step),1)
        seekTo(f,'\n')
        row = parseRow(f.readline())
        if row[0] < minRow:
            if minRow - row[0] < maxRowOffset:
                with open('outputFile.txt','w') as fo:
                    for row in f:
                        row = parseRow(row)
                        if row[0] > maxRow:
                            sys.exit()
                        if row[0] >= minRow:
                            fo.write(row[1])
            else:
                step /= 2.
                step = step * -1 if step < 0 else step
        else:
            step /= 2.
            step = step * -1 if step > 0 else step

它首先对文件执行二进制搜索,直到它靠近(小于maxRowOffset)要查找的行。然后它开始读取每一行,直到找到大于 的行x-y。该行及其之后的每一行都被写入输出文件,直到找到大于 的行x+y,以及程序退出的点。

我在一个 1,000,000 行的文件上进行了测试,它在 0.05 秒内运行。将此与阅读每行花费 3.8 秒进行比较。

于 2012-10-12T15:09:59.173 回答
4

您需要随机访问文本文件无法获得的行,除非这些行都填充到相同的长度。

一种解决方案是将表转储到具有两列的数据库(例如 SQLite)中,一列用于数字,另一列用于所有其他数据(假设数据保证适合单个允许的最大字符数)数据库中的列是)。然后索引数字列,你就可以开始了。

如果没有数据库,您可以一次读取文件并创建一个内存数据结构,其中包含显示包含(数字,行偏移)的值对。您可以通过添加每行的长度(包括行尾)来计算行偏移。现在您可以在数字上对这些值对进行二进制搜索,并使用偏移量随机访问文件中的行。如果您需要稍后重复搜索,请腌制内存结构并重新加载以供以后重用。

这会读取整个文件(您说过您不想这样做),但只执行一次以构建索引。之后,您可以根据需要对文件执行任意数量的请求,它们会非常快。

请注意,第二个解决方案本质上是在您的文本文件上创建数据库索引。

在第二种解决方案中创建索引的粗略代码:

 import Pickle

 line_end_length = len('\n') # must be a better way to do this!
 offset = 0
 index = [] # probably a better structure to use than a list

 f = open(filename)
 for row in f:
     nbr = float(row.split(' ')[0])
     index.append([nbr, offset])
     offset += len(row) + line_end_length

 Pickle.dump(index, open('filename.idx', 'wb')) # saves it for future use

现在,您可以对列表执行二进制搜索。可能有比列表更好的数据结构来累积索引值,但我必须阅读各种集合类型。

于 2012-10-12T13:06:02.540 回答
2

由于您想匹配第一个字段,您可以使用gawk

$ gawk '{if ($1 >= 15 && $1 <= 25) { print }; if ($1 > 25) { exit }}' your_file

编辑:获取一个包含 261,775,557 行的文件,大小为 2.5 GiB,50,010,01550,010,025我的Intel(R) Core(TM) i7 CPU 860 @ 2.80GHz. 听起来对我来说已经足够好了。

于 2012-10-12T12:53:30.157 回答
0

为了找到以刚好高于下限的数字开头的行,您必须逐行浏览文件,直到找到该行。没有其他方法,即必须读取文件中的所有数据并解析换行符。

我们必须将此搜索运行到超过您的上限的第一行并停止。因此,它有助于文件已经排序。这段代码希望能有所帮助:

with open(outpath) as outfile:
    with open(inpath) as infile:
        for line in infile:
            t = float(line.split()[0])
            if lower_limit <= t <= upper_limit:
                outfile.write(line)
            elif t > upper_limit:
                break

我认为理论上没有其他选择。

于 2012-10-12T13:02:24.287 回答