Bringing Order to programming

[MRAB]

On 2019-02-01 00:28, Avi Gross wrote:
> The discussion moved on to debating if an algorithm is O(N) or O(N**2).
> 
> For small amounts of text, on fast machines, it really is not worth worrying
> about the cost of appending to the end of a growing string resulting in
> multiple copies and lots of garbage collection. Many computer textbooks love
> to tell you that nothing should be modifiable as a paradigm and endless
> copying is good for you since you never change existing data so fewer
> mistakes ...
> 
> But, for any programmers that happily want to read in entire books and for
> some reason then replace all spaces with newlines, may I suggest the
> following.
> 
> Convert your "text" to/from a list of individual characters. Copy the
> non-space characters to the end of an empty list and append a newline when
> you see a space. This part should be O(N) as lists have a fast way to append
> in constant time. At the end, use str(listname) to do what is needed to get
> back a string. Also O(N).
> 
> I won't supply the code for obvious reasons but it looks like:
> 
> final_list = []
> for character in initial_text:
> 	# Add carefully to the end of final_list
> final_text = str(final_list)
> 
> The second variant is to use the newer bytearray data structure very
> carefully as it is to a first approximation a mutable string. Adding to the
> end of a new one should be quick. WARNING: I said be careful. A bytearray is
> more like a list of 8-bit ints. With care you can handle ASCII text.
> 
If you're replacing anything within the ASCII range, it'll also work for 
UTF-8!