1

I am working with a text file of about 12*10^6 rows which is stored on my hard disk. The structure of the file is:

data|data|data|...|data\n
data|data|data|...|data\n
data|data|data|...|data\n
...
data|data|data|...|data\n

There's no header, and there's no id to uniquely identify the rows.

Since I want to use it for machine learning purposes, I need to make sure that there's no order in the text file which may affect the stochastic learning.

Usually I upload such kind of files into memory, and I shuffle them before rewriting them to disk. Unfortunately this time it is not possible, due to the size of the file, so I have to manage the shuffling directly on disk(assume I don't have problem with the disk space). Any idea about how to effectively (with lowest possible complexity, i.e. writing to the disk) manage such task with Python?

4

4 回答 4

6

除了其中一个之外，所有这些想法都使用 O(N) 内存——但如果你使用array.array或者numpy.ndarray我们正在谈论 N*4 字节，这比整个文件要小得多。（为简单起见，我将使用一个简单的列表；如果您需要帮助转换为更紧凑的类型，我也可以展示。）

使用临时数据库和索引列表：

with contextlib.closing(dbm.open('temp.db', 'n')) as db:
    with open(path) as f:
        for i, line in enumerate(f):
            db[str(i)] = line
    linecount = i
    shuffled = random.shuffle(range(linecount))
    with open(path + '.shuffled', 'w') as f:
        for i in shuffled:
            f.write(db[str(i)])
os.remove('temp.db')

这是 2N 单行磁盘操作，和 2N 单 dbm-key 磁盘操作，应该是 2NlogN 单磁盘磁盘操作等效操作，所以总复杂度是 O(NlogN)。

如果你使用关系数据库sqlite3而不是 dbm，你甚至不需要索引列表，因为你可以这样做：

SELECT * FROM Lines ORDER BY RANDOM()

这与上面的时间复杂度相同，空间复杂度是 O(1) 而不是 O(N)——理论上。在实践中，您需要一个 RDBMS，它可以一次从 100M 行集中为您提供一行，而无需在任一侧存储该 100M。

一个不同的选择，不使用临时数据库——理论上 O(N**2)，但实际上如果你碰巧有足够的内存让行缓存有用的话，可能会更快：

with open(path) as f:
    linecount = sum(1 for _ in f)
shuffled = random.shuffle(range(linecount))
with open(path + '.shuffled', 'w') as f:
    for i in shuffled:
        f.write(linecache.getline(path, i))

最后，通过将索引列表的大小加倍，我们可以消除临时磁盘存储。但在实践中，这可能会慢很多，因为您正在进行更多的随机访问读取，而驱动器几乎不擅长这些读取。

with open(path) as f:
    linestarts = [f.tell() for line in f]
    lineranges = zip(linestarts, linestarts[1:] + [f.tell()])
    shuffled = random.shuffle(lineranges)
    with open(path + '.shuffled', 'w') as f1:
        for start, stop in shuffled:
            f.seek(start)
            f1.write(f.read(stop-start))
于 2013-10-10T19:38:48.093 回答
2

这是根据我上面的评论提出的建议。它依赖于让压缩线仍然能够放入内存中。如果不是这种情况，则需要其他解决方案。

import zlib
from random import shuffle

def heavy_shuffle(filename_in, filename_out):
    with open(filename_in, 'r') as f:
        zlines = [zlib.compress(line, 9) for line in f]
    shuffle(zlines)
    with open(filename_out, 'w') as f:
        for zline in zlines:
            f.write(zlib.decompress(zline) + '\n')

我的经验是 zlib 很快，而 bz2 提供更好的压缩，所以你可能想比较一下。

此外，如果您可以避免分块，例如将 n 行放在一起，那么这样做可能会提高您的压缩率。

我想知道有用压缩的可能性，所以这里有一个 IPython 实验。我不知道您的数据是什么样的，所以我只是将浮点数（作为字符串）四舍五入到 3 个位置并用管道串在一起：

最好的情况（例如，许多行都有相同的数字）：

In [38]: data = '0.000|'*200

In [39]: len(data)
Out[39]: 1200

In [40]: zdata = zlib.compress(data, 9)

In [41]: print 'zlib compression ratio: ',1.-1.*len(zdata)/len(data)
zlib compression ratio:  0.98

In [42]: bz2data = bz2.compress(data, 9)

In [43]: print 'bz2 compression ratio: ',1.-1.*len(bz2data)/len(data)
bz2 compression ratio:  0.959166666667

正如预期的那样，最好的情况非常好，>95% 的压缩率。

最坏情况（随机数据）：

In [44]: randdata = '|'.join(['{:.3f}'.format(x) for x in np.random.randn(200)])

In [45]: zdata = zlib.compress(randdata, 9)

In [46]: print 'zlib compression ratio: ',1.-1.*len(zdata)/len(data)
zlib compression ratio:  0.5525

In [47]: bz2data = bz2.compress(randdata, 9)

In [48]: print 'bz2 compression ratio: ',1.-1.*len(bz2data)/len(data)
bz2 compression ratio:  0.5975

令人惊讶的是，最坏的情况并不算太差 ~60% 的压缩比，但如果您只有 8 GB 内存（15 GB 的 60% 是 9 GB），则可能会出现问题。

于 2013-10-11T04:21:17.167 回答
0

这个问题可以被认为是一个有效的内存页面管理问题，以减少交换文件 I/O。让您的缓冲区buf成为您希望存储到输出文件中的连续文件块的列表。让一个连续的文件块成为固定数量的整行的列表。

现在，生成一个随机序列并将返回的值重新映射到相应的块编号和该块内的行偏移。

此操作为您留下了一个数字序列[1..num of chunks]，可以将其描述为对包含在[1..num of chunks]. 对于在线变体（如在真实操作系统中），没有针对此问题的最佳策略，但是由于您知道页面引用的实际顺序，因此可以在此处找到最佳解决方案。

这种方法有什么好处？最常使用的页面从 HDD 中重新读取的次数最少，这意味着读取数据的 I/O 操作更少。此外，考虑到与内存占用相比，您的块大小足以最大程度地减少页面交换，输出文件后面的行很多时候将取自存储在内存中的同一块（或任何其他块，但尚未交换到驱动器），而不是从驱动器重新读取。

也许这不是最简单的解决方案（尽管最佳页面交换算法很容易编写），但它可能是一个有趣的练习，不是吗？

于 2013-10-10T19:55:06.990 回答
0

假设磁盘空间对您来说不是问题，我正在创建多个文件来保存数据。

import random
import os

PMSize = 100 #Lesser value means using more primary memory
shuffler = lambda x: open(x, 'w')
shufflers = [shuffler('file'+str(x)) for x in range(PMSize)]

with open('filename') as file:
    for line in file:
        i = random.randint(0, len(shufflers)-1)
        shufflers[i].write(line)

with open('filename', 'w') as file:
    for file in shufflers:
        newfile.write(file.read())

for file in shufflers:
    os.remove(file)

您的内存复杂性将由 PMSize 控制。时间复杂度约为 O(N + PMSize)。

于 2013-10-10T19:55:28.540 回答