Слияние k отсортированных списков в Python3, проблема с компромиссом между памятью и временем
Входные данные: первая строка - количество массивов (k); Каждая следующая строка - первое число - размер массива, следующие числа - элементы.
Макс. K равно 1024. Максимальный размер массива 10*k. Все числа от 0 до 100. Ограничение памяти - 10 МБ, ограничение по времени - 1 с. Рекомендуемая сложность k is 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 и читает строки ввода по блокам, один использует 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
Отлично, если бы в первом примере у меня были массивы по частям, чтобы мне не требовалась память для всего ввода, но я не знаю, как правильно читать строки по блокам.
Не могли бы вы предложить что-то, чтобы решить проблему?
2 ответа
О компьютер глубокой мысли, каков ответ на жизнь вселенной и всего остального
Вот код, который я использовал для тестов
"""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 - второе, которое вы дали). Похоже, что ограничение скорости задается вводом / выводом программы, а не самой сортировкой. 
Обратите внимание, что я генерирую квадраты (количество строк == число в строке)
Если строки целых чисел уже отсортированы, вам нужно сосредоточиться только на том, как соединить части вместе.
Для этого мое решение отслеживает 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