Ответ 1

Если вы задаете вопрос об оптимизации кода python вообще (что, я думаю, это должно быть;), тогда есть всевозможные вещи, которые вы можете делать, но сначала:

Вероятно, вы не должны навязчиво оптимизировать код Python! Если вы используете самый быстрый алгоритм для проблемы, которую вы пытаетесь решить, и python не делает это достаточно быстро, вы, вероятно, должны использовать другой язык.

Тем не менее, есть несколько подходов, которые вы можете предпринять (потому что иногда вы действительно хотите сделать код на Python быстрее):

Профиль (сделайте это первым!)

Существует много способов профилирования кода python, но есть два, которые я упомянул: cProfile (или profile) module и PyCallGraph.

Cprofile

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

Вы можете запустить функцию в cProfile следующим образом:

import cProfile
cProfile.run('myFunction()', 'myFunction.profile')

Затем для просмотра результатов:

import pstats
stats = pstats.Stats('myFunction.profile')
stats.strip_dirs().sort_stats('time').print_stats()

Это покажет вам, какие функции большую часть времени потрачены.

PyCallGraph

PyCallGraph предоставляет самый красивый и, возможно, самый простой способ профилирования программ python - и это хорошее введение в понимание того, где время ваша программа потрачена, однако она добавляет значительные накладные расходы

Чтобы запустить pycallgraph:

pycallgraph graphviz ./myprogram.py

Simple! Вы получаете графическое изображение png как результат (возможно, через некоторое время...)

Использовать библиотеки

Если вы пытаетесь сделать что-то в python, что модуль уже существует (возможно, даже в стандартной библиотеке), тогда используйте этот модуль!

Большинство стандартных библиотечных модулей написаны на C, и они будут выполняться в сотни раз быстрее, чем эквивалентные реализации python, скажем, bisection search.

Сделать интерпретатором так много работы, как вы можете

Интерпретатор сделает для вас кое-что, например, цикл. В самом деле? Да! Вы можете использовать ключевые слова map, reduce и filter, чтобы значительно ускорить тесные циклы:

рассмотреть следующие вопросы:

for x in xrange(0, 100):
    doSomethingWithX(x)

против

map(doSomethingWithX, xrange(0,100))

Ну, очевидно, это может быть быстрее, потому что интерпретатору нужно иметь дело только с одним утверждением, а не с двумя, но это немного расплывчато... на самом деле это происходит быстрее по двум причинам:

• все управление потоком (мы закончили цикл еще...) выполняется в интерпретаторе
• имя функции doSomethingWiспасибо разрешается только один раз

В цикле for каждый цикл вокруг цикла python должен точно проверять, где находится функция doSomethingWithX! даже с кэшированием это немного накладные расходы.

Помните, что Python - это интерпретируемый язык

(Обратите внимание, что этот раздел действительно касается крошечных крошечных оптимизаций, которые вы не должны допускать, чтобы повлиять на ваш обычный, читаемый стиль кодирования!) Если вы исходите из программирования на компилированном языке, например c или Fortran, то некоторые вещи о производительности различных операторов python могут быть неожиданными:

try: ing дешево, if дорого стоит

Если у вас есть такой код:

if somethingcrazy_happened:
     uhOhBetterDoSomething()
else:
     doWhatWeNormallyDo()

И doWhatWeNormallyDo() выкинет исключение, если произойдет что-то сумасшедшее, тогда было бы быстрее упорядочить ваш код следующим образом:

try:
    doWhatWeNormallyDo()
except SomethingCrazy:
    uhOhBetterDoSomething()

Почему? хорошо переводчик может погрузиться прямо и начать делать то, что вы обычно делаете; в первом случае интерпретатор должен выполнять поиск символа каждый раз, когда выполняется оператор if, поскольку имя может ссылаться на что-то другое с момента последнего выполнения оператора! (И поиск имени, особенно если somethingcrazy_happened есть global, может быть нетривиальным).

Вы имеете в виду Who??

Из-за стоимости поиска по именам также может быть лучше кэшировать глобальные значения внутри функций и выпекать простые логические тесты в таких функциях:

Неоптимизированная функция:

def foo():
    if condition_that_rarely_changes:
         doSomething()
    else:
         doSomethingElse()

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

Когда условие становится истинным:

foo = doSomething # now foo() calls doSomething()

Когда условие становится ложным:

foo = doSomethingElse # now foo() calls doSomethingElse()

PyPy

PyPy - это реализация python, написанная на python. Неужели это означает, что он будет запускать код бесконечно медленнее? Ну нет. PyPy на самом деле использует компилятор Just-In-Time (JIT) для запуска программ python.

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

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

Где искать дальше

Конечно, первое, на что вы должны обратить внимание, это улучшить ваши алгоритмы и структуры данных, а также рассмотреть такие вещи, как кеширование, или даже нужно ли вам делать это в первую очередь, но в любом случае:

• Эта страница вики python.org содержит много информации о том, как ускорить код python, хотя некоторые из них немного устаревший.

• Здесь сам BDFL по вопросу оптимизации циклов.

Есть немало вещей, даже из-за моего ограниченного опыта, который я пропустил, но этот ответ был уже достаточно длинным!

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

Ответ 2

Прежде всего, профиль вашего кода, чтобы вы знали, где проблемы. Существует много примеров того, как это сделать: здесь https://codereview.stackexchange.com/questions/3393/im-trying-to-understand-how-to-make-my-application-more-efficient

Вы много индексировали доступ, как в:

for pair in range(i-1, j):
    if coordinates[pair][0] >= 0 and coordinates[pair][1] >= 0:

Что можно было бы написать более просто:

for coord in coordinates[i-1:j]:
    if coord[0] >= 0 and cood[1] >= 0:

Пояснения в списках классные и "pythonic", но этот код, вероятно, будет работать быстрее, если вы не создали 4 списка:

N = int(raw_input())
coordinates = []
coordinates = [raw_input() for i in xrange(N)]
coordinates = [pair.split(" ") for pair in coordinates]
coordinates = [[int(pair[0]), int(pair[1])] for pair in coordinates]

Вместо этого я свернул бы все эти элементы в один простой цикл или, если вы действительно мертвы, на основе списка, инкапсулируйте множественные преобразования в функцию, которая работает с raw_input().

Ответ 3

Этот ответ показывает, как я могу найти код для оптимизации. Предположим, что есть некоторая строка кода, которую вы могли бы заменить, и она стоит, скажем, 40% времени. Затем он находится в стеке вызовов 40% времени. Если вы возьмете 10 образцов стека вызовов, они появятся на 4 из них, дайте или возьмите. На самом деле неважно, сколько образцов показывает это. Если он отображается на двух или более, и если вы можете его заменить, вы сэкономите время, затрачиваемое на него.

Ответ 4

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

Другими словами, если вы терпите неудачу в некоторых тестах из-за нехватки времени, проблема в том, что вам нужно найти решение с более низкой алгоритмической сложностью, а не микро-оптимизировать алгоритм, который у вас есть. Вот почему они обычно утверждают, что N может быть довольно большим.