Слияние k отсортированных списков в Python3, проблема с компромиссом между памятью и временем

Question

Ввод: первая строка - количество массивов (k);Каждая следующая строка - первое число - размер массива, следующие числа - элементы.

Макс. K равно 1024. Максимальный размер массива 10 * k.Все числа от 0 до 100. Ограничение памяти - 10 МБ, ограничение по времени - 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 

Iесть 4 решения.Один использует heapq и читает входные строки по блокам, один использует 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=' ')

Это расширенная версия предыдущей.Он читает строки по блокам, однако это очень сложное решение, я не знаю, как оптимизировать это чтение:

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 

Отлично, если бы у меня были массивычастей в первом примере, так что мне не понадобится память для всего ввода, но я не знаю, как правильно читать строки по блокам.

Не могли бы вы предложить что-нибудь для решения проблемы?

Answer 1

Если строки целых чисел уже отсортированы, вам нужно сосредоточиться только на том, как соединить части вместе.

Для этого мое решение отслеживает state проблемы в списке кортежей.

Каждый кортеж записывает offset строки, num_elements, которая являетсячисло элементов в строке, которые еще предстоит обработать, next_elem - это значение следующего элемента, который должен быть обработан, last_elem - это значение последнего элемента в строке.

Алгоритм проходит по циклу:список state кортежей, которые сортируются на основе значений next_elem и last_elem, добавляя следующие самые низкие значения в список A.state обновляется, и список сортируется, промывается и повторяется до тех пор, пока список не станет пустым.

Мне было бы интересно посмотреть, как это работает относительно других решений.

from operator import itemgetter

def solution():
    state = []
    A = []
    k = int(f.readline())
    for _ in range(k):
        offset = f.tell()
        line = f.readline().split()
        # Store the state data for processing each line in a tuple
        # Append tuple to the state list: (offset, num_elements, next_elem, last_elem)
        state.append((offset, int(line[0]), int(line[1]), int(line[-1])))
    # Sort the list of stat tuples by value of next and last elements
    state.sort(key=itemgetter(2, 3))
    # [
    #    (34, 7, 1, 69),
    #    (2, 6, 2, 96),
    #    (21, 4, 8, 86),
    #    (55, 1, 84, 84)
    # ]
    while (len(state) > 0):
        offset, num_elements, _, last = state[0]
        _ = f.seek(offset)
        line = f.readline().split()
        if ((len(state) == 1) or (last <= state[1][2])):
            # Add the remaining line elements to the `result`
            A += line[-(num_elements):]
            # Delete the line from state
            del state[0]
        else:
            while (int(line[-(num_elements)]) <= state[1][2]):
                # Append the element to the `result`
                A.append(line[-(num_elements)])
                # Decrement the number of elements in the line to be processed
                num_elements -= 1
            if (num_elements > 0):
                # Update the tuple
                state[0] = (offset, (num_elements), int(
                    line[-(num_elements)]), int(line[-1]))
                # Sort the list of tuples
                state.sort(key=itemgetter(2, 3))
            else:
                # Delete the depleted line from state
                del state[0]
    # Return the result
    return A

Answer 2

O Deep Thought computer, каков ответ на жизнь вселенной и всего на свете

Вот код, который я использовал для тестов

"""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 - второе, которое вы дали).Похоже, что ограничение скорости задается вводом / выводом программы, а не самой сортировкой.

Обратите внимание, что я генерирую квадраты (количество строк == число в строке)