Разве CPython str.join() не является немного неэффективным?

Этот ответ и его комментарии дают некоторое представление о внутренней работе CPython str.join():

  1. Если аргумент еще не является list или tuple, создается новый list с тем же содержимым.
  2. Аргумент повторяется один раз, чтобы суммировать длины строк, которые он содержит.
  3. Память выделяется для новой строки.
  4. Наконец, аргумент повторяется во второй раз, и строки копируются в память для новой строки.

Мне это кажется сомнительным. Во-первых, зачем отбрасывать все типы последовательностей, кроме двух? Разве не будет намного быстрее просто повторять любую последовательность дважды вместо ее копирования? И зачем делать list, особенно если вы не можете знать длину итерации, из которой вы ее делаете? Вам не нужен произвольный доступ, просто повторная итерация, а использование list означает, что вам, возможно, придется перераспределять и копировать несколько раз во время его создания. Не лучше ли использовать связанный список или deque?

Может ли кто-нибудь дать некоторое представление об этих дизайнерских решениях?


python performance cpython python-internals
person Blacklight Shining    schedule 12.04.2015    source источник
comment
Для строк разумного размера требуется перераспределить гораздо меньше данных при увеличении списка, чем при изменении размера создаваемой строки.   -  person user2864740    schedule 12.04.2015
comment
@user2864740 user2864740 Сравните это с использованием связанного списка, который всегда требует нулевого перераспределения для всего запуска.   -  person Blacklight Shining    schedule 12.04.2015
comment
Совсем не так. Ячейки в связанном списке должны быть выделены. Разница только в том, выделяются ли они в одном массиве (согласно list) или если они выделяются индивидуально. В обоих случаях элементы внутри не клонируются. То есть схема распределения list фактически действует как SLAB.   -  person user2864740    schedule 12.04.2015
comment
@user2864740 user2864740 O (n) выделений для построения связанного списка. Никаких пере-распределений.   -  person Blacklight Shining    schedule 12.04.2015
comment
Разница между двумя схемами распределения обсуждалась снова и снова. Есть очень мало случаев, когда связанный список даже «лучше» в этом аспекте. Существует значительно меньше общих выделений для структуры на основе массива, но для этого требуется копия после выделений, а резерв требуется для уменьшения общих выделений (и копий ячеек). Копии обычно дешевле, чем распределения.   -  person user2864740    schedule 12.04.2015
comment
@BlacklightShining обратите внимание, что список Python представляет собой массив ссылок на объекты, а не на сами объекты.   -  person jonrsharpe    schedule 12.04.2015
comment
@jonrsharpe Верно. И чтобы увеличить размер этого массива (как только у вас закончится резерв), вам нужно выделить новый, больший блок памяти, скопировать все элементы и освободить старый блок.   -  person Blacklight Shining    schedule 12.04.2015
comment
@BlacklightShining В конце концов, это не имеет значения. Список, поддерживаемый массивом, эффективно действует как собственная плита. Требуется только ~O(lg n) перераспределения (с коэффициентом роста, равным двум). Во многих случаях это оказывается намного лучше, чем выделение O(n) новых узлов, особенно если учесть, что это позволяет избежать накладных расходов на каждый узел. Даже если здесь есть небольшая разница (мои деньги по-прежнему связаны с реализацией массива-списка), это не имеет значения для общей стоимости операции соединения.   -  person user2864740    schedule 12.04.2015
comment
Связано: itertools.tee. Обратите внимание на комментарий: В общем случае, если один итератор использует большую часть или все данные до запуска другого итератора, быстрее использовать list() вместо tee().   -  person jonrsharpe    schedule 12.04.2015
comment
Копирование списка ссылок из одного блока памяти в другой на уровне C является тривиальным, если вы знаете, что это просто перемещение - счетчики ссылок обновлять не нужно. Это просто memcpy. В итоге вы делаете это только log(n) раз.   -  person Mark Ransom    schedule 13.04.2015

Ответы (1)


arrow_upward
2
arrow_downward

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

Аргумент join не обязательно должен быть последовательностью. Это может быть любой итерируемый, а некоторые итерируемые объекты нельзя повторять более одного раза. Это может быть, например, выражение генератора, которое будет исчерпано после однократного повторения.

Что касается вашего второго вопроса, я не знаю конкретно, хотя я предполагаю, что использование списков и кортежей внутренне упрощает реализацию на уровне C. Я думаю, что более широкий ответ на ваш вопрос заключается в том, что никто на самом деле не собирался делать все возможные оптимизации для str.join. Я предполагаю, что подавляющее большинство вариантов использования в любом случае вызывают его в списке или кортеже.

person BrenBarn    schedule 12.04.2015
comment
Да, но зачем отклонять все типы sequence? Вы можете просто попытаться вызвать __getitem__() и вернуться к созданию из него list. - person Blacklight Shining; 12.04.2015
comment
@BlacklightShining, потому что __getitem__ является атрибутом (некоторых) объектов Python - он не существует для объектов, которыми манипулируют в C за кулисами (в CPython - вы могли бы рассмотреть, например, реализацию PyPy str.join). - person jonrsharpe; 12.04.2015
comment
@BlacklightShining: list и tuple - это, по сути, единственные типы, в которых вы можете быть уверены, что они являются последовательностями (кроме str и unicode, которые бесполезны для join, и, возможно, нескольких эзотерических типов, таких как xrange). Могут быть типы отображения, которые имеют __getitem__, но не являются типами последовательности (например, dict). Конечно, вы можете дважды использовать итерацию на основе __getitem__, но это более рискованно, поскольку вы не знаете, что с этим могут делать пользовательские типы. - person BrenBarn; 12.04.2015
comment
@BrenBarn Почему бы не позволить этому случиться с типами сопоставления? Если все ключи являются strings, то вы получаете строку ключей, разделенную какой-либо разделяющей строкой. Если нет, то все равно не получится. - person Blacklight Shining; 12.04.2015
comment
@BlacklightShining это не то, что __getitem__ делает, например. dict; вы получите значения для целочисленных ключей, но могут отсутствовать числа и нецелочисленные ключи. - person jonrsharpe; 12.04.2015
comment
@jonrsharpe Ты прав; Я перепутал __iter__() и __getitem__(). - person Blacklight Shining; 12.04.2015
comment
Хорошо. Как насчет обнаружения неконтейнерных итераций путем проверки __next__(), создания из них list и простого использования __iter__() для всего остального? Сомневаюсь, что никто не думал об оптимизации str.join(); это похоже на действительно часто используемую функцию. - person Blacklight Shining; 12.04.2015
comment
@BlacklightShining снова, это все на уровне Python — str.join это < i>реализовано на C. - person jonrsharpe; 12.04.2015
comment
@jonrsharpe … нет ли способа найти атрибуты объекта на уровне C? - person Blacklight Shining; 12.04.2015
comment
@BlacklightShining эти атрибуты не существуют на уровне C. Вероятно, вам следует взглянуть на PySequence_Fast, где функциональность, на которую вы ссылаетесь, реализована (т.е. списки и кортежи передаются, все остальное превращается в список). - person jonrsharpe; 12.04.2015
comment
@BlacklightShining: все эти комментарии сводятся к тому, что я сказал в конце своего ответа: причина, по которой ни одна из этих оптимизаций не выполняется, заключается в том, что всем наплевать. Дело не в том, что люди не думали об оптимизации str.join; как я сказал в своем ответе, это потому, что люди не заботятся об оптимизации str.join для необычных вариантов использования, связанных с пользовательскими итерируемыми типами, потому что большинство из них все равно используют его со списком или кортежем. - person BrenBarn; 12.04.2015