Estimating the number of tanks based on a sample of serial numbers

Question

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?

Answer 1

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
  

Answer 2

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.