"The Minion Game" challenge This is an implementation of the minion game, which takes in string input and declares a winner between two pre-determined players.

The logic is player 1 gets all sequenced words not starting with a vowel and player 2 gets all sequenced words starting with vowel in the input string.

Objective: performance optimisation. The code passed all the test cases, but I am very unsure where to tune the performance.

For a 1000 letter word, here are the time stats:


real 0m10.142s
user 0m6.386s
sys 0m0.743s




import string
import sys
import itertools

def minion(str):
    person_a_name = 'Stuart'
    person_b_name = 'Kevin'
    letter_list = [a for a in str]
    l = len(letter_list)
    vowel = ['A','E','I','O','U']
    consonants = ['Q','W','R','T','Y','P','S','D','F','G','H','J','K','L','Z','X','C','V','B','N','M']
    all_word = []
    person_a_words = []
    person_b_words = []
    all_word = [letter_list[start:end+1] for start in xrange(l) for end in xrange(start, l)]
    for array in all_word:
        if array[0] in vowel:
            person_b_words.append(array)
    for array in all_word:
        if array[0] in consonants:
            person_a_words.append(array)
    if len(person_a_words) == len(person_b_words):
        print 'Draw'
    if len(person_a_words) &gt; len(person_b_words):
        print person_a_name, len(person_a_words)
    if len(person_b_words) &gt; len(person_a_words):
        print person_b_name, len(person_b_words)

def main():
    str = raw_input()
    minion(str.upper())

if __name__ == '__main__':
    main()


Sample input / output:




banana
Stuart 12

guavaisanotherfruit     
Kevin 98
The big performance hit probably comes in this block of code, where you don a bunch of array manipulations and looping:

all_word = [letter_list[start:end+1] for start in xrange(l)
                                     for end in xrange(start, l)]
for array in all_word:
    if array[0] in vowel:
        person_b_words.append(array)
for array in all_word:
    if array[0] in consonants:
        person_a_words.append(array)
if len(person_a_words) == len(person_b_words):
    print 'Draw'
if len(person_a_words) &gt; len(person_b_words):
    print person_a_name, len(person_a_words)
if len(person_b_words) &gt; len(person_a_words):
    print person_b_name, len(person_b_words)




Appending to an array is a (relatively) expensive operation, as is looping over a list. I can see a number of optimisations here. [Edit: I wrote these in the order I thought of them; the big performance gain comes on the last item. I'm leaving the remaining items because they're still instructive, even if not directly applicable here.]


Only loop over all_word once. You can check for starting with a consonant and vowel in the same iteration of the loop:

for array in all_word:
    if array[0] in vowel:
        person_b_words.append(array)
    elif array[0] in consonants:
        person_a_words.append(array)


We've just cut out an iteration over all_word. If all_word is large, that will be a significant saving.
Don't store the words in a list, just the count. All you care about is the relative number of words in each list; the words themselves don't matter. It's much easier to increment an integer than mutate a list, so consider the following:

person_a_words = 0
person_b_words = 0
for array in all_word:
    if array[0] in vowel:
        person_b_words += 1
    elif array[0] in consonants:
        person_a_words += 1


and then you can compare the two integers at the end. That's bound to be a performance saving.
Don't construct all_word as a list; use a generator. If you replace the square brackets with parens:

all_word = (letter_list[start:end+1] for start in xrange(l)
                                     for end in xrange(start, l))


then this becomes a generator comprehension instead of a list comprehension. This means it only creates the elements as they're needed by the for loop; it doesn't create them all in memory before continuing.

Using generators instead of lists is a really good way to reduce occupancy and speed up programs.
Do you even need to use all_word? For each value of start, the first letter of the resulting words will be the same, and this gives you (l - start) different words. You don't actually need to create the words; you just care about their initial letter, and how many distinct words they create.

You could just add the number of distinct words to each person's score directly:

person_a_words = 0
person_b_words = 0
for idx, letter in enumerate(letter_list):
    if letter in vowel:
        person_b_words += len(letter_list) - idx
    else:
        person_a_words += len(letter_list) - idx


That is substantially faster: I just ran this with a 1.5m character string, and it finished in ~1.5s.


Other non-performance related comments:


Don't use str as a variable name; overriding builtins is bad practice.
You've imported the string, sys and itertools modules, but you never use any of them. Why?
PEP 8 requires a space after commas in a list; you should add this in vowel and consonants.
You can get the individual letters of a string by calling list() on it. These calls are equivalent:

letter_list = [a for a in my_string]
letter_list = list(my_string)


although in this case, you don't need to coerce to a list first &ndash; you can iterate over the characters of a string directly.
There's no need to assign the length of letter_list to a variable, especially not one with as undescriptive a name as l. It just makes your code harder to read.
The name of your function isn't particularly helpful. Ideally it should give me some idea of what the function does. There should also be a docstring to explain the result.
I would rename the person_a* and person_b* variables to be consonant* and vowel*, respectively &ndash; that will make the code easier to read. A and B don't really mean anything (and as evidence, I got them the wrong way round when I first wrote that sentence).
Your function is doing some work (finding out whether there are more vowel sub-words or consonant subwords) and printing to screen (the result). It would be better to separate this into two functions: one that does the work, the other does the result.

That makes it easier to reuse the work of vowels vs. consonants.
To aid readability, I'd keep the same order of variables when you do the comparison at the end. i.e.

if vowel_count &gt; consonant_count:
    print("Vowels victorious!")
elif vowel_count &lt; consonant_count:
    print("Consonants champion!")
else:
    print("Draw!")