python использует лучшие алгоритмы, чтобы сэкономить как можно больше времени?

Question

У меня есть вопрос, на который может быть очень просто ответить. Я нигде не мог найти ответ. Использует ли python наилучшие возможные алгоритмы, чтобы сэкономить как можно больше времени? Я только что видел на каком-то веб-сайте, что, например, порядок времени в методах max - в списках - это O (n) в python, что, как вы знаете, имеет лучшие временные порядки. Это правда? я должен использовать алгоритмы, которые, как я знаю, могут работать лучше, чтобы сэкономить больше времени, или python сделал это для меня своими методами?

Answer 1

максимальный порядок времени в методе - в списках - это O (n) в python, которые, как вы знаете, имеют лучшие временные порядки. Это правда?

Нет, это не правда. Поиск максимального значения в списке потребует проверки всех значений в списке, следовательно, O (n) .

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

• У вас есть список, который уже отсортирован (это процесс O (nlogn) ). В этом случае вы, конечно, можете получить максимум за постоянное время, так как вы знаете его индекс. Если список отсортирован в порядке возрастания, было бы неразумно вызывать max, так как это действительно было бы пустой тратой времени. Вы можете знать, что список отсортирован, но python не примет это и все равно сканирует весь список.

• У вас есть список, который был heapified до максимальной кучи (что является процессом O (n) ). Опять же, в этом случае вы можете получить максимум за постоянное время, так как он хранится с индексом 0. Списки можно накапливать с помощью heapq - по умолчанию используется min-heap.

Итак, если вы ничего не знаете о своем списке, то вам придется проверить все значений, чтобы точно определить максимум. Вот что делает max(). Если вы действительно знаете что-то большее, что может помочь определить максимум без необходимости просматривать все значения, тогда используйте другой, более подходящий метод.

Должен ли я использовать алгоритмы, которые, как я знаю, могут работать лучше, чтобы сэкономить больше времени, или python сделал это для меня в своих методах?

Вам следует использовать алгоритмы, которые, как вы знаете, могут работать лучше (исходя из того, что вы знаете о структуре данных). Во многих случаях такая лучшая реализация алгоритма доступна через библиотеку python. Например, чтобы найти определенное значение в отсортированном списке, используйте bisect.bisect_left, а не index.

. Посмотрите на более сложный пример. Допустим, вы написали код, который может генерировать шахматные ходы и имитировать игру в шахматы. У вас есть хорошие идеи о функциях оценки, сокращении алфавита, перемещениях убийцы, таблицах поиска и ... и множестве других методов оптимизации. Вы не можете ожидать, что python станет умным, когда вы введете наивный max для "всех" оцененных шахматных состояний. Вам необходимо реализовать сложный алгоритм для эффективного поиска и фильтрации правильных состояний, чтобы получить «лучшие» шахматные ходы из этого леса информации, не тратя время на менее многообещающие ходы.

Answer 2

A Python список - это последовательный и непрерывный контейнер. Это означает, что поиск i-го элемента происходит за постоянное время, а добавление в конец легко, если перераспределение не требуется.

Нахождение значения равно O (n / 2), а нахождение min или max равно O ( n).

Если вы хотите получить список и сможете найти его минимальное значение в O (1), доступен модуль heapq, который поддерживает двоичное дерево.

Но Python предлагает несколько специализированных контейнеров в своей стандартной библиотеке.

Answer 3

С точки зрения сложности, вы обнаружите, что python почти всегда использует решения, основанные на алгоритмах с лучшей сложностью. Производительность может варьироваться в зависимости от констант, и python - это не самый быстрый язык по сравнению с C или C ++.

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

Answer 4

Отличается от библиотеки к библиотеке

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

К сожалению, Python довольно медленный по родам по сравнению с такими языками, как C, C ++ или java.

. Это потому, что python - это один скрипт, который читает ваш скрипт и выполняет его вживую.

C, C ++ и Java все компилируются в двоичный файл (exe) перед выполнением.

// SW