1
\$\begingroup\$

I'm working on a project for an Intro to C/Python class and am looking to improve the efficiency of the program. The program is a lottery simulation where the user inputs the number of tickets they want to buy, then generates tickets, and finally outputs the total winnings and net gain (usually loss).

This is my code (in Python, as required):

def main():

    numb_tickets = int(input("How many tickets would you like to buy?\n"))

    #Calculate Winnings
    winnings = 0

    for i in range(numb_tickets):

        #For testing only, gives feedback progress of program
        print(i,"     ",winnings)

        #Creating winning ticket/your ticket, find number of matches
        win_tic = getRandomTicket(MAX_VALUE, TIX_SIZE)
        my_tic = getRandomTicket(MAX_VALUE, TIX_SIZE)
        numb_win = numMatches(win_tic, my_tic)

        #Add appropriate payout for number of matches
        if numb_win == 6:
            winnings += WIN_SIX
        elif numb_win == 5:
            winnings += WIN_FIVE
        elif numb_win == 4:
            winnings += WIN_FOUR
        elif numb_win == 3:
            winnings += WIN_THREE     

    #Calculate cost of purchasing tickets
    cost_tics = numb_tickets * COST_TIC

    if winnings >= cost_tics:
        profit = winnings - cost_tics
        print("You won $",winnings,", for a net earnings of $",profit,".", sep="")
    elif winnings < cost_tics:
        loss = cost_tics - winnings
        print("You won $",winnings,", for a net loss of $",loss,".", sep="")    

main()

Note: the getRandomTicket() and numMatches() functions were provided by the professor to generate a lottery ticket and check the number of matches it has, respectively.

My program works fine for smaller numbers of tickets, but when testing the required 1,000,000 tickets, takes a massive amount of time. It makes sense that the time increases rapidly as the range of the loop increases, but I don't know of a better way to loop this yet. Any input or suggestions are greatly appreciated.

\$\endgroup\$
  • 4
    \$\begingroup\$ Remove the print(i," ",winnings) and see if the performance improves. Or you could print every 10000 by if i % 10000 == 0: \$\endgroup\$ – Jonas Elfström Sep 9 '13 at 19:36
  • 3
    \$\begingroup\$ In your program, for every ticket you buy, you generate NEW winning ticket. Is this supposed to work this way? Oh, and yes, printing to console on windows platform is very slow. \$\endgroup\$ – SigTerm Sep 9 '13 at 19:36
  • 1
    \$\begingroup\$ Printing is really slow on any platform. It's almost certainly your bottleneck. \$\endgroup\$ – user2357112 supports Monica Sep 9 '13 at 19:38
  • \$\begingroup\$ On an unrelated note, I'd recommend string formatting to clean up those print statements. print('You won ${}, for a net loss of ${}.'.format(winnings, loss)). \$\endgroup\$ – user2357112 supports Monica Sep 9 '13 at 19:40
1
\$\begingroup\$

It's more of a style preference, but instead of the paragraph with if and elif's, I would do

winnings += payouts_dictionary[numb_wins]

where

payouts_dictionary = {6: WIN_SIX, 5: WIN_FIVE, 4: WIN_FOUR, 3: WIN_THREE, 2: 0, 1: 0, 0: 0}

is defined as a constant before the loop.

\$\endgroup\$
  • \$\begingroup\$ I noticed Ankur has the same answer. However, I doubt using a dict will increase performance over a 4-deep if statement. I would be glad if someone could do a performance comparison. \$\endgroup\$ – toto2 Sep 9 '13 at 19:49
  • \$\begingroup\$ Just did a profiling on both the ways and it's strange that the nested if-else ran faster than dictionary. Any idea why this is happening? \$\endgroup\$ – Ankur Ankan Sep 9 '13 at 20:06
  • \$\begingroup\$ It might be O(1) to fetch a dictionary entry, but there is some processing for transformimg the given key to an array index. The big-O notation only gives the asymptotic behavior. I'm not surprised that it is slower. \$\endgroup\$ – toto2 Sep 9 '13 at 20:11
0
\$\begingroup\$

Doing this in a loop means O(N) time, where N = # of tickets.

If tickets are independent of each other, you can break this into chunks and process them in parallel. But threading is an advanced topic that you aren't likely to deal with in an intro class.

\$\endgroup\$
0
\$\begingroup\$

If this is python 2, try using xrange instead of range in your for loop. This will allow the for loop to generate the next iteration value on demand rather than generating and storing them all in memory upon the initial call to range.

See http://docs.python.org/2/library/functions.html#xrange

\$\endgroup\$
  • 4
    \$\begingroup\$ It's not. You can see the use of Python 3-style input and print. \$\endgroup\$ – user2357112 supports Monica Sep 9 '13 at 19:40
0
\$\begingroup\$

A major optimization that you could do is to define a dictionary for WIN_SIX, WIN_FIVE etc. This will return the value to add in O(1) rather than going into nested if else every time. Other than that you could combine all your statements like winnings += numb_win_dict[numMatches(getRandomTicket(MAX_VALUE, TIX_SIZE), getRandomTicket(MAX_VALUE, TIX_SIZE))] but it will result in loss of readability of your code. Final code would be like this:

numb_win_dict = { 3: WIN_SIX, 4: WIN_FOUR, 5: WIN_FIVE, 6: WIN_SIX}

def main():

    numb_tickets = int(input("How many tickets would you like to buy?\n"))

    #Calculate Winnings
    winnings = 0

    for i in range(numb_tickets):

        #For testing only, gives feedback progress of program
        print(i,"     ",winnings)

        #Add appropriate payout for number of matches   
        winnings += numb_win_dict[numMatches(getRandomTicket(MAX_VALUE, TIX_SIZE), getRandomTicket(MAX_VALUE, TIX_SIZE))]
    #Calculate cost of purchasing tickets
    cost_tics = numb_tickets * COST_TIC

    if winnings >= cost_tics:
        profit = winnings - cost_tics
        print("You won $",winnings,", for a net earnings of $",profit,".", sep="")
    elif winnings < cost_tics:
        loss = cost_tics - winnings
        print("You won $",winnings,", for a net loss of $",loss,".", sep="")    

main()
\$\endgroup\$
  • \$\begingroup\$ Your code fails for <= 2 matches. \$\endgroup\$ – user2357112 supports Monica Sep 9 '13 at 19:44
  • \$\begingroup\$ @user2357112: I haven't checked the code whether it's working or not. I have just rewritten the exact same code in the question in a compact form and have replaced the nested if-else with a dictionary. \$\endgroup\$ – Ankur Ankan Sep 9 '13 at 19:49
  • \$\begingroup\$ I've fixed some bugs (for numMatches <= 3) (pending acceptance of edits). For small non-negative integers, just use an array instead of a dict. Also, I've restored the win_tic and my_tic variables because the variable names self-document the functionality of numMatches(), and it keeps lines shorter, and doesn't hurt efficiency. \$\endgroup\$ – 200_success Sep 9 '13 at 20:19
  • \$\begingroup\$ @200_success: I agree that having the variables win_tic and my_tic improves the readability of the code but it does hurt efficiency a bit. \$\endgroup\$ – Ankur Ankan Sep 9 '13 at 20:39
  • \$\begingroup\$ @AnkurAnkan this is not the exact same code as in the question, because dictionary throws a KeyError if the number of matches is not defined whereas the original if... sequence does not. I suggest using winnings += numb_win_dict.get(..., 0) \$\endgroup\$ – Stuart Sep 9 '13 at 20:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy