5
\$\begingroup\$

I created code that was supposed to determine how well my system of guessing is.

The scenario is that there are n amount of tanks. Each tank is uniquely numbered 1 to n. Seven of these tanks are captured so we only know their serial number (This is done by getting a random number from 1 to n for each of the seven tanks).

I am supposed to predict n based on those serial numbers. My method (the one I have to code) was to first find the max number in the list and the number three standard deviations above the mean of the list. Then, I get my own random numbers from 1 to n where n ranges from the max number and the three standard deviations number.

During this time, I calculate the standard deviation for each of the seven serial numbers generated and after all of the standard deviations are calculated, I find which one is closest to the standard deviation of the original list. Whichever one is the closest to the standard deviation would constitute as my guess for n. I repeat this process as many times as necessary (the more times the more accurate results) to generate a list of guesses. My final guess then would be the mean of that list.

import random
import statistics

chosenNum = 429 #n is given only to check how well our process works
numRuns = 100 #number of guesses - my teacher wants at least 100
numCorrect = 0
numGuessN = []
guesses = []
percentErrors = []
for x in range(numRuns): 
  randNum = [random.randint(1,chosenNum + 1),random.randint(1,chosenNum + 1),random.randint(1,chosenNum + 1),random.randint(1,chosenNum + 1),random.randint(1,chosenNum + 1),random.randint(1,chosenNum + 1),random.randint(1,chosenNum + 1)] #generates the seven serial numbers.
  NumSTD = statistics.stdev(randNum) #standard deviation
  maxNumSTD = statistics.mean(randNum)+(3*(statistics.stdev(randNum))) #three standard deviations above the mean
  maxNum = max(randNum) #max number in list
  #print (NumSTD)
  #print (maxNumSTD)
  #print (maxNum)
  #print (randNum)
  for x in range(200): #the greater the range, the more accurate the results
    STDarray = []
    if (maxNum - maxNumSTD < 0):
      for y in range(maxNum,int(maxNumSTD)): #n is max number to max number from Standard Deviation
        randNumZwei =  [random.randint(1,y),random.randint(1,y),random.randint(1,y),random.randint(1,y),random.randint(1,y),random.randint(1,y),random.randint(1,y)] #my simulated serial numbers
        testNumSTD = statistics.stdev(randNumZwei)
        STDarray.append(testNumSTD)
    else:
      for y in range(int(maxNumSTD),maxNum):
        randNumZwei =  [random.randint(1,y),random.randint(1,y),random.randint(1,y),random.randint(1,y),random.randint(1,y),random.randint(1,y),random.randint(1,y)]
        testNumSTD = statistics.stdev(randNumZwei)
        STDarray.append(testNumSTD)
    for z in range((len(STDarray) - 1)):
      if((min(STDarray, key=lambda x:abs(x-NumSTD))) == STDarray[z]): #find closest number to original standard deviation
        numGuessed = z + maxNum
    numGuessN.append(numGuessed) #make a list of all the guessed numbers
  guess = int(statistics.mean(numGuessN)) #the final guess is simply mean of all the other guesses generated
  #print(guess)
  guesses.append(guess) #number of final guesses should be the same as number of trials
print ("Your guesses are: " + str(guesses))
for x in range(len(guesses) - 1):
  percentError = (abs(guesses[x] - (chosenNum))/float(chosenNum)) * 100
  percentErrors.append(percentError)
  if(guesses[x] == chosenNum):
    numCorrect = numCorrect + 1
  else:
    closestNumber = min(guesses, key=lambda x:abs(x-chosenNum))
averagePercentError = statistics.mean(percentErrors)
print ("The average Percent Error is: " + str(averagePercentError) + "%")
if (numCorrect > 0):
  print ("You got the correct number " + str(numCorrect/float(len(guesses))))
else:
  print ("Your closest number was: " + str(closestNumber))

This code works but takes way too long to give me my result. The whole point of this is to calculate accuracy but not take way too long. How can I make this code more efficient to run faster?

\$\endgroup\$
  • 1
    \$\begingroup\$ I feel like this isn't worth an answer, but the basic performance question your code has is you are trying to simulate and see how close you are rather than calculate directly what the answer should be based on what you observe. Specifically, you can find a function for the mean an stdev of a sample, invert it, and then use that to get an estimate n. \$\endgroup\$ – Oscar Smith Dec 9 '17 at 2:48
  • \$\begingroup\$ How would you invert the stdev? I couldn't find anything. \$\endgroup\$ – PGODULTIMATE Dec 9 '17 at 3:12
  • 1
    \$\begingroup\$ Does this link help? en.wikipedia.org/wiki/German_tank_problem#Example \$\endgroup\$ – Oscar Smith Dec 9 '17 at 3:23
  • 1
    \$\begingroup\$ Please do not update the code in your question to incorporate feedback from answers, doing so goes against the Question + Answer style of Code Review. This is not a forum where you should keep the most updated version in your question. Please see what you may and may not do after receiving answers. \$\endgroup\$ – Mast Dec 10 '17 at 22:13
  • 1
    \$\begingroup\$ New Post: codereview.stackexchange.com/questions/182508/… \$\endgroup\$ – PGODULTIMATE Dec 11 '17 at 0:42
3
\$\begingroup\$

I'm not going to comment on speed, only on coding style. For speed you should probably look at the python numerics library numpy (often abbreviated to np) especially Quickstart, Random numbers and Statistics sections.

The biggest problem with the code is that one huge block is doing everything. There aren't any functions; the code is generating random numbers, attempting to reverse-engineer them, and then testing performance. It's very hard to distinguish what part of the code is responsible for what; I had trouble piecing it together until I read over several times. It would be very hard to re-use portions of this code, even with copy and paste.

These should all be separate functions. This won't get you any speed boost but will make analysis much easier. That way you can update each function on its own without having to comb through your code for where the logic is located. Each function should have one job, this is called the single responsibility principle.

In addition, there should be a main() type function that acts as the driver for all the other functions. And the only line that ought to be at top-level of the file is the main guard:

    if __name__ == "__main__":
        main()

In particular, main() should pass the parameters in to the functions that actually do the work. Don't rely on global variables; again it makes the code impossible to use elsewhere. Variables should be scoped to where they are actually used.

  • Use _ for dummy variables in loops

    for x in range(numRuns):
    

    Since the loop index is not being used, convention is to use _ for the variable name.

  • Don't repeat yourself, make sure code is modular.

    randNum = [random.randint(1,chosenNum + 1),random.randint(1,chosenNum + 1),random.randint(1,chosenNum + 1),random.randint(1,chosenNum + 1),random.randint(1,chosenNum + 1),random.randint(1,chosenNum + 1),random.randint(1,chosenNum + 1)] #generates the seven serial numbers.
    

    This line is too long, has repeated code, and is fixed at 7. What if the problem requirements change, and you need to solve the problem for capturing 13 tanks? Much better to have the number of captured tanks be a parameter, then use a list comprehension to call the randomness repeatedly. (I think since you used randint you don't need to add the + 1. randint is already inclusive. randrange is half-inclusive.) I suggest

    tankSerialNumbers = [random.randint(1,chosenNum) for _ in range(numCapturedTanks)]
    
  • Choose meaningful variable names, and don't repeat yourself

    maxNumSTD = statistics.mean(randNum)+(3*(statistics.stdev(randNum))) #three standard deviations above the mean
    

    You just calculated stdev(randNum) on the line above, why calculate it again? And maxNumSTD is a poor variable name as it does not describe the variable at all. It's not a max of anything, and it's certainly not a standard deviation. It's a guess as to the highest tank number, so call it that!

    highestTankSerial = statistics.mean(randNum) + 3*NumSTD
    
  • Don't repeat yourself. Seeing a trend here? In this section

    if (maxNum - maxNumSTD < 0):
      for y in range(maxNum,int(maxNumSTD)): #n is max number to max number from Standard Deviation
        randNumZwei =  [random.randint(1,y),random.randint(1,y),random.randint(1,y),random.randint(1,y),random.randint(1,y),random.randint(1,y),random.randint(1,y)]
        testNumSTD = statistics.stdev(randNumZwei)
        STDarray.append(testNumSTD)
    else:
      for y in range(int(maxNumSTD),maxNum):
        randNumZwei =  [random.randint(1,y),random.randint(1,y),random.randint(1,y),random.randint(1,y),random.randint(1,y),random.randint(1,y),random.randint(1,y)]
        testNumSTD = statistics.stdev(randNumZwei)
        STDarray.append(testNumSTD)
    

    the code is almost exactly the same in the if and else blocks. Compare the two elements and swap them if necessary, then you don't need to duplicate your code.

  • Use Python's list features. In your code,

    for z in range((len(STDarray) - 1)):
        if((min(STDarray, key=lambda x:abs(x-NumSTD))) == STDarray[z]): #find closest number to original standard deviation
            numGuessed = z + maxNum
    

    you do use both the array index and the value. That's what enumerate is for. Also why are you skipping the last element of the list? And why are you recalculating the min each time through the loop? And why aren't you jumping out of the loop right away?

    minStd = min(STDarray, key=lambda x:abs(x-NumSTD))
    for (z,this_std) in enumerate(STDarray):
        if(minStd == this_std): #find closest number to original standard deviation
            numGuessed = z + maxNum
            break
    

    But wait a minute. The whole goal of this is just to get the index of the minimal element. That's easy to do in one step with enumerate using tools you already know about.

    (z, _) = min(enumerate(STDarray), key=lambda (_,x):abs(x-NumSTD))
    numGuessed = z + maxNum
    
\$\endgroup\$
  • \$\begingroup\$ I updated my code based on what you said, but it still takes too long (I understand that it only fixes formatting errors). With 1000 runs it takes 13.82 minutes. I was hoping to get at least 10,000 but at that rate, it would take way too long to do so. \$\endgroup\$ – PGODULTIMATE Dec 10 '17 at 19:16
  • \$\begingroup\$ Post the updated code as a new question (link to this one). If it's easier to read, possibly other people will comment on it. I had some ideas for speed but didn't feel like I understood it well enough. \$\endgroup\$ – Snowbody Dec 11 '17 at 0:18
  • 1
    \$\begingroup\$ I have created a new question with the updated code: link is in OP comments. \$\endgroup\$ – PGODULTIMATE Dec 11 '17 at 0:43
1
\$\begingroup\$

The most obvious problem with this code is you are using a really weird mix of lists and numpy code. Numpy is fast because it lets things be vectorized. For example, instead of [np.random.randint(1,chosenNum + 1) for _ in range(numCapturedTanks)] you should just use np.random.randint(1, chosenNum + 1, size=numCapturedTanks). This generates an ndArray, and means you aren't looping unnecessarily. Making the same change in createListOfStandardDeviations yields a 2x speedup.

\$\endgroup\$
  • \$\begingroup\$ Remember posters aren't supposed to edit their code after they post it. So nobody should be adding answers related to edited code, just comments warning people to post a new question. \$\endgroup\$ – Snowbody Dec 12 '17 at 14:46

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.