Dlaczego ".join() jest szybsze niż + = w Pythonie?

Question

Jestem w stanie znaleźć zbiór informacji online (na stosie   Przepełnienie i inne) o tym, jak to jest bardzo nieefektywne i złe podejście do stosowania + lub += do konkatenacji w Pythonie.

Nie mogę znaleźć WHY += jest tak nieefektywny. Poza wzmianką o numerze here, że "została ona zoptymalizowana pod kątem 20% poprawy w niektórych przypadkach" (wciąż nie jest jasne, jakie to są przypadki), nie mogę znaleźć żadnych dodatkowych informacji.

Co dzieje się na poziomie technicznym, który sprawia, że ​​''.join() jest lepszy od innych metod łączenia konkrenty Pythona?

Answer 1

powiedzmy masz ten kod do budowania ciąg z trzech ciągów:

x = 'foo' 
x += 'bar' # 'foobar' 
x += 'baz' # 'foobarbaz' 

W tym przypadku, Python musi najpierw przydzielić i tworzyć 'foobar' zanim będzie mogła przeznaczyć i tworzyć 'foobarbaz'.

Tak dla każdego wywoływanego += cała zawartość ciągu i wszystkiego, co się do niego dodaje, należy skopiować do zupełnie nowego bufora pamięci. Innymi słowy, jeśli masz ciągi, które mają być połączone, musisz przydzielić około N tymczasowych ciągów, a pierwszy podciąg zostanie skopiowany ~ N razy. Ostatni podciąg zostaje skopiowany tylko jeden raz, ale średnio każdy podciąg zostaje skopiowany kilka razy.

Z .join, Python może odgrywać pewną liczbę trików, ponieważ pośrednie ciągi nie muszą być tworzone. CPython ustala, ile pamięci potrzebuje z góry, a następnie przydziela bufor o prawidłowym rozmiarze. Na koniec kopiuje każdy element do nowego bufora, co oznacza, że ​​każdy element jest kopiowany tylko raz.

---

Istnieją inne realne podejście, które mogłyby doprowadzić do lepszej wydajności dla += w niektórych przypadkach. Na przykład. jeśli wewnętrzna reprezentacja ciągów jest w rzeczywistości rope lub jeśli środowisko wykonawcze jest wystarczająco inteligentne, aby w jakiś sposób dowiedzieć się, że tymczasowe ciągi nie są użyteczne dla programu i optymalizować je.

Jednak CPython pewno robi nie robić te optymalizacje wiarygodny (choć może na few corner cases) i ponieważ jest najczęstszym realizacja w użyciu, wiele najlepsze praktyki oparte są na tym, co działa dobrze dla CPython. Posiadanie znormalizowanego zestawu norm ułatwia także innym działaniom optymalizację ich wysiłków optymalizacyjnych.

Answer 2

Myślę, że to zachowanie najlepiej wyjaśnić w Lua's string buffer chapter.

przepisać to wyjaśnienie w kontekście Pythonie, zacznijmy od niewinnego fragmencie kodu (pochodna z jednej na docs Lua):

s = "" 
for l in some_list: 
    s += l 

Załóżmy, że każdy l jest 20 bajtów i s ma już został sparsowany do rozmiaru 50 KB. Kiedy Python łączy się z s + l, tworzy nowy ciąg o rozmiarze 50,020 bajtów i kopiuje 50 KB z s do nowego ciągu. Oznacza to, że dla każdej nowej linii program przenosi 50 KB pamięci i rośnie. Po przeczytaniu 100 nowych linii (tylko 2 KB), fragment został już przeniesiony ponad 5 MB pamięci.Na domiar złego, po przypisaniu starego ciągu jest teraz śmieciem. Po dwóch cyklach pętli istnieją dwa stare ciągi, które łącznie zawierają ponad 100 KB śmieci. Tak więc, kompilator języka decyduje się uruchomić swój garbage collector i zwalnia te 100 KB. Problem polega na tym, że zdarza się to co dwa cykle, a program będzie uruchamiał garbage collector dwa tysiące razy, zanim przeczyta całą listę. Nawet przy całej tej pracy jego użycie pamięci będzie dużą wielokrotnością rozmiaru listy.

I na koniec:

Ten problem nie jest specyficzna dla Lua: Inne języki z prawdziwego śmieci kolekcji, a gdzie łańcuchy są niezmienne obiekty prezentują podobny zachowanie, Java jest najbardziej znany przykład. (Java oferuje strukturę StringBuffer aby złagodzić ten problem.)

Python ciągi są również immutable objects.