Соединение строк. Понимание генератора или списка?

Question

Рассмотрите проблему извлечения алфавитов из огромной строки.

Один из способов сделать это

''.join([c for c in hugestring if c.isalpha()]) 

Механизм понятен: Список понимание формирует список символов. Метод join знает, сколько символов ему нужно объединить, обратившись к длине списка.

Другой способ сделать это

''.join(c for c in hugestring if c.isalpha()) 

Здесь результаты генератора постижение в генераторе. Метод соединения не знает, сколько символов он собирается присоединиться, потому что генератор не обладает атрибутом len. Таким образом, этот способ соединения должен быть медленнее, чем метод понимания списка.

Но тестирование на питоне показывает, что оно не медленнее. Почему это так? Может ли кто-нибудь объяснить, как соединение работает на генераторе.

Чтобы был ясен:

sum(j for j in range(100)) 

не нужно иметь какие-либо знания 100, поскольку он может следить за нарастающий итог. Он может получить доступ к следующему элементу, используя следующий метод для генератора, а затем добавить к суммарной сумме. Однако, поскольку строки неизменяемы, объединение строк кумулятивно создало бы новую строку на каждой итерации. Так что это займет много времени.

Answer 1

Когда вы вызываете str.join(gen), где gen является генератором, Python выполняет эквивалент list(gen), прежде чем переходить к рассмотрению длины результирующей последовательности.

В частности, если вы look at the code implementing str.join in CPython, вы увидите этот призыв:

fseq = PySequence_Fast(seq, "can only join an iterable"); 

Вызов PySequence_Fast преобразует seq аргумента в список, если он не был список или кортеж уже.

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

Answer 2

join() не нужно реализовывать как последовательное присоединение элементов последовательности к более длинной и более длинной скопированной строке (что было бы очень медленным для длинных последовательностей); ему просто нужно произвести тот же результат. Таким образом, join(), вероятно, просто добавляет символы в некоторый буфер внутренней памяти и создает из него строку в конце. С другой стороны, конструкцию понимания списка нужно сначала построить список (путем перемещения генератора hugestring), и только тогда пусть join() начнет свою работу.

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

Answer 3

По крайней мере, на моей машине понимание списка выполняется быстрее для случая, который я тестировал, вероятно, из-за того, что ''.join способен оптимизировать распределение памяти. Это, вероятно, зависит только от конкретного примера, который вы тестируете (например, если условие вы тестируете происходит реже, цена CPython платит не зная длину загодя может быть меньше):

In [18]: s = ''.join(np.random.choice(list(string.printable), 1000000)) 

In [19]: %timeit ''.join(c for c in s if c.isalpha()) 
10 loops, best of 3: 69.1 ms per loop 

In [20]: %timeit ''.join([c for c in s if c.isalpha()]) 
10 loops, best of 3: 61.8 ms per loop