Как оптимизировать эту проблему с питоном?

Question

Здесь - это проблема. И мое решение:

import sys
LIST_ITEM = []
NUMBER_OF_TEST_CASES = int(raw_input())
def non_decreasing(my_list):
    if len(my_list) < 2:
        return my_list
    my_list.sort()
    return my_list

if __name__ == "__main__":
    if NUMBER_OF_TEST_CASES >= 1000001 or NUMBER_OF_TEST_CASES <= 0:
        sys.exit()

    for val in range(1, NUMBER_OF_TEST_CASES+1):
        x = int(raw_input())

        if x >= 1000001 or x<0:
            sys.exit()
        else:
            LIST_ITEM.append(x)
    values =  non_decreasing(LIST_ITEM)
    for i in values:
        print i

Но это скажи мне Time Limit Exceeded. Вот ссылка на мое решение

Answer 1

РЕДАКТИРОВАТЬ: Ну дерьмо, видимо, у вас не должно быть дураков?Это меняет положение вещей, и ваш текущий код все равно не работает правильно.Оставляя мой старый ответ на данный момент ...

Простой ответ - это профиль!Я сгенерировал данные с помощью:

import random
out = open('foobar.txt', 'w')

total = random.randint(100000, 1e6)
out.write('%s\n' % total)

for x in xrange(total):
    out.write('%s\n' % random.randint(0, 1e6))

Затем я протестировал с помощью команды: time python -m cProfile -o foo.profile foo.py < foobar.txt > fooout.txt && gprof2dot -f pstats foo.profile | dot -Tpng -o foo_profile.png.Это генерирует эту изящную графику с использованием инструмента gprof2dot и сообщает о времени, которое потребовалось для ее запуска (1,9 с в моей системе с 266 тыс. Строк ввода).sort -n foobar.txt > foo_sorted.txt - мой золотой стандарт, ~ 0,41 с.

Таким образом, вы можете видеть, что 44,81% вашего времени тратится на сам ваш базовый код, 38,82% тратится на raw_input, а 14% тратится наsort.

Итак, мы приступаем к оптимизации.

Сначала нужно поместить ваш код в метод.Просто добавьте def main() вокруг всего вашего кода и в конце if __name__ == '__main__': main().Для меня это сократило время выполнения примерно на 5%, до 1,8 с, и переместило raw_input на самый высокий процент нашей нагрузки.

Давайте посмотрим, сможем ли мы уменьшить это.Возможно, заменить raw_input прямым использованием sys.stdin?Я предполагаю, что raw_input предназначен для интерактивного использования и, вероятно, не очень хорошо профилирован, поскольку (вероятно) не предназначен для интенсивного использования.Заменив raw_input чем-то вроде sys.stdin.readline (), мы должны использовать более эффективный путь кода.Для меня это снижает время выполнения с 1,8 до 0,952.Экономия наполовину!Вот код и вывод профиля.

import sys 

def non_decreasing(my_list):
    if len(my_list) < 2:
        return my_list
    my_list.sort()
    return my_list

def main():
    LIST_ITEM = []
    NUMBER_OF_TEST_CASES = int(sys.stdin.readline().strip())

    if NUMBER_OF_TEST_CASES >= 1000001 or NUMBER_OF_TEST_CASES <= 0:
        sys.exit()

    for x in sys.stdin:
        x = int(x.strip())

        if x >= 1000001 or x<0:
            sys.exit()
        else:
            LIST_ITEM.append(x)
    values =  non_decreasing(LIST_ITEM)
    for i in values:
        print i

if __name__ == '__main__':
    main()

Так что это хорошее начало.Сейчас у нас меньше половины нашего первоначального времени выполнения.Давайте посмотрим, что сейчас медленно.Основная функция sort, strip () и append.Возможно, мы можем оптимизировать что-то в основном?Хорошо, я замечаю, что мы распечатываем строки одну за другой.Можем ли мы это отключить с помощью одного sys.stdout.write () и посмотреть, поможет ли это?Я попытался sys.stdout.writelines([str(x) for x in values]), и это на самом деле казалось медленнее, поэтому я думаю, что печать супер эффективна.Давайте придерживаться этого.

Что еще мы можем уменьшить?Может быть, if x >= 1000001 or x<0: заявление?Это совершенно необходимо?Похоже, мы можем легко избавиться от нескольких сотых долей секунды, удалив ее.

Что еще?Возможно, не нужна вся нерасширяющая вещь, и мы можем просто использовать LIST_ITEM.sort ()?Я полагаю, ваша проверка и дополнительный вызов функции на самом деле ничего не ускоряют.Да, это немного ускоряет это!

В идеале на этом этапе мы будем делать что-то вроде того, чтобы не удалять строки из ввода, сортировать их как строки и затем записывать их.К сожалению, это не дает желаемой сортировки :( Итак, давайте попробуем несколько вариантов

1. for x in sys.stdin: values.append(x[:-1])
2. x.rstrip()
3. x.rstrip('\n')
4. values = sys.stdin.split('\n')
5. values = sys.stdin.read().splitlines()
6. values = sys.stdin.readlines()

В моем тестировании вариант на # 1 самый быстрый и поддерживает правильность, ~.783. Вот мой окончательный код:

import sys

def main():
    NUMBER_OF_TEST_CASES = int(sys.stdin.readline().strip())
    if NUMBER_OF_TEST_CASES >= 1000001 or NUMBER_OF_TEST_CASES <= 0:
        sys.exit()

    values = [int(x) for x in sys.stdin.readlines()]
    values.sort()
    for i in values:
        print i

if __name__ == '__main__':
    main()

И последняя информация о профиле gprof2dot ...

Answer 2

Не сортируйте!

Просто создайте массив нулей длины 1e6 (возможно, в numpy), прочитайте список с установкой a [i] = 1 всякий раз, когда вы встретите число i, а затем распечатайте все ненулевые записи.

Я думаю, что это работает:

import numpy as np
import sys

nn = 1000000
a = np.zeros(nn+1, dtype=np.int)

for l in sys.stdin:
    a[np.int(l)]=1

for i in xrange(nn+1):
    if a[i]: print i

Я ожидаю, что есть способ ускорить ввод / вывод.

Answer 3

Поскольку значение и размер входных данных ограничены 10 ^ 6, вы можете просто инициализировать массив из 10 ^ 6 значений и отслеживать, какие значения появились. Сортировка и обнаружение дубликатов "бесплатно".

Этот метод будет иметь начальную стоимость (инициализация массива), но он будет оправдан для больших входных размеров.

Пример: импортировать массив из sys import stdin из itertools импорт повтор

low  = 1000001
high = -1
data = array.array('i', repeat(-1, 1000000))
count = int(stdin.readline().strip())

while count:
    v = int(stdin.readline().strip())
    count -= 1
    data[v] = v
    low  = min(v, low)
    high = max(v, high)

for v in xrange(low, high+1):
    if data[v] > 0:
        print v

Обратите внимание, что я использовал array, поскольку размер и тип известны заранее, поэтому мы можем обойти накладные расходы, связанные с использованием list.

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