def process_sliding(in_filename, out_filename, window_size=20):
with (open(in_filename, newline='') as fin,
open(out_filename, 'w', newline='') as fout):
reader = csv.reader(fin)
writer = csv.writer(fout)
first_window = sorted(next(reader) for _ in range(window_size))
window = collections.deque(first_window, maxlen=window_size)
for row in reader:
writer.writerow(window.popleft())
window.append(row)
if row[0] < window[-2][0]:
window = collections.deque(sorted(window), maxlen=window_size)
for row in window:
writer.writerow(row)
这是一个非常有趣的问题,因为数据太大,不容易放入内存中。在
首先,关于I/O:如果是CSV,我会使用标准库^{} 对象,如下所示(假设是Python3):
然后我可能会在一个^{} 实例中保留一个行的滑动窗口,根据您的描述,窗口大小设置为20。将第一个
WINDOW_SIZE
行读入deque,然后进入主Read循环,该循环将输出deque中最左边的项(行),然后追加当前行。在在附加每一行之后,如果当前行的时间戳在前一行的时间戳之前(
^{pr2}$window[-2]
),则对deque进行排序。您不能直接对deque进行排序,但可以执行以下操作:Python的Timsort算法可以有效地处理已经排序的运行,因此这应该非常快(线性时间)。在
如果窗口大小和无序行的数量很小(听起来可能是这样),我相信整个算法将是O(N),其中N是数据文件中的行数,所以是线性时间。在
更新:我编写了一些演示代码来生成这样一个文件,然后使用上面的技术对其进行排序请参见this Gist,在Python3.5上进行了测试。在相同的数据上,它比
sort
实用程序快得多,而且在N=1000000之后也比Python的sorted()
函数快得多。顺便说一下,生成演示CSV的函数比排序代码慢得多。:-)我的结果显示各种N的计时(绝对是线性的):作为参考,以下是我的
process_sliding()
版本的代码:相关问题 更多 >
编程相关推荐