Оптимизация по времени и памяти кода на Python3

#python #python_36

Есть задача в условии которой есть ограничения Время: 1 сек. Память: 16 Мб.
Ссылка на задачу

Условие:


  Задана последовательность целых чисел. Числа нумеруются по порядку следования,
начиная с единицы.
  
  Требуется написать программу, которая найдет сумму максимума из чисел с четными
номерами и минимума из чисел с нечетными номерами – max{a2, a4, …}+min{a1, a3, …}.  


Есть 2 варианта кода для решения этой задачи (на самом деле их больше но эти ближе
остальных к выполнению требований): 

Код раз:

in_file = open('INPUT.TXT')
num_set = in_file.read().split()
max_even, min_odd = int(max(tuple(num_set[i] for i in range(1, len(num_set), 2)),
key=int)), \
                    int(min(tuple(num_set[i] for i in range(0, len(num_set), 2)),
key=int))

open('OUTPUT.TXT', 'w').write(str(sum([max_even, min_odd])))



  Время: 0,093 - Память: 17 Мб  




Код два:

in_file = open('INPUT.TXT')
num_set = in_file.read().split()
in_file.close()
evens = []
odds = []
while len(num_set) > 0:
    odds.append(num_set.pop(0))
    if len(num_set) > 0:
        evens.append(num_set.pop(0))

open('OUTPUT.TXT', 'w').write(str(sum([max(map(int, evens)), min(map(int, odds))])))



  Время: 1,218 - Память: 8,3 Мб




Вопрос:

Есть-ли какие-нибудь способы оптимизации по использованию ресурсов?
    

Ответы

Ответ 1

Вот мое решение:

Время: 0,343

Память: 5,8 Мб

Код:

import re

with open('INPUT.TXT') as f:
    num_set = re.finditer('-?\d+', f.read())

def get_next_num():
    return int(next(num_set).group())

odd_min = get_next_num()
even_max = get_next_num()

while True:
    try:
        num = get_next_num()
        if odd_min > num:
            odd_min = num

        num = get_next_num()
        if even_max < num:
            even_max = num

    except StopIteration:
        break

with open('OUTPUT.TXT', 'w') as f:
    f.write(str(even_max + odd_min))




Оптимизация через открытие файла в бинарном режиме чтения:

Время: 0,296

Память: 4178 Кб

with open('INPUT.TXT', 'rb') as f:
    num_set = re.finditer(b'-?\d+', f.read())
...




Оптимизация через использование модуля mmap:

Время: 0,296

Память: 1934 Кб

import mmap
import re

with open('INPUT.TXT', 'rb') as fin:
    mf = mmap.mmap(fin.fileno(), 0, access=mmap.ACCESS_READ)
    num_set = re.finditer(b'-?\d+', mf)

...




PS.

Мне все-время нехватало памяти, когда делал split по строчке с числами (num_set =
f.read().split()), поэтому решил извернуться и сделать итератор чисел. Сразу что пришло
в голову -- finditer из модуля регулярок.

А т.к. по заданию четные и нечетные числа идут друг за другом, то посчитал, что используя
next можно будет запрашивать следующие друг за другом значения пока они не закончатся
(StopIteration)

Открытие 'INPUT.TXT' в бинарном режиме уменьшает итоговое время и потребление памяти:
0,343 -> 0,296 и 5,8 Мб -> 4178 Кб.

Результаты по времени и памяти могут немного отличаться от запуска к запуску в той
проверяющей системе.

Этот же самый код совместим с PyPy и на PyPy будет быстрее выполняться: 0,296 ->
0,203 и 1934 Кб -> 1753 Кб


Ответ 2

Память: 12 Мб
Время:  0,125
у такого варианта:

import csv
with open('INPUT.TXT', newline='') as csvfile:
    line_reader = csv.reader(csvfile, delimiter=' ', quoting = csv.QUOTE_NONNUMERIC)
    for row in line_reader:
        with open('OUTPUT.TXT', 'w') as f:
            f.write(str(int(min(row[::2])+max(row[1::2]))))


Здесь сплит и конвертация делается "руками" модуля csv, однако автоматическая конвертация
идет к типу float, хотя не думаю что это скажется на скорости операции "сравнение".
А вот чего память так расходуется - интересненько бы понять.