python - Python3中合并k个排序列表，内存和时间之间的权衡问题

Question

输入为: 第一行 - 数组数量(k)； 下一行 - 第一个数字是数组大小，接下来的数字是元素。

最大 k 为 1024。最大数组大小为 10*k。所有数字都在 0 到 100 之间。内存限制 - 10MB，时间限制 - 1 秒。 建议的复杂度为 k ⋅ log(k) ⋅ n，其中 n 是数组长度。

输入示例:

4            
6 2 26 64 88 96 96
4 8 20 65 86
7 1 4 16 42 58 61 69
1 84

示例输出:

1 2 4 8 16 20 26 42 58 61 64 65 69 84 86 88 96 96 

我有4个解决方案。一种使用 heapq 并按 block 读取输入行，一种使用 heapq，一种使用 Counter，一种不使用任何内容。

这个使用 heapq (有利于时间，但对内存不利，我认为堆是正确的方式，但是如果我按部分读取行，也许可以优化它，这样我就不需要为整个输入提供内存):

from heapq import merge


if __name__ == '__main__':
    print(*merge(*[[int(el) for el in input().split(' ')[1:]] for _ in range(int(input()))]), sep=' ')

这个是上一个的高级版本。它按 block 读取行，但这是非常复杂的解决方案，我不知道如何优化这些读取:

from heapq import merge
from functools import reduce


def read_block(n, fd, cursors, offset, has_unused_items):
    MEMORY_LIMIT = 10240000
    block_size = MEMORY_LIMIT / n
    result = []

    for i in range(n):
        if has_unused_items[i]:
            if i == 0:
                fd.seek(cursors[i] + offset)
            else:
                fd.read(cursors[i])

            block = ''
            c = 0
            char = ''

            while c < block_size or char != ' ':
                if cursors[i] == 0:
                    while char != ' ':
                        char = fd.read(1)
                        cursors[i] += 1

                char = fd.read(1)

                if char != '\n':
                    block += char
                    cursors[i] += 1
                    c += 1
                else:
                    has_unused_items[i] = False
                    break

            result.append([int(i) for i in block.split(' ')])

            while char != '\n':
                char = fd.read(1)

    return result


def to_output(fd, iter):
    fd.write(' '.join([str(el) for el in iter]))


if __name__ == '__main__':
    with open('input.txt') as fd_input:
        with open('output.txt', 'w') as fd_output:
            n = int(fd_input.readline())
            offset = fd_input.tell()
            cursors = [0] * n
            has_unused_items = [True] * n
            result = []

            while reduce(lambda x, p: x or p, has_unused_items):
                result = merge(
                    result,
                    *read_block(n, fd_input, cursors, offset, has_unused_items)
                )

            to_output(fd_output, result)

这个对内存有好处(使用计数器排序，但我没有使用所有数组都排序的信息):

from collections import Counter


def solution():
    A = Counter()

    for _ in range(int(input())):
        A.update(input().split(' ')[1:])

    for k in sorted([int(el) for el in A]):
        for _ in range(A[str(k)]):
            yield k

这个很适合时间(但可能还不够好):

def solution():
    A = tuple(tuple(int(el) for el in input().split(' ')[1:]) for _ in range(int(input())) # input data
    c = [0] * len(A) # cursors for each array

    for i in range(101):
        for j, a in enumerate(A):
            for item in a[c[j]:]:
                if item == i:
                    yield i
                    c[j] += 1
                else:
                    break 

完美，如果我在第一个示例中按部分排列数组，这样我就不需要整个输入的内存，但我不知道如何正确按 block 读取行。

您能提出一些解决问题的建议吗？

Answer 1

深思计算机啊，生命、宇宙和一切的答案是什么

这是我用于测试的代码

"""4
6 2 26 64 88 96 96
4 8 20 65 86
7 1 4 16 42 58 61 69
1 84"""

from heapq import merge
from io import StringIO
from timeit import timeit

def solution():
    pass

times = []
for i in range(5000):
    f = StringIO(__doc__)
    times.append(timeit(solution, number=1))

print(min(times))

这是结果，我测试了评论中提出的解决方案:

6.5e-06 秒

def solution():
    A = []
    A = merge(A, *((int(i)
                    for i in line.split(' ')[1:])
                    for line in f.readlines()))
    return A

7.1e-06 秒

def solution():
    A = []
    for _ in range(int(f.readline())):
        A = merge(A, (int(i) for i in f.readline().split(' ')[1:]))
    return A

7.9e-07 秒

def solution():
    A = Counter()
    for _ in range(int(f.readline())):
        A.update(f.readline().split(' ')[1:])
    for k in sorted([int(el) for el in A]):
        for _ in range(A[str(k)]):
            yield k

8.3e-06 秒

def solution():
    A = []
    for _ in range(int(f.readline())):
        for i in f.readline().split(' ')[1:]:
            insort(A, i)
    return A

6.2e-07 秒

def solution():
    A = Counter()
    for _ in range(int(f.readline())):
        A.update(f.readline().split(' ')[1:])
    l = [int(el) for el in A]
    l.sort()
    for k in l:
        for _ in range(A[str(k)]):
            yield k

你的代码很棒，不要使用排序(数组越大，影响就越大)。你应该用更大的输入来测试它(我使用了你提供的)。

这仅包含上一题的获胜者(加上解决方案 6，即您提供的第二个解决方案)。看起来速度限制是由程序的 I/O 给出的，而不是排序本身。

请注意，我生成了正方形(行数 == 每行数)