Timeline for Encode and decode string as base-32 number
Current License: CC BY-SA 4.0
6 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Aug 19, 2022 at 6:01 | history | edited | Toby Speight | CC BY-SA 4.0 |
It's more efficient to append to a list than a string
|
| Aug 19, 2022 at 6:01 | comment | added | Toby Speight | Thanks Jasmijn - that's a good explanation. I'd forgotten that Python strings are immutable (perhaps I've done too much C++ lately). | |
| Aug 19, 2022 at 1:31 | comment | added | Jasmijn |
Because in Python lists are mutable, if you call append, lists can allocate more memory than required on the assumption it may be used later, which if you append items in a loop means you need significantly fewer reallocations. So a single call to list.append may or may not be (relatively) expensive, but the amortized time for that method is O(1), while s1 += s2 where they are both strings always needs a reallocation, which is at least O(len(s1 + s2)).
|
|
| Aug 18, 2022 at 16:47 | comment | added | Toby Speight |
How does list.append() avoid the quadratic performance problem that affects string.__iadd__()? I would have thought them to have similar implementations, and now I'm intrigued.
|
|
| Aug 17, 2022 at 22:36 | comment | added | Jasmijn |
Gather into a list and then using join is the preferred way to build strings. Using += on a string in a loop generally results in quadratic runtime. In some cases, CPython can optimise it in a way that results in a linear runtime, but it's best not to depend on that.
|
|
| Aug 17, 2022 at 7:23 | history | answered | Toby Speight | CC BY-SA 4.0 |