There are two points I would like to emphasize as really performance penalties in your code:
- Memory usage when generating all the possible word combinations, which is exponential when increasing word length
- Unneccessary complexity to calculate points
Before diving into these points, I would like to say that both alexwlchan and SuperBiasedMan has given good pointers related to other code smells and stuff you need to look into as well.
Exponential memory usage
There is only line which really stands out and will require a load of memory when the length of the text increases:
all_word = [letter_list[start:end+1]
for start in xrange(length)
for end in xrange(start, length)]
Lets do some numbers, in a text of
length = 4, like in
abcd, you'll get the following word combinations:
- 4 words starting with first letter: abcd, abc, ab, a
- 3 words starting with second letter: bcd, bc, b
- 2 words starting with third letter: cd, c
- 1 word starting with fourth letter: d
In other words the total points available in your game for a text with length, \$N\$, is the sum of \$N + N-1 + N-2 + ... + 2 + 1\$. Luckily there exist an easy formula to calculate this number: \$(N+1)*N/2\$. This is listed at points in the table below.
But that was only the points (or number of words), when looking at memory usage we need at least to look at how long each of the words are. Continueing with our example with \$N=4\$, we have 4 words of length 1, 3 words of length 2, and so on. In general \$N \cdot 1 + (N-1)\cdot 2 + ... + 2\cdot (N-2) + 1\cdot N\$. I haven't found the general formula1 for this, but made a simple Python function to calculate it:
# Shift the range index by +1 so that we get the proper 1 to N sequence
sum( (n+1-k)*k for k in xrange(1, n+1) )
In the table below I've listed the length of text with corresponding number of points/words, and how many characters are needed to store these words. As can be seen these number increase quite fast. The last line is memory usage in megabytes when using memory_profiler on the original code.
text length : 4 10 50 100 500 1000 5000
points/words: 10 55 1275 5050 125250 500500 1250250
characters: 20 220 22100 171700 20958500 167167000 20845835000
usage in MiB: ~0 0.24 1.52 185.68 1251.93 too much
When reviewing your original problem statement, you need to calculate points of words starting with either a vowel or a consonant. You don't need to actually now the words.
Combining this with knowledge from previous section that at a given position, \$k\$, in the text you can generate \$N-k\$ words, the total complexity reduces quite nicely to a method like the following:
text_length = len(text)
word_count_vowels = 0
word_count_consonants = 0
for (index, character) in enumerate(text):
if character in ['A', 'E', 'I', 'O', 'U']:
word_count_vowels += text_length - index
word_count_consonants += text_length - index
return (word_count_vowels, word_count_consonants)
This doesn't require any memory besides the original text, loops through the entire text in one go, and calculates the points for word counts starting with either a vowel or consonant. Feel free to test this one with text length of 1000 or more. Tested it with a text of length 1.5m, and it completed within 0.35 seconds.
1 Added: Thanks to my question at Mathematica SE I now know that the formula is: