Bringing Order to programming

[Avi Gross]

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.