3
\$\begingroup\$

I wrote this code. But it works very slowly.

I'm figuring out how many times I have to run the case generator to find numbers less than or equal to inv, in this case six. I count the number of attempts until a digit <= 6 is generated. I find inv equal to 1 and repeat the loop. Until inv is 0. I will keep trying to generate six digits <= 6.

And I will repeat all this 10 ** 4 degrees again to find the arithmetic mean.

Help me speed up this code. Works extremely slowly. The solution should be without third-party modules. I would be immensely grateful. Thank!

import random

inv = 6

    def math_count(inv):
        n = 10**4
        counter = 0
        while n != 0:
            invers = inv
            count = 0
            while invers > 0:
                count += 1
                random_digit = random.randint(1, 45)
                if random_digit <= invers:
                    invers -= 1
                    counter += count
                    count = 0
    
            if invers == 0:
                n -= 1
                invers = inv
        
        return print(counter/10**4)

math_count(inv)
\$\endgroup\$
6
  • \$\begingroup\$ Why do you need "invers = inv"? \$\endgroup\$
    – Russ J
    Sep 23, 2020 at 20:57
  • \$\begingroup\$ First, the invers is equal to inv. After the cycles, the invers is 0. And then I again assign the inv value to it \$\endgroup\$
    – Pythonist
    Sep 23, 2020 at 21:12
  • 3
    \$\begingroup\$ I don't really understand what you're trying to do. Please could you clarify. It looks like you basically have a relatively simple probability question, it likely has a closed form which you can use to avoid all this looping. \$\endgroup\$ Sep 23, 2020 at 21:50
  • 1
    \$\begingroup\$ @Countingstuff If I have reverse engineered the OP's code correctly, it's doing this: def math_count(inv, trials = 10000): return sum(attempts_to_get_lte(x) for n in range(trials, 0, -1) for x in range(inv, 0, -1)) / trials, where trials = 10000 and attempts_to_get_lte() is a simple function that computes how many attempts are needed until random.randint(1, 45) <= x. So, one answer to the OP's question is Use fewer trials for the estimate. Another answer, as you note, is Use math to get the answer immediately. \$\endgroup\$
    – FMc
    Sep 23, 2020 at 22:59
  • \$\begingroup\$ Aha, yes that looks correct based on the numbers. And in that case, yes it is simply a matter of working out a closed form for the limit of (attempts_to_get_lte(x) over n attempts / n), from which a closed form of the full expression will follow. Which is simple as for x in 1..45 it's just the expected number of flips of a biased coin to get a tail with probability x / 45 of getting a tail. \$\endgroup\$ Sep 23, 2020 at 23:29

1 Answer 1

3
\$\begingroup\$

The code is very hard to follow. Here's a possible refactor to make its intent clearer. Some key ideas in the simplification: (1) use loops to manage counters rather than manually incrementing/decrementing; (2) use more meaningful variable names when context isn't clear; and (3) delegate some of the complexity to a helper function. The third idea is the most impactful: the helper function is simple because it does so little; and the main function, having been relieved of a burden, is simpler as well -- so simple, in fact, that it boils down to computing a sum over two loops.

def math_count(inv, trials = 10000):
    total_attempts = sum(
        attempts_to_get_lte(x)
        for _ in range(trials, 0, -1)
        for x in range(inv, 0, -1)
    )
    return total_attempts / trials

def attempts_to_get_lte(x):
    attempts = 0
    while True:
        attempts += 1
        if random.randint(1, 45) <= x:
            return attempts

But attempts_to_get_lte() is an easily solved probability problem: rather than have Python simulate the manual flipping of coins, we can just do a little math. If you prefer that approach, I believe the following is correct (probability experts should chime in if I've gone astray):

def math_count_exact(inv):
    return sum(45 / x for x in range(inv, 0, -1))
\$\endgroup\$
4
  • \$\begingroup\$ We need a simulation. Simulation gives more accurate calculations. Thanks for your code. I tested it, but it still works slowly, I already don’t know how to speed it up. \$\endgroup\$
    – Pythonist
    Sep 24, 2020 at 11:03
  • \$\begingroup\$ @Pythonist Correct, the edited math_count() won't be any faster. Currently it takes about 1 sec. A key question is how much faster? The answer – a little bit faster or an order of magnitude faster – affects which strategies are viable. \$\endgroup\$
    – FMc
    Sep 24, 2020 at 16:01
  • 1
    \$\begingroup\$ @Pythonist it'd help if you add in the question what you're trying to simulate? maybe there might be entirely different route to take? \$\endgroup\$
    – hjpotter92
    Sep 24, 2020 at 16:09
  • \$\begingroup\$ @hjpotter92 I have 10 digits out of 45. inv = 10. need to calculate how many random number generations need to make on average to get 10 times the number <= inv. Each time the number is found, the inv decreases by 1. \$\endgroup\$
    – Pythonist
    Sep 24, 2020 at 16:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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