Будет ли когда-нибудь сокращаться список Python?(с помощью операций pop ())

Question

Я широко использовал .pop() и .append() для задач программирования в стиле Leetcode, особенно в тех случаях, когда вам нужно накопить палиндромы, подмножества, перестановки и т. Д.

Получу ли я существенную производительностьвыиграть от перехода на использование списка фиксированного размера вместо?Меня беспокоит то, что внутренне список python перераспределяется во внутренний массив меньшего размера, когда я выполняю несколько всплывающих окон, а затем должен снова «выделять» при добавлении.

Я знаю, что сложность амортизируемого времени при добавлениии pop это O (1), но я хочу получить лучшую производительность, если смогу.

Answer 1

Да.

Python (по крайней мере, реализация CPython) использует магию под капотом, чтобы сделать списки максимально эффективными.Согласно этого сообщения в блоге (2011), вызовы append и pop динамически распределяют и освобождают память порциями (перераспределяют при необходимости) для эффективности.Список освобождает память только в том случае, если он сжимается ниже размера чанка.Таким образом, в большинстве случаев, если вы выполняете много операций добавления и удаления, выделение / освобождение памяти выполняться не будет.

В основном идея с этими языками высокого уровня заключается в том, что вы должны иметь возможность использовать структуру данныхнаиболее подходит для вашего случая использования, и переводчик гарантирует, что вам не придется беспокоиться о фоновой работе.(например, избегайте микрооптимизации и вместо этого сосредотачивайтесь на эффективности алгоритмов в целом). Если вы беспокоитесь о производительности, я бы предложил использовать язык, где у вас больше контроля над памятью, например C / C ++ или Rust.

Python гарантирует сложность O (1) для append и pops, как вы заметили, поэтому, похоже, он идеально подойдет для вашего случая.Если вы хотите использовать его как очередь и использовать такие вещи, как list.pop(1) или list.insert(0, obj), которые работают медленнее, вы можете посмотреть в выделенную структуру данных очереди, например.